Multi-robot Path Planning Based On Improved Fruit Fly Optimization Algorithm

Robot path planning technology is a key technology in robot navigation that is the premise and basis for robots to perform various tasks.It has a wide range of applications in manufacturing,service industry,military,etc.Researching this technology has important theoretical significance and practical application significance.Robot path planning problem refers to finding an optimal safe path from the starting position to the target position in environment with various obstacles according to specific evaluation criteria(such as minimum time,shortest path,or minimum working cost).This technique can be modeled as an optimization problem.A solution to the multi-robot path planning problem is to adopt a path planner to sequentially plan paths for each robot,and the latter robot is planned according to the path of the previous robot until paths of all robot are planned.Solving the problem of multi-robot path planning with fruit fly optimization algorithm(FOA)is the purpose of this paper.The existing multi-robot path planning methods,the idea and principles of FOA,the problem of path planning for single robot and multi-robot are investigated.A FOA incorporating average learning and step changing(AL-SC-FOA)and a robot path planning method based on improved fruit fly optimization algorithm and cubic spline(IFOA-CS)were proposed,and multi-robot global path planning method based on IFOA-CS and virtual obstacles(VO)was designed.The main works are as follows:(1)The principle analysis and simulation of FOA are performed.Then AL-SC-FOA was proposed to improve the disadvantages of slow convergence speed,easily relapsing into local extremum and poor stability of traditional FOA.There are two improvements have been made compared to basic FOA and other improvement strategy.Firstly,a new diminishing factor of search range is designed,which decreases the step size to adjust search of each fruit fly,so that the local optimization ability of individual can be enhanced to improve the accuracy of algorithm.Then,fruit fly population learns from the optimal individual and the average of solutions of the optimal individual to avoid the algorithm falling into a local optimum and increase the stability of the algorithm.The test on the 8 intelligent algorithm test examples show the superiority of the proposed improved method.(2)Aiming at shortcomings such as instability,easy to fall into the local optimum,slow convergence speed for FOA-based path planning,a new improved fruit fly optimization algorithm and cubic spline fusion(IFOA-CS)is proposed for mobile robot.This method uses the idea of decreasing the step and learning the average value from the population.Compared to(1),The difference is that average learning strategy was taken after the algorithm is trapped in the local optimum,which is equivalent to disturbance information is given when the algorithm falls into a local optimum.At the same time,the scope of group initialization position is narrowed for the path planning problem.Then the path planning problem was transformed into the problem of IFOA to optimize the coordinate of the cubic spline control points.Simulation results show that the proposed method has faster convergence speed,better stability and higher accuracy.It also can avoid falling into local optimum to a certain extent and the resulting path is smooth and shorter.(3)Guaranteeing the safety of each robot is an important issue in multi-robot path planning.A centralized multi-robot path planning method based on IFOA-CS path planner and VO is proposed.Firstly,the path of a robot is planned by IFOA-CS,and virtual obstacle centered on interpolation points that make up the path of the robot are set appropriately to ensure the safety of robots.Then the path of the next robot was planned until paths of all robots were planned.Simulation results show that the multi-robot path planning problem can be effectively solved by proposed method.