1)11/6/2026

WHO: Omrit Filtser, Open University of Israel 

WHEN: Thursday, June 11th, 2026 at 12:00

WHERE: BUILDING 503 (Computer Science), AUDITORIUM

Title:  Multi-Robot Motion Planning: A Computational Geometry Perspective

Abstract: 

Multi-robot motion planning (MRMP) is a classical problem in computational geometry, in which a set of robots operate in a common workspace and must move from a given set of start positions to a given set of target positions. MRMP and its many variants have been widely investigated from both theoretical and practical perspectives, and are generally PSPACE-hard. Interestingly, however, the separation between robots plays a key role in the complexity of the problem: polynomial-time algorithms exist under some assumptions on the distance between the start and target positions. Moreover, when robots are also sufficiently separated from the obstacles in the workspace, polynomial-time algorithms with optimality guarantees can also be obtained. In this talk, I will survey recent advances in the area and present algorithms that provide trade-offs between the different separation assumptions.
Based on a Joint work with Tsuri Farhana and Shalev Goldshtein.

Short bio:
Omrit is a faculty member at the Department of Mathematics and Computer Science at the Open University of Israel. She obtained her Ph.D. in Computer Science from Ben-Gurion University of the Negev, and was a postdoctoral researcher at Stony Brook University. Her research interest is in discrete and computational geometry, optimization problems, geometric data structures and algorithms.