Coordinating Multiple Robots with Kinodynamic Constraints
along Specified Paths
Jufeng Peng and Srinivas Akella
Abstract
This research focuses on the collision-free coordination of multiple
robots with kinodynamic constraints along specified paths. The goal is
to generate continuous velocity profiles for the robots. The
approach consists of identifying collision segments along each robot's
path, and then optimizing the motions of the robots along the
collision and collision-free segments to avoid collisions and minimize
the completion time. We optimize the robots motions by combining
techniques from optimal control and mathematical programming. First,
for each path segment for each robot, the minimum and maximum possible
traversal times, while satisfying the dynamics constraints, are
computed by solving the corresponding two-point boundary value
problems. Using the times when a robot enters and exits a collision
segment, the collision avoidance constraints for pairs of robots can
be combined to formulate a mixed integer nonlinear programming (MINLP)
problem. Since the resulting nonconvex MINLP model is difficult to
solve, we describe two related mixed integer linear programming (MILP)
formulations that provide schedules that are lower and upper bounds on
the optimum. The approach is illustrated with coordination of
multiple robots, modeled as double integrators subject to velocity and
acceleration constraints. Results illustrating
coordination of 12 robots are described. We also
describe the application of this approach to nonholonomic car-like
robots.
Animations
- 12 robots moving radially, before coordination
( gif movie
), and after coordination ( gif movie ).
(AVI format: before
and after )
- 12 car-like robots moving along circular and straight
line paths, before coordination ( gif movie ), and after coordination ( gif movie ).
(AVI format: before
and after )
- 12 car-like robots moving along simple continuous
curvature paths, before coordination ( gif movie ), and after coordination ( gif movie ).
(AVI format: before
and after )
- Overhead view of bunny robot avoiding moving obstacles, 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.
The avi movies may be best viewed with Windows Media player.
They use the DivX codec
, which you may need to install.
Srinivas Akella / sakella@cs.rpi.edu
