基于改进多元优化算法的动态路径规划

doi:10.7527/S1000-6893.2015.0016

Abstract

Abstract:

To meet the demands for hard real time and high tracking accuracy in dynamic path planning problems, a solver based on the improved multivariant optimization algorithm (IMOA) which can simultaneously locate and track multiple optimal and sub-optimal paths is proposed. Firstly, the dynamic path planning problems are transferred into the dynamic optimization problems by defining a path with a Bezier curve. Then, the probability of tracking different optimal and sub-optimal solutions simultaneously is improved through introducing a similarity check operation into multivariate optimization algorithm (MOA). Finally, the IMOA is applied to optimize the control points of Bezier curve. Experiment results show that once the optimal path becomes less optimal or infeasible, the IMOA, by making use of its characteristics of tracking multiple dynamic optimal and suboptimal solutions, has the ability to quickly adjust optimization strategy to refine other suboptimal paths in the purpose of finding the optimal path again. What is more, the overall offline performance is improved compared with other algorithms. The presented IMOA method is adaptable to the dynamic path planning problems and meets the real demands in dynamic environments.

Key words: improved multivariant optimization algorithm, dynamic path planning, dynamic optimization, Bezier curve, multimodal optimization, multi-swarm optimization algorithm

CLC Number:

V448

LI Baolei, SHI Xinling, LI Jingjing, LYU Danju. Dynamic path planning based on improved multivariant optimization algorithm[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2015, 36(7): 2319-2328.

References

[1] Raja P, Pugazhenthi S. Path planning for a mobile robot in dynamic environments[J]. International Journal of Physical Sciences, 2011, 6(20): 4721-4731.
[2] Gao X G, Yang Y L. Initial path planning based on different threats for unmanned combat air vehicles[J]. Acta Aeronautica et Astronautica Sinica, 2003, 24(5): 435-438 (in Chinese). 高晓光, 杨有龙. 基于不同威胁体的无人作战飞机初始路径规划[J]. 航空学报, 2003, 24(5): 435-438.
[3] Li X, Xu X H, Zhao Y F, et al. Flight rerouting path planning in dispersedly distributed severe weather areas [J]. Acta Aeronautica et Astronautica Sinica, 2009, 30(12): 2342-2347 (in Chinese). 李雄, 徐肖豪, 赵嶷飞, 等. 散点状分布危险天气区域下的航班改航路径规划[J]. 航空学报, 2009, 30(12): 2342-2347.
[4] Zhou L F, Jiang J. An approach to navigation for lunar rover based on virtual reality technology[J]. Journal of Software, 2012, 7(3): 632-637.
[5] Zhang Y, Gao X G, Wei X F. Simulation of dynamic path planning for UAV in 4D space[J]. Journal of System Simulation, 2009, 21(24): 7838-7841 (in Chinese). 张艳, 高晓光, 魏小丰. 四维空间中的无人机动态路径规划及仿真[J]. 系统仿真学报, 2009, 21(24): 7838-7841.
[6] Willms A R, Yang S X. An efficient dynamic system for real-time robot-path planning[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2006, 36(4): 755-766.
[7] Ren J, Gao X G, Zhang Y. Path planning based on model predictive control algorithm under moving threat[J]. Control Theory & Applications, 2010, 27(5): 641-647 (in Chinese). 任佳, 高晓光, 张艳. 移动威胁情况下的无人机路径规划[J]. 控制理论与应用, 2010, 27(5): 641-647.
[8] Raja P, Pugazhenthi S. Optimal path planning of mobile robots: a review[J]. International Journal of Physical Sciences, 2012, 7(9): 1314-1320.
[9] Cui J, Zhu Q B, Wang J. Path planning of robot based on second division and improved genetic algorithm[J]. Computer Engineering and Applications, 2011, 47(28): 232-236 (in Chinese). 崔靖, 朱庆保, 王娟. 二次划分和改进遗传算法的机器人路径规划[J]. 计算机工程与应用, 2011, 47(28): 232-236.
[10] Ren P, Gao X G. Human intervention flight path planning for UAV low-altitude penetration[J]. Systems Engineering and Electronics, 2014, 35(4): 679-684 (in Chinese). 任鹏, 高晓光. 有限干预下的UAV低空突防航迹规划[J]. 系统工程与电子技术, 2014, 35(4): 679-684.
[11] Tuncer A, Yildirim M. Dynamic path planning of mobile robots with improved genetic algorithm[J]. Computers & Electrical Engineering, 2012, 38(6): 1564-1572.
[12] Nasrollahy A Z, Javadi H. Using particle swarm optimization for robot path planning in dynamic environments with moving obstacles and target[C]//Proceedings of Third UKSim European Symposium on Computer Modeling and Simulation. Piscataway, NJ: IEEE Press, 2009: 60-65.
[13] Raja P, Pugazhenthi S. Path planning for mobile robots in dynamic environments using particle swarm optimization[C]//Proceedings of International Conference on Advances in Recent Technologies in Communication and Computing. Piscataway, NJ: IEEE Press, 2009: 401-405.
[14] Kala R, Shukla A, Tiwari R. Dynamic environment robot path planning using hierarchical evolutionary algorithms[J]. Cybernetics and Systems: An International Journal, 2010, 41(6): 435-454.
[15] Brits R, Engelbrecht A P, Van Den Bergh F. Scalability of niche PSO[C]// Proceedings of the 2003 IEEE Swarm Intelligence Symposium. Piscataway, NJ: IEEE Press, 2003: 228-234.
[16] Xu X Q, Zhu Q B. Multi-artificial fish-swarm algorithm and a rule library based dynamic collision avoidance algorithm for robot path planning in a dynamic environment [J]. Acta Electronica Sinica, 2012, 40(8): 1694-1700 (in Chinese). 徐晓晴, 朱庆保. 动态环境下基于多人工鱼群算法和避碰规则库的机器人路径规划[J]. 电子学报, 2012, 40(8): 1694-1700.
[17] Liang J J, Suganthan P N. Dynamic multi-swarm particle swarm optimizer[C]//Proceedings of the 2005 IEEE Swarm Intelligence Symposium. Piscataway, NJ: IEEE Press, 2005: 124-129.
[18] Liang J J, Song H, Qu B Y, et al. Path planning based on dynamic multi-swarm particle swarm optimizer with crossover[J]. Intelligent Computing Theories and Applications, 2012, 7390: 159-166.
[19] Liang J J, Song H, Qu B Y. Performance evaluation of dynamic multi-swarm particle swarm optimizer with different constraint handling methods on path planning problems[C]//Proceedings of 2013 IEEE Workshop on Memetic Computing (MC). Piscataway, NJ: IEEE Press, 2013, 65-71.
[20] Hocaoglu C, Sanderson A C. Planning multiple paths with evolutionary speciation[J]. IEEE Transactions on Evolutionary Computation, 2001, 5(3): 169-191.
[21] Huang V L, Suganthan P N, Liang J J. Comprehensive learning particle swarm optimizer for solving multiobjective optimization problems[J]. International Journal of Intelligent Systems, 2006, 21(2): 209-226.
[22] Zhao S Z, Suganthan P N, Pan Q K, et al. Dynamic multi-swarm particle swarm optimizer with harmony search[J]. Expert Systems with Applications, 2011, 38(4): 3735-3742.
[23] Yang X S. Firefly algorithm, stochastic test functions and design optimisation[J]. International Journal of Bio-Inspired Computation, 2010, 2(2): 78-84.
[24] Li B L, Shi X L, Gou C X, et al. Multivariant optimization algorithm for multimodal optimization[J]. Applied Mechanics and Materials, 2014, 483: 453-457.
[25] Liang J J, Qin A K, Suganthan P N, et al. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(3): 281-295.
[26] Yang X S. Nature-inspired metaheuristic algorithms[M]. Bristol, UK: Luniver press, 2010: 4-5.
[27] Yang X S. Stochastic algorithms: foundations and applications:firefly algorithms for multimodal optimization[M]. Heidelberg, Berlin: Springer, 2009: 169-178.
[28] Liu C, Gao Z, Zhao W. A new path planning method based on firefly algorithm[C]//Proceedings of 2012 Fifth International Joint Conference on Computational Sciences and Optimization (CSO). Piscataway, NJ: IEEE Press, 2012: 775-778.
[29] Zhu Q B, Ma W. A robot path planning algorithm based on scout ants in collaboration with foraging ants[J]. Control and Decision, 2009, 24(4): 601-605 (in Chinese). 朱庆保, 马卫. 基于侦察蚁和觅食蚁协作的机器人路径规划算法[J]. 控制与决策, 2009, 24(4): 601-605.
[30] Gao X G, Wei X F, Zheng J S. UAV on-line path re-planning based on threats evaluation improved algorithm[J]. Fire Control & Command Control, 2012, 37(9): 45-49 (in Chinese). 高晓光, 魏小丰, 郑景嵩. 基于改进威胁代价的无人机路径在线重规划[J]. 火力与指挥控制, 2012, 37(9): 45-49.
[31] Liang J J, Song H, Qu B Y, et al. Comparison of three different curves used in path planning problems based on particle swarm optimizer[J]. Mathematical Problems in Engineering, 2014, 2014: 1-15.
[32] Huy Q, Seiichi M, Nejad H T N, et al. Dynamic and safe path planning based on support vector machine among multi moving obstacles for autonomous vehicles[J]. IEICE Transactions on Information and Systems, 2013, 96(2): 314-328.
[33] Sturtevant N R. Benchmarks for grid-based pathfinding[J]. IEEE Transactions on Computational Intelligence and AI in Games, 2012, 4(2): 144-148.
[34] Miao Y Q, Khamis A, Karray F O, et al. Global optimal path planning for mobile robots based on hybrid approach with high diversity and memorization[C]//Proceedings of the 2nd International Conference on Autonomous and Intelligent Systems. Berlin: Springer, 2011: 1-10.
[35] Fu X W, Li J L, Gao X G. Defense penetration path planning for UCAV based on threat neting[J]. Acta Aeronautica et Astronautica Sinica, 2014, 35(4): 1042-1052 (in Chinese). 符小卫, 李金亮, 高晓光. 威胁联网下无人作战飞机突防作战航迹规划[J]. 航空学报, 2014, 35(4): 1042-1052.
[36] Shi Y, Eberhart R. A modified particle swarm optimizer[C]//Evolutionary Computation Proceedings of 1998 IEEE World Congress on Computational Intelligence. Piscataway, NJ: IEEE Press, 1998: 69-73.
[37] Djuriši? A B. Elite genetic algorithms with adaptive mutations for solving continuous optimization problems-application to modeling of the optical constants of solids[J]. Optics Communications, 1998, 151(1): 147-159.
[38] Li X D. Adaptively choosing neighbourhood bests using species in a particle swarm optimizer for multimodal function optimization[C]//Genetic and Evolutionary Computation-GECCO 2004. Berlin: Springer, 2004: 105-116.
[39] Baykasoglu A, Ozsoydan F B. An improved firefly algorithm for solving dynamic multidimensional knapsack problems[J]. Expert Systems with Applications, 2014, 41(8): 3712-3725.
[40] Zhang X J, Guan X M, Hwang I, et al. A hybrid distributed-centralized conflict resolution approach for multi-aircraft based on cooperative co-evolutionary[J]. Science China Information Sciences, 2013, 56(12): 1-16.
[41] Guan X M, Zhang X J, Wei J, et al. A strategic conflict avoidance approach based on cooperative coevolutionary with the dynamic grouping strategy[J]. International Journal of Systems Science, DOI: 10.1080/00207721.2014.966282.

Dynamic path planning based on improved multivariant optimization algorithm

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]	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.
[3]	Siji WANG, Yuwei ZHANG, Kaiming HUANG, Biao LYU, Haifeng ZHAO, Hu WANG, Mingfu LIAO. An optimization method for helicopter power turbine rotor system based on improved particle swarm optimization algorithm [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(1): 228608-228608.
[4]	Huan ZHAO, Zhenghong GAO, Lu XIA. Aerodynamic shape design optimization method based on novel high⁃dimensional surrogate model [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(5): 126924-126924.
[5]	Chaoyu LIU, Feng QU, Di SUN, Chuanzhen LIU, Zhansen QIAN, Junqiang BAI. Discretized adjoint based aerodynamic optimization design for hypersonic osculating-cone waverider [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(4): 126664-126664.
[6]	Jiehua TIAN, Di SUN, Feng QU, Junqiang BAI. Airfoil parameterization method based on CST⁃GAN [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(18): 128280-128280.
[7]	LUO Jiajie, SONG Wenbin. Nested collaborative optimization of laminar wing and its high-lift devices [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(8): 125377-125377.
[8]	GAO Chang, LI Zhengzhou, HUANG Jiangtao, HE Yuanyuan, WU Yingchuan, LE Jialing, GUI Feng. High-accuracy aerodynamic optimization of hypersonic vehicles based on continuous adjoint [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(7): 124490-124490.
[9]	SHI Lei, YANG Guang, DING Guanghua, LIN Wenjun. Fine maintenance of an eroded fan rotor and related flow characteristics analysis [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(9): 423446-423446.
[10]	LI Chunna, ZHANG Yangkang. An efficient adaptive global optimization method suitable for aerodynamic optimization [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(5): 623352-623352.
[11]	LIU Fengbo, JIANG Cheng, MA Tuliang, LIANG Yihua. Aerodynamic optimization design of large civil aircraft using pressure distribution inverse design method based on discrete adjoint [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(5): 623372-623372.
[12]	ZHANG Xinshuai, LIU Jun, LUO Shibin. An improved multi-objective cuckoo search algorithm for airfoil aerodynamic optimization design [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2019, 40(6): 122550-122550.
[13]	CHEN Haixin, DENG Kaiwen, LI Runze. Utilization of machine learning technology in aerodynamic optimization [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2019, 40(1): 522480-522480.
[14]	HAN Zhonghua, ZHANG Yu, XU Chenzhou, WANG Kai, WU Mengmeng, ZHU Zhen, SONG Wenping. Aerodynamic optimization design of large civil aircraft wings using surrogate-based model [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2019, 40(1): 522398-522398.
[15]	WANG Chao, GAO Zhenghong, ZHANG Wei, XIA Lu, HUANG Jiangtao. Efficient surrogate-based aerodynamic design optimization method with adaptive design space expansion [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2018, 39(7): 121745-121745.