改进烟花算法在虚拟士兵路径规划中的应用

樊永生,连云霞,杨 臻

(中北大学 a.大数据学院; b.机电工程学院,太原 030051)

0 概述

路径规划是虚拟作战技术[1]研究中的重要领域,利用寻路算法使虚拟士兵以最小代价从起始位置到达目标位置[2],从而提高虚拟士兵的存活率。文献[3]将感知模型与路径规划相结合,能够提高虚拟士兵路径规划的效率和能力,对路径规划行为进行精确模拟。文献[4]通过A*算法实现在三维场景中获取两点之间的寻路路线。文献[5]将A*算法应用到虚拟船员路径规划当中,实现虚拟船员的路径规划。但A*算法的复杂度和寻路能力与栅格细化程度相关,且所规划的路径转折频繁、效率较低,不符合真实士兵的前进方式。蚁群算法[6]、遗传算法等其他智能算法存在搜索机制不佳、容易陷入局部最优等问题,因此,研究虚拟士兵的路径规划问题具有重要意义。作为具有爆炸式搜索机制的新型群体智能算法,烟花算法在求解复杂优化问题方面有较好的性能。文献[7]将烟花算法融入到免疫遗传算法中,形成烟花爆炸式免疫算法。文献[8]提出线性权重法与烟花算法结合的混合算法,解决了多目标无人机任务规划问题。但烟花算法的变异操作会导致烟花个体变成“不连续”路径。

本文将可视图法、士兵视觉模型与改进烟花算法相结合，提出一种基于改进烟花算法的路径规划算法。使用Unity3D游戏引擎将路径规划过程可视化，并将所提算法与烟花算法、A*算法进行比较分析。

1 虚拟士兵及环境建模

1.1 士兵三维模型和动作模型的建立

虚拟士兵是作战仿真的关键支撑技术。在作战仿真中,依据人的真实骨骼架构与骨骼关联,构建以骨骼为基础、具有高还原度的虚拟士兵模型[9],如图1所示。

图1 士兵骨骼架构

虚拟士兵的基础动作建模包括站立、站着跑、蹲下瞄准和开枪,如图2所示。

图2 虚拟士兵3种基础动作建模

1.2 士兵视觉模型的建立

虚拟士兵视觉模型的设计主要体现视觉的有限性特征,仿真人眼使行为更加逼真。视觉模型通过对感知对象是否在虚拟士兵视觉范围内的可见性分析,结合记忆脚本模块之前的信息判断对象是否可见,最终生成感知能力。

模型的建立分为以下步骤:

1)确定虚拟士兵的视觉范围;

2)判断敌方目标或障碍物威胁是否在视觉范围之内;

3)分析可见性;

4)结合记忆脚本判断敌方目标或障碍物威胁是否可见;

5)生成感知能力。

根据人眼视度,即人的肉眼可视角度的度数,水平视度120°,纵向视度60°构建士兵视觉感知模型触发器,当有敌方目标或障碍物威胁进入该区域时即被触发器识别,如图3所示。

图3 虚拟士兵视觉触发器

1.3 平原环境地形建模

虚拟士兵在平原环境中进行对抗,可在地形中设置有轮胎、障碍墙等隐蔽物。可视图法[10-11]建模时间短,占用储存空间小,因此,使用可视图法处理地形数据。

以障碍物为基础,用近似凸多边形表示障碍物,构建电子地图。然后把虚拟士兵的出发位置、障碍物多边形的顶点以及目标位置用线段连接,并保证这些线不会与障碍物相交,这些线即为“可视线”,而构成“可视线”的端点即为“可视点”,形成一张“可视图”,采用搜索算法寻找从起始点到目标点的最优路径。通过可视图法建立的地图模型如图4所示,在障碍物的顶点中确定最优的、最适合放到路径中的顶点,由顶点的连接线段穿行于空间中的多边形障碍物之间,从起始点通往目标点的任何一条最短路径,都是一条多边形路径,其中,内部节点是地图模型中的顶点。

图4 地图模型

2 改进烟花算法

2.1 改进烟花算法介绍

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

烟花个体变异时产生的变化是随机的,因此可能会出现“不连续”路径。本文在烟花算法中加入插入和删除操作,一方面可以消除“不连续”路径,另一方面可以对路径进行进一步优化。同时,将士兵视觉模型与算法结合,加强士兵对环境威胁的判断,有利于规划出更加安全的路径。

烟花算法使用适应度度量烟花路径个体或火花路径个体可能达到或是接近最优解的优良程度,而改进烟花算法会根据适应度以及火花路径个体到最优个体的距离来决定其是否保留。在爆炸中每个烟花路径个体产生的火花数量Si为:

(1)

其中,Si表示第i个烟花路径个体产生的火花路径个体个数,m用来限制产生的火花路径个体总数,Ymax是当前种群中适应度值最差路径个体的适应度值,f(xi)表示路径个体xi的适应度值,ε是绩效常数,以避免出现分母为零的情况。

采用式(2)限制每个烟花路径个体产生火花路径个体的数量,即:

(2)

每个烟花路径个体的爆炸幅度Ai如式(3)所示。

(3)

路径个体经过位移操作和变异操作,使用映射规则保证变异后的路径个体处于可行域内,以避免算法陷入局部最优。

位移操作是对烟花路径个体的每一维进行位移,其表达式如式(4)所示。

(4)

其中,rand(0,Ai)表示在幅度Ai内生成的均匀随机数。

为进一步提高种群的多样性,在改进烟花算法中引入了高斯变异。在烟花种群中随机选择烟花路径个体,对其选择一定数量的维度进行高斯变异。高斯变异如式(5)所示。

(5)

变异操作会使路径出现间断(相邻两路径点间的连线穿过障碍物的内部),引入插入操作处理间断路径。删除操作是用来删除烟花或火花之中2个一样的路径点之间的冗余路径点以及相同路径点中的1个,简化路径。

2.2 改进烟花算法流程

改进烟花算法的流程如图5所示。

图5 改进烟花算法自动寻路流程

2.3 改进烟花算法在路径规划中的应用

本文改进烟花算法在路径规划中的应用如下:

1)构建适应度函数。对抗仿真需要考虑路径的长短和隐蔽需求,路径中某一线段的代价值为:

pij=(1-θij)eij

(6)

其中,eij表示从i节点到j节点的线段长度,θij为隐蔽系数,其值在0到1之间,值越大则表示隐蔽程度越好。路径的代价值可表示为:

(7)

其中,n表示这条路径通过路径点(去除起点和终点)的数量。在路径规划过程中,需要优先考虑路径代价值最小,因此个体适应度评价函数如式(8)所示。

(8)

其中,Pmax是一个合适且相对较大的数。

2)在战场中虚拟士兵根据视觉感知判断路径点是否存在危险。对于障碍物和威胁,士兵将信息记录下来并与记忆脚本进行对比,如果记忆库没有该威胁,则加入,由此做出决断。给定对抗仿真的初始和目标位置,对于存在危险的路径点,直接排除在外,然后将剩余的路径点作为路径规划的路径点,把起始点、目标点和中间路径点用线段连接起来。算法初始化,将连接出发点和目标点的所有线段作为解空间,在解空间中随机生成N个烟花,将最优烟花的爆炸半径设置为整个搜索空间,每一个烟花个体代表一条路径。路径由路径点组合形成。

每个烟花个体使用符号标记,设共有n个路径点和m条线段,假设起始点为S,目标点为G,用wi(i=1,2,…,n)表示路径点,一条具体的路径P:S→w12→w16→w23→G可以用节点序列{12,16,23}表示,序列的数字是路径点wi的下标,其中不包括起点和终点。如果用bj做wi的下标,则P烟花可以表示为(wb12,wb16,wb23)。

群体中的路径个体进行位移和变异操作。位移是将所选烟花路径个体中某部分路径点序列进行如式(4)所示的位移操作。变异即引入高斯变异,在烟花路径种群中随机选择烟花,对所选烟花再选择一定数量的维度执行高斯变异。比如,该条路径中包含7个路径点,则可以选择7维中随机维进行如式(5)所示的变异。

5)判断是否需要删除操作。删除路径个体中2个一样的路径点之间的冗余路径点,同时删除两相同路径点中的1个,实现路径的简化。然后对烟花路径个体或火花路径个体节点序列的第i(i=1,2,…,n)位操作,判断两点wbj-1和wbj+1之间可否成为连续可通行路径,若是则删除wbj,否则不执行删除操作。

6)根据路径点的数量设定合适的迭代次数,计算最优路径。由于爆炸半径是趋于减小的,因此若迭代次数够大、火花数量够多,算法收敛,最优解存在,即最优路径存在。

3 仿真实现

3.1 仿真模块的功能

采用Unity3D游戏引擎[14-15]构建视景仿真系统,将路径规划过程可视化,并记录相关数据。该模块主要实现以下功能:

1)实现主控制界面与士兵路径规划界面的人性化交互。

2)士兵路径规划算法选择及初始化设置。

3)对士兵路径规划算法的应用增加枪械对抗测试,在界面实时显示作战情况,并将评估结果显示在NGUI界面中。

3.2 仿真模块的具体实现

该模块主要是将虚拟士兵路径规划过程可视化。在对抗仿真中,虚拟士兵分别使用本文算法、A*算法和烟花算法进行寻路,然后将每种算法规划的路径进行对比。

虚拟士兵在平原环境中使用某型步枪进行对抗仿真,仿真分3组进行:

1)士兵A使用A*算法,士兵B使用改进烟花算法。

2)士兵A使用A*算法,士兵B使用烟花算法。

3)士兵A使用改进烟花算法,士兵B使用烟花算法。

每组仿真中枪械参数和士兵生命数相同,有一方士兵牺牲则生命数减1,同时重新规划路径,直至生命数为0,2个虚拟士兵规划路径长度相同,但起始点和目标点的位置随机出现在地图中的固定区域。

每组仿真中虚拟士兵根据每次的路径规划到达目标位置开始对抗,双方命中率计算公式相同。为使仿真结果更有说服力,每组士兵进行50次测试。测试结束后,显示评估结果,其中,每次测试数据通过文本储存,平均路径长度、平均规划时间和命中率在界面显示,可视化过程如图6所示。

图6 虚拟士兵路径规划可视化过程

在第1组仿真测试中,参与对抗仿真的2个虚拟士兵路径如图7所示。从图7可以看出,使用A*算法寻路的士兵A与使用改进烟花算法寻路的士兵B相比,A*算法路径转弯频繁,效率较低,可得出改进烟花算法简捷高效,可行性高。

图7 第1组仿真中虚拟士兵的路径

在第2组和第3组仿真测试中,虚拟士兵使用烟花算法进行自动寻路路径如图8所示。由图8可以看出,使用烟花算法所规划的路径“穿过”障碍物的内部,路径不可行。第2组和第3组中士兵B均使用烟花算法寻路,故2组不可行。

图8 烟花算法规划路径

由3组仿真可以看出,改进烟花算法在进行路径规划时优于烟花算法和A*算法。

为了使仿真结果更加真实可靠,设计第4组仿真。士兵A使用改进烟花算法,士兵B使用A*算法,测试50次。第1组和第4组的仿真数据结果如表1所示。从表1可以看出,与A*算法相比,改进烟花算法规划的路径平均长度减少约21%,平均规划时间减少约45%,平均转弯次数明显减少。此外,利用改进烟花算法进行自动寻路的士兵在相同条件下的命中率更高,证实改进烟花算法的优越性和可行性。

表1 第1组和第4组仿真数据结果

4 结束语

针对虚拟士兵在作战仿真中路径规划存在“不连续”的问题,本文在烟花算法中加入插入和删除操作,结合视景仿真系统真实地再现对抗仿真中的路径规划。仿真结果表明,与A*算法、烟花算法相比,改进烟花算法具有较强的搜索能力,能够减少路径长度,节省规划时间,且命中率较高。该方法为虚拟战场中的路径规划提供新的思路和方法，也可广泛应用于虚拟行人视觉模型路径规划。