The relative pruning power of strong stubborn sets and expansion core

Wehrle, Martin and Helmert, Malte and Alkhazraji, Yusra and Mattmüller, Robert. (2013) The relative pruning power of strong stubborn sets and expansion core. In: Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013) : [held 10 - 14 June 2013 in Rome, Italy]. Palo Alto, Calif., pp. 251-259.

PDF - Published Version

Official URL: http://edoc.unibas.ch/dok/A6212198

Downloads: Statistics Overview


In the last years, pruning techniques based on partial order reduction have found increasing attention in the planning community. One recent result is that the expansion core method is a special case of the strong stubborn sets method proposed in model checking. However, it is still an open question if there exist efficiently computable strong stubborn sets with strictly higher pruning power than expansion core. In this paper, we prove that the pruning power of strong stubborn sets is strictly higher than the pruning power of expansion core even for a straight-forward instantiation of strong stubborn sets. This instantiation is as efficiently computable as expansion core. Hence, our theoretical results suggest that strong stubborn sets should be preferred to expansion core. Our empirical evaluation on all optimal benchmarks from the international planning competitions up to 2011 supports the theoretical results.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Wehrle, Martin and Helmert, Malte
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
edoc DOI:
Last Modified:20 Nov 2018 09:42
Deposited On:23 May 2014 08:34

Repository Staff Only: item control page