An Algorithm Better than AO*?

Blai Bonet, Hector GeffnerAAAI 2005 · OpenReview

Abstract

Recently there has been a renewed interest in AO as planning problems involving uncertainty and feedback can be naturally formulated as AND/OR graphs. This work presents a detailed empirical evaluation of AO in relation to other AND/OR search algorithms, specifically Value Iteration (VI) and the new Learning in Depth-First Search (LDFS). Testing across four domains and three heuristic functions, the study focuses on cost optimization in the worst case (Max AND/OR graphs). Results indicate that while AO outperforms VI with informed heuristics, it struggles with cycles. In contrast, LDFS and its variant Bounded LDFS are almost never slower than AO or VI and are frequently orders of magnitude faster.

Introduction

AND/OR graphs are fundamental for modeling problems with uncertainty or feedback. For decades, AO has been the "textbook" best-first search algorithm for these structures. However, AO faces two significant challenges: it is notoriously difficult to adapt for graphs with cycles (loops), and its "best-first" nature incurs high computational overhead by re-evaluating the entire partial policy after every single state expansion. This paper evaluates whether modern alternatives, specifically depth-first learning approaches, can surpass this classic method in complex, real-world-style scenarios.

Methodology

The study compares four primary algorithmic approaches:

  1. Value Iteration (VI): A foundational method that updates state values in parallel until they converge. It is simple but often slow.
  2. AO*: A best-first search that builds a partial solution graph. The authors use the $CFC_{rev^*}$ variant specifically designed to handle cycles.
  3. Learning DFS (LDFS): A depth-first approach that performs successive searches and updates state values when they are found to be "inconsistent" with their children. It can be viewed as a generalization of IDA* for AND/OR graphs.
  4. Bounded LDFS: A variant optimized for "Max" AND/OR graphs (minimizing worst-case cost) that uses both lower and upper bounds to prune the search space more aggressively.

Experimental Setup

The algorithms were tested on four parametric domains: Coins (counterfeit detection), Diagnosis (binary system testing), Rules (logic-based planning), and Moving Target Search (MTS). MTS is particularly challenging as the predator-prey dynamics naturally create cycles and very large state spaces.

Table 1: Characteristics of problem instances across the four domains, showing state space sizes (|S|) and optimal policy sizes (|π*|).

Results and Discussion

The empirical results challenge the long-standing dominance of AO. A key insight is that AO's commitment to always expanding the absolute best node is often its undoing; the overhead of constant re-evaluation outweighs the guidance benefits. LDFS, by contrast, handles cycles natively and maintains the memory efficiency of depth-first search.

Figure 1: Performance comparison (time in seconds) across different domains and heuristic functions. LDFS and Bounded LDFS consistently outperform AO* and VI.

Key findings include:

  • Speed: LDFS and Bounded LDFS were almost never slower than AO or VI. In many cases, they were orders of magnitude faster*, as illustrated in the performance curves of Figure 1.
  • Robustness: In the MTS domain, which features cycles and millions of states, AO* variants struggled or failed, while LDFS solved the problems efficiently.
  • Pruning Power: Bounded LDFS proved exceptionally strong in the Diagnosis and Coins domains. Its ability to maintain an upper bound allowed it to ignore large portions of the state space that AO* was forced to consider.

Conclusion

LDFS represents a significant advancement in AND/OR graph search, offering a more robust and faster alternative to AO. While AO may still hold advantages in specific "Additive" models (where costs are summed across branches), LDFS's native handling of cycles and superior speed make it a more versatile tool for modern planning. Future work should focus on standardizing benchmarks to continue this empirical research.

Summary updated

Abstract

Recently there has been a renewed interest in AO* as planning problems involving uncertainty and feedback can he naturally formulated as AND/OR graphs. In this work, we carry out what is prohably the first detailed empirical evaluation of AO* in relation to other AND/OR search algorithms. We compare AO* with two other methods: the well-known Value Iteration (VI) algorithm, and a new algorithm, Learning in Depth-First Search (LDFS). We consider instances from four domains. usc three different heuristic functions, and focus on the optimization of cost in the worst case (Max AND/OR graphs). Roughly we find that while AO* does better than VI in the presence of informed heuristics, VI does better than recent extensions of AO* in the presence of cycles in the AND/OR graph. At the same time, LOFS and its variant Bounded LOFS, which can be regarded as extensions of IDA*, are almost never slower than either AO* or VI, and in many cases, are orders-of-magnitude faster.
BibTeX
@inproceedings{bonet2005algorithm,
  author = {Blai Bonet and Hector Geffner},
  title = {{An Algorithm Better than AO*?}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2005},
  url = {https://openreview.net/forum?id=HJNikgZu-B},
}
Figure