BibTex

A note on the complexity of some multiobjective A* search algorithms

Lawrence Mandow and J.L. Pérez De La Cruz.
A note on the complexity of some multiobjective a* search algorithms.
In Proceedings of the 2010 conference on ECAI 2010: 19th European Conference on Artificial Intelligence, pages 727-731, Amsterdam, The Netherlands, The Netherlands, 2010. IOS Press.

Abstract

This paper studies the complexity of two different algorithms proposed as extensions of A* for multiobjective search: MOA * and NAMOA *. It is known that, for any given problem, NAMOA * requires the consideration of no more alternatives than MOA * when provided with the same heuristic information. In this paper we show that, in fact, expansions performed by MOA * can be many more than those demanded by the problem, and hence than those performed by NAMOA *. More specifically, we show a sequence of problems whose size grows linearly such that the number of expansions performed by NAMOA * grows also linearly, but the number of expansions performed by MOA * grows exponentially. Therefore, there are problems where NAMOA * performs exponentially better than MOA *.

BibTex

@inproceedings{MAN:2010:C,
  acmid={1861110},
  affiliation={Universidad de M{\'a}laga Dpto. Lenguajes y Ciencias de la Computaci{\'o}n 29071 M{\'a}laga Spain},
  numpages={5},
  url={http: //dl.acm.org/citation.cfm?id = 1860967.1861110},
  author={Mandow, Lawrence and P{\'e}rez De La Cruz, J.L.},
  title={A note on the complexity of some multiobjective A* search algorithms},
  booktitle={Proceedings of the 2010 conference on ECAI 2010: 19th European Conference on Artificial Intelligence},
  publisher={IOS Press},
  address={Amsterdam, The Netherlands, The Netherlands},
  year={2010},
  pages={727--731},
}
Redmine Appliance - Powered by TurnKey Linux