Multi-Robot Motion Planning: The Easy, the Hard and the Uncharted
There are multi-robot motion planning (MRMP) problems involving dozens of robots, which can be speedily solved, while other 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.
Dan Halperin is a professor of Computer Science at Tel Aviv University. His main field of research is Computational Geometry and its Applications. A major focus of his work has been in research and development of robust geometric algorithms, principally as part of the CGAL project and library. The application areas he is interested in include robotics, automated manufacturing, algorithmic motion planning and 3D printing. Halperin is an IEEE Fellow and an ACM Fellow.