Multiobjective A*

Authors:
Open Access
Publisher website
Google Scholar
Abstract
A multiobjective generalization of the heuristic search algorithm A* is presented, called MOA*. The research is motivated by the observation that the most real world problems involve multiple, conflicting, and non commensurate objectives. MOA* explicitly accomodates this observation by identifying the set of all nondominated paths from a specified start node to a given set of goal nodes in the OR graph.It is shown that MOA* is complete and, when used with a suitably de ned set of admissible heuristic functions, admissible. Several results concerning the comparison of versions of MOA* directed by different sets of heuristic functions are provided. The implications of using a monotone or consistent set of heuristic functions in MOA* are also discussed. Two simple examples are used to illustrate the behavior of the algorithm.

This publication has 15 references indexed in Scilit: