Abstraction heuristics for symbolic bidirectional search

Alvaro Torralba, Carlos Linares Lopez, Daniel Borrajo

Research output: Contribution to journalConference article in JournalResearchpeer-review

17 Citations (Scopus)

Abstract

Symbolic bidirectional uniform-cost search is a prominent technique for cost-optimal planning. Thus, the question whether it can be further improved by making use of heuristic functions raises naturally. However, the use of heuristics in bidirectional search does not always improve its performance. We propose a novel way to use abstraction heuristics in symbolic bidirectional search in which the search only resorts to heuristics when it becomes unfeasible. We adapt the definition of partial and perimeter abstractions to bidirectional search, where A is used to traverse the abstract state spaces and/or generate the perimeter. The results show that abstraction heuristics can further improve symbolic bidirectional search in some domains. In fact, the resulting planner, SymBA, was the winner of the optimal-track of the last IPC.

Original languageEnglish
JournalIJCAI International Joint Conference on Artificial Intelligence
Volume2016-January
Pages (from-to)3272-3278
Number of pages7
ISSN1045-0823
Publication statusPublished - 2016
Externally publishedYes
Event25th International Joint Conference on Artificial Intelligence, IJCAI 2016 - New York, United States
Duration: 9 Jul 201615 Jul 2016

Conference

Conference25th International Joint Conference on Artificial Intelligence, IJCAI 2016
Country/TerritoryUnited States
CityNew York
Period09/07/201615/07/2016
SponsorAI Journal, Arizona State University, Baidu, et al., IBM Watson, Sony Group Corporation

Keywords

  • Planning and scheduling
  • Artificial Intelligence (AI)

Fingerprint

Dive into the research topics of 'Abstraction heuristics for symbolic bidirectional search'. Together they form a unique fingerprint.

Cite this