Efficient Planning with State-Dependent Action Costs

• Applicant: Dr. Robert Mattmüller
• Subject Area: Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: from 2018 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 405834399

• Final Report Year: 2022

Final Report Abstract

Planning is the art and practice of thinking before acting and is a central subfield of Artificial Intelligence. In classical planning, the objective is to derive a course of actions that allows an intelligent agent to move from any situation it finds itself in to one that satisfies its goals. In practice, some properties of a planning problem require an expressive extension of the standard classical planning formalism to capture and model them, e.g., the cost of actions, which often depends on the state in which the actions are applied. While in probabilistic planning and other planning formalisms a concise encoding of action costs or rewards has long been standard, in classical planning it is common to consider a potentially exponentially larger representation with constant action costs. With the DFG-funded project EPSDAC, we aimed to close this gap by investigating planning with state-dependent costs and developing efficient methods for generating action plans considering such action cost functions. In the course of the project, we established a comprehensive classification of compilability and non-compilability of state-dependent action costs for combinations of action cost functions and possible cost measures for the compilations showing that it can be helpful or even necessary not to compile them away but to leave them in the model and support them natively in algorithms. Considering this theoretical result, we have investigated when and how complex action cost functions can occur, with the result that in practice derived predicates often yield such complex cost functions. In addition, we empirically investigated the effects of considering or ignoring statedependent action costs, with the result that solution quality strongly depends on the domain. Considering state-dependent costs, we introduced subset-saturated transition cost partitioning, where costs are directly assigned to transitions and are thus statedependent. The resulting heuristics are empirically more informative than other cost partitioned heuristics. Finally, we developed and established symbolic search based on decision diagrams as a state-of-the-art technique for planning with state-dependent action costs. The project was a resounding success in terms of scientific output, with 13 peer-reviewed publications at high-level international conferences , 4 peer-reviewed workshop publications, and 3 pending patents resulting from work on the project topics by the principal investigator’s research group.

Publications

• An Empirical Study of the Usefulness of State-Dependent Action Costs in Planning. Lecture Notes in Computer Science, 123-130. Springer International Publishing.
  Corraya, Sumitra; Geißer, Florian; Speck, David & Mattmüller, Robert
  
• Symbolic Planning with Axioms. Proceedings of the International Conference on Automated Planning and Scheduling, 29, 464-472.
  Speck, David; Geißer, Florian; Mattmüller, Robert & Torralba, Álvaro
  
• Symbolic Top-k Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06), 9967-9974.
  Speck, David; Mattmüller, Robert & Nebel, Bernhard
  
• When Perfect Is Not Good Enough: On the Search Behaviour of Symbolic Heuristic Search. Proceedings of the International Conference on Automated Planning and Scheduling, 30, 263-271.
  Speck, David; Geißer, Florian & Mattmüller, Robert
  
• Learning Heuristic Selection with Dynamic Algorithm Configuration. Proceedings of the International Conference on Automated Planning and Scheduling, 31, 597-605.
  Speck, David; Biedenkapp, André; Hutter, Frank; Mattmüller, Robert & Lindauer, Marius
  
• On the Compilability and Expressive Power of State-Dependent Action Costs. Proceedings of the International Conference on Automated Planning and Scheduling, 31, 358-366.
  Speck, David; Borukhson, David; Mattmüller, Robert & Nebel, Bernhard
  
• Subset-Saturated Transition Cost Partitioning. Proceedings of the International Conference on Automated Planning and Scheduling, 31, 131-139.
  Drexler, Dominik; Seipp, Jendrik & Speck, David
  
• Symbolic Search for Optimal Total-Order HTN Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 11744-11754.
  Behnke, Gregor & Speck, David
  
• Symbolic Search for Oversubscription Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 11972-11980.
  Speck, David & Katz, Michael
  
• Trial-Based Heuristic Tree Search for MDPs with Factored Action Spaces. Proceedings of the International Symposium on Combinatorial Search, 11(1), 38-47.
  Geißer, Florian; Speck, David & Keller, Thomas