Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



The 2<i><SUP>k</SUP></i> Neighborhoods for Grid Path Planning
Indexado
WoS WOS:000528198400003
DOI
Año 2020
Tipo artículo de investigación

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



Grid path planning is an important problem in AI. Its understanding has been key for the development of autonomous navigation systems. An interesting and rather surprising fact about the vast literature on this problem is that only a few neighborhoods have been used when evaluating these algorithms. Indeed, only the 4- and 8-neighborhoods are usually considered, and rarely the 16-neighborhood. This paper describes three contributions that enable the construction of effective grid path planners for extended 2(k)-neighborhoods; that is, neighborhoods that admit 2(k) neighbors per state, where k is a parameter. First, we provide a simple recursive definition of the 2(k)-neighborhood in terms of the 2(k-1)-neighborhood. Second, we derive distance functions, for any k >= 2, which allow us to propose admissible heuristics that are perfect for obstacle-free grids, which generalize the well-known Manhattan and Octile distances. Third, we define the notion of canonical path for the 2(k)-neighborhood; this allows us to incorporate our neighborhoods into two versions of A*, namely Canonical A* and Jump Point Search (JPS), whose performance, we show, scales well when increasing k. Our empirical evaluation shows that, when increasing k, the cost of the solution found improves substantially. Used with the 2(k)-neighborhood, Canonical A* and JPS, in many configurations, are also superior to the any-angle path planner Theta* both in terms of solution quality and runtime. Our planner is competitive with one implementation of the any-angle path planner, ANYA in some configurations. Our main practical conclusion is that standard, well-understood grid path planning technology may provide an effective approach to any-angle grid path planning.

Disciplinas de Investigación



WOS
Computer Science, Artificial Intelligence
Scopus
Artificial Intelligence
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 Rivera, Nicolas Hombre UNIV CAMBRIDGE - Reino Unido
2 HERNANDEZ-ULLOA, CARLOS MARCELO Hombre Universidad Nacional Andrés Bello - Chile
3 Hormazabal, Nicolas Hombre Universidad Nacional Andrés Bello - Chile
4 BAIER-ARANDA, JORGE ANDRES Hombre Pontificia Universidad Católica de Chile - Chile

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
FONDECYT
Becas Chile initiative
Proyecto VRI Puente

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
We thank Dietrich Daroch and Alejandro Pimentel for their comments on early drafts of this paper. Nicolas Rivera acknowledges funding from the Becas Chile initiative. Carlos Hernandez and Jorge Baier are grateful to Fondecyt which partly funded this work through grants 1150328 and 1161526. Jorge Baier acknowledges funding from Proyecto VRI Puente

Muestra la fuente de financiamiento declarada en la publicación.