TITLE: 
Multi-Robot Motion Planning: The Easy, the Hard and the Uncharted

SPEAKER: 
Prof. Dan Halperin, School of Computer Science, Tel Aviv University

TIME & LOCATION: 
11am, Wednesday (Aug 28), NCS 120

ABSTRACT: 
There are multi-robot motion planning (MRMP) problems involving dozens of robots, which can be speedily solved, while others are practically unsolvable. What makes an MRMP problem easy or hard? In the first part of the talk I'll describe our quest to resolve this issue, and some progress we have made in the context of unlabeled MRMP.

In the second part of the talk I'll review recent algorithms that we have developed for various types of MRMP problems in tight obstacle-cluttered environments: from sampling-based methods tailored to the coordination of a few complex robots, to complete and exact solutions for hundreds of simply shaped robots. The talk will conclude with surprisingly open problems for the coordinated motion of two robots.

SPEAKER BIO: 
Dan Halperin is a Professor of Computer Science at Tel Aviv University, and leads the TAU Computational Geometry Lab (CGL). His current research interests include computational geometry and its applications, robust geometric computing and CGAL, robotics and automation, algorithmic motion planning, and 3D printing. Professor Halperin is a Fellow of the IEEE and an ACM Fellow.