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
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 SizeFormat 
fb14_2013_01.pdf343,43 kBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.