Strengthening Potential Heuristics with Mutexes and Disambiguations

Authors

  • Daniel Fišer Czech Technical University in Prague
  • Rostislav Horčík Czech Technical University in Prague
  • Antonín Komenda Czech Technical University in Prague

DOI:

https://doi.org/10.1609/icaps.v30i1.6653

Abstract

Potential heuristics assign a numerical value (potential) to each fact and compute the heuristic value for a given state as the sum of these potentials. A mutex is an invariant stating that a certain combination 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 yielding stronger heuristics. Second, we utilize mutexes in a construction of new optimization functions based on counting of the number of states containing certain sets of facts. The experimental evaluation shows a significant increase in the number of solved tasks.

Downloads

Published

2020-06-01

How to Cite

Fišer, D., Horčík, R., & Komenda, A. (2020). Strengthening Potential Heuristics with Mutexes and Disambiguations. Proceedings of the International Conference on Automated Planning and Scheduling, 30(1), 124-133. https://doi.org/10.1609/icaps.v30i1.6653