基于选择交叉烟花算法的无人车路径规划

doi:10.19678/j.issn.1000-3428.0062896

摘要/Abstract

摘要： 在三维地形环境下，基本烟花算法进行路径规划时易陷入局部最优解且存在收敛速度慢的问题，为此，提出选择交叉烟花算法。利用栅格法构建三维地形环境并设置威胁区域，使无人车选择合适的节点进行路径探索，结合燃耗代价、平滑代价和威胁代价构建适应度函数，以约束路径节点的生成位置，确保规划出的路径平滑且远离威胁区域。通过基本烟花算法的爆炸、变异、映射和选择操作进行路径搜索，同时加入针对路径节点的轮盘选择操作，使偏离原始路径较远的节点具有更高的爆炸概率，以约束路径的搜索方向，从而加快算法的搜索速度。在此基础上，引入选择交叉火花，通过对轮盘选择后节点间的路径片段进行交叉，以增强种群中烟花之间信息的交互性，提高搜索全局最优解的性能。仿真结果表明，相比基本烟花算法，该算法在简单和复杂地形环境下的适应度值平均提高6%，且运行时间平均缩短13.5%。在各类地形环境下，无人车通过该算法能有效规避威胁区域，并在较短时间内寻找到更加平滑且燃耗更低的路径。

关键词: 无人车, 路径规划, 三维环境, 烟花算法, 选择交叉火花

Abstract: In the three-dimensional terrain environment, the basic fireworks algorithm is easy to fall into the optimal solution and has the problem of slow convergence when path planning.A selection crossover fireworks algorithm is proposed.The grid method is used to build a three-dimensional terrain environment and set a threat area such that an unmanned vehicle can select appropriate nodes to explore the path.The fitness function is derived in combination with the fuel costs, smooth costs, and threat costs to restrict the generation position of the path nodes and ensure that the planned road path is smooth and far from the threat area.A path search is conducted via the explosion, mutation, mapping, and selection operations of the basic fireworks algorithm.In addition, the roulette selection operation for the path nodes is added such that the nodes farther from the original path have a higher explosion probability to restrict the search direction of the path, thereby speeding up the search speed of the algorithm.Based on this, a selection crossover spark is introduced to enhance the information interaction between fireworks in the population and improve the performance of searching the global optimal solution by crossing the path segments between nodes after wheel selection.The simulation results show that compared with the basic fireworks algorithm, the fitness of the proposed algorithm in the simple and complex terrain environments improves by 6% on average, and the running time shortens by 13.5% on average.In various terrain environments, the unmanned vehicle can successfully evade the threat area using the proposed algorithm and find a smoother path with lower fuel cost within a relatively short time.

Key words: unmanned vehicle, path planning, three-dimensional environment, fireworks algorithm, selection crossover spark

中图分类号:

TP391.9

高万博, 朱俊武, 章永龙, 章小卫. 基于选择交叉烟花算法的无人车路径规划[J]. 计算机工程, 2022, 48(11): 314-320.

GAO Wanbo, ZHU Junwu, ZHANG Yonglong, ZHANG Xiaowei. Unmanned Vehicle Path Planning Based on Selection Crossover Fireworks Algorithm[J]. Computer Engineering, 2022, 48(11): 314-320.

http://www.ecice06.com/CN/Y2022/V48/I11/314

图/表 9

20230221182106

20230221182109

20230221182112

20230221182116

20230221182119

20230221182122

20230221182126

20230221182129

20230221182132

参考文献

[1] 朱大奇, 颜明重.移动机器人路径规划技术综述[J].控制与决策, 2010, 25(7):961-967. ZHU D Q, YAN M Z.Survey on technology of mobile robot path planning[J].Control and Decision, 2010, 25(7):961-967.(in Chinese)
[2] PATLE B K, BABU L G, PANDEY A, et al.A review:on path planning strategies for navigation of mobile robot[J].Defence Technology, 2019, 15(4):582-606.
[3] WAHAB M N A, NEFTI-MEZIANI S, ATYABI A.A comparative review on mobile robot path planning:classical or meta-heuristic methods?[J].Annual Reviews in Control, 2020, 50:233-252.
[4] MASEHIAN E, SEDIGHIZADEH D.A multi-objective PSO-based algorithm for robot path planning[C]//Proceedings of International Conference on Industrial Technology.Washington D.C., USA:IEEE Press, 2010:465-470.
[5] DORIGO M, MANIEZZO V, COLORNI A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1996, 26(1):29-41.
[6] SOLTANI A R, TAWFIK H, GOULERMAS J Y, et al.Path planning in construction sites:performance evaluation of the Dijkstra, A, and GA search algorithms[J].Advanced Engineering Informatics, 2002, 16(4):291-303.
[7] 谭营, 郑少秋.烟花算法研究进展[J].智能系统学报, 2014, 9(5):515-528. TAN Y, ZHENG S Q.Recent advances in fireworks algorithm[J].CAAI Transactions on Intelligent Systems, 2014, 9(5):515-528.(in Chinese)
[8] 谭营.烟花算法引论[M].北京:科学出版社, 2015. TAN Y.Introduction to fireworks algorithm[M].Beijing:Science Press, 2015.(in Chinese)
[9] 张玮, 马焱, 赵捍东, 等.基于改进烟花-蚁群混合算法的智能移动体避障路径规划[J].控制与决策, 2019, 34(2):335-343. ZHANG W, MA Y, ZHAO H D, et al.Obstacle avoidance path planning of intelligent mobile based on improved fireworks-ant colony hybrid algorithm[J].Control and Decision, 2019, 34(2):335-343.(in Chinese)
[10] 薛裕颖, 张祥银, 张国梁, 等.基于量子行为烟花算法的移动机器人路径规划及平滑[J].控制理论与应用, 2019, 36(9):1398-1408. XUE Y Y, ZHANG X Y, ZHANG G L, et al.Path planning and smoothing based on quantum-behaved fireworks algorithm for mobile robot[J].Control Theory & Applications, 2019, 36(9):1398-1408.(in Chinese)
[11] 樊永生, 连云霞, 杨臻.改进烟花算法在虚拟士兵路径规划中的应用[J].计算机工程, 2018, 44(12):228-232. FAN Y S, LIAN Y X, YANG Z.Application of improved fireworks algorithm in path planning of virtual soldier[J].Computer Engineering, 2018, 44(12):228-232.(in Chinese)
[12] PFEIFFER M, SCHAEUBLE M, NIETO J, et al.From perception to decision:a data-driven approach to end-to-end motion planning for autonomous ground robots[C]//Proceedings of International Conference on Robotics and Automation.Washington D.C., USA:IEEE Press, 2017:1527-1533.
[13] TAI L, LIU M.Towards cognitive exploration through deep reinforcement learning for mobile robots[EB/OL].[2021-09-10].https://arxiv.org/pdf/1610.01733.pdf.
[14] CHEN Y F, EVERETT M, LIU M, et al.Socially aware motion planning with deep reinforcement learning[C]//Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems.Washington D.C., USA:IEEE Press, 2017:1343-1350.
[15] LAKSHMANAN A K, MOHAN R E, RAMALINGAM B, et al.Complete coverage path planning using reinforcement learning for tetromino based cleaning and maintenance robot[J].Automation in Construction, 2020, 112:1-10.
[16] YANG Y, LI J T, PENG L L.Multi-robot path planning based on a deep reinforcement learning DQN algorithm[J].CAAI Transactions on Intelligence Technology, 2020, 5(3):177-183.
[17] XIN L, SONG W, CAO Z G, et al.Multi-decoder attention model with embedding glimpse for solving vehicle routing problems[EB/OL].[2021-09-10].https://arxiv.org/abs/2012.10638v1.
[18] LI J W, XIN L, CAO Z G, et al.Heterogeneous attentions for solving pickup and delivery problem via deep reinforcement learning[J].IEEE Transactions on Intelligent Transportation Systems, 2022, 23(3):2306-2315.
[19] LI J W, MA Y N, GAO R Z, et al.Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem[EB/OL].[2021-09-10].https://arxiv.org/abs/2110.02629v1.
[20] WU Y X, SONG W, CAO Z G, et al.Learning improvement heuristics for solving routing problems[EB/OL].[2021-09-10].https://arxiv.org/abs/1912.05784.
[21] CAI Y W, ZHAO H, LI M D, et al.3D real-time path planning based on cognitive behavior optimization algorithm for UAV with TLP model[J].Cluster Computing, 2019, 22(2):5089-5098.
[22] 吉根林.遗传算法研究综述[J].计算机应用与软件, 2004, 21(2):69-73 JI G L.Survey on genetic algorithm[J].Computer Applications and Software, 2004, 21(2):69-73.(in Chinese)
[23] HUANG H C, TSAI C C.Global path planning for autonomous robot navigation using hybrid metaheuristic GA-PSO algorithm[C]//Proceedings of SICE Annual Conference.Washington D.C., USA:IEEE Press, 2011:1338-1343.
[24] STENTZ A.Optimal and efficient path planning for partially known environments[C]//Proceedings of IEEE International Conference on Robotics and Automation.Washington D.C., USA:IEEE Press, 1994:203-220.
[25] 付振秋, 季光, 杨瑛.改进型蚁群算法的AUV三维路径规划[J].舰船科学技术.2018, 40(19):72-77. FU Z Q, JI G, YANG Y.AUV three-dimensional path planning method based on improved antcolony optimization and particle swarm optimization[J].Ship Science and Technology, 2018, 40(19):72-77.(in Chinese)
[26] NAZARAHARI M, KHANMIRZA E, DOOSTIE S.Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm[J].Expert Systems with Applications, 2019, 115:106-120.

选择文件类型/文献管理软件名称

选择包含的内容