DocumentCode :
2939985
Title :
Coordinating Multiple Double Integrator Robots on a Roadmap: Convexity and Global Optimality
Author :
Peng, Jufeng ; Akella, Srinivas
Author_Institution :
Department of Mathematical Sciences Rensselaer Polytechnic Institute Troy, New York 12180, USA pengj@rpi.edu
fYear :
2005
fDate :
18-22 April 2005
Firstpage :
2751
Lastpage :
2758
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 [25], 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.
Keywords :
Acceleration; Collision avoidance; Computer science; Job shop scheduling; Mobile robots; Optimal control; Optimal scheduling; Orbital robotics; Road accidents; Robot kinematics;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Robotics and Automation, 2005. ICRA 2005. Proceedings of the 2005 IEEE International Conference on
Print_ISBN :
0-7803-8914-X
Type :
conf
DOI :
10.1109/ROBOT.2005.1570530
Filename :
1570530
Link To Document :
بازگشت