Decoupled Strong Stubborn Sets
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 3110-3115.
Abstract
Recent work has introduced fork-decoupled search, addressing classical planning problems where a single center component provides preconditions for several leaf components. Given a fixed center path πC, the leaf moves compliant with πC can then be scheduled independently for each leaf. Fork-decoupled search thus searches over center paths only, maintaining the compliant paths for each leaf separately. This can yield dramatic benefits. It is empirically complementary to partial order reduction via strong stubborn sets, in that each method yields its strongest reductions in different benchmarks. Here we show that the two methods can be combined, in the form of strong stubborn sets for fork-decoupled search. This can yield exponential advantages relative to both methods. Empirically, the combination reliably inherits the best of its components, and often outperforms both.
@inproceedings{ijcai2016p441,
title = {Decoupled Strong Stubborn Sets},
author = {Gnad, Daniel and Wehrle, Martin 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 = {3110--3115},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/441},
}
TY - CPAPER TI - Decoupled Strong Stubborn Sets AU - Gnad, Daniel AU - Wehrle, Martin 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 - 3110 EP - 3115 UR - https://ijcai.org/proceedings/2016/441 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
