In the field of classical automated planning, heuristic forward state-space search has long been a dominant paradigm. However, even state-of-the-art systems like the Fast-Forward (FF) planner face significant challenges when scaling to massive problem instances. This paper, presented by Vincent Vidal, introduces two pivotal modifications to search exploration: treating "relaxed plans" as actual roadmaps for shortcuts and prioritizing "helpful" actions through an optimistic search algorithm that maintains completeness. These innovations are implemented in the YAHSP (Yet Another Heuristic Search Planner) system.
The Challenge of Search Granularity and Completeness
Most modern solvers evaluate states and select the next action based on a heuristic value, often derived from a "relaxed" version of the problem where negative side effects are ignored. While effective, this approach has two primary weaknesses:
- Search Granularity: Planners typically move one action at a time, ignoring the fact that a relaxed plan might suggest a valid sequence of actions leading to a distant, more favorable state.
- Incompleteness: To maintain speed, planners like FF often only consider "helpful actions" (those in the relaxed plan). If a solution requires an action outside this set, the planner may fail unless it falls back to a much slower exhaustive search.
Proposed Innovations: Lookahead and Optimism
Vidal proposes two main techniques to overcome these limitations:
1. Lookahead States
Instead of using the relaxed plan solely as a distance estimator, YAHSP uses it to find shortcuts. When evaluating a state $S$, the planner generates a relaxed plan $P$. It then attempts to execute as many actions from $P$ as possible in the real environment. If a sequence of actions is valid, it creates a "lookahead state" $S'$, which is added to the search graph as a direct descendant of $S$. This allows the planner to "teleport" across large sections of the search space in a single step.
2. Optimistic Best-First Search (OBFS)
To address completeness, Vidal introduces a partitioning strategy. Actions are divided into helpful actions (suggested by the heuristic) and rescue actions (all others). The search algorithm prioritizes nodes generated by helpful actions regardless of their heuristic value. However, because rescue actions are still maintained in the queue at a lower priority, the search remains systematic and complete, providing a safety net if the heuristic's advice is insufficient.
Evaluation and Results
The approach was tested on classic benchmarks from the International Planning Competitions, including Logistics, Rovers, Satellite, and Driver domains. The results demonstrate a dramatic improvement in both scaling and search efficiency.
As shown in the performance plots, YAHSP (specifically the LOBFS configuration) maintains low search times even as problem complexity increases, whereas baseline planners like FF and standard BFS show exponential growth in time. The most striking results appear in the Logistics and Satellite domains.
According to the experimental data in Table 1, for the "Logistics 30" problem, the standard FF planner required nearly 2,800 seconds to find a solution. In contrast, LOBFS solved the same problem in just 3.88 seconds. This efficiency is driven by a massive reduction in search depth; while FF evaluated over 45,000 nodes for Logistics 15, LOBFS reached the goal in Logistics 30 by evaluating only 5 nodes, thanks to the shortcuts provided by lookahead states.
Conclusion
The success of YAHSP highlights that relaxed plans are often high-quality roadmaps, not just distance estimators. By compressing search depth through lookahead states and maintaining completeness via prioritized action partitioning, Vidal's strategy allows automated planners to solve problems that were previously considered computationally out of reach. While the strategy's effectiveness depends on the quality of the relaxed plan in a given domain, it represents a significant leap forward in search-based planning efficiency.
Summary updated