Path planning with CPD heuristics

Massimo Bono, Alfonso Gerevini, Daniel Harabor, Peter Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

Compressed Path Databases (CPDs) are a leading technique for optimal pathfinding in graphs with static edge costs. In this work we investigate CPDs as admissible heuristic functions and we apply them in two distinct settings: problems where the graph is subject to dynamically changing costs, and anytime settings where deliberation time is limited. Conventional heuristics derive cost-to-go estimates by reasoning about a tentative and usually infeasible path, from the current node to the target. CPD-based heuristics derive cost-to-go estimates by computing a concrete and usually feasible path. We exploit such paths to bound the optimal solution, not just from below but also from above. We demonstrate the benefit of this approach in a range of experiments on standard gridmaps and in comparison to Landmarks, a popular alternative also developed for searching in explicit state-spaces.

Original languageEnglish
Title of host publicationProceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
EditorsSarit Kraus
Place of PublicationMarina del Rey CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages1199-1205
Number of pages7
ISBN (Electronic)9780999241141
DOIs
Publication statusPublished - 2019
EventInternational Joint Conference on Artificial Intelligence 2019 - Macao, China
Duration: 10 Aug 201916 Aug 2019
Conference number: 28th
https://ijcai19.org/

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
Volume2019-August
ISSN (Print)1045-0823

Conference

ConferenceInternational Joint Conference on Artificial Intelligence 2019
Abbreviated titleIJCAI-19
CountryChina
CityMacao
Period10/08/1916/08/19
Internet address

Keywords

  • Heuristic Search
  • Motion and Path Planning

Cite this

Bono, M., Gerevini, A., Harabor, D., & Stuckey, P. (2019). Path planning with CPD heuristics. In S. Kraus (Ed.), Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (pp. 1199-1205). (IJCAI International Joint Conference on Artificial Intelligence; Vol. 2019-August). Association for the Advancement of Artificial Intelligence (AAAI). https://doi.org/10.24963/ijcai.2019/167