Coordinating Multiple Double Integrator Robots on a Roadmap: Convexity and Global Optimality

2005 International Conference on Robotics and Automation, Barcelona, Spain, pages 2762-2769, April 2005.

Abstract

This paper focuses on finding the global minimum time control for the collision-free coordination of multiple robots with double integrator dynamics and with additional robot state constraints and control constraints. We initially assume each robot's path is specified and decompose it into collision segments and collision-free segments. The collision avoidance constraints for pairs of robots and the dynamics constraints can then be combined to formulate the coordination problem as a mixed integer nonlinear program (MINLP). In this paper, we first show convexity of the constraints for an individual robot path segment under certain assumptions. We next establish that we are guaranteed to find the global optimum of the MINLP because each subproblem of the MINLP is a convex program, based on the convexity result on individual robot segments. To the best of our knowledge, this is the first result on directly obtaining the global optimum coordination of multiple (more than two) robots with dynamics constraints.

Finally, we extend these results to the task of coordinating robots on a given roadmap, where the roadmap has multiple candidate paths for each robot. We present an approach to simultaneously select each robot's traversal path and generate its continuous velocity profile. These robot velocity profiles satisfy the dynamics constraints, avoid collisions, and globally minimize the completion time.

We use the MINLP Solver, which combines a branch-and-bound algorithm with a filterSQP algorithm, to solve the MINLP coordination problems. We illustrate the approach with multiple robot coordination examples with up to 156 collision zones.

Animations

16 robots moving horizontally or vertically, before coordination ( gif movie ), and after coordination ( gif movie ).
12 car-like robots moving along simple continuous curvature paths, before coordination ( gif movie ), and after coordination ( gif movie ).
Multi-path example: car-like robots moving along circular and straight line paths. Each robot along a semi-circular path can either choose either the left semi-circular path or right semi-circular path. Before coordination ( gif movie ), and after coordination ( gif movie ).

Note:

When two robots collide, their color changes to red.
The gif animations repeat in a loop. The animations may sometimes appear a bit jerky.

Srinivas Akella / sakella@cs.rpi.edu