Publications

Complete list of publications

Recent publications (last 12 months):

(Show all abstracts) (Hide all abstracts)

David Speck and Jendrik Seipp.
New Refinement Strategies for Cartesian Abstractions.
In Proceedings of the 32nd International Conference on Automated Planning and Scheduling (ICAPS 2022). 2022.
(Show abstract) (Hide abstract) (PDF)

Cartesian counterexample-guided abstraction refinement (CEGAR) yields strong heuristics for optimal classical planning. CEGAR repeatedly finds counterexamples, i.e., abstract plans that fail for the concrete task. Although there are usually many such abstract plans to choose from, the refinement strategy from previous work is to choose an arbitrary optimal one. In this work, we show that an informed refinement strategy is critical in theory and practice. We demonstrate that it is possible to execute all optimal abstract plans in the concrete task simultaneously, and present methods to minimize the time and number of refinement steps until we find a concrete solution. The resulting algorithm solves more tasks than the previous state of the art for Cartesian CEGAR, both during refinement and when used as a heuristic in an A* search.
Julian von Tschammer, Robert Mattmüller and David Speck.
Loopless Top-k Planning.
In Proceedings of the 32nd International Conference on Automated Planning and Scheduling (ICAPS 2022). 2022.
(Show abstract) (Hide abstract) (PDF)

In top-k planning, the objective is to determine a set of k cheapest plans that provide several good alternatives to choose from. Such a solution set often contains plans that visit at least one state more than once. Depending on the application, plans with such loops are of little importance because they are dominated by a loopless representative and can prevent more meaningful plans from being found.

In this paper, we motivate and introduce loopless top-k planning. We show how to enhance the state-of-the-art symbolic top-k planner, symK, to obtain an efficient, sound and complete algorithm for loopless top-k planning. An empirical evaluation shows that our proposed approach has a higher k-coverage than a generate-and-test approach that uses an ordinary top-k planner, which we show to be incomplete in the presence of zero-cost loops.
David Speck.
Symbolic Search for Optimal Planning with Expressive Extensions.
FreiDok plus 2022.
PhD Thesis.
(Show abstract) (Hide abstract) (PDF)

In classical planning, the goal 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. Classical planning is considered domain-independent, i.e., it is not limited to a particular application and can be used to solve different types of reasoning problems. In practice, however, some properties of a planning problem at hand require an expressive extension of the standard classical planning formalism to capture and model them. Although the importance of many of these extensions is well known, most planners, especially optimal planners, do not support these extended planning formalisms. The lack of support not only limits the use of these planners for certain problems, but even if it is possible to model the problems without these extensions, it often leads to increased effort in modeling or makes modeling practically impossible as the required problem encoding size increases exponentially.

In this thesis, we propose to use symbolic search for cost-optimal planning for different expressive extensions of classical planning, all capturing different aspects of the problem. In particular, we study planning with axioms, planning with state- dependent action costs, oversubscription planning, and top-k planning. For all formalisms, we present complexity and compilability results, highlighting that it is desirable and even necessary to natively support the corresponding features. We analyze symbolic heuristic search and show that the search performance does not always benefit from the use of a heuristic and that the search performance can exponentially deteriorate even under the best possible circumstances, namely the perfect heuristic. This reinforces that symbolic blind search is the dominant symbolic search strategy nowadays, on par with other state-of-the-art cost-optimal planning strategies. Based on this observation and the lack of good heuristics for planning formalisms with expressive extensions, symbolic search turns out to be a strong approach. We introduce symbolic search to support each of the formalisms individually and in combination, resulting in optimal, sound, and complete planning algorithms that empirically compare favorably with other approaches.
Stefan Borgwardt, Jörg Hoffmann, Alisa Kovtunova, Markus Krötzsch, Bernhard Nebel and Marcel Steinmetz.
Expressivity of Planning with Horn Description Logic Ontologies.
In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI 2022). 2022.
(Show abstract) (Hide abstract) (Online; PDF)

State constraints in AI Planning globally restrict the legal environment states. Standard planning languages make closed-domain and closed-world assumptions. Here we address open-world state constraints formalized by planning over a description logic (DL) ontology. Previously, this combination of DL and planning has been investigated for the light-weight DL DL-Lite. Here we propose a novel compilation scheme into standard PDDL with derived predicates, which applies to more expressive DLs and is based on the rewritability of DL queries into Datalog with stratified negation. We also provide a new rewritability result for the DL Horn-ALCHOIQ, which allows us to apply our compilation scheme to quite expressive ontologies. In contrast, we show that in the slight extension Horn-SROIQ no such compilation is possible unless the weak exponential hierarchy collapses. Finally, we show that our approach can outperform previous work on existing benchmarks for planning with DL ontologies, and is feasible on new benchmarks taking advantage of more expressive ontologies.
Roman Barták, Simona Ondrčková, Gregor Behnke and Pascal Bercher.
Correcting Hierarchical Plans by Action Deletion.
In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning (KR-2021). 2021.
(PDF)
Roman Barták, Simona Ondrčková, Gregor Behnke and Pascal Bercher.
Correcting Hierarchical Plans by Action Deletion.
In Proceedings of the Fourth ICAPS Workshop on Hierarchical Planning. 2021.
(PDF)
Roman Barták, Simona Ondrčková, Gregor Behnke and Pascal Bercher.
On the Verification of Totally-Ordered HTN Plans.
In Proceedings of the Fourth ICAPS Workshop on Hierarchical Planning, pp. 44-48. 2021.
(PDF)
Daniel Höller, Julia Whichlacz, Pascal Bercher and Gregor Behnke.
Compiling HTN Plan Verification Problems into HTN Planning Problems.
In Proceedings of the Fourth ICAPS Workshop on Hierarchical Planning, pp. 8-15. 2021.
(PDF)