Fast and almost optimal any-angle pathfinding using the 2k neighborhoods

Nicolás Hormazábal, Antonio Díaz, Carlos Hernández, Jorge A. Baier

Research output: Contribution to conferencePaperpeer-review

4 Citations (Scopus)


Any-angle path finding on grids is an important problem with applications in autonomous robot navigation. In this paper, we show that a well-known pre-processing technique, namely subgoal graphs, originally proposed for (non anyangle) 8-connected grids, can be straightforwardly adapted to the 2k neighborhoods, a family of neighborhoods that allow an increasing number of movements (and angles) as k is increased. This observation yields a pathfinder that computes 2k-optimal paths very quickly. Compared to ANYA, an optimal true any-angle planner, over a variety of benchmarks, our planner is one order of magnitude faster while being less than 0.0005% suboptimal. Important to our planner’s performance was the development of an iterative 2k heuristic, linear in k, which is also a contribution of this paper.

Original languageEnglish
Number of pages5
Publication statusPublished - 1 Jan 2017
Event10th Annual Symposium on Combinatorial Search, SoCS 2017 - Pittsburgh, United States
Duration: 16 Jun 201717 Jun 2017


Conference10th Annual Symposium on Combinatorial Search, SoCS 2017
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'Fast and almost optimal any-angle pathfinding using the 2<sup>k</sup> neighborhoods'. Together they form a unique fingerprint.

Cite this