An Analysis of Merge Strategies for Merge-and-Shrink Heuristics. Sievers, S., Wehrle, M., & Helmert, M. In
An Analysis of Merge Strategies for Merge-and-Shrink Heuristics [link]Paper  abstract   bibtex   
The merge-and-shrink framework provides a powerful basis for the computation of admissible planning heuristics. Recently, it has been shown theoretically that non-linear strategies are strictly more powerful than linear ones, and several non-linear strategies have been proposed and implemented. However, it is still unclear what makes up for a "good" merge strategy, and in particular, how much of the theoretical potential of non-linear strategies is actually exploited by the existing ones. In this paper, we address these questions on the accuracy of existing merge strategies. We provide an extensive experimental analysis, suggesting that there is still room for large improvements. Finally, we present a simple non-linear strategy that considerably improves over the efficiency of the existing merge strategies.
@inproceedings {icaps16-118,
    track    = {​Main Track},
    title    = {An Analysis of Merge Strategies for Merge-and-Shrink Heuristics},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13148},
    author   = {Silvan Sievers and  Martin Wehrle and  Malte Helmert},
    abstract = {The merge-and-shrink framework provides a powerful basis for the
computation of admissible planning heuristics. Recently, it has been
shown theoretically that non-linear strategies are strictly more
powerful than linear ones, and several non-linear strategies have
been proposed and implemented. However, it is still unclear what
makes up for a "good" merge strategy, and in particular, how much
of the theoretical potential of non-linear strategies is actually
exploited by the existing ones. In this paper, we address these
questions on the accuracy of existing merge strategies. We provide
an extensive experimental analysis, suggesting that there is still
room for large improvements. Finally, we present a simple non-linear
strategy that considerably improves over the efficiency of the
existing merge strategies.},
    keywords = {Classical planning,Search techniques}
}

Downloads: 0