改进D*Lite算法在虚拟士兵路径规划中的应用

连云霞+樊永生+余红英+杨臻

摘 要： 针对传统D*Lite算法存在的频繁转弯、过于靠近障碍物的问题提出改进D*Lite算法。该算法使用烟花算法中的映射规则将过于靠近障碍物的格子判定在安全范围之外，并使用烟花算法对D*Lite算法规划好的路径中的关键转折点间的路径进行二次规划以减少不必要的转弯。路径规划结果显示，所提出的改进D*Lite算法能够实现虚拟士兵最优路径搜索并且效率更高。仿真结果分析表明，所提出的算法比已有的改进D*Lite算法更优，可以有效减少路径中不必要的转弯，且使路径与障碍物保持合适的距离。

关键词： D*Lite算法； 烟花算法； 虚拟士兵； 路径规划； 关键转折点； 路径平滑

中图分类号： TN915.5?34； TP391.9 文献标识码： A 文章编号： 1004?373X（2018）06?0023?05

Abstract： Aiming at the problems of virtual soldiers′ frequent turning and close proximity to obstacles in the traditional D*Lite algorithm， an improved D*Lite algorithm is proposed. In the algorithm， the mapping rules in firework algorithm are used to determine the lattice too close to the obstacle beyond the safe range. The firework algorithm is used to make secondary planning for the path between the key turning points in the path planned by D*Lite algorithm， so as to reduce unnecessary turns. The path planning results show that the improved D*Lite algorithm can achieve the optimal path search for virtual soldiers and has high efficiency. The analysis of simulation results show that the proposed algorithm is better than the existing improved D*Lite algorithm， can effectively reduce unnecessary turns in the path， and keep an appropriate distance between path and obstacles.

Keywords： D*Lite algorithm； firework algorithm； virtual soldier； path planning； key turning point； path smoothing

0 引 言

隨着国防事业的迅猛发展，越来越多的高端技术被应用到军事理论与实际工作中[1]。在虚拟战场中，将寻路算法应用到虚拟士兵[2]路径规划问题中，为虚拟士兵规划出一条安全快捷的路径，使虚拟士兵模拟真实情况绕过障碍物，付出最小的代价沿着这条路径从起始位置到达目标位置[3]，从而有效提高仿真真实性。

D*Lite算法是一种高效的动态路径规划方法。文献[4]使用D*Lite算法解决了在不确定环境下目标移动时的无人飞行器三维航迹规划问题。D*Lite算法也存在着不足。算法长度优先，所以搜索到的路径存在频繁转弯。此外，算法在路径规划中只有遇到障碍物时才重新搜索最短可行路径，因此所规划路径可能会过于靠近障碍物。……