Total Order Planning Is More Efficient than We Thought

AAAI 1999

TL;DR

This paper challenges the prevailing wisdom that partial-order planning is inherently more efficient than total-order planning. By introducing a "state loop control" mechanism to a classical forward state-space planner (VVPLAN), the authors demonstrate significant performance improvements, often outperforming a leading partial-order planner (UCPOP) on various benchmarks.

What Problem Does This Paper Address?

For decades, the field of AI planning has largely operated under the assumption that partial-order planning, which allows for parallel actions and less commitment, is more efficient than total-order planning, which enforces a strict sequence of actions. This belief is widely held and supported by numerous studies. However, the authors argue that many of these comparisons are flawed, particularly by not adequately accounting for the knowledge of the current world state that forward state-space planners can leverage. They aim to re-evaluate this comparison by implementing and testing a forward state-space planner with an effective state-pruning mechanism.

Methods

The core of the paper lies in the development and evaluation of VVPLAN, a forward state-space planner that uses the ADL (Action Description Language) for problem representation. The authors compare three versions of VVPLAN:

  • VVPLAN-breadth-first without state loop control: A standard breadth-first search in the state space.
  • VVPLAN-breadth-first with state loop control: This version introduces a crucial optimization. Before adding a newly generated state to the search queue, it checks if that state has already been visited or is present in the queue. If so, it's pruned, significantly reducing redundant exploration.
  • VVPLAN-A* with state loop control: This version builds upon the previous one by employing an A* search algorithm, using a domain-independent heuristic (maximizing solved subgoals) to guide the search.

These VVPLAN variants are compared against UCPOP, a well-established partial-order planner, on a set of 39 classical planning problems.

Datasets

The experiments were conducted using 39 classical planning problems, originally supplied with the UCPOP planner. These problems are drawn from 15 different domains and have been adapted to the ADL language. The authors note that these problems are standard in the planning community.

Key Insights and Ideas

  • State Loop Control is a Game Changer: The most significant finding is the dramatic performance improvement achieved by VVPLAN when the "state loop control" mechanism is introduced. This simple yet effective pruning strategy drastically reduces the search space, making a classical state-space approach competitive and often superior.
  • Challenging the "Partial-Order is Always Better" Mantra: The paper directly confronts the long-held belief that partial-order planners are universally more efficient. Their results suggest that when state-space planners are implemented with effective pruning (like state loop control), they can outperform partial-order planners, especially in domains where parallelism is limited or redundant states are common.
  • Domain Characteristics Matter: The authors emphasize that no single planning approach is universally superior. The efficiency of a planner is highly dependent on the characteristics of the planning domain, such as the degree of parallelism, the complexity of subgoals, and the number of redundant states.
  • Heuristics vs. Pruning: While A* search with a heuristic function (VVPLAN-A*) offers further improvements, the paper highlights that the state loop control itself is the primary driver of the performance gains, even for the basic breadth-first version.

Key Results

  • VVPLAN-breadth-first with state loop control solved all 39 problems, compared to UCPOP's 32 (82%). For the 32 problems solved by both, VVPLAN was significantly faster, solving them on average 7 times faster than UCPOP. It also created and developed far fewer nodes.
  • VVPLAN-A* with state loop control further improved performance, solving all 39 problems and being faster than UCPOP on 75% of the problems. The average CPU time was reduced to 0.46 seconds, and it created and developed even fewer nodes than the breadth-first version.
  • In contrast, VVPLAN-breadth-first without state loop control performed worse than UCPOP on many metrics, solving fewer problems and being slower on average. This highlights the critical importance of the state loop control.
  • The "Tyre World" problem, notoriously difficult for some planners, was solved by VVPLAN (both versions) while UCPOP failed.

Limitations and Future Work

  • Domain-Specific Heuristics: The paper uses a domain-independent heuristic for VVPLAN-A*. The authors suggest that domain-specific heuristics could lead to even greater improvements.
  • Characterizing Domains: A key future direction proposed is to systematically characterize the properties of different planning domains to better predict which algorithm will be most efficient for a given problem.
  • Optimality: While VVPLAN-A* aims for optimality, the paper notes that GRAPHPLAN-like planners may sacrifice optimality (in terms of plan length) for speed. The authors' work focuses on efficiency, and the optimality of VVPLAN's solutions is not the primary focus of this comparison.
  • Memory Usage: The state loop control mechanism requires memory to store visited states. While the authors implemented efficient data structures, this could become a limitation for problems with an extremely large number of unique states.

Summary updated

BibTeX
@inproceedings{1999total,
  title = {{Total Order Planning Is More Efficient than We Thought}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure