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ículorevisión exhaustiva

4 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ís/TerritorioEstados Unidos
CiudadPittsburgh
Período16/06/1717/06/17

Áreas temáticas de ASJC Scopus

  • Redes de ordenadores y comunicaciones

Huella

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

Citar esto