基于改进多元优化算法的动态路径规划
收稿日期: 2014-08-22
修回日期: 2015-01-13
网络出版日期: 2015-01-16
基金资助
国家自然科学基金 (61261007); 云南省重点自然科学基金 (2013FA008)
Dynamic path planning based on improved multivariant optimization algorithm
Received date: 2014-08-22
Revised date: 2015-01-13
Online published: 2015-01-16
Supported by
National Natural Science Foundation of China (61261007); Yunnan Province Natural Science Foundation of Key Projects (2013FA008)
为满足动态路径规划实时性强和动态跟踪精度高的需求,提出一种基于能够同时发现并追踪多条最优以及次优路径的改进多元优化算法(IMOA)的求解方法。首先,通过利用贝赛尔曲线描述路径的方法把动态路径规划问题转化为动态优化问题;然后,把相似性检测操作引入到多元优化算法(MOA)中,增加算法同时跟踪多个不同最优以及次优解的概率;最后,用IMOA对贝赛尔曲线的控制点进行寻优。实验结果表明:当最优路径由于环境变化而变为非优或者不可行时,利用IMOA对多个最优以及次优解动态跟踪的特点,能够快速调整寻优策略对其他次优路径进行寻优以期望再次找到最优路径;其综合离线性能较其他方法也有一定的提高。因此,IMOA满足动态路径规划的实际需求,适用于解决动态环境中的路径规划问题。
李宝磊 , 施心陵 , 李敬敬 , 吕丹桔 . 基于改进多元优化算法的动态路径规划[J]. 航空学报, 2015 , 36(7) : 2319 -2328 . DOI: 10.7527/S1000-6893.2015.0016
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.
[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.
/
| 〈 |
|
〉 |
CJA