An Optimal Any-Angle Pathfinding Algorithm

Authors

  • Daniel Harabor NICTA and The Australian National University
  • Alban Grastien NICTA and The Australian National University

DOI:

https://doi.org/10.1609/icaps.v23i1.13609

Keywords:

search, pathfinding, any-angle

Abstract

Any-angle pathfinding is a common problem from robotics and computer games: it requires finding a Euclidean shortest path between a pair of points in a grid map. Prior research has focused on approximate online solutions. A number of exact methods exist but they all require supra-linear space and preprocessing time. In this paper we describe Anya: a new optimal any-angle pathfinding algorithm which searches over sets of states represented as intervals. Each interval is identified online. From each we select a representative point to derive a corresponding f-value for the set. Anya always returns an optimal path. Moreover it does so entirely online, without any preprocessing or memory overheads. This result answers an open question from the areas of Artificial Intelligence and Game Development: is there an any-angle pathfinding algorithm which is online and optimal? The answer is yes.

Downloads

Published

2013-06-02

How to Cite

Harabor, D., & Grastien, A. (2013). An Optimal Any-Angle Pathfinding Algorithm. Proceedings of the International Conference on Automated Planning and Scheduling, 23(1), 308-311. https://doi.org/10.1609/icaps.v23i1.13609