Abstract：A collision-free, coordinated motion planning is presented for multiple robots in a shared workspace. The proposed method consists of two phases. In the first phase, a collision-free path with respect to stationary obstacles for each robot is planned according to task requirements without considering the conflicts among the robots by employing the probabilistic roadmap (PRM) method. In the second phase, the robot path is described by continuous configuration sequences, the state space of the whole system is constructed, and the investigated problem is transformed into a continuous path search problem in a high dimensional state space. On this basis, a collision-avoidance strategy for multiple robots, a dynamic modification method of motion sequence priorities, and an improved A* algorithm are proposed, and collision-free, coordinated motion planning for multiple robots are implemented. The feasibility and effectiveness of the proposed approach are demonstrated with 2 simulation cases. The results show that the proposed method can rapidly, effectively obtain the coordinated collision-free paths for multiple robots.
 LaValle S M, Kuffner J J. Randomized kinodynamic planning[J]. International Journal of Robotics Research, 2001, 20(5): 378-400.
 Jaillet L, Cortes J, Simeon T. Sampling-based path planning on configuration-space costmaps[J]. IEEE Transactions on Robotics, 2010, 26(4): 635-646.
 Xie B Y, Zhuo J, Liu Y. Motion planning of reaching point movements for 7R robotic manipulators in obstacle environment based on rapidly-exploring random tree algorithm[J]. Journal of Mechanical Engineering, 2012, 48(3): 63-69.
 Erdmann M, Lozano-Perez T. On multiple moving objects[J]. Algorithmica, 1987, 2(4): 477-521.
 Kant K, Zucker S W. Toward efficient trajectory planning: The path-velocity decomposition[J]. International Journal of Robotics Research, 1986, 5(3): 72-89.
 Chiddarwar S S, Babu N R. Offline decoupled path planning approach for effective coordination of multiple robots[J]. Robotica, 2009, 28(4): 477-491.
 Chiddarwar S S, Babu N R. Conflict free coordinated path planning for multiple robots using a dynamic path modification sequence[J]. Robotics and Autonomous Systems, 2011, 59(7/8): 508-518.
 O'Donnell P A, Lozano-Perez T. Deadlock-free and collision-free coordination of two robot manipulators[C]//IEEE International Conference on Robotics and Automation. Piscataway, USA: IEEE, 1989: 484-489.
 Cheng X. On-line collision-free path planning for service and assembly tasks by a two-arm robot[C]//IEEE International Conference on Robotics and Automation. Piscataway, USA: IEEE, 1995: 1523-1528.
 Li T Y, Latombe J C. On-line manipulation planning for two robot arms in a dynamic environment[J]. International Journal of Robotics Research, 1997, 16(2): 144-167.
 Liu C L, Zhang K, Lee J. Research on collision algorithm for dual-robot under coordinative operation and simulation[J]. Robot, 2003, 25(2): 167-171.
 Li P, Meng Q X, Wang L Q. Analysis of collision for loosely coordinated two-robot system[J]. China Mechanical Engineering, 2005, 16(13): 1150-1153.
 Flordal H, Fabian M, Akesson K, et al. Automatic model generation and PLC-code implementation for interlocking policies in industrial robot cells[J]. Control Engineering Practice, 2007, 15(11): 1416-1426.
 Spensieri D, Carlson J S, Ekstedt F, et al. An iterative approach for collision free routing and scheduling in multirobot stations[J]. IEEE Transactions on Automation Science and Engineering, 2016, 13(2): 950-962.
 Qadeer U, Sualeh M. Automatic coordination and collision avoidance using sequence planning and process simulate[D]. Gothenburg, Sweden: Chalmers University of Technology, 2011.
 Bengtsson K, Bergagard P, Thorstensson C, et al. Sequence planning using multiple and coordinated sequences of operations[J]. IEEE Transactions on Automation Science and Engineering, 2012, 9(2): 308-319.
 Kannan A, Gupta P, Tiwari R, et al. Robot motion planning using adaptive hybrid sampling in probabilistic roadmaps[J]. Electronics, 2016, 5(2): No.16.
 Sanchez G, Latombe J C. On delaying collision checking in PRM planning: Application to multi-robot coordination[J]. International Journal of Robotics Research, 2002, 21(1): 5-26.
 GAMMA Group at the University of North Carolina. Proximity Query Packages[EB/OL].[2016-08-25]. http://gamma.cs.unc.edu/SSV/.