Making A* Run Faster than D*-Lite for Path-Planning in Partially Known Terrain


  • Carlos Hernandez Universidad Católica de la Santísima Concepción
  • Jorge Baier Pontificia Universidad Católica de Chile
  • Roberto Asin Universidad Católica de la Santísima Concepción



Incremental Heuristic Search, Pathplanning


Focused D* and D*-Lite are two popular incremental heuristic search algorithm amenable to goal-directed navigation in partially known terrain. Recently it has been shown that, unlike commonly believed, a version of A* is in many cases faster than D*-Lite, posing the question of whether or not there exist other variants of A* which could outperform algorithms in the D* family on most problems. In this paper we present Multipath Adaptive A* (MPAA*), a simple, easy-to-implement modification of Adaptive A* (AA*) that reuses paths found in previous searches to speed up subsequent searches, and that almost always outperforms D*Lite. We evaluate MPAA* against D*-Lite on random maps and standard game, room, and maze maps, assuming partially known terrain. In environments comparable to indoor and outdoor navigation (room and game maps) MPAA* is 35% faster than D*Lite on average, while on random maps MPAA* is over 3 times faster than D*Lite. D*Lite is faster than MPAA* only in mazes; notwithstanding, we show that if a small percentage of obstacle cells in a maze are made traversable, MPAA* outperforms D*Lite. In addition, we prove MPAA* is optimal and that it finds a solution if one exists. We conclude that for most real-life goal-directed navigation applications MPAA* should be preferred to D*Lite.




How to Cite

Hernandez, C., Baier, J., & Asin, R. (2014). Making A* Run Faster than D*-Lite for Path-Planning in Partially Known Terrain. Proceedings of the International Conference on Automated Planning and Scheduling, 24(1), 504-508.