Generlized A* for cyclic AND/OR graphs
Supriyo Ghose · National Conference on Artificial Intelligence · 1998
The A* algorithm (Hart, Nilsson and Raphael 1968) has been the cornerstone of state-space search methods. Simultaneously, the vexing problem of cycles in AND/OR graphs has received considerable attention in recent times (Ghose 1998, Hvalica 1996, Chakrabarti 1994). We propose a generalization of A* to search AND/OR graphs that may contain cycles. The basic idea is that, if each AND node in an AND/OR graph has exactly one child, then the graph is virtually an ordinary (OR) graph and can be searched by applying A*-like steps. This idea is simulated in our algorithm, GA*, by making full expansion of OR nodes (as in A*) but partial expansion of AND nodes. While expanding an AND node, GA* generates only the leftmost unsolved child, and adds to its cost the costs of all other children of the AND parent. This updated cost is maintained as the current cost provided the child has not been generated earlier in this iteration, or if the updated cost is less than the previously computed cost through some other path. This is done iteratively, using two lists OPEN and CLOSED. An iteration starts by putting s in OPEN, continues by selecting and expanding nodes like A*, and ends either (a) successfully by selecting a terminal leaf or a previously SOLVED node, or (b) unsuccessfully when it finds it has no more nodes to expand (in which case GA* terminates with FAILURE). At the end of an iteration, if s is SOLVED then GA* terminates with SUCCESS. Furthermore, in each iteration, backpointers are set from nodes to their parents, as in A*, to indicate the current minimum costly path to each node. When an iteration of GA* ends successfully, GA* traces these backpointers and updates the heuristic estimates of nodes higher up in the solution graph, and declares some of them SOLVED. Our conjecture is that, in each successful iteration of GA*, at least one distinct node is labeled SOLVED; this node has its heuristic estimate set to its minimum cost of solution. If N is the number of nodes lying on any path P from s such that cost of P ? h* (s), then GA* has a complexity of O(N2) node expansions with monotone heuristics; under admissible heuristics, its worst-case complexity of O(N2N) can be reduced to O(N3) by applying modifications similar to (Martelli 1977). The empirical performance of GA* is currently under investigation. A broad outline of GA* is given below.