Multiobjective heuristic search in AND/OR graphs

Abstract

The multiobjective search model is a framework for solving multi-criteria optimization problems using heuristic search techniques. In this framework, the different non-commensurate optimization criteria are mapped into distinct dimensions of a vector valued cost structure and partial order search techniques are used to determine the set of non-inferior solutions. Multiobjective state space search has been studied and generalizations of algorithms such as A* to the multiobjective framework have been considered. In this paper we address the problem of multiobjective heuristic (best-first) search of acyclic additive AND/OR graphs. We establish two results which show that in the multiobjective framework, the task of identifying a non-dominated cost potential solution graph is NP-hard in general. This indicates that by extending popular AND/OR graph search algorithms such as AO* to the multiobjective framework we will not be able to preserve some of their desirable properties. Under such circumstances, we investigate the task of developing effective algorithms for the multiobjective problem and present a linear space AND/OR graph search algorithm calledMObj*. Upper bounds on time and space complexities of this algorithm have been presented. It has also been established that when applied to OR graphs, the proposed algorithm is superior to the algorithm proposed by Stewart and White (Multiobjective A*,J. Assoc. Comput. Mech.38, No. 4 (1991), 775-814) in terms of the worst case set of nodes expanded.