A general best first search algorithm in AND/OR graphs

Abstract A general formulation of best first search in the setting of AND/OR graphs has been considered where both minimization and maximization occur together. This leads to the development of an AND/OR graph search algorithm called GEN-AO ∗ which works with two types of OR nodes, MIN and MAX, and uses both upper and lower bound estimates. It is shown that this algorithm generates optimal cost solutions. The worst case set of nodes expanded is examined. Such an algorithm generalizes other known algorithms. Pruning conditions for the depth-first variation is examined.