蚁群算法的改进设计及在航迹规划中的应用

doi:10.7527/S1000-6893.2020.24381

Abstract

Abstract: 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.

Key words: ant colony algorithm, artificial potential field, optimization, UAV, path planning

CLC Number:

V279

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.

References

[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.

Improved design of ant colony algorithm and its application in path planning

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Haifeng WANG, Kunpeng LIU, Hongxin JIANG, Chenxi DU. Aerodynamic optimization method of propeller multi⁃design points and variable pitch angle strategy [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(9): 528831-528831.
[2]	Jiaqi LIU, Rongqian CHEN, Jinhua LOU, Xu HAN, Hao WU, Yancheng YOU. Aerodynamic shape optimization of high-speed helicopter rotor airfoil based on deep learning [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(9): 529828-529828.
[3]	Yining ZHANG, Changxuan WEN, Bo PANG, Tianhao ZHU, Jiaxin HE, Zihan JIN. Optimization of occultation observation configuration based on precise repeat ground-track resonant orbit [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(8): 329151-329151.
[4]	Chuanyun WANG, Yang SU, Linlin WANG, Tian WANG, Jingjing WANG, Qian GAO. Multi-object continuous robust tracking algorithm for anti-UAV swarm [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(7): 329017-329017.
[5]	Yanyan LUO, Shuo YANG, Xiaosong PAN, Xuhuai ZHAO, Li ZHANG. Signal reflection suppression and optimized design of high⁃speed connectors for aerospace applications [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(7): 328937-328937.
[6]	Jian ZHANG, Ruitian LI, Liang DENG, Zhe DAI, Jie LIU, Chuanfu XU. Shared⁃memory parallelization technology of unstructured CFD solver for multi⁃core CPU/many⁃core GPU architecture [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(7): 128888-128888.
[7]	Jing ZHAO, Dan SONG. Integrity monitoring method for GNSS/IMU integrated navigation system of UAV [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(7): 328943-328943.
[8]	Hongyu YIN, Yu WU, Tianjiao LIANG. Cooperative path planning for patrol coverage of fixed wing UAV [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(6): 328944-328944.
[9]	Xudong LUO, Yiquan WU, Jinlin CHEN. Research progress on deep learning methods for object detection and semantic segmentation in UAV aerial images [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(6): 28822-028822.
[10]	Pengbo SUN, Zhou ZHOU, Xu LI, Kelei WANG. Influence analysis and optimization of distribution-propulsion-wing parameters with target aerodynamic characteristics [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(6): 629368-629368.
[11]	Shusheng CHEN, Muliang JIA, Yanxu LIU, Zhenghong GAO, Xinghao XIANG. Deformation modes and key technologies of aerodynamic layout design for morphing aircraft: Review [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(6): 629595-629595.
[12]	Chuihuan KONG, Dawei WU, Zhaoguang TAN, Lijun PAN, Rubing MA, Jiangtao SI. Design of fully electric scheme for three⁃surface verification aircraft [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(6): 629618-629618.
[13]	Shusheng CHEN, Cong FENG, Zhaokang ZHANG, Ke ZHAO, Xinyang ZHANG, Zhenghong GAO. Aerodynamic design of wide-speed-range waverider-wing configuration based on global & gradient optimization method [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(6): 629596-629596.
[14]	Jinzhao DAI, Haixin CHEN. Optimization design method of three⁃dimensional wave cancellation biplane derived by shock⁃wave morphology [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(6): 628942-628942.
[15]	Liang MENG, Jinyuan YANG, Zhiwei YANG, Tong GAO, Hongquan LIU, Weihong ZHANG. Buckling⁃resisting optimization design of typical aircraft panel and test validation [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(5): 529679-529679.