Multimedia  

 

Volume 24 Issue 4 - Publication Date: 1 April 2005
 
Coordinating Multiple Robots with Kinodynamic Constraints Along Specified Paths
 
J. Peng Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, New York 12180, USA and S. Akella Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York 12180, USA
 
This paper focuses on the collision-free coordination of multiple robots with kinodynamic constraints along specified paths. We present an approach to generate continuous velocity profiles for multiple robots; these velocity profiles satisfy the dynamics constraints, avoid collisions, and minimize the completion time. The approach, which combines techniques from optimal control and mathematical programming, consists of identifying collision segments along each robot’s path, and then optimizing the robots’ velocities along the collision and collision-free segments. First, for each path segment for each robot, the minimum and maximum possible traversal times that satisfy the dynamics constraints are computed by solving the corresponding two-point boundary value problems. The collision avoidance constraints for pairs of robots can then be combined to formulate a mixed integer nonlinear programming (MINLP) problem. Since this nonconvex MINLP model is difficult to solve, we describe two related mixed integer linear programming (MILP) formulations, which provide schedules that give lower and upper bounds on the optimum; the upper bound schedule is designed to provide continuous velocity trajectories that are feasible. The approach is illustrated with coordination of multiple robots, modeled as double integrators subject to velocity and acceleration constraints. An application to coordination of nonholonomic car-like robots is described, along with implementation results for 12 robots.
 
Multimedia Key
= Video = Data = Code = Image
 
Extension
Type
Description
1
Example One: 12 robots moving along radial paths with symmetry, with a bottleneck at the center (before coordinator). (3.9 MB GIF animation)
2
Example Two: 12 robots moving along radial paths with symmetry, with a bottleneck at the center (after coordinator). (2.8 MB GIF animation)
3

Example Three: 12 car-like robots moving on constant curvature straight-line and circular paths (before coordination). (2.8 MB GIF animation)

4
Example Four: 12 car-like robots moving on constant curvature straight-line and circular paths (after coordination). (3.0 MB GIF animation)
5
Example Five: 12 car-like robots moving on simple continous curvature paths (before coordination). (3.4 MB GIF animation)
6
Example Six: 12 car-like robots moving on simple continous curvature paths (after coordination). (2.8 MB GIF animation)
 
Return to Contents