Event Location: NSH 1305

Abstract: Planning optimal paths for large numbers of robots is computationally expensive.  In our research, we developed a new framework for multirobot path planning called subdimensional expansion, which initially plans for each robot individually, and then coordinates motion among the robots as needed.  More specifically, subdimensional expansion initially creates a one-dimensional search space embedded in the  joint configuration space of the multirobot system.  When the search space is found to be blocked during planning by a robot-robot collision, the dimensionality of the search space is locally increased to ensure that an alternative path can be found.  As a result, robots are only coordinated when necessary, which reduces the computational cost of finding a path.  We will present the M* algorithm, an implementation of subdimensional expansion that adapts the A* planner to perform efficient multirobot planning, as well as implementations using probabilistic planners. 

We will propose four new directions of research.  First, we will describe how to adapt M* to handle tasks that require multiple teams of cooperative robots.  We will then describe how to combine fast, polynomial time solutions with subdimensional expansion to efficiently compute near-optimal paths.  Finally, we will discuss methods of robust path planning utilizing sequential composition and topological heuristics.

Committee:Howie Choset, Chair

Manuela Veloso

Maxim Likhachev

Sven Koenig, University of Southern California