An optimal any-angle pathfinding algorithm

Daniel Harabor, Alban Grastien

Research output: Chapter in Book/Report/Conference proceedingConference PaperOtherpeer-review

28 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationProceedings of the Twenty-Third International Conference on Automated Planning and Scheduling
EditorsDaniel Borrajo, Simone Fratini, Subbarao Kambhampati, Angelo Oddi
Place of PublicationMenlo Park, California
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages4
ISBN (Print)9781577356097
Publication statusPublished - 2013
Externally publishedYes
EventInternational Conference on Automated Planning and Scheduling 2013 - Rome, Italy
Duration: 10 Jun 201314 Jun 2013
Conference number: 23rd (Proceedings)


ConferenceInternational Conference on Automated Planning and Scheduling 2013
Abbreviated titleICAPS 2013
Internet address

Cite this