A new optimization algorithm is proposed by combining the ant colony algorithm and the artificial potential field algorithm. In the design process of the algorithm, the artificial potential field method is first introduced to allocate the initial pheromone of the ant colony algorithm, thereby avoiding the problem of local optimization caused by concentration of ants on the path with the strongest heuristic information due to the disproportion of too few pheromones to the heuristic information at the initial stage of the iteration. Secondly, by introducing the potential field guiding function to improve the state transfer function of the ant colony algorithm, we avoid the problem of long search time caused by blind selection which results from the fact that the ant searches in 3D space and easily ignores the obstacles around the node. Finally, the optimization algorithm is applied to solve the UAV 3D path planning problem, and the effectiveness is verified by simulation.
LI Xianqiang
,
MA Rong
,
ZHANG Shen
,
HOU Yanze
,
PEI Yifei
. Improved design of ant colony algorithm and its application in path planning[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020
, 41(S2)
: 724381
-724381
.
DOI: 10.7527/S1000-6893.2020.24381
[1] MATTHEW C, TOM F, CHEN W H, et al. Optimal polygon decomposition for UAV survey coverage path planning in wind[J]. Sensors, 2018, 18(7):2132-2146.
[2] VÍCTOR S J, MATILDE S, MANUEL A J. Intelligent UAV map generation and discrete path planning for search and rescue operations[J]. Complexity, 2018, 15(1):1123-1140.
[3] GAO F, WU W, GAO W, et al. Flying on point clouds:Online trajectory generation and autonomous navigation for quadrotors in cluttered environments[J]. Journal of Field Robotics, 2019, 36(4):1452-1463.
[4] JI J, KHAJEPOUR A, MELEK W W, et al. Path planning and tracking for vehicle collision avoidance based on model predictive control with multiconstraints[J]. IEEE Transactions on Vehicular Technology, 2017, 66(2):952-964.
[5] LIU S, WATTERSON M, MOHTA K, et al. Planning dynamically feasible trajectories for quadrotors using safe flight corridors in 3-D complex environments[J]. IEEE Robotics & Automation Letters, 2017, 25(1):71-79.
[6] FARADI A Q, SHARMA S, SHUKLA A, et al. Multi-robot multi-target dynamic path planning using artificial bee colony and evolutionary programming in unknown environment[J]. Intelligent Service Robotics, 2018, 11(2):171-186.
[7] LIU Y, ZHANG W, CHEN F, et al. Path planning based on improved deep deterministic policy gradient algorithm[C]//2019 IEEE 3rd Information Technology, Networking, Electronic and Automation Control Conference. Piscataway:IEEE Press, 2019:295-299.
[8] AMMAR A, BENNACEUR H, CHAARI I, et al. Relaxed dijkstra and A* with linear complexity for robot path planning problems in large-scale grid environments[J]. Soft Computing, 2016, 20(10):4149-4171.
[9] GUO H, MAO Z, DING W, et al. Optimal search path planning for unmanned surface vehicle based on an improved genetic algorithm[J]. Computers & Electrical Engineering, 2019, 20(10):106-117.
[10] NEYDORF R, YARAKHMEDOV O, POLYAKH V, et al. Robot path planning based on ant colony optimization algorithm for environments with obstacles[M]//Improved Performance of Materials. 2018:175-184.
[11] WEI W, DONG P, ZHANG F. The shortest path planning for mobile robots using improved A* algorithm[J]. Journal of Computer Applications, 2018, 25(8):234-243.
[12] KUMAR P B, RAWAT H, PARHI D R. Path planning of humanoids based on artificial potential field method in unknown environments[J]. Expert Systems, 2019, 36(2):1-12.
[13] ZHEN X, ENZE Z, QINGWEI C. Rotary unmanned aerial vehicles path planning in rough terrain based on multi-objective particle swarm optimization[J]. Journal of Systems Engineering and Electronics, 2020, 31(1):130-141.
[14] DORIGO M, MANIEZZO V. Ant system:Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 1996, 26(1):29-41.
[15] YOUSEFIKHOSHBAKHT M, DIDEHVAR F, RAHMATI F. A combination of modified tabu search and elite ant system to solve the vehicle routing problem with simultaneous pickup and delivery[J]. Journal of Industrial and Production Engineering, 2014, 31(2):65-75.
[16] SKINDEROWICZ R. Implementing a GPU-based parallel MAX-MIN ant system[J]. Computer Science, 2020, 30(3):237-253.
[17] YANG Q, CHEN W N, YU Z, et al. Adaptive multimodal continuous ant colony optimization[J]. IEEE Transactions on Evolutionary Computation, 2017, 21(2):191-205.
[18] WANG D, SHAO X, LIU S. Assembly sequence planning for reflector panels based on genetic algorithm and ant colony optimization[J]. International Journal of Advanced Manufacturing Technology, 2017, 91(1-4):987-997.
[19] GAO W. Displacement back analysis for underground engineering based on immunized continuous ant colony optimization[J]. Engineering Optimization, 2016, 48(5):868-882.
[20] SKINDEROWICZ R. An improved ant colony system for the sequential ordering problem[J]. Computers & Operations Research, 2017, 86(1):1-17.
CJA