Μάθημα : Ανακοινώσεις Τμήματος Πληροφορικής ΟΠΑ

Μέρα/Ώρα: Πέμπτη 18/6, ώρα 11:00

Τόπος: T105, Κτήριο Τροίας

Διαδικτυακή παρακολούθηση μέσω Teams:

Eduard Eiben talk | Meeting-Join | Microsoft Teams

Title: Coordinated Motion Planning is FPT on Discretized Simple Polygons

Abstract: 

In the coordinated motion planning problem, we are given a graph together with the starting and destination vertices of k robots. At each time step, any subset of robots may move, each traversing an edge of the graph, provided that no two robots collide. The goal is to compute a schedule that routes all robots to their destinations while minimizing some objective function. In this talk, we focus on the well-studied objective of minimizing the total travel length of all robots. This problem is known to be NP-hard, and it has been shown to be fixed-parameter tractable (FPT), when parameterized by the number k of robots, on full grids (SoCG 2023) and on bounded-treewidth graphs (ICALP 2024).

We present a fixed-parameter algorithm for coordinated motion planning, parameterized by the number k of robots, on graphs arising from discretizations of simple polygons. Such graphs are of particular interest in real-world applications, where planar motion is often constrained to discretized representations of polygonal environments. Moreover, these graphs generalize rectangular grids; consequently, our result constitutes a significant step toward resolving the parameterized complexity of coordinated motion planning on subgrids and, ultimately, planar graphs -- two prominent open problems in the field.

Short Bio: 

Eduard Eiben is a Lecturer (Assistant Professor) in Computer Science at Royal Holloway, University of London. He received his PhD at TU Wien, Vienna, Austria, under the supervision of Stefan Szeider and Robert Ganian. His research focuses on applying the Parameterized Algorithms and Complexity paradigm to a variety of research topics and problems, including multi-agent pathfinding, fair division, graph theory, and temporal graphs.