MULTIOBJECTIVE HEURISTIC-SEARCH IN AND OR GRAPHS/

The multiobjective search model is a framework for solving multi-crite ria optimization problems using heuristic search techniques. In this f ramework, the different non-commensurate optimization criteria are map ped into distinct dimensions of a vector valued cost structure and par tial order search techniques are used to determine the set of non-infe rior solutions. Multiobjective state space search has been studied and generalizations of algorithms such as A to the multiobjective framew ork have been considered. In this paper we address the problem of mult iobjective heuristic (best-first) search of acyclic additive AND/OR gr aphs. We establish two results which show that in the multiobjective f ramework, the task of identifying a non-dominated cost potential solut ion graph is NP-hard in general. This indicates that by extending popu lar AND/OR graph search algorithms such as AO to the multiobjective f ramework we will not be able to preserve some of their desirable prope rties. Under such circumstances, we investigate the task of developing effective algorithms for the multiobjective problem and present a lin ear space AND/OR graph search algorithm called MObj. 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. (C) 1996 Academic P ress, Inc.