Multiobjective A* search with consistent heuristics

Lawrence Mandow and J.L. Pérez de la Cruz.
Multiobjective a* search with consistent heuristics.
J. ACM, 57:27:1-27:25, June 2010.


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.


  doi={http: //},
  issue_date={June 2010},
  journal={J. ACM},
  keywords={Consistent heuristics, multiobjective search, optimality},
  url={http: //},
  author={Mandow, Lawrence and P{\'e}rez de la Cruz, J.L.},
  title={Multiobjective A* search with consistent heuristics},
  address={New York, NY, USA},
Redmine Appliance - Powered by TurnKey Linux