On planning with state-dependent action costs

Abstract: Automated Planning is an established research field of Artificial Intelligence. While in probabilistic planning models, such as Stochastic Shortest Path problems, the cost of an action can be state-dependent, the classical deterministic planning literature mostly considers the cost of actions to be constant. Therefore, even if a planning task naturally admits state-dependent costs, the modeler has to distribute these costs over multiple copies of the action. This does not only introduce additional burden on the modeler, but it also hides structure which may be apparent in the action cost function and may provide useful information for planning algorithms.

In this thesis we do away this restriction to constant costs, by considering classical planning with state-dependent action costs. We show how we can make use of edge-valued multi-valued decision diagrams (EVMDDs) to represent the action cost functions and provide compilations of state-dependent action cost tasks to classical tasks with constant costs, which allows us to leverage classical planning tools. These compilations are polynomial in the size of the underlying EVMDDs.
While their size is worst-case exponential, for many commonly encountered cost functions this results in a classical planning task with compact size.

Heuristic search is one of the most prominent tools in classical planning to produce optimal solutions. Two well-known families of heuristics are delete relaxation and abstraction heuristics.
We generalize both families to planning with state-dependent action costs and show how we can use the EVMDD representation to efficiently compute the generalized heuristics. Furthermore, we provide a theoretical analysis of our introduced compilations, showing that many heuristics are invariant under compilation, i.e. the compilation preserves the heuristic estimates and does not lead to a loss of information. We empirically evaluate how these theoretical results behave in practice, by comparing different compilations and heuristics on a benchmark set consisting of tasks with state-dependent action costs

Angaben zum Objekt

• Standort: Deutsche Nationalbibliothek Frankfurt am Main
• Umfang: Online-Ressource
• Sprache: Englisch
• Anmerkungen: Universität Freiburg, Dissertation, 2018

Klassifikation und Themen

• Schlagwort: Planning ; Automatische Handlungsplanung ; Künstliche Intelligenz ; Entscheidungsgraph

Beteiligte, Orts- und Zeitangaben

• Ereignis: Veröffentlichung
• (wo): Freiburg
• (wer): Universität
• (wann): 2019
• Urheber: Geißer, Florian
• Beteiligte Personen und Organisationen: Nebel, Bernhard ; Albert-Ludwigs-Universität Freiburg. Fakultät für Angewandte Wissenschaften

Weitere Informationen

• DOI: 10.6094/UNIFR/149749
• URN: urn:nbn:de:bsz:25-freidok-1497495
• Rechteinformation: Der Zugriff auf das Objekt ist unbeschränkt möglich.
• Letzte Aktualisierung: 25.03.2025, 13:44 MEZ