Abstract

In optimal planning as heuristic search, admissible pruning techniques are paramount. One idea is dominance pruning, identifying states "better than" other states. Prior approaches are limited to simple dominance notions, like "more STRIPS facts true" or "higher resource supply". We apply simulation, well-known in model checking, to compute much more general dominance relations based on comparing transition behavior across states. We do so effectively by expressing state-space simulations through the composition of simulations on orthogonal projections. We show how simulation can be made more powerful by intertwining it with a notion of label dominance. Our experiments show substantial improvements across several IPC benchmark domains.

Abstract

Simulation-Based Admissible Dominance Pruning / 1689 álvaro Torralba, Jörg Hoffmann PDF