Landmark Orderings And LM-Count Heuristic In Planning And Optimization.pdf

G3. Landmarks: Orderings & LM-Count Heuristic

This section focuses on using landmarks to efficiently guide planning algorithms. Landmarks are formulas that need to be true in a state for a plan to succeed. The paper introduces three types of landmark orderings and their applications:

1. Natural Orderings:

Directly determined from the Simplified Relaxed Task Graph (sRTG).
A formula `v'` has a natural ordering over another formula `v` if `v'` must be true before `v` in any valid plan.

2. Greedy-Necessary Orderings:

Determined from the sRTG, specifically focusing on first achievers - formulas that need to be true immediately before their dependent landmarks.
A formula `v'` has a greedy-necessary ordering over `v` if `v'` needs to be achieved before `v` is added in any valid plan.

3. Reasonable Orderings:

Also determined from the sRTG, considering when formulas are first and last added.
A formula `v'` has a reasonable ordering over `v` if it must be true at some point before `v` is last added in any valid plan.

Landmark Propagation:

The paper outlines an algorithm (LM-BFS) for propagating landmark information through the state space:

Landmark Graph: Combines all known landmark information for a state into a structured graph.
Graph Construction:
Starts with initial state and its landmarks.
For each successor state, updates the landmark graph based on applied operators.
BFS Search: Utilizes Breadth-First Search to explore paths through the landmark graph, prioritizing states that require fewer landmark additions.

Benefits of Landmark Orderings & Propagation:

Efficient Heuristics: Reduces the need to recompute landmarks for every state, saving computational resources.
* Improved Planning Performance: Guides search towards more promising paths by prioritizing states based on required landmark achievements.