• English
• Deutsch

• University of Freiburg
• Faculty of Engineering
• Department of Computer Science

Publications

Complete list of publications

• sorted by year of publication
• sorted by author
• sorted by area

Recent publications (last 12 months):

(Show all abstracts) (Hide all abstracts)

• 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|.

• Contact Legal Information