MULTIOBJECTIVE HEURISTIC-SEARCH IN AND OR GRAPHS/

We develop and analyze a heuristic search algorithm that determines th e nondominated set of solution graphs for a multiobjective AND/OR grap h, This algorithm, MOAO, is a multiobjective generalization of AO*, M OAO uses sets of vector-valued heuristic estimates to give guidance t o 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.