Landmark (in Planning)

A landmark's defining property is its logical necessity. For a given planning problem with initial state I and goal G, a proposition L is a landmark if, for every plan π that solves the problem, there exists at least one state s in the execution trace of π where L is true. This is a semantic property derived from the domain and problem definition, not from a specific search algorithm.

• Example: In a logistics domain where a package must be moved from city A to city B, the proposition (at package cityB) is a landmark because it is the goal itself. The proposition (in package truck) is also very likely a landmark, as the package must be inside a vehicle to be transported between cities.

Landmarks induce a natural partial order over the plan. If landmark L1 must be achieved before landmark L2 can be achieved in every valid plan, then L1 is ordered before L2. This creates a landmark graph, a directed acyclic graph where nodes are landmarks and edges represent necessary orderings.

• Natural Order: (in package truck) is naturally ordered before (at package cityB).
• Greedy-Necessary Order: Two landmarks may be mutually exclusive in a state; achieving one may delete the other's preconditions, forcing an order.
• Reasoning Benefit: This graph decomposes the planning problem into a sequence of sub-problems (achieve the next set of landmarks), providing critical structural guidance.

Landmarks are the basis for highly effective admissible heuristics, such as the Landmark-Count Heuristic. The core idea: any plan must achieve all required landmarks. Therefore, a lower-bound estimate of the remaining plan cost is the cost of achieving all yet-unachieved landmarks.

• Landmark-Count Heuristic: The simplest form counts the number of unachieved landmarks. While admissible, it can be weak.
• Landmark-Cost Heuristic: A more powerful variant sums the minimum cost of achieving each remaining landmark, respecting their orderings in the landmark graph. This provides a much more informed, yet still admissible, estimate that dramatically prunes the search space for algorithms like A*.

Identifying landmarks automatically is a key computational challenge. Exact discovery can be as hard as planning itself, so efficient approximations are used.

• Reachable & Necessary: Common algorithms work by analyzing the relaxed planning graph (used in Fast-Forward planning). A proposition is a candidate landmark if it is reachable from the initial state and necessary for achieving the goal in the relaxed problem.
• LAMA Algorithm: The LAMA planner popularized the use of landmark-based heuristics. It extracts a set of landmarks and their orderings from a relaxed planning graph, then uses the landmark-cost heuristic to drive a greedy best-first search with periodic restarts.

While the classical definition centers on fact landmarks (propositions), the concept extends to action landmarks.

• Fact Landmark: A proposition that must be true. (at package cityB).
• Action Landmark: An action that must appear at least once in every valid plan. In a problem requiring driving between two cities, the action (drive truck cityA cityB) is an action landmark.
• Relationship: Action landmarks can often be derived from fact landmarks (an action that achieves a necessary fact is a candidate). Using both types provides a more comprehensive view of the plan's necessary structure.

Landmarks can be complex logical formulas, not just single facts.

• Disjunctive Landmark: A set of propositions {L1, L2, ..., Ln} where at least one must be true in every plan. Example: To board a plane, you must have (has boarding-pass) OR (has mobile-pass). This represents multiple ways to satisfy a requirement.
• Conjunctive Landmark: A set of propositions that must all be true together at some point. Example: To perform a chemical reaction, you must have (in beaker reagent-A) AND (in beaker reagent-B) AND (temperature beaker 100C) simultaneously.
• System Impact: Recognizing disjunctive landmarks prevents heuristic overestimation, while conjunctive landmarks reveal critical synchronization points.

A heuristic function estimates the cost to reach a goal from a given state, guiding search algorithms like A* toward promising solutions. Landmarks are a primary source for deriving informed heuristics (e.g., landmark-count heuristics), which are more accurate than uninformed ones. These heuristics calculate the number of remaining landmarks or the cost to achieve them, providing a powerful lower-bound estimate that dramatically prunes the search space.

An admissible heuristic never overestimates the true cost to the goal, guaranteeing that algorithms like A* will find an optimal plan. Heuristics derived from landmarks, such as the landmark-cut heuristic, are often admissible. This property is critical for domains requiring provably optimal solutions, as it ensures the planner will not be misled by an overly optimistic cost estimate during its state-space exploration.

An ordering constraint specifies a necessary temporal relationship between two plan steps. Landmark analysis automatically discovers two key types:

• Natural Orderings: A landmark L1 must be achieved before L2 in every valid plan.
• Necessary Orderings: L1 must be achieved before L2 in at least one valid plan. These constraints are crucial for plan graph algorithms like Graphplan, as they refine the search by eliminating invalid action sequences early.

A precondition is a logical proposition that must be true in the current state for an action to be executable. Landmarks are a generalization of this concept. While a precondition is a fact required before a single action, a landmark is a fact required at some point in the entire plan. Recognizing that a goal is a landmark whose achievement is necessarily deferred helps planners reason about action sequencing and intermediate subgoals.

STRIPS (Stanford Research Institute Problem Solver) is the foundational representation for classical planning, defining states as sets of logical propositions. Landmarks are inherently defined within STRIPS-like representations. The formalism's clear semantics—preconditions, add effects, and delete effects—enable the automated extraction of landmarks through causal analysis of how propositions become true and are used by subsequent actions.

Graphplan is a planning algorithm that builds a layered planning graph, alternating between proposition layers and action layers. Landmark discovery is deeply integrated into modern Graphplan derivatives. The algorithm's structure naturally reveals mutual exclusions (mutexes) between propositions and actions, which is directly used to infer landmark ordering constraints and to compute effective landmark-based heuristics for guiding the solution extraction phase.