On State-Dominance Criteria in Fork-Decoupled Search
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 3265-3270.
Abstract
Fork-decoupled search is a recent approach to classical planning that exploits fork structures, where a single center component provides preconditions for several leaf components. The decoupled states in this search consist of a center state, along with a price for every leaf state. Given this, when does one decoupled state dominate another? Such state-dominance criteria can be used to prune dominated search states. Prior work has devised only a trivial criterion. We devise several more powerful criteria, show that they preserve optimality, and establish their interrelations. We show that they can yield exponential reductions. Experiments on IPC benchmarks attest to the possible practical benefits.
@inproceedings{ijcai2016p462,
title = {On State-Dominance Criteria in Fork-Decoupled Search},
author = {de Reyna, Álvaro Torralba Arias and Gnad, Daniel and Dubbert, Patrick and Hoffmann, Jörg},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {3265--3270},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/462},
}
TY - CPAPER TI - On State-Dominance Criteria in Fork-Decoupled Search AU - de Reyna, Álvaro Torralba Arias AU - Gnad, Daniel AU - Dubbert, Patrick AU - Hoffmann, Jörg T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 3265 EP - 3270 UR - https://ijcai.org/proceedings/2016/462 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
