AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 14

The Closed List Is an Obstacle Too

Authors

Ariel Felner,Shahaf S. Shperberg,Hadar Buzhish

Ben-Gurion University, Be’er-Sheva, Israel,Ben-Gurion University, Be’er-Sheva, Israel,Ben-Gurion University, Be’er-Sheva, Israel


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 14

Volume

Issue:

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search

Track:

Short Papers

Downloads:

Download PDF

Abstract:

The baseline approach for optimal path finding in 4-connected grids is A* with Manhattan Distance. Nevertheless, a large number of enhancements were suggested over the years, usually requiring a preprocessing phase and/or additional memory to store smart lookup tables. In this paper we introduce an enhancement to A* (called BOXA*) on grids which does not need any preprocessing and only needs negligible additional memory. The main idea is to treat the closed-list as a dynamic obstacle. We maintain a list of rectangles which surround CLOSED nodes and calculate an admissible heuristic using the fact that an optimal path from a given node must go around these rectangles. We experimentally show the benefits of this approach on a variety of grid domains.

DOI:

10.1609/socs.v12i1.18559


SOCS

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search