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/2024/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  <p>Abstract:<br>\
 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.</p>\n
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