HEURISTIC-SEARCH STRATEGIES FOR MULTIOBJECTIVE STATE-SPACE SEARCH

The multiobjective search model is a framework for solving multicriter ia optimization problems using heuristic search techniques, where the different dimensions of a multiobjective search problem are mapped int o a vector valued cost structure and partial order search is employed to determine the set of non-inferior solutions. This new framework for solving multicriteria optimization problems has been introduced by St ewart and White, who presented a generalization of the well known algo rithm A in this model. This paper presents several results on multiob jective state space search which helps in refining the scheme proposed by them. In particular, the following results have been presented. Th e concept of pathmax has been generalized to the multiobjective framew ork. It has been established that unlike in the conventional model, mu ltidimensional pathmax (in the multiobjective model) is useful for non -pathological tree search instances as well. We investigate the utilit y of an induced total order on the partial order search mechanism. The results presented are as follows: - If an induced total order is used in the selection process, then in general it is not necessary to comp ute the entire set of heuristic vectors at a node. - In memory-bounded search, a multiobjective search strategy that uses an induced total o rder for selection can back up a single cost vector while backtracking and yet guarantee admissibility though multiple noninferior candidate back-up vectors may be present in the space pruned while backtracking . In this paper we study multiobjective state space search using inadm issible heuristics: We show that if heuristics are allowed to overesti mate, then no algorithm is guaranteed to find all non-inferior solutio ns unless it expands dominated nodes also. The paper also addresses th e task of multiobjective search under memory bounds, which is importan t in order to make the search scheme viable for practical purposes. Th e paper presents a linear space multiobjective search strategy called MOR0 and suggests several variants of the strategy which may be usefu l under different situations.