A Suboptimality Bound for 2kGrid Path Planning

Benjamin Kramm, Nicolas Rivera, Carlos Hernandez, Jorge A. Baier

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

1 Cita (Scopus)


The 2kneighborhood has been recently proposed as an alternative to optimal any-angle path planning over grids. Even though it has been observed empirically that the quality of solutions approaches the cost of an optimal any-angle path as k is increased, no theoretical bounds were known. In this paper we study the ratio between the solutions obtained by an any-angle path and the optimal path in the 2kneighborhood. We derive a suboptimality bound, as a function of k, that generalizes previously known bounds for the 4- and 8- connected grids. We analyze two cases: when vertices of the search graph are placed (1) at the corners of grid cells, and (2) when they are located at their centers. For case (1) we obtain a suboptimality bound of 1 + 1/8k2+ O(1/k3), which is tight; for (2), however, worst-case suboptimality is a fixed value, for every k = 3. Our results strongly suggests that vertices need to be placed in corners in order to obtain near-optimal solutions. In an empirical analysis, we compare theoretical and experimental suboptimality.

Idioma originalInglés
Título de la publicación alojadaProceedings of the 11th International Symposium on Combinatorial Search, SoCS 2018
EditoresVadim Bulitko, Sabine Storandt
EditorialAAAI press
Número de páginas9
ISBN (versión digital)9781577358022
EstadoPublicada - 2018
Evento11th International Symposium on Combinatorial Search, SoCS 2018 - Stockholm, Suecia
Duración: 14 jul 201815 jul 2018

Serie de la publicación

NombreProceedings of the 11th International Symposium on Combinatorial Search, SoCS 2018


Conferencia11th International Symposium on Combinatorial Search, SoCS 2018

Áreas temáticas de ASJC Scopus

  • Redes de ordenadores y comunicaciones


Profundice en los temas de investigación de 'A Suboptimality Bound for 2<sup>k</sup>Grid Path Planning'. En conjunto forman una huella única.

Citar esto