Heuristic search strategies for multiobjective state space search

Dasgupta, Pallab ; Chakrabarti, P. P. ; Desarkar, S. C. (1996) Heuristic search strategies for multiobjective state space search Sadhana (Academy Proceedings in Engineering Sciences), 21 (3). pp. 263-290. ISSN 0256-2499

PDF - Publisher Version

Official URL: http://link.springer.com/article/10.1007/BF0274552...

Related URL: http://dx.doi.org/10.1007/BF02745524


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.

Item Type:Article
Source:Copyright of this article belongs to Indian Academy of Sciences.
Keywords:Heuristic Search; Multicriteria Optimization
ID Code:101448
Deposited On:12 Dec 2016 11:28
Last Modified:12 Dec 2016 11:29

Repository Staff Only: item control page