Grid Pathfinding on the 2k Neighborhoods

Nicolás Rivera, Carlos Hernández, Jorge A. Baier

Resultado de la investigación: Conference contribution

5 Citas (Scopus)

Resumen

Grid pathfinding, an old AI problem, is central for the development of navigation systems for autonomous agents. A surprising fact about the vast literature on this problem is that very limited neighborhoods have been studied. 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 2k-neighborhoods. First, we provide a simple recursive definition of the 2k-neighborhood in terms of the 2k-1-neighborhood. Second, we derive distance functions, for any k > 1, which allow us to propose admissible heurisitics which are perfect for obstacle-free grids. Third, we describe a canonical ordering which allows us to implement a version of A∗ whose performance scales well when increasing k. Our empirical evaluation shows that the heuristics we propose are superior to the Euclidean distance (ED) when regular A∗ is used. For grids beyond 64 the overhead of computing the heuristic yields decreased time performance compared to the ED. We found also that a configuration of our A∗-based implementation, without canonical orders, is competitive with the "any-angle" path planner Theta∗ both in terms of solution quality and runtime.

Idioma originalEnglish
Título de la publicación alojada31st AAAI Conference on Artificial Intelligence, AAAI 2017
EditorialAAAI press
Páginas891-897
Número de páginas7
EstadoPublished - 2017
Evento31st AAAI Conference on Artificial Intelligence, AAAI 2017 - San Francisco, United States
Duración: 4 feb 201710 feb 2017

Conference

Conference31st AAAI Conference on Artificial Intelligence, AAAI 2017
PaísUnited States
CiudadSan Francisco
Período4/02/1710/02/17

Huella dactilar

Autonomous agents
Navigation systems

ASJC Scopus subject areas

  • Artificial Intelligence

Citar esto

Rivera, N., Hernández, C., & Baier, J. A. (2017). Grid Pathfinding on the 2k Neighborhoods. En 31st AAAI Conference on Artificial Intelligence, AAAI 2017 (pp. 891-897). AAAI press.
Rivera, Nicolás ; Hernández, Carlos ; Baier, Jorge A. / Grid Pathfinding on the 2k Neighborhoods. 31st AAAI Conference on Artificial Intelligence, AAAI 2017. AAAI press, 2017. pp. 891-897
@inproceedings{b4028d90677048ad83dc2d77ddc114b1,
title = "Grid Pathfinding on the 2k Neighborhoods",
abstract = "Grid pathfinding, an old AI problem, is central for the development of navigation systems for autonomous agents. A surprising fact about the vast literature on this problem is that very limited neighborhoods have been studied. 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 2k-neighborhoods. First, we provide a simple recursive definition of the 2k-neighborhood in terms of the 2k-1-neighborhood. Second, we derive distance functions, for any k > 1, which allow us to propose admissible heurisitics which are perfect for obstacle-free grids. Third, we describe a canonical ordering which allows us to implement a version of A∗ whose performance scales well when increasing k. Our empirical evaluation shows that the heuristics we propose are superior to the Euclidean distance (ED) when regular A∗ is used. For grids beyond 64 the overhead of computing the heuristic yields decreased time performance compared to the ED. We found also that a configuration of our A∗-based implementation, without canonical orders, is competitive with the {"}any-angle{"} path planner Theta∗ both in terms of solution quality and runtime.",
author = "Nicol{\'a}s Rivera and Carlos Hern{\'a}ndez and Baier, {Jorge A.}",
year = "2017",
language = "English",
pages = "891--897",
booktitle = "31st AAAI Conference on Artificial Intelligence, AAAI 2017",
publisher = "AAAI press",

}

Rivera, N, Hernández, C & Baier, JA 2017, Grid Pathfinding on the 2k Neighborhoods. En 31st AAAI Conference on Artificial Intelligence, AAAI 2017. AAAI press, pp. 891-897, 31st AAAI Conference on Artificial Intelligence, AAAI 2017, San Francisco, United States, 4/02/17.

Grid Pathfinding on the 2k Neighborhoods. / Rivera, Nicolás; Hernández, Carlos; Baier, Jorge A.

31st AAAI Conference on Artificial Intelligence, AAAI 2017. AAAI press, 2017. p. 891-897.

Resultado de la investigación: Conference contribution

TY - GEN

T1 - Grid Pathfinding on the 2k Neighborhoods

AU - Rivera, Nicolás

AU - Hernández, Carlos

AU - Baier, Jorge A.

PY - 2017

Y1 - 2017

N2 - Grid pathfinding, an old AI problem, is central for the development of navigation systems for autonomous agents. A surprising fact about the vast literature on this problem is that very limited neighborhoods have been studied. 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 2k-neighborhoods. First, we provide a simple recursive definition of the 2k-neighborhood in terms of the 2k-1-neighborhood. Second, we derive distance functions, for any k > 1, which allow us to propose admissible heurisitics which are perfect for obstacle-free grids. Third, we describe a canonical ordering which allows us to implement a version of A∗ whose performance scales well when increasing k. Our empirical evaluation shows that the heuristics we propose are superior to the Euclidean distance (ED) when regular A∗ is used. For grids beyond 64 the overhead of computing the heuristic yields decreased time performance compared to the ED. We found also that a configuration of our A∗-based implementation, without canonical orders, is competitive with the "any-angle" path planner Theta∗ both in terms of solution quality and runtime.

AB - Grid pathfinding, an old AI problem, is central for the development of navigation systems for autonomous agents. A surprising fact about the vast literature on this problem is that very limited neighborhoods have been studied. 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 2k-neighborhoods. First, we provide a simple recursive definition of the 2k-neighborhood in terms of the 2k-1-neighborhood. Second, we derive distance functions, for any k > 1, which allow us to propose admissible heurisitics which are perfect for obstacle-free grids. Third, we describe a canonical ordering which allows us to implement a version of A∗ whose performance scales well when increasing k. Our empirical evaluation shows that the heuristics we propose are superior to the Euclidean distance (ED) when regular A∗ is used. For grids beyond 64 the overhead of computing the heuristic yields decreased time performance compared to the ED. We found also that a configuration of our A∗-based implementation, without canonical orders, is competitive with the "any-angle" path planner Theta∗ both in terms of solution quality and runtime.

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

M3 - Conference contribution

AN - SCOPUS:85030482721

SP - 891

EP - 897

BT - 31st AAAI Conference on Artificial Intelligence, AAAI 2017

PB - AAAI press

ER -

Rivera N, Hernández C, Baier JA. Grid Pathfinding on the 2k Neighborhoods. En 31st AAAI Conference on Artificial Intelligence, AAAI 2017. AAAI press. 2017. p. 891-897