### 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 2^{k}-neighborhood in terms of the 2^{k-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 original | English |
---|---|

Título de la publicación alojada | 31st AAAI Conference on Artificial Intelligence, AAAI 2017 |

Editorial | AAAI press |

Páginas | 891-897 |

Número de páginas | 7 |

Estado | Published - 2017 |

Evento | 31st AAAI Conference on Artificial Intelligence, AAAI 2017 - San Francisco, United States Duración: 4 feb 2017 → 10 feb 2017 |

### Conference

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

País | United States |

Ciudad | San Francisco |

Período | 4/02/17 → 10/02/17 |

### Huella dactilar

### ASJC Scopus subject areas

- Artificial Intelligence

### Citar esto

^{k}Neighborhoods. En

*31st AAAI Conference on Artificial Intelligence, AAAI 2017*(pp. 891-897). AAAI press.

}

^{k}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 2 ^{k} Neighborhoods.** / Rivera, Nicolás; Hernández, Carlos; Baier, Jorge A.

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 -

^{k}Neighborhoods. En 31st AAAI Conference on Artificial Intelligence, AAAI 2017. AAAI press. 2017. p. 891-897