-
Bernhard Nebel.
The Computational Complexity of Multi-Agent Pathfinding on Directed Graphs.
Artificial Intelligence. 2023.
Accpeted for publication.
(Show abstract)
(Hide abstract)
(Preprint; PDF)
While the non-optimizing variant of multi-agent pathfinding on undirected graphs is known to be a polynomial-time problem since almost forty years, a similar result has not been established for directed graphs. In this paper, it will be shown that this problem is NP-complete. For strongly connected directed graphs, however, the problem is polynomial. And both of these results hold even if one allows for synchronous rotations on fully occupied cycles. Interestingly, the results apply also to the so-called motion planning feasibility problem on directed graphs.
-
Bernhard Nebel.
The Small Solution Hypothesis for MAPF on Strongly Connected Directed Graphs Is True.
In
Proceedings of the 33rd International Conference on Automated Planning and Scheduling (ICAPS 2023), pp. 304-313.
2023.
(Show abstract)
(Hide abstract)
(Online; DOI)
The determination of the computational complexity of multi-agent pathfinding on directed graphs has been an open problem for many years. Only recently, it has been established that the problem is NP-hard. Further, it has been proved that it is in NP, provided the short solution hypothesis for strongly connected digraphs holds. In this paper, it is shown that this hypothesis is indeed true, even when one allows for synchronous rotations.
-
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), pp. 11525-11532.
2023.
(Show abstract)
(Hide abstract)
(Online; DOI)
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.
