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

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

Producción científica: Contribución a los distintos tipos de conferenciaArtículorevisión exhaustiva

6 Citas (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.

Idioma originalInglés
Número de páginas5
EstadoPublicada - 1 ene. 2017
Evento10th Annual Symposium on Combinatorial Search, SoCS 2017 - Pittsburgh, Estados Unidos
Duración: 16 jun. 201717 jun. 2017


Conferencia10th Annual Symposium on Combinatorial Search, SoCS 2017
País/TerritorioEstados Unidos

Áreas temáticas de ASJC Scopus

  • Redes de ordenadores y comunicaciones


Profundice en los temas de investigación de 'Fast and almost optimal any-angle pathfinding using the 2k neighborhoods'. En conjunto forman una huella única.

Citar esto