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: Paper

2 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 originalEnglish
Páginas139-143
Número de páginas5
EstadoPublished - 1 ene 2017
Evento10th Annual Symposium on Combinatorial Search, SoCS 2017 - Pittsburgh, United States
Duración: 16 jun 201717 jun 2017

Conference

Conference10th Annual Symposium on Combinatorial Search, SoCS 2017
PaísUnited States
CiudadPittsburgh
Período16/06/1717/06/17

Huella dactilar

Navigation
Robots
Processing

ASJC Scopus subject areas

  • Computer Networks and Communications

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, United States.
Hormazábal, Nicolás ; Díaz, Antonio ; Hernández, Carlos ; Baier, Jorge A. / Fast and almost optimal any-angle pathfinding using the 2k neighborhoods. Papel presentado en 10th Annual Symposium on Combinatorial Search, SoCS 2017, Pittsburgh, United States.5 p.
@conference{34a45f1b463f4a738966881ea61a6d2c,
title = "Fast and almost optimal any-angle pathfinding using the 2k neighborhoods",
abstract = "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.",
author = "Nicol{\'a}s Hormaz{\'a}bal and Antonio D{\'i}az and Carlos Hern{\'a}ndez and Baier, {Jorge A.}",
year = "2017",
month = "1",
day = "1",
language = "English",
pages = "139--143",
note = "10th Annual Symposium on Combinatorial Search, SoCS 2017 ; Conference date: 16-06-2017 Through 17-06-2017",

}

Hormazábal, N, Díaz, A, Hernández, C & Baier, JA 2017, 'Fast and almost optimal any-angle pathfinding using the 2k neighborhoods' Papel presentado en 10th Annual Symposium on Combinatorial Search, SoCS 2017, Pittsburgh, United States, 16/06/17 - 17/06/17, pp. 139-143.

Fast and almost optimal any-angle pathfinding using the 2k neighborhoods. / Hormazábal, Nicolás; Díaz, Antonio; Hernández, Carlos; Baier, Jorge A.

2017. 139-143 Papel presentado en 10th Annual Symposium on Combinatorial Search, SoCS 2017, Pittsburgh, United States.

Resultado de la investigación: Paper

TY - CONF

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

AU - Hormazábal, Nicolás

AU - Díaz, Antonio

AU - Hernández, Carlos

AU - Baier, Jorge A.

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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.

AB - 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.

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

M3 - Paper

AN - SCOPUS:85050566439

SP - 139

EP - 143

ER -

Hormazábal N, Díaz A, Hernández C, Baier JA. Fast and almost optimal any-angle pathfinding using the 2k neighborhoods. 2017. Papel presentado en 10th Annual Symposium on Combinatorial Search, SoCS 2017, Pittsburgh, United States.