Finding State Similarities for Faster Planning

Christian FritzAAAI 2008

Introduction

In classical AI planning, forward-search algorithms like A* typically explore a tree of possible actions starting from an initial state. While effective, these planners often suffer from redundancy. For instance, in a logistics task requiring both a flight and a hotel booking, a standard planner might explore "Flight then Hotel" and "Hotel then Flight" as distinct branches, failing to recognize that the resulting states are functionally identical for subsequent planning steps.

While backward-searching "least commitment" planners handle such independence naturally, they often lack the powerful heuristic guidance of modern forward-search systems. This paper introduces Forward Search Regression Planning, a method designed to bridge this gap by identifying state similarities to avoid redundant computations, thereby accelerating the search process in complex domains.

Methodology: Forward Search Regression Planning

The proposed approach operates in two distinct phases to leverage state similarities through regression.

Phase 1: Pre-computation

The planner first performs a shallow breadth-first or A* search to generate a set of potential "start states" ($S_1, S_2, ..., S_n$). It constructs a matrix mapping these states to their specific fluent values (state variables). Crucially, the algorithm identifies groups of states that share identical values for specific fluents.

Instead of standard progression, the algorithm performs a modified search where action sequences are evaluated against the entire set of start states simultaneously. For every action considered, the planner uses regression to pull the goal conditions, preconditions, and heuristic functions back toward the start states.

Figure 1: The two-phase planning process. Phase 1 generates start states, and Phase 2 performs parallel regression search across them.

The core efficiency gain—the "secret sauce"—lies in formula evaluation. If a regressed formula (such as a goal condition) only references variables that a group of start states have in common, the planner evaluates that formula only once for the entire group. This pruning of the state set allows the planner to explore a single search tree that covers multiple starting points at once.

Experimental Evaluation

The authors evaluated the approach using domains from the International Planning Competition (IPC), specifically the Trucks domain (logistics with constraints) and the Zenotravel domain (transportation with fuel/speed trade-offs).

Figure 3: Performance comparison between conventional A* and the proposed regression search at various depths across the Trucks and Zenotravel domains.

Key Results

  • Trucks Domain: The method demonstrated significant performance gains. As problem complexity increased, the parallel regression approach drastically reduced the number of expanded nodes compared to the A* baseline. This reduction occurs because the planner effectively processes multiple states within a single search node.
  • Zenotravel Domain: Initial results were less favorable because states in this domain are highly distinct, leading to "thin" state sets that offer fewer similarity opportunities. To address this, the authors implemented an adaptive mechanism that reverts to standard A* if the similarity-check overhead exceeds the search benefits. This allowed the algorithm to match or occasionally exceed baseline performance.

Discussion and Insights

Relevance via Regression

Regression serves as a diagnostic tool to reveal the "relevance structure" of a problem. If a variable does not appear in a regressed formula, it is irrelevant for that specific sub-goal. This allows the planner to ignore differences between states that do not impact future success. Furthermore, the approach exploits "non-effects": if two actions leave the same relevant variables untouched, the resulting states can be treated as similar.

Limitations and Future Work

A primary constraint is the requirement for "regressable" heuristics. Many state-of-the-art heuristics are defined procedurally (e.g., via planning graphs) and are difficult to express as logical formulas suitable for regression. Additionally, the current method relies on a simple depth-limited search for start states; future work may explore dynamic, adaptive start-state selection during the search process to further optimize performance in highly variable domains.

Summary updated

BibTeX
@inproceedings{fritz2008finding,
  author = {Christian Fritz},
  title = {{Finding State Similarities for Faster Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure