TY - GEN
T1 - A Cell Potential and Motion Pattern Driven Multi-robot Coverage Path Planning Algorithm
AU - Xu, Meng
AU - Xin, Bin
AU - Dou, Lihua
AU - Gao, Guanqiang
N1 - Publisher Copyright:
© 2020, Springer Nature Singapore Pte Ltd.
PY - 2020
Y1 - 2020
N2 - This paper proposes an intelligent “Cell Potential and Motion Pattern driven Coverage (CPMPC)” algorithm to solve a cooperative coverage path planning problem for multiple robots in two-dimensional target environment. The target environment is divided into cell areas according to the detection range of robot, and the cell matrix is given correspondingly. The values in the cell matrix are defined as cell potential, which represents the number of times each cell is detected by robots. The priority of the robot’s neighbor cell is called the motion pattern. At different moments, robots can choose within different motion patterns. Genetic algorithm (GA) is used to optimize the combination of motion patterns. By taking account obstacle avoidance and collision avoidance into consideration, the CPMPC algorithm adopts a double-layer choice strategy driven by cell potential and motion pattern to generate the next waypoint. Furthermore, this algorithm contains two optimal strategies: avoiding collision and jumping out of the detected area. Compared with the pattern-based genetic algorithm, the results obtained by us show that the CPMPC algorithm could solve the multi-robot coverage path planning (MCPP) problem effectively with guarantee of complete coverage, and improved makespan.
AB - This paper proposes an intelligent “Cell Potential and Motion Pattern driven Coverage (CPMPC)” algorithm to solve a cooperative coverage path planning problem for multiple robots in two-dimensional target environment. The target environment is divided into cell areas according to the detection range of robot, and the cell matrix is given correspondingly. The values in the cell matrix are defined as cell potential, which represents the number of times each cell is detected by robots. The priority of the robot’s neighbor cell is called the motion pattern. At different moments, robots can choose within different motion patterns. Genetic algorithm (GA) is used to optimize the combination of motion patterns. By taking account obstacle avoidance and collision avoidance into consideration, the CPMPC algorithm adopts a double-layer choice strategy driven by cell potential and motion pattern to generate the next waypoint. Furthermore, this algorithm contains two optimal strategies: avoiding collision and jumping out of the detected area. Compared with the pattern-based genetic algorithm, the results obtained by us show that the CPMPC algorithm could solve the multi-robot coverage path planning (MCPP) problem effectively with guarantee of complete coverage, and improved makespan.
KW - Cell potential and motion pattern driven coverage path planning algorithm
KW - Genetic algorithm
KW - Multi-robot system
UR - http://www.scopus.com/inward/record.url?scp=85083973579&partnerID=8YFLogxK
U2 - 10.1007/978-981-15-3425-6_36
DO - 10.1007/978-981-15-3425-6_36
M3 - Conference contribution
AN - SCOPUS:85083973579
SN - 9789811534249
T3 - Communications in Computer and Information Science
SP - 468
EP - 483
BT - Bio-inspired Computing
A2 - Pan, Linqiang
A2 - Liang, Jing
A2 - Qu, Boyang
PB - Springer
T2 - 14th International Conference on Bio-inspired Computing: Theories and Applications, BIC-TA 2019
Y2 - 22 November 2019 through 25 November 2019
ER -