The 2<i><SUP>k</SUP></i> Neighborhoods for Grid Path Planning

Simple item page
dc.contributor.authorRivera, Nicolas
dc.contributor.authorHernandez, Carlos
dc.contributor.authorHormazabal, Nicolas
dc.contributor.authorBaier, Jorge A.
dc.date.accessioned2025-01-23T19:52:11Z
dc.date.available2025-01-23T19:52:11Z
dc.date.issued2020
dc.description.abstractGrid 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.
dc.fuente.origenWOS
dc.identifier.eissn1943-5037
dc.identifier.issn1076-9757
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/100621
dc.identifier.wosidWOS:000528198400003
dc.language.isoen
dc.pagina.final113
dc.pagina.inicio81
dc.revistaJournal of artificial intelligence research
dc.rightsacceso restringido
dc.subject.ods11 Sustainable Cities and Communities
dc.subject.odspa11 Ciudades y comunidades sostenibles
dc.titleThe 2<i><SUP>k</SUP></i> Neighborhoods for Grid Path Planning
dc.typeartículo
dc.volumen67
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Collections
Artículos de revistas