BEGIN:VCALENDAR
VERSION:2.0
PRODID:ILLC Website
X-WR-TIMEZONE:Europe/Amsterdam
BEGIN:VTIMEZONE
TZID:Europe/Amsterdam
X-LIC-LOCATION:Europe/Amsterdam
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:/NewsandEvents/Archives/current/newsitem/14762
/14-June-2024-FOAM-Seminar-Bernhard-Nebel
DTSTAMP:20240212T142507
SUMMARY:FOAM Seminar, Bernhard Nebel
ATTENDEE;ROLE=Speaker:Bernhard Nebel (Freiburg)
DTSTART;TZID=Europe/Amsterdam:20240614T150000
DTEND;TZID=Europe/Amsterdam:20240614T161500
LOCATION:Room L3.33, ILLC Lab42, Science Park 900,
Amsterdam
DESCRIPTION:Abstract: “Multi-agent pathfinding”,
also called “pebble motion on graphs” or “cooperat
ive pathfinding”, is the problem of deciding the e
xistence of or generating a collision-free movemen
t plan for a set of agents moving on a graph. Whil
e the non-optimizing variant of multi-agent pathfi
nding on undirected graphs is known to be a polyno
mial-time problem since forty years, a similar res
ult for directed graphs was missing. In the talk,
it will be shown that this problem is NP-complete.
For strongly connected directed graphs, however,
the problem is polynomial. And both of these resul
ts hold even if one allows for synchronous rotatio
ns on fully occupied cycles.
X-ALT-DESC;FMTTYPE=text/html:\n Abstract:

\
n “Multi-agent pathfinding”, also called “pebble
motion on graphs” or “cooperative pathfinding”, is
the problem of deciding the existence of or gener
ating a collision-free movement plan for a set of
agents moving on a graph. While the non-optimizing
variant of multi-agent pathfinding on undirected
graphs is known to be a polynomial-time problem si
nce forty years, a similar result for directed gra
phs was missing. In the talk, it will be shown tha
t this problem is NP-complete. For strongly connec
ted directed graphs, however, the problem is polyn
omial. And both of these results hold even if one
allows for synchronous rotations on fully occupied
cycles.

URL:https://events.illc.uva.nl/FOAM/posts/talk15/
CONTACT:Gregor Behnke at g.behnke at uva.nl
CONTACT:Ronald de Haan at r.dehaan at uva.nl
END:VEVENT
END:VCALENDAR