Abstractions for Planning with State-Dependent Action Costs

Geißer, Florian and Keller, Thomas and Mattmüller , Robert. (2016) Abstractions for Planning with State-Dependent Action Costs. In: Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling (ICAPS 2016). pp. 140-148.

PDF - Published Version

Official URL: http://edoc.unibas.ch/45222/

Downloads: Statistics Overview


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 allows 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 that represent concrete cost functions without adjusting them to the selected abstraction. Our theoretical analysis shows that this is efficiently possible for abstractions that are Cartesian or coarser. We adapt the counterexample-guided abstraction refinement approach to derive such abstractions. An empirical evaluation of the resulting heuristic shows that highly accurate values can be computed quickly.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Keller, Thomas
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
edoc DOI:
Last Modified:02 Oct 2017 13:17
Deposited On:02 Oct 2017 13:10

Repository Staff Only: item control page