Abstract
This paper presents an efficient $O(n^2)$ algorithm for determining the optimal search order in "AND" or "OR" trees to locate a single satisfying solution. By incorporating a "pruning" outcome—where a branch is identified as a dead end—the authors extend classical search models. The research demonstrates that while simple trees permit pre-planned static search sequences, more complex structures like AND-OR trees necessitate dynamic, "on-the-fly" decision-making.
Introduction
In many artificial intelligence applications, the goal is not to find a globally optimal solution but rather any solution that satisfies given constraints—a process known as satisficing search. Common examples include theorem proving and robotic path planning. Traditional models, such as the "gold-digging" metaphor by Simon and Kadane (1975), typically consider only two outcomes: success (finding the treasure) or failure.
Geiger and Barnett argue that this binary model is insufficient for real-world AI. In actual search trees, exploring a node might reveal that the entire subtree below it is non-viable, allowing for pruning. This paper addresses the challenge of finding the most cost-effective search order when nodes can result in success, pruning, or the revelation of further child nodes to explore.
The Greedy Algorithm for Tree Search
The authors propose a greedy algorithm that constructs an optimal search sequence by prioritizing the benefit-to-cost ratio ($\phi^+$) of each node. This ratio is calculated based on the cost of exploration ($c$) and the probability of success ($p^+$).
The algorithm's optimality is grounded in two key properties:
- The Local Property: The relative order of two adjacent nodes in an optimal sequence can be determined solely by comparing their individual benefit-to-cost ratios.
- The Merging Strategy: If a non-root node possesses the highest ratio in the set, the optimal strategy must involve searching it immediately after its parent.
The algorithm iteratively identifies the node with the highest ratio. If it is a root, it is added to the sequence; otherwise, it is "collapsed" into its parent to form a "super-node" with updated aggregate costs and probabilities. This process continues until all nodes are sequenced, achieving a computational complexity of $O(n^2)$.
Static vs. Dynamic Strategies
A significant contribution of this work is the formal distinction between search problems that allow for static strategies and those requiring dynamic strategies. For simple OR or AND trees, a "perfect" search order can be established a priori. However, the authors prove that for AND-OR trees—where some nodes require all children to be satisfied while others require only one—a fixed list is insufficient.
In AND-OR trees, the optimal next move depends on the information gained from previous steps, requiring a decision-tree approach for the search itself. Furthermore, in general graphs where nodes can have multiple parents, the search order becomes contingent on which path first "opened" the node, further complicating the strategy.
Conclusion and Future Work
The paper successfully provides a polynomial-time algorithm that guarantees minimum expected cost for searching trees with pruning. While the $O(n^2)$ complexity is efficient, the model's reliance on the independence of node outcomes remains a limitation. In many real-world scenarios, a failure in one branch may statistically correlate with failures in similar branches. Future research is needed to address optimal search strategies for general graphs and scenarios with dependent probabilities.
Summary updated