PaperlayerView exact revision on arXiv

Source-linked AI summary

The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks

Silvia Richter, Matthias Westphal

arXiv:1401.3839v1cs.AI

TL;DR

LAMA addresses how heuristic forward search can combine landmark guidance, action costs, and anytime search to produce high-quality plans under non-uniform costs. The paper details this architecture and evaluates its components, finding that landmarks and iterative search help, whereas cost-sensitive heuristics often reduce coverage without much quality improvement. These results identify action-cost handling as an unresolved challenge for planning.

  • Problem

    The paper investigates which of LAMA’s landmarks, action costs, and anytime search features account for its strong IPC 2008 performance, including why cost-sensitive planning can be difficult.

  • Method

    LAMA combines a landmark heuristic with a cost-sensitive FF heuristic in multi-heuristic search and uses decreasing-weight weighted A* searches to improve solutions over time.

  • Results

    Landmarks improve coverage and solution quality, iterative search notably improves results, but cost-sensitive heuristics perform worse than cost-unaware heuristics and solve fewer tasks.

  • Takeaways & Limitations

    Landmarks can mitigate weaknesses of cost-sensitive search, while iterative search helps exploit faster initial solutions and improve plan quality over time.

  • Takeaways & Limitations

    Cost-sensitive search can overfocus on cheap plans, while zero-cost operators may produce long paths that do not approach a goal within the time limit.

Abstract

from arXiv · show

LAMA is a classical planning system based on heuristic forward search. Its core feature is the use of a pseudo-heuristic derived from landmarks, propositional formulas that must be true in every solution of a planning task. LAMA builds on the Fast Downward planning system, using finite-domain rather than binary state variables and multi-heuristic search. The latter is employed to combine the landmark heuristic with a variant of the well-known FF heuristic. Both heuristics are cost-sensitive, focusing on high-quality solutions in the case where actions have non-uniform cost. A weighted A* search is used with iteratively decreasing weights, so that the planner continues to search for plans of better quality until the search is terminated. LAMA showed best performance among all planners in the sequential satisficing track of the International Planning Competition 2008. In this paper we present the system in detail and investigate which features of LAMA are crucial for its performance. We present individual results for some of the domains used at the competition, demonstrating good and bad cases for the techniques implemented in LAMA. Overall, we find that using landmarks improves performance, whereas the incorporation of action costs into the heuristic estimators proves not to be beneficial. We show that in some domains a search that ignores cost solves far more problems, raising the question of how to deal with action costs more effectively in the future. The iterated weighted A* search greatly improves results, and shows synergy effects with the use of landmarks.

1. Introduction

The paper describes LAMA’s landmark-based, cost-sensitive, anytime heuristic search and evaluates how landmarks, action costs, and iterative search affect performance. The experiments find that landmarks and anytime search help, while cost-sensitive heuristics often hurt coverage.

  • LAMA’s distinguishing features: LAMA extends Fast Downward with landmark heuristics, cost-sensitive heuristic estimates, and anytime search.Landmarks guide search toward states where required subgoals have been achieved; action costs guide search toward cheap goals; iterative search improves solutions over time.
  • Motivation: LAMA outperformed its competitors by a substantial margin in the sequential satisficing track of IPC 2008.The paper investigates why this result occurred despite earlier landmark-heuristic work showing only modest improvement over a configuration without landmarks.
  • Evaluation focus: The paper evaluates how landmarks, action costs, and anytime search individually enhance the LAMA system.The experiments focus on features differentiating LAMA from predecessor systems rather than repeating earlier comparisons with other anytime or landmark methods.
  • Experimental findings: Cost-sensitive heuristics performed significantly worse than cost-unaware versions on IPC 2008 benchmark tasks.The cost-sensitive FF heuristic solved fewer tasks while yielding little solution-quality improvement, whereas landmarks substantially improved cost-sensitive coverage.
  • Experimental findings: Landmarks improve performance, and iterative search improves solution quality while showing synergy with landmarks in some domains.Landmarks provide search guidance, while repeated weighted A* searches continue seeking better solutions after an initial plan is found.

2. Preliminaries

The preliminaries formalize planning tasks in finite-domain representation, including variables, states, goals, operators, effects, and action costs. They also define domain transition graphs for representing possible changes to state-variable values.

  • Finite-domain planning tasks: An FDR planning task is represented as a 5-tuple ⟨V, s0, s⋆, O, C⟩.Its components are state variables, an initial state, a partial goal assignment, operators, and a non-negative action-cost function.
  • Finite-domain planning tasks: State variables have finite domains, and a state is a complete assignment of values to all variables.Facts pair a variable with a domain value, while partial assignments specify values for only some variables.
  • Operators and execution: Operators consist of preconditions and conditional effects that change variable values when their conditions hold.An operator is applicable when its precondition is contained in the current state, producing a successor state through consistent effects.
  • Operators and execution: A sequence is a plan when applying its operators produces a state satisfying the partial goal assignment.The cost of a plan is defined as the sum of its operators’ action costs.
  • Domain transition graphs: A domain transition graph represents the possible value changes of a state variable as a directed graph.Its vertices are the variable’s domain values, and its arcs correspond to operator effects that can change one value into another under applicable conditions.

3. System Architecture

LAMA extends Fast Downward with finite-domain translation, landmark and FF heuristics, and search procedures aimed at finding increasingly better plans. Its anytime restarts address heuristic bias, while cost-sensitive guidance trades estimated plan cost against goal distance.

  • Translation and compilation: LAMA translates PDDL input into a finite-domain planning task, using mutually exclusive fact groups as state variables.The translator also grounds schematic operators and axioms and retains mutex information for landmark ordering.
  • Translation and compilation: The knowledge compilation module builds domain transition graphs and data structures used by landmark generation and search.
  • Search: LAMA combines greedy best-first search for rapid solutions with weighted A* search for balancing search speed and solution quality.Weighted A* evaluates states using f′ = w · h + g and can re-expand states after cheaper paths are found.
  • Search: Separate queues combine a landmark heuristic with a variant of the FF heuristic, while preferred operators and deferred evaluation guide search efficiently.
  • Anytime search: LAMA first seeks a solution quickly, then runs weighted A* searches with decreasing weights, pruning states using the best known solution cost.Each improved-solution iteration restarts from the initial state rather than continuing the previous open lists.
  • Cost and distance estimates: LAMA adds cost-sensitive heuristics but combines estimated cost-to-go with estimated goal distance because focusing only on cost can jeopardize finding any plan.The system gives equal weight to these estimates, and zero-cost operators can create very long search paths without approaching a goal.

4. Landmarks

Landmarks are intermediate conditions that every plan must achieve, and their orderings guide LAMA’s search toward useful subgoals. LAMA represents these conditions as fact or disjunctive landmarks and uses ordering information to control when they should be achieved.

  • Landmarks: Landmarks are subgoals that must be achieved in every plan, such as transporting a box to an airport before loading it into a plane.LAMA automatically extracts these intermediate conditions during preprocessing.
  • Search guidance: LAMA uses ordering information to infer which landmarks should be achieved next and whether some landmarks must be achieved more than once.Preferred operators further direct search toward operators that achieve currently acceptable landmarks.
  • Landmark representation: LAMA generalizes landmarks from facts to propositional formulas, while its implementation supports fact landmarks and disjunctions of facts.For example, “box is in plane1 ∨ box is in plane2” can be a landmark even when neither fact alone is one.
  • Landmark orderings: Landmark orderings encode temporal relationships, including natural, necessary, greedy-necessary, reasonable, and obedient-reasonable orderings.Natural orderings are most general; necessary orderings imply greedy-necessary orderings, but not conversely.
  • Caveats: Reasonable orderings can guide search effort but may be problematic when landmarks are initially true or first become true simultaneously.LAMA avoids reflexive orderings and restricts some initially true landmark orderings, while noting that a redefinition remains future work.

4.2 Extracting Landmarks and Orderings

LAMA extracts landmarks and their orderings through back-chaining, domain transition graphs, and restricted relaxed planning graphs. The procedure uses approximations to remain practical, then derives additional reasonable orderings and removes cycles when necessary.

  • Overview: Landmark detection is computationally hard, so LAMA uses practical methods that may be incomplete or unsound.The algorithm combines back-chaining with finite-domain transition graphs and restricted relaxed planning graphs.
  • Postprocessing: After discovery, LAMA derives reasonable and obedient-reasonable orderings, prioritizes fact landmarks over redundant disjunctive landmarks, and removes orderings to break cycles.Obedient-reasonable orderings are removed before reasonable orderings whenever possible.
  • Back-chaining: Back-chaining identifies shared extended preconditions of possible first achievers as landmarks and can construct disjunctive landmarks from covering precondition sets.First achievers are operators that can potentially make a landmark true before it has previously been achieved.
  • Domain transition graphs: Domain transition graphs add a fact landmark when a variable value occurs on every path from its initial value to an existing landmark value.In the logistics example, the box must pass through both truck1 and location C on paths from B to F.
  • Restricted relaxed planning graphs: Restricted relaxed planning graphs identify orderings by omitting operators that could achieve a selected landmark; landmarks absent from the resulting graph must occur afterward.The graph is constructed once per landmark for efficiency during first-achiever analysis.

4.3 Related Work

LAMA’s landmark extraction and use build on earlier landmark and goal-ordering research while adding finite-domain transition-graph detection and restricted-relaxed-graph ordering methods. Prior approaches differ in verification, task decomposition, and computational cost.

  • Goal orderings: Landmark orderings generalize earlier goal-ordering methods by extracting necessary temporal relationships before search.LAMA applies these relationships to landmarks rather than only to goals.
  • Earlier landmark methods: Hoffmann et al.’s approach back-chains from goals and verifies candidates with restricted relaxed planning tasks, but unsound orderings may remain.The verification condition is sufficient but not necessary for landmarkhood.
  • LAMA’s extension: LAMA adopts an over-approximation of possible first achievers that preserves correctness of found landmarks and orderings, while adding domain-transition-graph and restricted-relaxed-graph analyses.These additions distinguish LAMA’s detection method from the earlier approximation.
  • Landmarks as subgoals: Earlier landmark decomposition methods treated landmarks as intermediary goals, but their reported performance varied with the base planner and benchmark set.Using Fast Downward as a base planner, one such method performed worse on average on IPC benchmarks from 1998 to 2006.
  • Preprocessing trade-offs: Grouping landmarks into consistent sets reduced destructive interactions in one prior approach, but its preprocessing could take longer than solving the original problem.This trade-off was reported by the authors of that approach.

5. The Landmark Heuristic

LAMA’s landmark heuristic estimates remaining goal distance from accepted and still-required landmarks, while landmark orderings and preferred operators guide search. Its cost-sensitive version combines estimated landmark costs with distance, but the heuristic is path-dependent and has known edge cases.

  • Landmark count: The landmark count heuristic estimates a state’s goal distance by counting discovered landmarks that still need to be achieved.Accepted landmarks are tracked along the path, while required-again landmarks are counted when they must be re-established.
  • Accepted landmarks: A landmark is accepted when it is true in a state and its ordered predecessors were accepted in the predecessor state.Accepted landmarks remain accepted in successor states unless the heuristic identifies that they are required again.
  • Edge cases: The heuristic can assign a non-zero value to a goal state when the plan reaches the goal without accepting all landmarks according to the landmark graph.This can occur when a plan violates reasonable orderings.
  • Path dependence: The heuristic is path-dependent and is calculated only once when a state is first reached, even if other paths later reach the same state.An alternative would re-evaluate the state using information from all known paths.
  • Cost sensitivity: LAMA’s cost-sensitive landmark heuristic sums distance and estimated cost-to-go, weighting each landmark by the minimum action cost of its first achievers.The combination is intended to balance search speed and plan quality, particularly with zero-cost operators.
  • Preferred operators: Preferred operators are those that achieve an acceptable landmark next, or occur in a relaxed plan toward a nearest acceptable landmark.Applicable operators from that relaxed plan are marked preferred.

6. The Cost-Sensitive FF/add Heuristic

LAMA extends the FF heuristic to handle action costs while combining cost estimates with landmark guidance in multi-heuristic search. Its cost propagation uses relaxed planning-task information, with FF variants differing in whether precondition costs are aggregated by maximum or sum.

  • Landmark and FF integration: LAMA combines the FF and landmark heuristics in multi-heuristic search because the landmark heuristic alone was not competitive.The joint configuration improved performance over using only the FF heuristic.
  • FF heuristic: The FF heuristic estimates a state’s goal distance by constructing a relaxed plan from best supports selected during forward cost propagation.The relaxed-plan length is reported as the heuristic estimate.
  • Cost propagation: LAMA replaces explicit relaxed planning graphs with a generalized Dijkstra cheapest-path algorithm that reduces time and space requirements from O(NK) to O(N).Operators and facts are represented once, while conditional effects are handled by splitting operators and preserving original-operator inclusion.
  • Cost-sensitive heuristic: The cost-sensitive FF heuristic estimates operator cost using action costs alongside propagated precondition costs, rather than assuming unit-cost operators.The hmax criterion uses the maximum precondition cost plus the operator’s action cost.
  • FF/add variant: The FF/add variant sums precondition costs instead of taking their maximum when estimating operator costs.FF/add is a previously proposed variation of the FF heuristic and was independently implemented in FF(ha).

7. Experiments

The experiments isolate landmarks, cost-handling strategies, and anytime search using IPC 2008 benchmark tasks under competition-like resource limits. They compare cost-unaware, purely cost-sensitive, and combined distance-cost configurations, while landmarks provide supplementary guidance rather than a standalone estimator.

  • Experimental design: The evaluation compares LAMA configurations with and without landmarks while keeping other planner features fixed.It also tests three approaches to costs: cost-unaware, purely cost-sensitive, and combined distance-cost heuristics.
  • FF/add configurations: F, Fc, and F+c respectively use cost-unaware, purely cost-sensitive, and combined-cost-and-distance FF/add heuristics.These configurations isolate cost treatment without landmark heuristics.
  • Landmark configurations: FL, FLc, and FL+c respectively apply cost-unaware, purely cost-sensitive, and combined variants to both the FF/add and landmark heuristics.The configurations test whether cost treatment behaves similarly when landmark information is included.
  • Scope of landmark use: The landmark heuristic is not competitive by itself in this satisficing-planning setting and is therefore used only as additional information for an already guided search.Configurations relying exclusively on landmarks are excluded from the detailed results.
  • Anytime evaluation: Each configuration uses iterated anytime search, with first and final solutions compared within a 30-minute timeout.The final solution is the last and best solution found before timeout.
  • Evaluation protocol: Performance is scored using the IPC 2008 criterion, aggregating c*/c when a planner finds a plan of cost c.Experiments use the competition hardware, a 2 GB memory limit, and 30 minutes per task.

7.1 Overview of Results

Landmarks and iterated search substantially improve LAMA’s performance, while purely cost-sensitive search reduces coverage despite producing somewhat cheaper plans. Combining landmarks with cost-and-distance estimates largely recovers performance, and iterated search creates a slight synergy with landmarks.

  • Purely cost-based search solves significantly fewer tasks than cost-unaware search, although it can find higher-quality first solutions.Its lower coverage outweighs its quality advantage under the IPC criterion.
  • Adding landmarks substantially increases coverage for cost-sensitive search with only a small quality loss, mitigating the poor performance of the cost-sensitive FF/add heuristic.Landmarks bring cost-sensitive configurations to approximately the coverage level of cost-unaware search.
  • Iterated search significantly improves all configurations and largely eliminates the initial quality gap between cost-sensitive and cost-unaware search.After iteration, the difference between cost-sensitive and cost-unaware first solutions nearly disappears, while combined cost-and-distance estimates outperform pure cost search.
  • The combination of landmarks and cost-and-distance estimates achieves nearly the same performance as LAMA’s landmark-based configuration and is superior to pure cost search with iteration.This combination supports fast solution finding without overly sacrificing plan quality.
  • Landmarks improve performance, especially when combined with iterated search, while the landmark heuristic alone remains substantially worse than other LAMA configurations.With iterated search, landmark-only configurations score 164–167 and achieve 185–189 coverage points, versus scores above 194 and coverage above 223 for other configurations.
  • Landmarks and iterated search exhibit a slight synergy: in cost-unaware search, landmarks add 2 score points for first solutions but 9 points for final solutions.The larger final-solution gain is mainly associated with iterated search mitigating landmark-related quality loss in Openstacks.

7.2 Elevators

In Elevators, cost-sensitive FF/add configurations solve far fewer tasks and often produce worse plans than cost-unaware search. Poor relaxed plans, movement-cost plateaus, and capacity constraints explain much of this behavior, while landmarks improve coverage without eliminating the problem.

  • Domain and setup: The Elevators domain models passenger transportation using fast and slow elevators with distinct movement costs and capacity constraints.Slow elevators cost 6+n per move, while fast elevators cost 2+3n, where n is the traveled distance.
  • Overall results: Cost-sensitive FF/add configurations solve far fewer problems than cost-unaware configurations, and their solved plans are often lower quality.Landmarks increase coverage, but do not fully resolve the cost-sensitive heuristic’s poor performance.
  • Plan characteristics: Cost-sensitive configurations favor slow elevators and passenger transfers because individual trips are cheaper, whereas fast elevators usually require fewer operators.This reflects independence assumptions in the FF/add heuristic and produces different plan structures from cost-unaware search.
  • Local minima from movement costs: Movement costs can dominate heuristic estimates, making correct elevator movements appear worse and creating local minima that require temporarily blind progress.Relaxed costs can differ despite identical solution costs because relaxed plans effectively teleport elevators back to their starting floors.
  • Plateaus from capacity constraints: Capacity constraints create plateaus because boarding the capacity-threshold passenger may not improve the heuristic, prompting exploration of many passenger subsets.These plateaus are especially large when multiple passengers wait on the same floor.
  • Interpretation: The combined evidence attributes poor cost-sensitive performance to inaccurate relaxed plans, movement-cost local minima, and capacity-induced plateaus.Removing capacity constraints makes tasks easier and reduces the frequency of poor relative plan qualities.

7.3 PARC Printer

In PARC Printer, cost-sensitive FF/add heuristics reduce coverage but improve plan quality relative to cost-unaware search. Landmarks largely overcome the coverage problem, bringing cost-sensitive configurations to performance similar to cost-unaware configurations.

  • Domain: The PARC Printer domain models multi-engine printing jobs whose sheets must traverse printer components and arrive in order at finishing trays.The domain combines concurrent processing with routing and sequencing constraints.
  • Cost-sensitive search: Cost-sensitive configurations fail to solve many tasks that the cost-unaware configuration solves, although they produce notably better-quality plans.The two cost-sensitive configurations perform similarly because large action costs outweigh distance estimates in the combined heuristic.
  • Effect of landmarks: With landmarks, differences between cost-sensitive and cost-unaware configurations are strongly reduced, and all three landmark configurations outperform the cost-unaware configuration F.The comparison uses coverage and average IPC quality over tasks solved by all configurations.
  • Interpretation: Unlike Elevators, PARC Printer’s cost-sensitive heuristic problem concerns coverage rather than solution quality, and landmarks bring performance close to cost-unaware search.Poor relaxed plans remain a contributing issue in the domain.

7.4 Cyber Security

Cyber Security is a contrasting domain where cost-sensitive configurations perform better than cost-unaware search, especially for first solutions. Landmarks let both cost-sensitive configurations solve all problems while preserving their higher solution quality.

  • Domain: The Cyber Security domain models gaining sensitive network information through malware use or physical access during insider attacks.Its planning tasks involve exploiting vulnerabilities in computer networks.
  • Cost-sensitive search: Cost-sensitive configurations solve slightly fewer problems than F but achieve a better total score in Cyber Security.The table reports that Fc and F+c solve 2 and 1 fewer problems, respectively, than F.
  • Effect of landmarks: With landmarks, both cost-sensitive configurations solve all problems while maintaining high solution quality.FLc scores 27.59 points and FL+c scores 26.60, compared with 20.43 for FL.
  • Interpretation: Cost-sensitive search succeeds here because lower-cost plans are more complex, yet the relaxed plans are sufficiently accurate to support them.Cost-unaware plans often use physically costly access or emailed viruses, while software-heavy plans achieve lower costs.

7.5 Openstacks

In Openstacks, landmarks reduce search effort but initially produce worse-quality plans because their zero-cost estimates favor starting orders early. Iterative search largely recovers plan quality while retaining the search-speed benefit.

  • Domain: The Openstacks domain minimizes the maximum number of simultaneously open stacks needed to manufacture products for multiple orders.It is a combinatorial optimization problem in which products are produced before orders are completed.
  • Plan quality: Landmarks substantially worsen the quality of first plans, while iterative search improves both landmark and non-landmark configurations to similar levels.The landmark configuration can generate up to 21 increasingly improved plans per problem.
  • Why landmarks hurt quality: All landmarks found by LAMA have minimal cost zero, so the landmark heuristic cannot estimate goal cost and distinguishes states mainly by missing goals.This causes orders to be started as soon as possible, without accounting for future stack-opening costs.
  • Why landmarks help search: The landmark heuristic still provides a good goal-distance estimate, favoring states closer to the goal regardless of cost.This explains why landmarks can accelerate search even when they do not distinguish plan costs.
  • Representation boundary: LAMA cannot represent the multi-stack requirement as a conjunction landmark; unrestricted disjunctions would only express that at least one stack must be open.The domain therefore exposes a representational boundary of the landmark formulation used here.
  • Search effort and anytime improvement: Landmarks reduce expanded search nodes, enabling iterative search to improve solution quality within the time limit.Without iterative search, the landmark configuration achieves higher-cost plans despite its search-efficiency advantage.

7.6 Domains from Previous Competitions

On domains from earlier competitions, LAMA generally outperforms FF and Fast Downward, with landmarks and iterated search contributing to its performance.

  • LAMA performs better than FF and Fast Downward under the IPC 2008 criterion, unless both landmarks and iterated search are disabled.
  • LAMA’s advantage over Fast Downward comes from higher-quality solutions rather than coverage, while its advantage over FF includes better coverage.
  • Action-cost support introduced code changes that particularly reduced performance in the Philosophers domain.
  • Landmarks produce moderate improvements in both coverage and solution quality across the experimental LAMA configurations.

8. Conclusion and Outlook

The study finds that landmarks and iterative search improve LAMA’s planning performance, while cost-sensitive heuristics often underperform cost-unaware alternatives. It identifies improved cost-sensitive heuristics, landmark ordering, and repeated-landmark handling as directions for future work.

  • Conclusion: LAMA combines a cost-sensitive FF heuristic with a landmark heuristic in multi-heuristic state-space search, while iterative search improves solution quality over time.
  • Conclusion: Cost-sensitive FF/add solves far fewer tasks than its cost-unaware counterpart while yielding little solution-quality improvement on solved tasks.
  • Conclusion: Landmarks mitigate cost-sensitive FF/add’s weaknesses, improve coverage and solution quality in several settings, and improve solution quality on IPC 2008 cost-unaware search.
  • Conclusion: Iterative search raises LAMA’s IPC 2008 score by a quarter and can combine with landmarks to improve initially poor plans.
  • Outlook: The authors call for further research on cost-sensitive heuristics and more sophisticated combinations of distance estimators with cost-sensitive guidance.
  • Outlook: The authors also identify improving the definition of reasonable landmark orderings as a future research direction.
  • Outlook: Future landmark extensions should account for repeated landmark occurrences, which could help minimize stack creation costs in Openstacks.
Loading 1401.3839v1…