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:
- Value Iteration (VI): A foundational method that updates state values in parallel until they converge. It is simple but often slow.
- AO*: A best-first search that builds a partial solution graph. The authors use the $CFC_{rev^*}$ variant specifically designed to handle cycles.
- 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.
- 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.
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.
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