Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-26439
Titel: | What’s in it for my BDD? On causal graphs and variable orders in planning |
VerfasserIn: | Kissmann, Peter Hoffmann, Jörg |
Sprache: | Englisch |
Erscheinungsjahr: | 2013 |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Forschungsbericht (Report zu Forschungsprojekten) |
Abstract: | One decisive factor for the success of symbolic search using BDDs is whether or not the variable ordering is good. A general intuition is that smaller BDDs result if inter-dependent variables are close together. The most common means to capture variable dependencies in planning are causal graphs, and consequently previous work defined variable orders based on these. Starting from the observation that the two concepts of “dependency” are actually quite different, we introduce a framework for assessing the strength of variable ordering heuristics in sub-classes of planning. It turns out that causal graph based variable orders may be exponentially worse than optimal even for very simple planning tasks. Experiments with a broad range of such variable ordering variants indicate that they are mediocre at best. |
Link zu diesem Datensatz: | urn:nbn:de:bsz:291-scidok-51939 hdl:20.500.11880/26495 http://dx.doi.org/10.22028/D291-26439 |
Schriftenreihe: | Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes |
Band: | 2013/01 |
Datum des Eintrags: | 2-Apr-2013 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Informatik |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
fb14_2013_01.pdf | 343,43 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.