Heuristic search strategies for multiobjective state space search

Abstract

The multiobjective search model is a framework for solving multicriteria optimization problems using heuristic search techniques, where the different dimensions of a multiobjective search problem are mapped into 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 Stewart and White, who presented a generalization of the well known algorithmA* in this model. This paper presents several results on multiobjective state space search which helps in refining the scheme proposed by them. In particular, the following results have been presented.
• The concept of pathmax has been generalized to the multiobjective framework. It has been established that unlike in the conventional model, multidimensional pathmax (in the multiobjective model) is useful for nonpathological tree search instances as well. We investigate the utility 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 compute the entire set of heuristic vectors at a node.
- In memory-bounded search, a multiobjective search strategy that uses an induced total order 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 inadmissible heuristics. We show that if heuristics are allowed to overestimate, then no algorithm is guaranteed to find all non-inferior solutions unless it expands dominated nodes also.
The paper also addresses the task of multiobjective search under memory bounds, which is important in order to make the search scheme viable for practical purposes. The paper presents a linear space multiobjective search strategy called MOR*0 and suggests several variants of the strategy which may be useful under different situations.