Simulation-Based Admissible Dominance Pruning
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 1689-1694.
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.
@inproceedings{ijcai2015p241,
title = {Simulation-Based Admissible Dominance Pruning},
author = {de Reyna, Álvaro Torralba Arias and Hoffmann, Jörg},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {1689--1694},
year = {2015},
month = {7},
note = {Main Track},
url = {https://ijcai.org/proceedings/2015/241},
}
TY - CPAPER TI - Simulation-Based Admissible Dominance Pruning AU - de Reyna, Álvaro Torralba Arias AU - Hoffmann, Jörg T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 1689 EP - 1694 UR - https://ijcai.org/proceedings/2015/241 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
