Motion Planning for Multi-robot Cooperation Based on Cooperative Co-evolutionary Roadmap Method
WANG Mei, WU Tie-jun
Institute of Intelligent Systems & Decision Making, National Key Laboratory of Industrial Control Technology, Zhejiang University, Hangzhou 310027, China
Abstract：Motion planning for multi-robot cooperation,especially for those robots with many degrees of freedom,is very difficult.Getting some ideas from probabilistic roadmap method,we develop a new planner based on cooperative co-evolutionary roadmap method(CCRM).With the help of the capabilities of heuristic search and constraint handling,which the cooperative co-evolutionary algorithms have,the new CCRM algorithms will deal with the problem of high-dimension combined configuration space and timing and spatial optimization that come with the multi-robot cooperation.The experiments show that the algorithm is efficient for multi-robot cooperation.
[1] Kavraki L E,Svestka P,Latombe J C,et al.Probabilistic roadmaps for path planning in high-dimensional configuration spaces[J].IEEE Transactions on Robotics and Automation,1996,12(4);566-580. [2] Hsu D,Latombe J C,Motwani R.Path planning in expansive configuration spaces[J].International Journal of Computational Geometry and Applications,1999,9(4-5);495-512. [3] Kavraki L E.Random Networks in Configuration Space for Fast Path Planning[D].USA;Stanford University,1995. [4] Amato N M,Wu Y.A randomized roadmap method for path and manipulation planning[A].Proceedings of the IEEE International Conference on Robotics and Automation[C].USA;IEEE,1996.113-120. [5] Boor V,Overmars M H,van der Strappen A F.The Gaussian sampling strategy for probabilistic roadmap planners[A].Proceedings of the IEEE International Conference on Robotics and Automation[C].USA;IEEE,1999.1018-1023. [6] Guibas L,Holleman C,Kavraki L.A prolabilistic roadmap planner for flexible objects with a workspace medial-axis based sampling approach[A].Proceedings of the IEEE International Conferenec on Intelligent Robots and Systems[C].USA;IEEE,1999.254-260. [7] Hoff K,Culver T,Keyser J,et al.Interactive motion planning using hardware-accelerated computation of generalized Voronoi diagrams[A].Proceedings of the IEEE International Conference on Robotics and Automation[C].USA;IEEE,2000.2931-2937. [8] Hsu D,Latombe J C,Wilson R H.A general framework for assembly planning;the motion space approach[J].Algorithmica,2000,26(3-4);577-601. [9] Simeon T,Laumond J P.Notes on visibility roadmaps and path planning[A].Algorithmic and Computational Robotics[M].USA;A K Peters Ltd.,2001.317-328. [10] Sanchez G,Latombe J C.On delaying collision checking in PRM planning;application to multi-robot coordination[J].The International Journal of Robotics Research,2002,21(1);5-26. [11] Potter M A.The Design and Analysis of a Computational Model of Cooperative Coevolution[D].USA;George Mason University,1997. [12] Zheng C W,Ding M Y,Zhou C P.Cooperative path planning for multiple air vehicles using a co-evolutionary algorithm[A].Procecdings of the 2002 International Conference on Machine Learning and Cybernetics[C].USA;IEEE,2002.219-224. [13] Schoenauer M,Xanthakis S.Constrained GA optimization[A].Proceedings of the 5th International Conference on Genetic Algorithms[C].USA;Morgan Kaufmann,1993.573-580. [14] Michalewicz Z,Attia N.Evolutionary optimization of constrained problems[A].Proceedings of the 3rd Annual Conference on Evolutionary Programming[C].Singapore;World Scientific,1994.98-108. [15] Quinlan S.Efficient distance computation between non-convex objects[A].Proceedings of the IEEE International Conference on Robotics and Automation[C].USA;IEEE,1994.3324-3330. [16] Cameron S A.A study of the clash detection problem in robotics[A].Proceedings of the IEEE International Conference on Robotics and Automation[C].USA;IEEE,1985.488-493.
