Strengthening Potential Heuristics with Mutexes and Disambiguations

Book One

Volume

Proceedings of the International Conference on Automated Planning and Scheduling, 30

Main Track

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.

10.1609/icaps.v30i1.6653