Finding a Dominating State in a Haystack: Efficient Data Structures for Dominance Pruning

Abstract

Dominance pruning is a technique to reduce search effort by comparing states against each other and discarding dominated states. However, despite being effective at significantly reducing the number of expansions in many domains, the overhead of comparing states may lead to reduced performance. This is specially critical in hard problems, as the overhead of comparing all pairs of states grows quadratically with the number of explored states. In this paper, we investigate how to use data structures that exploit the inner structure of dominance relations in order to perform this check efficiently. We show that these data structures can avoid the quadratic worst-case in many domains, significantly improving the performance of search with dominance pruning.