-
Bernhard Nebel.
The Computational Complexity of Multi-Agent Pathfinding on Directed Graphs.
Artificial Intelligence. 2024.
(Show abstract)
(Hide abstract)
(Preprint; PDF)
(Online; DOI)
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.
-
Moritz Graf, Thorsten Engesser and Bernhard Nebel.
A Symbolic Sequential Equilibria Solver for Game Theory Explorer (Demo Track).
In
Proceedings of the 23rd Int. Joint Conf. on Autonomous Agents and Multiagent Systems
(AAMAS 2024).
2024.
(Show abstract)
(Hide abstract)
We present the first implemented symbolic solver for sequential equilibria in general finite imperfect information games.
-
Moritz Graf, Thorsten Engesser and Bernhard Nebel.
Symbolic Computation of Sequential Equilibria.
In
Proceedings of the 23rd Int. Joint Conf. on Autonomous Agents and Multiagent Systems
(AAMAS 2024).
2024.
(Show abstract)
(Hide abstract)
The sequential equilibrium is a standard solution concept for extensive-form games with imperfect information that includes an explicit representation of the players' beliefs. An assessment consisting of a strategy and a belief is a sequential equilibrium if it satisfies the properties of sequential rationality and consistency.
Our main result is that both properties together can be written as a finite set of polynomial equations and inequalities. The solutions to this system are exactly the sequential equilibria of the game. We construct this system explicitly and describe an implementation that solves it using cylindrical algebraic decomposition. To write consistency as a finite system of equations, we need to compute the extreme directions of a set of polyhedral cones. We propose a modified version of the double description method, optimized for this specific purpose. To the best of our knowledge, our implementation is the first to symbolically solve general finite imperfect information games for sequential equilibria.
-
Stefano Ardizzoni, Irene Saccani, Luca Consolini, Marco Locatelli and Bernhard Nebel.
An Algorithm with Improved Complexity for Pebble Motion/Multi-Agent Path Finding on Trees.
Journal of Artificial Intelligence Research 79. 2024.
(Show abstract)
(Hide abstract)
(Online; DOI)
The pebble motion on trees (PMT) problem consists in finding a feasible sequence of moves that repositions a set of pebbles to assigned target vertices. This problem has been widely studied because, in many cases, the more general Multi-Agent path finding (MAPF) problem on graphs can be reduced to PMT. We propose a simple and easy to implement procedure, which finds solutions of length O(|P|nc + n2), where n is the number of nodes, P is the set of pebbles, and c the maximum length of corridors in the tree. This complexity result is more detailed than the current best known result O(n3), which is equal to our result in the worst case, but does not capture the dependency on c and |P|.
-
Vaishak Belle, Thomas Bolander, Andreas Herzig and Bernhard Nebel.
Epistemic planning: Perspectives on the special issue.
Artificial Intelligence 316, p. 103842. 2023.
(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.