An algorithm better than AO
Blai Bonet, Héctor Geffner · 2005
Recently there has been a renewed interest in AO * as planning problems involving uncertainty and feedback can be naturally formulated as AND/OR graphs. In this work, we carry out what is probably 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, use 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, LDFS and its variant Bounded LDFS, 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.