Speaker: Kiril Solovey, TAU

Title: Motion Planning for Unlabeled Discs with Optimality Guarantees

Abstract
--------
We study the problem of path planning for unlabeled
(indistinguishable) unit-disc robots in a planar environment
cluttered with polygonal obstacles.  We introduce an algorithm
which minimizes the total path length, i.e., the sum of lengths
of the individual paths.

Our algorithm is guaranteed to find a solution if one exists, or
report that none exists otherwise. Furthermore, it has a
running-time complexity of O(m^4+mn^2+m^2n), where
O(m) is the number of robots and O(n) is the total complexity
of the workspace. Moreover, the total length of the returned
solution is at most OPT+O(m), where OPT is the
optimal-solution cost.  To the best of our knowledge this is the
first algorithm for the problem that has such guarantees.  The
algorithm has been implemented in an exact manner and we present
experimental results that attest to its efficiency.

This is joint work with Dan Halperin, Jingjin Yu, and Or Zamir.