Bernhard Nebel |
PosterID:
43
PDF
Slides
Poster
BibTeX
|
| The determination of the computational complexity of multi-agent pathfinding on directed graphs has been an open problem for many years. For undirected graphs, solvability can be decided in polynomial time, as has been shown already in the eighties. Further, recently it has been shown that a special case on directed graphs is solvable in polynomial time. In this paper, we show that the problem is NP-hard in the general case. In addition, some upper bounds are proven. | |
| Canb | 10/28/2020, 17:00 – 18:00 |
| 10/30/2020, 00:00 – 01:00 |
| Paris | 10/28/2020, 07:00 – 08:00 |
| 10/29/2020, 14:00 – 15:00 |
| NYC | 10/28/2020, 02:00 – 03:00 |
| 10/29/2020, 09:00 – 10:00 |
| LA | 10/27/2020, 23:00 – 00:00 |
| 10/29/2020, 06:00 – 07:00 |
On timeline-based games and their complexity
Nicola Gigante, Angelo Montanari, Andrea Orlandini, Marta Cialdea Mayer, Mark Reynolds
On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs
Bernhard Nebel
Dynamic Controllability and (J,K)-Resiliency in Generalized Constraint Networks with Uncertainty
Matteo Zavatteri, Romeo Rizzi, Tiziano Villa
Search-Guidance Mechanisms for Numeric Planning Through Subgoaling Relaxation
Enrico Scala, Alessandro Saetti, Ivan Serina, Alfonso E. Gerevini