改进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算法也存在着不足。算法长度优先，所以搜索到的路径存在频繁转弯。此外，算法在路径规划中只有遇到障碍物时才重新搜索最短可行路径，因此所规划路径可能会过于靠近障碍物。此前有不少人对D*Lite算法进行了改进。张浩、孙新柱提出增强D*Lite算法[5]，针对复杂障碍物的可优化路径给出路径优化方法；张晓冉、居鹤华在D*Lite算法中引入Bresenham画线算法[6]，并通过建立分辨率高于全局障碍图的局部障碍图实时重规划机器人当前位置到目标点的最优路径。但上述方法都存在一定的局限性，并不完全适用于本文的仿真，所以本文提出一种新的改进D*Lite算法。

本文针对D*Lite算法的不足引入烟花算法，利用改进后的D*Lite算法进行路径规划。通过Unity3D游戏引擎设计了平原环境中的虚拟士兵作战仿真，使自动寻路可视化，并与张晓冉等人的改进D*Lite算法进行对比，将理论付诸实践，对路径规划问题具有指导意义。

1 地形信息建模

路径规划首先需要考虑地图建模。所研究仿真为虚拟士兵在平原环境中的作战仿真，地形中设置轮胎、墙等来模拟战场中士兵的隐蔽物。

采用栅格地图对士兵所处平原环境进行建模。将虚拟战场的三维空间转变成有限的二维空间，并将虚拟战场所占空间区域划分为固定大小的栅格，栅格的大小称为栅格粒度，其大小的确定需要考虑地图的尺寸、虚拟士兵的移速、虚拟士兵的尺寸等。如果粒度过小，计算量就会变大，降低路径规划的时效性；如果粒度过于大，会导致所规划的路径不精准，显得粗糙[7]。

把虚拟战场中的栅格映射到空间坐标系中，将虚拟士兵的活动空间离散化为在横轴上坐标从1～10，在纵轴上坐标从A～J的二维坐标系，如图1所示。endprint

栅格化后的地图模型如图2所示。

2 D*Lite路径规划算法

D*Lite算法是一种常用、高效的动态路径规划算法。该算法利用启发函数计算二维平面上节点的代价估计值，每次选择具有最小代价估计值的节点作为最佳扩展方向，并迭代搜索计算周围8个格子的代价估计值，直到找到目标位置[8]。进行二次规划时，D*Lite算法从目标节点展开扇形搜索，可以再次利用前一次路徑规划所计算出的信息，减少重复计算，提高二次规划效率。

D*Lite算法在首次路径规划时，用g（s）表示从出发点到当前位置的代价值，用启发函数h（s）表示从当前位置到出发位置的启发值。g（s）是从目标位置前往当前位置的最小代价值，在对当前位置周围8个格子做扩展时，g（s）会被重新计算，这样可以保证其为最小代价值。当计算出一个格子的rhs（s），把rhs（s）值赋给g（s），方程如下：

[g（s）=rhs（s）] （1）

式中，rhs（s）表示Right Hand Side的值，表示相对目标点的估计值。其计算公式如下：

[rhs（s）=0， s=sgoalmins′∈Pred（s）（g（s′）+c（s′，s））， others] （2）

而h（s）的计算公式为：

[h（s，sstart）=0， s=sstartc（s，s′）+h（s′，sgoal）， others] （3）

k1和k2作为优先队列排列参数，虚拟士兵在分析周围格子时会计算格子的这两个参数，将最小k1值格子选为下一格子。k1和k2的计算公式如下：

[k1（s）=min（g（s），rhs（s））+h（s）] （4）

[k2（s）=min（g（s），rhs（s））] （5）

当k1和k2相等时，路径规划完成。D*Lite路径规划算法的流程图如图3所示。

3.1 烟花算法

烟花算法是近年来提出的全局最优算法，有着良好的优化性能。烟花算法主要由爆炸算子、变异操作、映射规则和选择策略四部分组成[9]。其主要思想是通过交互传递信息（直接或间接地）使群体对环境的适应性逐代变得越来越好，从而求得全局最优解或足够接近最优解的近似解。在烟花算法中，对下一代的选择引入免疫浓度思想，在选择时与火花相似的火花越多，火花被选中的概率就越小，保证了火花的多样性[10]。

3.2 改进D*Lite算法路径规划

将烟花算法引入D*Lite算法，利用烟花算法的映射规则保证所规划路径与障碍物保持合适距离，然后通过烟花算法对关键转折点之间的路径进行平滑处理，从而实现虚拟士兵作战仿真中最优路径规划。

仿真过程中，改进D*Lite路径规划算法的流程图如图4所示。

具体步骤如下：

1） 将虚拟士兵感知到的环境格子化，如图5所示。图5中用格子S表示士兵所在的位置，也就是路径的出发位置，用格子Y表示战场中的目标地点，黑色格子表示在虚拟士兵在行进过程中遇到的障碍，划线格子表示地图上的威胁。

2） 规划最优路径。应用烟花算法中的映射规则，对可以行走的区域里的格子进行安全等级的判定，这样虚拟士兵在路径规划时就可以将过于靠近障碍物的格子判定在安全范围之外，从而优先选择相对安全的格子，实现远离存在复杂障碍物的危险区域、减少干扰的目的。然后使用D*Lite算法规划路径，所规划路径如图6所示。

3） 选取关键转折点。从D*Lite算法所规划的路径点组合中的第二个路径点开始，如果这个节点的方向和前一邻近的节点的父节点一致，那么就可以认为该相邻节点为冗余节点，删除掉这个节点并更新路径点组合；这样按顺序处理所有规划的路径节点，最后得到只包含起始点、转折点和目标点的路径点组合，称为关键转折点。

4） 构建适应度函数。烟花算法中，使用适应度度量烟花或火花在优化计算中接近于最优解的优良程度，而烟花算法会根据适应度以及火花到最优个体的距离来决定其是否保留，所以适应度会影响到算法的收敛性和稳定性，进而对算法的效率产生直接影响[11]。同时考虑路径的长短以及作战中的隐蔽需求，用式（6）来表达某一路径的代价值：

[C=12i=1nj=1npij] （6）

选取下式作为个体适应度评价函数：

[T=Pmax-C， C

式中，Pmax是一个合适的，相对较大的数。

5） 关键转折点间路径平滑。从起始点开始，选定两个相近的关键转折点作为出发位置和目标位置。将两个关键转折点间的二维空间进行再次栅格化。然后烟花算法初始化，随机生成N个烟花，每一个烟花个体代表一条路径。路径由出发位置和目标位置间的路径点连线形成。根据适应度函数计算每一个烟花的适应度的值，并根据适应度值产生火花。

6） 位移和变异操作。让群体中的每个火花经历位移操作和变异操作。位移操作是对烟花的每一维进行位移，表达式如下：

[Δxki=xki+rand（0，Ai）] （8）

式中，rand（0，Ai）表示在幅度Ai内生成的均匀随机数。为进一步提高种群的多样性，在烟花算法中引入了高斯变异[12]。在烟花种群中随机选择一个烟花，对选择到的烟花再选择一定数量的维度进行高斯变异。

通过烟花的爆炸、火花的选择，即可产生一条在两个邻近关键转折点间的近似最优路径。所有的关键转折点之间路径优化过后，即生成全局最优路径，如图7所示。

7） 检查环境参数变化。虚拟士兵前进过程中，检查路径上相关格子是否发生变化。当环境信息发生变化且这种变化对最优路径上格子的参数有影响时，D*Lite的路径规划结果以及更新的格子如图8所示。

如果虚拟战场环境信息变化，但是这种改变对已有最优路径无影响，即不会影响现有的路径规划结果，则算法不更新路径。在图7的基础上加入一个障碍格子和威胁格子，如图9所示。可知，D*Lite算法不會更新和扩展其他格子。

4 仿真测试与结果分析

4.1 仿真模块功能与实现

利用Unity3D游戏引擎构建视景仿真系统实现对虚拟士兵作战仿真过程中所规划路径的测试。设置三个虚拟士兵在同等条件下持相同枪械在平原环境中进行作战仿真，士兵A使用D*Lite算法进行自动寻路，士兵B使用文献[6]提出的改进D*Lite算法进行自动寻路，士兵C使用本文提出的改进D*Lite算法进行自动寻路，通过比较几种算法所规划路径的平滑度以及是否距离障碍物过近来判断算法的优劣性。

使用D*Lite算法规划的虚拟士兵A的路径如图10所示。由图10可知，D*Lite所规划的路径转弯频繁，与真实士兵路径相差较大。

使用文献[6]改进D*Lite算法规划的虚拟士兵B的路径如图11所示。由图11可知，该改进D*Lite算法所规划的路径虽然没有冗余转弯，但是过于靠近障碍物。

使用本文提出的改进D*Lite算法规划的虚拟士兵C的路径如图12所示。由图12可知，利用本文提出的改进D*Lite算法所规划的路径更加平滑，不存在多余转弯，并且路径与障碍物距离合适，符合虚拟士兵作战仿真对于路径规划的要求。

4.2 仿真结果分析

通过程序驱动虚拟士兵作战仿真系统对改进D*Lite算法在路径规划中的优化应用进行验证。经过多次测试，所得试验数据见表1。由数据可得，本文提出的改进D*Lite算法效率高、适应性强，搜寻到的路径转折次数明显减少且相对D*Lite算法和已有的改进D*Lite算法更优。

5 结 语

本文使用烟花算法对D*Lite算法进行改进，有效地减少了所规划路径中不必要的转弯，并解决了路径过于靠近障碍物的问题。通过对比相同条件下利用D*Lite算法、已有的改进D*Lite算法以及本文所提出的改进D*Lite算法进行自动寻路的三个虚拟士兵的路径，验证了利用烟花算法改进D*Lite算法的优越性，为虚拟士兵在虚拟战场的路径规划提供了新的思路，也增强了虚拟士兵作战仿真的实用性，为虚拟士兵班组动态对抗路径规划研究打下坚实的基础。

参考文献

[1] 张育军.虚拟现实技术在军事领域的应用与发展[J].科技创新与应用，2014（15）：290?291.

ZHANG Yujun. The application and development of virtual reality technology in the military field [J]. Technology innovation and applications， 2014（15）： 290?291.

[2] 荣明，李小龙，王钦钊，等.三维虚拟士兵建模与仿真研究[J].系统仿真学报，2012，24（4）：843?847.

RONG Ming， LI Xiaolong， WANG Qinzhao， et al. Modeling and simulation of 3D virtual soldiers [J]. Journal of system simulation， 2012， 24（4）： 843?847.

[3] 吴润方，王鲁.A*寻路算法在即时战略游戏中的应用[J].科技广场，2016（4）：164?166.

WU Runfang， WANG Lu. Application of A* routing algorithm in instant strategic game [J]. Science mosaic， 2016（4）： 164?166.

[4] 陈侠，刘冬.应用D*Lite算法的目标移动时无人机三维航迹规划[J].电光与控制，2013，20（7）：1?5.

CHEN Xia， LIU Dong. An improved D*Lite algorithm based 3D path planning for UAVs when target is moving [J]. Electronics optics & control， 2013， 20（7）： 1?5.

[5] 张浩，孙新柱.增强D*Lite在自主移动机器人安全路径规划中应用[J].河北工程大学学报（自然科学版），2014，31（2）：89?92.

ZHANG Hao， SUN Xinzhu. Application of improved D* Lite in security path planning of autonomous mobile robot [J]. Journal of Hebei University of Engineering （Natural science edition）， 2014， 31（2）： 89?92.

[6] 张晓冉，居鹤华.采用改进D*Lite算法的自主移动机器人路径规划[J].计算机测量与控制，2011，19（1）：155?157.

ZHANG Xiaoran， JU Hehua. Path planning of autonomous mobile robot using improved D*Lite algorithm [J]. Computer measurement and control， 2011， 19（1）： 155?157.endprint

[7] 李凯业.基于改进分层D*搜索算法的室内路径规划问题研究[D].合肥：合肥工业大学，2015.

LI Kaiye. Research on indoor path planning based on improved hierarchical D*search algorithm [D]. Hefei： Hefei University of Technology， 2015.

[8] 隨裕猛，陈贤富，刘斌.D?star Lite算法及其动态路径规划实验研究[J].微型机与应用，2015，34（7）：16?19.

SUI Yumeng， CHEN Xianfu， LIU Bin. D?star Lite algorithm and its experimental study on dynamic path planning [J]. Microcomputer and its applications， 2015， 34（7）： 16?19.

[9] 朱启兵，王震宇，黄敏.带有引力搜索算子的烟花算法[J].控制与决策，2016，31（10）：1853?1859.

ZHU Qibing， WANG Zhenyu， Huang Min. Fireworks algorithm with gravitational search operator [J]. Control and decision， 2016， 31（10）： 1853?1859.

[10] 张以文，吴金涛，赵姝，等.基于改进烟花算法的Web服务组合优化[J].计算机集成制造系统，2016，22（2）：422?432.

ZHANG Yiwen， WU Jintao， ZHAO Shu， et al. Optimization service composition based on improved firework algorithm [J]. Computer integrated manufacturing systems， 2016， 22（2）： 422?432.

[11] 胡庆生.烟花算法及其应用[D].西安：陕西师范大学，2016.

HU Qingsheng. Fireworks algorithm and its application [D]. Xian： Shaanxi Normal University， 2016.

[12] 陈璇，樊永生，余红英，等.自适应烟花算法在重型装备装载中的应用[J].科学技术与工程，2016，16（25）：296?300.

CHEN Xuan， FAN Yongsheng， YU Hongying， et al. Application of adaptive algorithm of fireworks in the heavy equipment loading [J]. Science technology and engineering， 2016， 16（25）： 296?300.endprint