Decoupled Strong Stubborn Sets
Daniel Gnad, Martin Wehrle, Jörg Hoffmann · edoc (University of Basel) · 2016
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 bench- marks. 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. Empiri- cally, the combination reliably inherits the best of its components, and often outperforms both.