Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-38039
Titel: | Strong Stubborn Set Pruning for Star-Topology Decoupled State Space Search |
VerfasserIn: | Gnad, Daniel Hoffmann, Jörg Wehrle, Martin |
Sprache: | Englisch |
Titel: | Journal of Artificial Intelligence Research |
Bandnummer: | 65 |
Verlag/Plattform: | JAIR |
Erscheinungsjahr: | 2019 |
Freie Schlagwörter: | planning heuristics problem solving search |
DDC-Sachgruppe: | 500 Naturwissenschaften |
Dokumenttyp: | Journalartikel / Zeitschriftenartikel |
Abstract: | Analyzing reachability in large discrete transition systems is an important sub-problem in several areas of AI, and of CS in general. State space search is a basic method for conducting such an analysis. A wealth of techniques have been proposed to reduce the search space without affecting the existence of (optimal) solution paths. In particular, strong stubborn set (SSS) pruning is a prominent such method, analyzing action dependencies to prune commutative parts of the search space. We herein show how to apply this idea to star-topology decoupled state space search, a recent search reformulation method invented in the context of classical AI planning. Star-topology decoupled state space search, short decoupled search, addresses planning tasks where a single center component interacts with several leaf components. The search exploits a form of conditional independence arising in this setting: given a fixed path p of transitions by the center, the possible leaf moves compliant with p are independent across the leaves. Decoupled search thus searches over center paths only, maintaining the compliant paths for each leaf separately. This avoids the enumeration of combined states across leaves. Just like standard search, decoupled search is adversely affected by commutative parts of its search space. The adaptation of strong stubborn set pruning is challenging due to the more complex structure of the search space, and the resulting ways in which action dependencies may affect the search. We spell out how to address this challenge, designing optimality-preserving decoupled strong stubborn set (DSSS) pruning methods. We introduce a design for star topologies in full generality, as well as simpler design variants for the practically relevant fork and inverted fork special cases. We show that there are cases where DSSS pruning is exponentially more effective than both, decoupled search and SSS pruning, exhibiting true synergy where the whole is more than the sum of its parts. Empirically, DSSS pruning reliably inherits the best of its components, and sometimes outperforms both. |
DOI der Erstveröffentlichung: | 10.1613/jair.1.11576 |
URL der Erstveröffentlichung: | https://jair.org/index.php/jair/article/view/11576 |
Link zu diesem Datensatz: | urn:nbn:de:bsz:291--ds-380395 hdl:20.500.11880/34374 http://dx.doi.org/10.22028/D291-38039 |
ISSN: | 1076-9757 |
Datum des Eintrags: | 16-Nov-2022 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Informatik |
Professur: | MI - Prof. Dr. Jörg Hoffmann |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
sminton,+Journal+manager,+11576-Article+(PDF)-21690-1-11-20190701.pdf | 517,35 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.