What Makes You Special? Contrastive Heuristics Based on Qualified Dominance

In cost-optimal planning, dominance pruning methods discard states during the search that are dominated by others. However, the binary nature of pruning fails to exploit information when we cannot prove that a state is fully dominated. To this end, we introduce qualified dominance, an automatic method that given a pair of states s,t synthetizes a finite state automaton that represents a language of plans from s that are dominated by t. This not only explains why s cannot be pruned, but also can be used to improve the heuristic function to guide the search. This results in a new type of heuristic, which we call contrastive heuristics, that are dependent on the search performed so far. We provide the theoretical foundation for showing that contrastive heuristics can be used to find optimal plans even when their more informative estimates are not admissible.