An overview of a multiobjective heuristic search algorithm for AND/OR graphs

We develop and analyze a heuristic search algorithm that determines the nondominated set of solution graphs for a multiobjective AND/OR graph. This algorithm, MOAO*, is a multiobjective generalization of AO*. MOAO* uses sets of vector-valued heuristic estimates to give guidance to the search. We show that MOAO* satisfies termination, completeness, and admissibility conditions, generalizing results associated with AO*. Further, we prove that if the heuristic sets satisfy a monotonicity condition, then MOAO* possesses an efficiency property reminiscent of a well-known result associated with A*