Multiobjective A * search with consistent heuristics

Abstract

The article describes and analyzes NAMOA ^* , an algorithm for multiobjective heuristic graph search problems. The algorithm is presented as an extension of A ^* , an admissible scalar shortest path algorithm. Under consistent heuristics A ^* is known to improve its efficiency with more informed heuristics, and to be optimal over the class of admissible algorithms in terms of the set of expanded nodes and the number of node expansions. Equivalent beneficial properties are shown to prevail in the new algorithm.