Hamilton Institute Seminar

Wednesday, October 5, 2022 - 13:00 to 14:00

Passcode: 279596

Speaker: Professor Irina Kostitsyna, TU Eindhoven

Title: "Unlabeled multi-robot motion planning for disc robots"

Abstract: In this talk I will discuss the unlabeled motion-planning problem for unit-disc robots. The goal of the problem is to find a motion plan that moves the robots from their start positions to a given set of target positions. For
the unlabeled variant, it does not matter which robot reaches which target position as long as all target positions are occupied in the end.

If the workspace has narrow passages such that the robots cannot fit through them, then the free configuration space, representing all possible unobstructed positions of the robots, will consist of multiple connected components. Even if in each component of the free space the number of targets matches the number of start positions, the unlabeled multi-robot motion planning problem does not always have a solution when the robots and their targets are positioned very densely. In this talk, I will show tight bounds on how much separation between start and target positions
is necessary for a solution to exist, and will present an algorithm to find such a solution.

Bio: Irina Kostitsyna is an assistant professor in the Department of Mathematics and Computer Science at TU Eindhoven in the Netherlands. Her research interests lie in the field of computational geometry, both in its theoretical and applied aspects. In particular, her main topics of research include geometric algorithms for mobile agents, including path planning and routing; and for programmable matter, including shape reconfiguration problems.

Irina received her BSc and MSc in Applied Physics and Mathematics from Moscow Institute of Physics and Technology, and her PhD in Computer Science from Stony Brook University. After that, Irina spent two years as a postdoc in TU Eindhoven, and one year as a postdoc in Université libre de Bruxelles. In 2017 she returned to TU Eindhoven as an assistant professor.