A General Bottom-up Procedure for Searching And/Or Graphs

Vipin KumarAAAI 1984

Abstract

This paper introduces Procedure BUS, a generalized bottom-up heuristic search framework designed to find optimal solutions in AND/OR graphs. By integrating problem-specific heuristic information into a bottom-up approach, the framework unifies several classical algorithms—such as Dijkstra’s, Knuth’s generalization, and various dynamic programming techniques—into a single theoretical structure.

Introduction

In artificial intelligence, complex problems like theorem proving or planning are frequently represented as AND/OR graphs, where a primary goal is decomposed into various sub-problems. Traditionally, these have been solved using top-down heuristic searches like AO*. While bottom-up search—starting from known facts and building toward the goal—is a viable alternative, it was historically restricted to uninformed breadth-first strategies. This paper addresses the gap by formalizing how heuristic "hints" can guide a bottom-up search and demonstrates the fundamental relationship between these procedures and Dynamic Programming (DP).

Problem Formulation: AND/OR Graphs and Cost Functions

The search space is modeled as an AND/OR graph where nodes represent problems and hyperarcs represent the decomposition of a problem into sub-problems.

An example AND/OR graph G with hyperarcs p1 through p4.

A critical component of this model is the cost function associated with each hyperarc. The procedure assumes that the cost of solving a problem is a monotone function of the costs of its constituent sub-problems. This broad assumption covers most real-world optimization problems.

Cost functions associated with the hyperarcs of the graph in Figure 1, illustrating various monotone functions.

The BUS Framework

The author proposes Procedure BUS (Bottom-Up Search) and its heuristic variant, BUS. The algorithm operates using an OPEN/CLOSED mechanism similar to A, maintaining sets of partially and fully solved sub-problems.

The core innovation is the lower-bound function $lb(n, x)$, which estimates the total cost of a solution tree given that a specific sub-problem $n$ has a cost $x$. In BUS*, the algorithm selects the most promising node from the OPEN set based on this lower bound, focusing the search on sub-problems most likely to contribute to the global optimal solution.

Key Insights and Unification

A major contribution of this work is the unification of search and Dynamic Programming. The paper demonstrates that most discrete optimization problems solved by DP are essentially bottom-up searches on AND/OR graphs with monotone cost functions.

Furthermore, the paper clarifies the relationship between different search paradigms. The distinction between algorithms like Dijkstra’s being labeled as "Dynamic Programming" versus "Branch-and-Bound" is shown to be largely a matter of perspective and graph representation. The author also defines "logical" and "heuristic" consistency for lower bounds; if these are met, the algorithm is guaranteed to find an optimal solution without re-solving sub-problems.

Key Results

The theoretical framework is validated through several key findings:

  • Theorem 3.1: A formal proof that Procedure BUS correctly identifies the cost of the optimal solution tree upon termination.
  • Algorithmic Subsumption: The paper proves that Dijkstra’s shortest path algorithm, Knuth’s grammar-based shortest path generalization, and standard breadth-first bottom-up searches are all special cases of the BUS framework.
  • Efficiency: The use of the $lb$ function allows BUS* to outperform blind breadth-first searches by pruning sub-problems that cannot lead to an optimal global solution.

Limitations and Future Work

While powerful, the framework has limitations. For general monotone cost functions, termination is not always guaranteed unless specific constraints (like acyclicity) are present. Additionally, the performance of BUS* is heavily dependent on the quality of the heuristic lower-bound function. Future research aims to integrate these bottom-up procedures with top-down "Branch-and-Bound" styles to create hybrid search algorithms.

Summary updated

BibTeX
@inproceedings{kumar1984general,
  author = {Vipin Kumar},
  title = {{A General Bottom-up Procedure for Searching And/Or Graphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}
Figure