An optimal any-angle pathfinding algorithm

Daniel Harabor, Alban Grastien

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

22 Citations (Scopus)

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.

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)
Pages308-311
Number of pages4
ISBN (Print)9781577356097
Publication statusPublished - 2013
Externally publishedYes
EventInternational Conference on Automated Planning and Scheduling 2013 - Auditorium Antonianum, Rome, Italy
Duration: 10 Jun 201314 Jun 2013
Conference number: 23
http://icaps13.icaps-conference.org/

Conference

ConferenceInternational Conference on Automated Planning and Scheduling 2013
Abbreviated titleICAPS 2013
CountryItaly
CityRome
Period10/06/1314/06/13
Internet address

Cite this

Harabor, D., & Grastien, A. (2013). An optimal any-angle pathfinding algorithm. In D. Borrajo, S. Fratini, S. Kambhampati, & A. Oddi (Eds.), Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling (pp. 308-311). Association for the Advancement of Artificial Intelligence (AAAI).