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

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

Resultado de la investigación: Contribución a los distintos tipos de conferenciaArtículo

3 Citas (Scopus)

Resumen

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
Páginas139-143
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

Conferencia

Conferencia10th Annual Symposium on Combinatorial Search, SoCS 2017
PaísEstados Unidos
CiudadPittsburgh
Período16/06/1717/06/17

    Huella digital

Áreas temáticas de ASJC Scopus

  • Redes de ordenadores y comunicaciones

Citar esto

Hormazábal, N., Díaz, A., Hernández, C., & Baier, J. A. (2017). Fast and almost optimal any-angle pathfinding using the 2k neighborhoods. 139-143. Papel presentado en 10th Annual Symposium on Combinatorial Search, SoCS 2017, Pittsburgh, Estados Unidos.