Heuristic search with multiple criteria and additive cost structure

We present a multiobjective generalization of the heuristic search algorithm A*. We call this generalization MOA*. The research is motivated by the observation that most real-world problems involve multiple, conflicting, and noncommensurate objectives. MOA* explicitly accommodates this observation by identifying the set of all nondominated paths from a specified start node to a given set of goal nodes in an OR graph. We present results indicating that MOA* is complete and, when used with a suitably defined set of admissible heuristic functions, admissible. We also present results that provide a means for comparisons to be made among sets of heuristic functions and the versions of MOA* that they direct, in terms of the number of nodes expanded during a search. A simple example is used to illustrate the algorithm.