Optimal any-angle pathfinding in practice

Daniel Harabor, Alban Grastien, Dindar Öz, Vural Aksakalli

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Any-angle pathfinding is a fundamental problem in robotics and computer games. The goal is to find a shortest path between a pair of points on a grid map such that the path is not artificially constrained to the points of the grid. Prior research has focused on approximate online solutions. A number of exact methods exist but they all require super-linear space and pre-processing time. In this study, we describe Anya: a new and optimal any-angle pathfinding algorithm. Where other works find approximate any-angle paths by searching over individual points from the grid, Anya finds optimal paths by searching over sets of states represented as intervals. Each interval is identified on-the-fly. From each interval Anya selects a single representative point that it uses to compute an admissible cost estimate for the entire set. Anya always returns an optimal path if one exists. Moreover it does so without any offline pre-processing or the introduction of additional memory overheads. In a range of empirical comparisons we show that Anya is competitive with several recent (sub-optimal) online and pre-processing based techniques and is up to an order of magnitude faster than the most common benchmark algorithm, a grid-based implementation of A∗.

Original languageEnglish
Pages (from-to)89-118
Number of pages30
JournalJournal of Artificial Intelligence Research
Volume56
DOIs
Publication statusPublished - May 2016
Externally publishedYes

Cite this

Harabor, Daniel ; Grastien, Alban ; Öz, Dindar ; Aksakalli, Vural. / Optimal any-angle pathfinding in practice. In: Journal of Artificial Intelligence Research. 2016 ; Vol. 56. pp. 89-118.
@article{ea121d4d57154976a964c4878aa911b9,
title = "Optimal any-angle pathfinding in practice",
abstract = "Any-angle pathfinding is a fundamental problem in robotics and computer games. The goal is to find a shortest path between a pair of points on a grid map such that the path is not artificially constrained to the points of the grid. Prior research has focused on approximate online solutions. A number of exact methods exist but they all require super-linear space and pre-processing time. In this study, we describe Anya: a new and optimal any-angle pathfinding algorithm. Where other works find approximate any-angle paths by searching over individual points from the grid, Anya finds optimal paths by searching over sets of states represented as intervals. Each interval is identified on-the-fly. From each interval Anya selects a single representative point that it uses to compute an admissible cost estimate for the entire set. Anya always returns an optimal path if one exists. Moreover it does so without any offline pre-processing or the introduction of additional memory overheads. In a range of empirical comparisons we show that Anya is competitive with several recent (sub-optimal) online and pre-processing based techniques and is up to an order of magnitude faster than the most common benchmark algorithm, a grid-based implementation of A∗.",
author = "Daniel Harabor and Alban Grastien and Dindar {\"O}z and Vural Aksakalli",
year = "2016",
month = "5",
doi = "10.1613/jair.5007",
language = "English",
volume = "56",
pages = "89--118",
journal = "Journal of Artificial Intelligence Research",
issn = "1076-9757",
publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",

}

Optimal any-angle pathfinding in practice. / Harabor, Daniel; Grastien, Alban; Öz, Dindar; Aksakalli, Vural.

In: Journal of Artificial Intelligence Research, Vol. 56, 05.2016, p. 89-118.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Optimal any-angle pathfinding in practice

AU - Harabor, Daniel

AU - Grastien, Alban

AU - Öz, Dindar

AU - Aksakalli, Vural

PY - 2016/5

Y1 - 2016/5

N2 - Any-angle pathfinding is a fundamental problem in robotics and computer games. The goal is to find a shortest path between a pair of points on a grid map such that the path is not artificially constrained to the points of the grid. Prior research has focused on approximate online solutions. A number of exact methods exist but they all require super-linear space and pre-processing time. In this study, we describe Anya: a new and optimal any-angle pathfinding algorithm. Where other works find approximate any-angle paths by searching over individual points from the grid, Anya finds optimal paths by searching over sets of states represented as intervals. Each interval is identified on-the-fly. From each interval Anya selects a single representative point that it uses to compute an admissible cost estimate for the entire set. Anya always returns an optimal path if one exists. Moreover it does so without any offline pre-processing or the introduction of additional memory overheads. In a range of empirical comparisons we show that Anya is competitive with several recent (sub-optimal) online and pre-processing based techniques and is up to an order of magnitude faster than the most common benchmark algorithm, a grid-based implementation of A∗.

AB - Any-angle pathfinding is a fundamental problem in robotics and computer games. The goal is to find a shortest path between a pair of points on a grid map such that the path is not artificially constrained to the points of the grid. Prior research has focused on approximate online solutions. A number of exact methods exist but they all require super-linear space and pre-processing time. In this study, we describe Anya: a new and optimal any-angle pathfinding algorithm. Where other works find approximate any-angle paths by searching over individual points from the grid, Anya finds optimal paths by searching over sets of states represented as intervals. Each interval is identified on-the-fly. From each interval Anya selects a single representative point that it uses to compute an admissible cost estimate for the entire set. Anya always returns an optimal path if one exists. Moreover it does so without any offline pre-processing or the introduction of additional memory overheads. In a range of empirical comparisons we show that Anya is competitive with several recent (sub-optimal) online and pre-processing based techniques and is up to an order of magnitude faster than the most common benchmark algorithm, a grid-based implementation of A∗.

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

U2 - 10.1613/jair.5007

DO - 10.1613/jair.5007

M3 - Article

VL - 56

SP - 89

EP - 118

JO - Journal of Artificial Intelligence Research

JF - Journal of Artificial Intelligence Research

SN - 1076-9757

ER -