Strengthening Potential Heuristics with Mutexes and Disambiguations

Daniel Fišer, Rostislav Horčík, Antonín Komenda

PosterID: 56 PDF Slides BibTeX

Potential heuristics assign a numerical value (potential) to each fact and compute the heuristic value for a given state as a sum of these potentials. Mutexes are invariants stating that a certain set of facts cannot be part of any reachable state. In this paper, we use mutexes to improve potential heuristics in two ways. First, we show that the mutex-based disambiguations of the goal and preconditions of operators leads to a less constrained linear program providing a better set of potentials. Second, we utilize mutexes in a construction of new optimization functions based on counting of a number of states containing certain sets of facts. The experimental evaluation shows a significant increase in the number of solved tasks.

Session E10: Heuristic Search Planning
Canb 10/28/2020, 21:00 – 21:45
10/30/2020, 04:00 – 04:45
Paris 10/28/2020, 11:00 – 11:45
10/29/2020, 18:00 – 18:45
NYC 10/28/2020, 06:00 – 06:45
10/29/2020, 13:00 – 13:45
LA 10/28/2020, 03:00 – 03:45
10/29/2020, 10:00 – 10:45