Please use this identifier to cite or link to this item:
doi:10.22028/D291-26439
Title: | What’s in it for my BDD? On causal graphs and variable orders in planning |
Author(s): | Kissmann, Peter Hoffmann, Jörg |
Language: | English |
Year of Publication: | 2013 |
DDC notations: | 004 Computer science, internet |
Publikation type: | Report |
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 to this record: | urn:nbn:de:bsz:291-scidok-51939 hdl:20.500.11880/26495 http://dx.doi.org/10.22028/D291-26439 |
Series name: | Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes |
Series volume: | 2013/01 |
Date of registration: | 2-Apr-2013 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
fb14_2013_01.pdf | 343,43 kB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.