Grid Pathfinding on the 2k Neighborhoods

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

Resultado de la investigación: Contribución a los tipos de informe/libroContribución a la conferencia

6 Citas (Scopus)


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 originalInglés
Título de la publicación alojada31st AAAI Conference on Artificial Intelligence, AAAI 2017
EditorialAAAI press
Número de páginas7
EstadoPublicada - 2017
Evento31st AAAI Conference on Artificial Intelligence, AAAI 2017 - San Francisco, Estados Unidos
Duración: 4 feb 201710 feb 2017


Conferencia31st AAAI Conference on Artificial Intelligence, AAAI 2017
PaísEstados Unidos
CiudadSan Francisco

    Huella digital

Áreas temáticas de ASJC Scopus

  • Inteligencia artificial

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.