Landmark (in Planning)

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.

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.