Multi-robot path planning using co-evolutionary genetic programming

被引:96
作者
Kala, Rahul [1 ]
机构
[1] Univ Reading, Sch Cybernet, Sch Syst Engn, Reading, Berks, England
关键词
Path planning; Motion planning; Mobile robotics; Genetic programming; Grammatical evolution; Co-operative evolution; Multi-robot systems; ENVIRONMENT;
D O I
10.1016/j.eswa.2011.09.090
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Motion planning for multiple mobile robots must ensure the optimality of the path of each and every robot, as well as overall path optimality, which requires cooperation amongst robots. The paper proposes a solution to the problem, considering different source and goal of each robot. Each robot uses a grammar based genetic programming for figuring the optimal path in a maze-like map, while a master evolutionary algorithm caters to the needs of overall path optimality. Co-operation amongst the individual robots' evolutionary algorithms ensures generation of overall optimal paths. The other feature of the algorithm includes local optimization using memory based lookup where optimal paths between various crosses in map are stored and regularly updated. Feature called wait for robot is used in place of conventionally used priority based techniques. Experiments are carried out with a number of maps, scenarios, and different robotic speeds. Experimental results confirm the usefulness of the algorithm in a variety of scenarios. (C) 2011 Elsevier Ltd. All rights reserved.
引用
收藏
页码:3817 / 3831
页数:15
相关论文
共 36 条
[1]  
[Anonymous], P 1992 IEEE RSJ INT
[2]  
[Anonymous], MULTIROBOT SYSTEMS S
[3]  
[Anonymous], 2003, Genetic programming IV: routine human-competitive machine intelligence
[4]  
Asama H., 1991, Proceedings IROS '91. IEEE/RSJ International Workshop on Intelligent Robots and Systems '91. Intelligence for Mechanical Systems (Cat. No.91TH0375-6), P1215, DOI 10.1109/IROS.1991.174665
[5]  
ASAMA H, 1989, ACTRESS IEEE RSJ INT, P283
[6]   Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots [J].
Bennewitz, M ;
Burgard, W ;
Thrun, S .
ROBOTICS AND AUTONOMOUS SYSTEMS, 2002, 41 (2-3) :89-99
[7]  
Bennewitz M, 2001, IEEE INT CONF ROBOT, P271, DOI 10.1109/ROBOT.2001.932565
[8]  
Bohlin R., 2000, Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065), P521, DOI 10.1109/ROBOT.2000.844107
[9]   An experimental study of distributed robot coordination [J].
Carpin, Stefano ;
Pagello, Enrico .
ROBOTICS AND AUTONOMOUS SYSTEMS, 2009, 57 (02) :129-133
[10]   Probabilistic Road Map sampling strategies for multi-robot motion planning [J].
Clark, CM .
ROBOTICS AND AUTONOMOUS SYSTEMS, 2005, 53 (3-4) :244-264