-
Pascal Bachor, Rolf-David Bergdoll and Bernhard Nebel.
The Multi-Agent Transportation Problem.
In
Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023).
2023.
(Show abstract)
(Hide abstract)
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.
-
Vaishak Belle, Thomas Bolander, Andreas Herzig and Bernhard Nebel.
Epistemic planning: Perspectives on the special issue.
Artificial Intelligence. 2022.
(Show abstract)
(Hide abstract)
(Online; DOI)
Epistemic planning is the enrichment of automated planning with epistemic notions such as knowledge and belief. In general, single-agent epistemic planning considers the following problem: given an agent's current state of knowledge, and a desirable state of knowledge, how does it get from one to the other? In multi-agent epistemic planning, the current and desirable states of knowledge might also refer to the states of knowledge of other agents, including higher-order knowledge like ensuring that agent A doesn't get to know that agent B knows P. Single-agent epistemic planning is of central importance in settings where agents need to be able to reason about their own lack of knowledge and, e.g., make plans of how to achieve the required knowledge. Multi-agent epistemic planning is essential for coordination and collaboration among multiple agents, where success can only be expected if agents are able to reason about the knowledge, uncertainty and capabilities of other agents. It is a relatively recent area of research involving several sub-areas of artificial intelligence, such as automated planning, decision-theoretic planning, epistemic logic, strategic reasoning and knowledge representation and reasoning. In
order to achieve formalisms and systems for epistemic planning that are both expressive and practically efficient, it is necessary to combine state of the art from several such sub-areas of artificial intelligence that have so far been considered mostly in separation. Application areas of epistemic planning include mobile service robots, explaining planning, game playing, human-robot interaction and social robotics. For this special issue of AIJ, we invited papers on theory, applications, and implemented systems of epistemic planning. In this document, we summarize the accepted papers whilst recapping the essentials of epistemic planning.
-
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.
