An optimal any-angle pathfinding algorithm

Daniel Harabor, Alban Grastien

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

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
PublisherAAAI Press
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). Menlo Park, California: AAAI Press.
Harabor, Daniel ; Grastien, Alban. / An optimal any-angle pathfinding algorithm. Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling. editor / Daniel Borrajo ; Simone Fratini ; Subbarao Kambhampati ; Angelo Oddi. Menlo Park, California : AAAI Press, 2013. pp. 308-311
@inproceedings{f483bcac88714f298478c2284336c495,
title = "An optimal any-angle pathfinding algorithm",
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.",
author = "Daniel Harabor and Alban Grastien",
year = "2013",
language = "English",
isbn = "9781577356097",
pages = "308--311",
editor = "Daniel Borrajo and Simone Fratini and Subbarao Kambhampati and Angelo Oddi",
booktitle = "Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling",
publisher = "AAAI Press",

}

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. AAAI Press, Menlo Park, California, pp. 308-311, International Conference on Automated Planning and Scheduling 2013, Rome, Italy, 10/06/13.

An optimal any-angle pathfinding algorithm. / Harabor, Daniel; Grastien, Alban.

Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling. ed. / Daniel Borrajo; Simone Fratini; Subbarao Kambhampati; Angelo Oddi. Menlo Park, California : AAAI Press, 2013. p. 308-311.

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

TY - GEN

T1 - An optimal any-angle pathfinding algorithm

AU - Harabor, Daniel

AU - Grastien, Alban

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84889809573&partnerID=8YFLogxK

M3 - Conference Paper

SN - 9781577356097

SP - 308

EP - 311

BT - Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling

A2 - Borrajo, Daniel

A2 - Fratini, Simone

A2 - Kambhampati, Subbarao

A2 - Oddi, Angelo

PB - AAAI Press

CY - Menlo Park, California

ER -

Harabor D, Grastien A. An optimal any-angle pathfinding algorithm. In Borrajo D, Fratini S, Kambhampati S, Oddi A, editors, Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling. Menlo Park, California: AAAI Press. 2013. p. 308-311