Abstractions for Planning with State-Dependent Action Costs. Geißer, F., Keller, T., & Mattmüller, R. In
Abstractions for Planning with State-Dependent Action Costs [link]Paper  abstract   bibtex   
Extending the classical planning formalism with state-dependent action costs (SDAC) allows an up to exponentially more compact task encoding. Recent work proposed to use edge-valued multi-valued decision diagrams (EVMDDs) to represent cost functions, which allow to automatically detect and exhibit structure in cost functions and to make heuristic estimators accurately reflect SDAC. However, so far only the inadmissible additive heuristic has been considered in this context. In this paper, we define informative admissible abstraction heuristics, which enable optimal planning with SDAC. We discuss how abstract cost values can be extracted from EVMDDs representing concrete cost functions. Our theoretical analysis shows that this is efficiently possible for abstractions that are Cartesian or coarser. We adapt counterexample-guided abstraction refinement approaches to derive such abstractions. An empirical evaluation of the resulting heuristics shows that highly accurate values can be computed quickly.
@inproceedings {icaps16-129,
    track    = {​Main Track},
    title    = {Abstractions for Planning with State-Dependent Action Costs},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13028},
    author   = {Florian Geißer and  Thomas Keller and  Robert Mattmüller},
    abstract = {Extending the classical planning formalism with state-dependent action costs (SDAC) allows an up to exponentially more compact task encoding. Recent work proposed to use edge-valued multi-valued decision diagrams (EVMDDs) to represent cost functions, which allow to automatically detect and exhibit structure in cost functions and to make heuristic estimators accurately reflect SDAC. However, so far only the inadmissible additive heuristic has been considered in this context. In this paper, we define informative admissible abstraction heuristics, which enable optimal planning with SDAC. We discuss how abstract cost values can be
extracted from EVMDDs representing concrete cost functions. Our theoretical analysis shows that this is efficiently possible for abstractions that are Cartesian or coarser. We adapt counterexample-guided abstraction refinement approaches to derive such abstractions. An empirical evaluation of the resulting heuristics shows that highly accurate values can be computed quickly.},
    keywords = {Classical planning}
}
Downloads: 0