Collision free 4D path planning for multiple UAVs based on spatial refined voting mechanism and PSO approach

In this paper, a four-dimensional coordinated path planning algorithm for multiple UAVs is proposed, in which time variable is taken into account for each UAV as well as collision free and obstacle avoidance. A Spatial Refined Voting Mechanism (SRVM) is designed for standard Particle Swarm Optimization (PSO) to overcome the defects of local optimal and slow convergence. For each generation candidate particle positions are recorded and an adaptive cube is formed with own adaptive side length to indicate occupied regions. Then space voting begins and is sorted based on voting results, whose centers with bigger voting counts are seen as sub-optimal positions. The average of all particles of corresponding dimensions are calculated as the refined solutions. A time coordination method is developed by generating specified candidate paths for every UAV, making them arrive the same destination with the same time consumption. A spatial-temporal collision avoidance technique is introduced to make collision free. Distance to destination is constructed to improve the searching accuracy and velocity of particles. In addition, the objective function is redesigned by considering the obstacle and threat avoidance, Estimated Time of Arrival (ETA), separation maintenance and UAV self-constraints. Experimental results prove the effectiveness and efficiency of the algorithm. Keywords: 4D path planning, Collision free, Multiple UAVs, Obstacle avoidance, Particle swarm optimization, Spatial refined voting mechanism