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

Application of improved D*Lite algorithm in virtual soldier path planning

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

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.