$\text{penalty}=\lambda CN$ (18)

${f}_{new}\left({x}_{i}\right)={f}_{old}\left({x}_{i}\right)+\text{penalty}$ (19)

$CN$ is the total number of collisions on a single chromosome, $\lambda \left(0<\lambda <1\right)$ is the Correction parameter of penalty. ${f}_{old}\left({x}_{i}\right)$ is the corresponding objective function value of individual ${x}_{i}$ , ${f}_{new}\left({x}_{i}\right)$ is the sum of corresponding objective function and collision penalties of individual ${x}_{i}$ .

5) Selection, crossover, mutation and other operations are performed according to genetic algorithms until the iteration goes to the maximum iteration path. The approximate optimal solution or optimal solution obtained is the optimal path.

4. Case Solving

In the warehouse layout shown in Figure 1, the gray grid represents the infeasible area, the red grid represents the departure platform and the blue grid represents the monitoring point. At the same time, each robot starts from the departure platform and completes the monitoring task of ten points to be monitored, which is $\left\{18,30,112,135,157,196,223,235,245,267\right\}$ .The warehouse has a total of 10 robots available, each robot filled with electricity can work continuously for 60 units of time and the speed of each robot is equal. The fixed cost of call a robot is 60 yuan and the cost of each robot driving unit distance is 2 yuan.

The program code is written by MATLAB, and the total number of collisions of each chromosome is calculated by the collision detection method, and the fitness of the penalty term is further calculated. Set the population size is 50 and the maximum evolution algebra is 100. In windows 7 (g4, 2G, 32 operating system) environment run the algorithm program 30 times [13] .

According to the working environment of the robot in Figure 1, the adjacency matrix is used to store Figure 1. Based on the advantages of the Floyd algorithm, the distance matrix and the routing matrix between any two points in the adjacency distance matrix can be calculated. The optimum number of robots is 3 based on a genetic algorithm with collision detection. The program with collision detection algorithm runs 30 times, and in the 30 run, the corresponding statistical results of the running distance of 3 robots are: the average value is 86.13, the maximum value is 90, the minimum value is 80, and the standard deviation is 2.36. The total cost of 3 robots completed tasks are: the average total cost is 357.62, the maximum is 364, the minimum is 340, and the standard deviation is 5.51. The statistical results of running the program for 30 times are: the average time is 33.65, the maximum is 37.86, the minimum is 29.96, and the standard deviation is 2.39.

Figure 2 is an iterative graph of an optimal solution. It can be seen that when the genetic algorithm program with collision detection runs, it converges to the

Figure 2. Convergence process of genetic algorithm.

optimal solution about 26 iterations, and the optimal solution does not change after 26 generations.

Figure 3 is a collision free path corresponding to 3 robots solved in this paper, which can be simply described as:

V1: 264--245--112--18--264;

V2: 264--223--157--196--267--264;

V3: 264--135--30--235--264.

It can be seen from Figure 3 that the optimal running path of 3 robots can be solved by using genetic algorithm with collision detection. Although the paths of V1, V2 and V3 shown in Figure 3 having overlapping parts, 3 robots leave the platform at the same time and the robots run at the same speed, so the time to run to the same path point is different and there will be no collisions actually.

5. Concluding Remarks

This paper studies the problem of multi-robot path planning based on genetic algorithm. Firstly, the adjacency matrix is used to store the example data. The shortest distance matrix and the routing matrix between the detected points are solved by using the Floyd algorithm according to the adjacency distance matrix [16] . The shortest time matrix is obtained from the shortest distance matrix, and the initial population is generated randomly according to the genetic algorithm. The task is assigned to robots with the longest running time of each robot as the constraint. Using the backtracking routing function of Floyd algorithm, the path of each robot is obtained according to the tasks assigned to each robot. The genetic algorithm of collision detection is used to solve the task allocation and path planning model of multi-robot, getting the optimum number of robots. The tasks each robot needs to accomplish, and the least cost collision free path is planned at the same time.

On the one hand, a collision detection algorithm is designed to avoid collisions in the running process of multi-robots; on the other hand, with the longest running time of each robot as the constraint, using the least robot completes

Figure 3. The running path of robots this paper.

the monitoring tasks making the total cost lowest. The genetic algorithm with collision detection designed in this paper can solve the problem of task allocation and path planning of multi-robot simultaneously.

In this paper, assuming that all robots start from the same platform, the collision between multi-robot can be further reduced by adjusting the starting platform of each robot actually; this paper does not consider the priority of robots to avoid collisions, so the robot can be based on a certain priority rules for collision avoidance. In the following research, we will consider these factors and further study the problem.

Acknowledgements

This work was supported by National Natural Science Foundation of China (71540028), Teaching Master of Beijing High Tech Project (G02040011); the Funding Project of High Level Cultivation of Beijing Wuzi University (GJB20164005).

Conflicts of Interest

The authors declare no conflicts of interest.

[1] | Sun, F. (2012) Research on the Development of Industrial Robots in China. Science Technology and Engineering, 12, 2912-2918. |

[2] | Zhang, F. (2005) Improved Market Approach for Multi Robot Collaborative Exploration. Control and Decision, 20, 516-524. |

[3] | Zeng, N. (2016) Path Planning for Intelligent Robot Based on Switching Local Evolu-tionary PSO Algorithm. Emerald Insight, 36, 120-126. |

[4] |
Dong, Y. (2016) Disordered and Multiple Destinations Path Planning Methods for Mobile Robot in Dynamic Environment. Journal of Electrical and Computer Engineering, 10, 1-10. https://doi.org/10.1155/2016/3620895 |

[5] | Lu, Y. and Zhao, Y, (2015) Path Planning of Narrow Space Based on Improved Genetic Algorithm. Application Research of Computers, 32, 414-418. |

[6] | Lie, X. (2011) A Tabu Search Autonomous Navigation Algorithm for Mobile Robot. Control and Decision, 26, 1310-1314. |

[7] | Tang, W. (2012) The Improved Optimization Algorithm Is Used for Path Planning of Robots. Science Technology and Engineering, 12, 7599-7601. |

[8] | Chen, X. (2013) Multi Robot Task Allocation Based on Partitioning. Journal of Southern Yangtze University (Natural Science Edition), 12, 412-414. |

[9] | Cao, Z. and Wu, B. (2013) Assignment of Multi Robot Tasks Based on Improved Ant Colony Algorithm. Modular Machine Tools and Automatic Machining Technology, 2, 34-37. |

[10] | Luo, X. and Liu, H. (2017) Application of Optimized Fuzzy Decision Algorithm in Multi Homing Vehicle Scheduling Problem. Science Technology and Engineering, 17, 85-90. |

[11] | Yin, X. and Hu, Y. (2016) Research on Path Planning of Robot Obstacle Avoidance in Unknown Environment. Science Technology and Engineering, 33, 221-225. |

[12] | Li, H. and Liang, Y. (2012) Research on Robot Collision Avoidance Motion Planning Algorithm Based on RRT. Journal of Shenzhen Institute of Information Technology, 10, 21-26. |

[13] | Li, Z. and Li, X. (2016) Genetic Algorithm for Task Allocation And Path Planning of Multi-Robot System. Journal of Mathematical Sciences and Application, 11, 1-7. |

[14] | Wang C. and Li, X. (2017) Leg Deformation Strategy of Antiriot Robot Based on Floyd Algorithm. Science Technology and Engineering, 17, 70-73. |

[15] | Zhu, H. and Zhang, Y. (2011) Find All the Shortest Paths among Nodes Based on Im-proved Floyd Algorithm. Network and Multimedia, 35, 65-67. |

[16] | Zuo, X. and Shen, W. (2017) Improved Algorithm for Multiple Shortest Path Problem Based on Floyd Algorithm. Computer Science, 44, 222-227. |

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.