Publikationen

Vollständige Liste der Publikationen

Aktuelle Veröffentlichungen (letzte 12 Monate):

(Alle Abstracts einblenden) (Alle Abstracts ausblenden)

Pascal Bachor, Rolf-David Bergdoll und Bernhard Nebel.
The Multi-Agent Transportation Problem.
In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023). 2023.
(Abstract einblenden) (Abstract ausblenden)

We introduce the multi-agent transportation (MAT) problem, where agents have to transport containers from their starting positions to their designated goal positions. Movement takes place in a common environment where collisions between agents and between containers must be avoided. In contrast to other frameworks such as MAPF or MAPD, the agents are allowed to separate from the containers at any time, which allows for plans in scenarios that might otherwise be unsolvable and has the potential to reduce the makespan. We present a complexity analysis establishing NP-completeness and show how the problem can be reduced to a sequence of SAT problems when optimizing for makespan. Finally, the implementation is empirically evaluated relative to input characteristics, and it is compared to some variants of the MAT problem and a CBS-based MAPD implementation.
David Speck und Jendrik Seipp.
New Refinement Strategies for Cartesian Abstractions.
In Proceedings of the 32nd International Conference on Automated Planning and Scheduling (ICAPS 2022). 2022.
(Abstract einblenden) (Abstract ausblenden) (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 und David Speck.
Loopless Top-k Planning.
In Proceedings of the 32nd International Conference on Automated Planning and Scheduling (ICAPS 2022). 2022.
(Abstract einblenden) (Abstract ausblenden) (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.
(Abstract einblenden) (Abstract ausblenden) (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 und Marcel Steinmetz.
Expressivity of Planning with Horn Description Logic Ontologies.
In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI 2022). 2022.
(Abstract einblenden) (Abstract ausblenden) (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.