第38卷 第9期 V_01.38 ・计算机工程 2012年5月 May 2012 NO。9 Computer Engineering 开发研究与设计技术・ 文章编号:100 428(2o12)09-__o262__03 文献标识码:A 中圈分类号:TP311.52 城市作战仿真中CGF Agent战术路径规划 彭辉,贺毅辉,姜峰,王勇 (解放军理工大学指挥自动化学院,南京210007) 摘要:在城市作战仿真中,提出一种单CGF Agent战术路径规划方法。分析Agent路径规划过程中需要考虑的战术任务要求,建立距离 代价与战术代价相结合的综合路径评价模型,设计基于改进概率路标图的战术路径规划方法。实验结果表明,该方法进行100次实验的平 均规划时间为72.94 ms,最大和最小规划时间分别为110 ms和15 ms。 关健词:计算机生成兵力;智能体;自主行为;路径规划;概率路标图 Tactical Path Planning for CGF Agent in Urban Combat Simulation PENG Hui,HE Yi-hui,JIANG Feng,WANG Yong (InstituteofCommandAutomation,PLAUniversityofScience andTechnology,Nanjing210007,China) [Abstract]In this paper,the tactical path planning method for Computer Generated Force(CGF)Agent in urban combat simulation is proposed.It analyzesthetactical requirementofAgentpathplanning,andthemathematicsmodel ofpath optimizationbasedOnthe distance cost andtactical COSt is established.A Probabilistic Roadmap Method(PRM、一based tactical path planning ̄amework is presented.Experimental results show that the average planning time is 72.94 ms,the maximum and minimum planning time are 1 10 ms and 15 ms. [Key wordsl Computer Generated Force(CGF);Agent;autonomous behavior;path plnniang;probabilisti ̄roadmap DOI:10.3969/j.issn.1000—3428.2012.09.080 1概述 作战实体的仿真建模是作战仿真系统研究的难点和关 键,它直接决定仿真结果的可靠性和作战训练的有效性。通 常的计算机生成兵力(Computer Generated Force,CGF)模型包 括物理模型和行为模型2个部分…。其中,自主行为建模作 为CGF系统建模的核心部分,是连接仿真系统中其他模型的 桥梁和纽带,决定系统行为的有效性和真实性。路径规划是 PRM)方法基础上,通过引入战术评价信息,提出一种城市作 战仿真中CGF Agent战术路径规划方法。 2问题分析与建模 2.1路径规划的战术要求 在仿真过程中,如果仅要求CGF Agent从任务出发点到 达任务结束点,那么寻找出一条通过该区域的最短无障碍路 径即可满足要求。然而,在真实的作战过程中,作战单元除 了要尽快地到达目标点,通常还要求在行进途中避免被敌方 侦查或攻击,从而最大限度的保证自身安全,这就区别与普 通的路径规划问题,而是一类战术路径规划问题,定义如下: 定义(战术路径规划)所谓CGF Agent战术路径规划,是 CGF Agent自主行为的重要体现,特别是在面向城市作战环 境(Military Operations on Urbanized Terrain,MOUT)的分队战 术仿真系统中,由于作战环境的复杂性,为使仿真中的CGF 作战行为显得更加真实和智能化,需要分别为分队中每个 CGF Agent实时规划出战术路径,因此单个CGF Agent的路 径规划问题成为目前作战仿真的一项重要内容。 指在战场环境下,综合考虑环境地理信息和敌方威胁信息, 在各种约束条件下,寻找从任务出发点到任务结束点的安全 针对Agent路径规划问题,目前国内外已经开展较为广 泛的研究。文献[2]综合分析在ModSAF系统中采用的多种路 路径,所找到的路径应满足一定的作战任务的战术要求,或 者要满足某种性能指标函数的度量。 通常,实现战术行为可以采用2类策略:隐蔽和掩护。 隐蔽是指作战单元借助于光线、噪音,以及自身的伪装实现; 掩护则是指作战单元在行动中相互依赖或依靠地形地物特征 来保护自身安全。因此,CGF Agent在规划其作战路径时, 径规划方法,包括单元分解一A 搜索方法、可视顶点法、势函 数法等,并比较上述方法的优劣和应用范围;文献[3]针对分 队Agent的路径规划问题,提出战术走廊的概念,并采用路 标图法(roadmap)求解;文献[4]初步研究CGF Agent借助掩体 的战术式路径规划问题,讨论一种基于环境预先设置路点 需要考虑以下3个方面的基本战术要求 J: (1)尽量利用障碍物的掩护。 (2)尽量少地暴露在敌方火力覆盖范围内。 基金项目:江苏省自然科学基金资助项目(BK20l1120,BK2010130) (waypoint)以及导航网络的规划方法,但没有给出具体实现。 然而,现有的CGF Agent路径规划存在一定不足,即大部分 方法在进行规划时,仅考虑路径的距离信息以及威胁避障信 息,没有考虑路径的战术要求,所规划出来的路径比较单一, 常是距离最短路径,这样使得CGF的智能行为不够丰富,不 能有效反映作战过程中Agent战术变化的行为特点。 本文主要针对城市作战仿真中的CGF战术规划问题开 展研究,在基本概率路标图(Probabilistic Roadmap Method, 作者简介:彭辉(1980-),男,讲师、博士,主研方向:协同控制, 分布式优化,Agent仿真;贺毅辉,教授、硕士;姜讲师、硕士 峰、王勇, 收稿日期:2011—08—15 E—mail:penghui.ph@gmail.com 第38卷第9期 彭辉,贺毅辉,姜峰,等:城市作战仿真中CGFAgent战术路径规划 263 (3)避免穿越己方的火力覆盖范围。 上述战术要求使得CGF Agent在进行路径规划时需要进 一步考虑的因素有:(1)敌方可能威胁的位置与分布;(2)环境 障碍物的分布和遮蔽效果;(3)敌方的视线范围(Line ofSight, LOS);(4)敌方的火力覆盖范围(Line ofFire,LOF)等。在综合 考虑敌方的位置和他们的火力线等战术要素后,一个理性的 Agent应该采取紧贴障碍物或者避开敌方威胁地域绕道行进 等方式来选择路径,这就与传统的最短路径规划问题存在较 大差别。 2.2威胁建模 战术路径规划的重要前提是对敌方威胁进行分析和建 模。由于城市作战仿真是一个对抗环境,CGF Agent在执行 任务过程中会受到来自敌方作战力量的攻击,因此Agent在 选择不同的路径运动时,所受到的火力威胁是不同的。显然, Agent所受到的威胁程度与其自身的空间位置、敌方威胁位 置、敌方数量以及敌方火力性能等因素紧密相关。 假设在空间中有Ⅳ 个敌方威胁,Agent位于空间某点 ( ,J,)处受到来自第七个敌方火力威胁的威胁值为wk( ,Y) k=1,2,…,Ⅳ ,则威胁程度值的计算公式如下: d Ⅵ ( , ) 嚣Fk r k<d< (1) 0 d> 其中,d为坐标点( , )到第k个敌方威胁距离; 为第k个 敌方威胁的火力覆盖(LOF)半径;r k为敌方威胁的视线(LOS) 范围; 为火力威胁最大强度参数。易知,Agent与敌人k 的距离越小,所受到威胁越大。当Agent被敌方发现时,所 受到的火力威胁最大,如果没有被敌方发现,但在敌方火力 打击范围内,则仍存在一定的危险。根据式(I)进一步可得到 Agent位于点( , )处时受到所有Ⅳ 个敌方威胁的综合威胁 程度值为: Ⅳ w(x,y)=∑ (x,Y) (2) =l 2.3 战术信息综合路径评价 区别于最短路径规划,战术路径规划需要定义综合的路 径评价指标。因此,在考虑战术行为的最优路径时,实际的 路径代价由距离代价和敌方威胁代价来综合决定: (1)距离代价DisCosti 。即Agent在2个路径点之间运动 的能量消耗,与路径的长度有关以及Agent的自身能力状态 相关。假设Agent以速度v运动,某2个路径点( , )和 ( ,, ,)之问的路径 .,的长度为 l『,则Agent在该段路径 ,, 运动所花费代价为: DisCosti,J=a'xf(v, ,,) (3) 其中, 为常数;函数f(v,‘,)对应于不同Agent的能量消耗 曲线。例如对单兵来说,即为其体能消耗曲线。 (2)威胁代价ThreatCosti,。即Agent在2个路径点(Xi Y ) 和(X,,y )之间的路径 上运动时暴露在敌方火力下的威胁 程度,根据式(2),本文采用平均威胁程度来定义,如下: Threa,Cos,。 : w(xt,Yi)+w(xj,y ̄) (4) .——,。。 2 由上述可知,距离代价和威胁代价分别趋于搜索最短路 径和最安全路径,通过线性组合可将其转换成单目标决策问 题,因此,Agent在路径 ,上的综合路径代价可写为: C0 ‘,= _ThreatCos6,+(1一 )_DisCost ̄(5) ,,,, 其中,0≤ ≤1的取值体现Agent的战术倾向; =1表明 Agent只追求路径的安全性; =0表明Agent不考虑安全因 素,仅追求路径的距离最短。 若进一步假设一条完整战术路径上包含有Ⅳ个路径点, 即{(t,Yi)li=1,2,…,N},则此完整路径可以表示为:P= { …, …,P ̄ },此时,路径P的综合代价评估值表 示为: N I F=∑Cost. I (6) l=I 通过以上形式化可看出,若综合代价评估值F越低,则 路径P就越优,表明所选路径的距离相对较短且路径所经过 区域的威胁程度较低。因此,Agent战术路径规划的优化目 标就是使得路径的综合代价评估值达到最小化,即: ,N一】 、 minF=minI∑Cos6 J (7) 3基于改进PRM的战术路径规划方法 3.1基本PRM方法 文献[6]提出的概率路标图方法是一种基于随机采样的 路径规划方法。最初主要针对高维位形空间中的机器人运动 规划问题,近年来逐渐在机器人路径规划_,J、无人机航路规 划 J等领域得到广泛应用。PRM方法的路标图在规划空间中 采用某种概率方法构造。其基本思想如下:首先在规划空间 区域中以某种概率随机采样,然后按照特定的规则将这些采 样点连接起来,形成概率路标图,此时,空间中的路径规划 问题就转化为概率路标图上的搜索问题,该方法的理论基础 是概率完备性,即在路径规划空问中以某种概率随机采样, 随着采样点数量的不断增加,问题求解(找到解或无解)的概 率将不断趋向于1。基本PRM方法示意图如图1所示。 I 障碍物 I 1 规划 起点 图1基本PRM方祛示意图 由图1可知,基本的PRM方法在总体上为2个阶段:离 线学习阶段和在线搜索阶段 j,具体为:(1)学习阶段。首先 以随机方式在自由空间中进行采样,构成路标点集合V;然 后由局部规划器(1ocal planner)为V中的每个路标点寻找其邻 居节点,如果两点之间距离小于某一个闽值并且可以实现无 障碍连接,那么建立节点之间的连接,从而形成路标图中的 自由路径集合E。经过学习阶段后,建立起来的路标图实际 上构成了一个无向图G=(V,E)。(2)路径搜索阶段,首先将规 划起点和终点加入路标点集合 ,为其寻找邻居节点并建立 局部连接,这样在无向图G中形成若干个连通图。如果规划 起点和终点在同一个连通图中,那么必然存在一条可行路 径,此时可以采用某种搜索算法,如A 算法、Dijkstra算法 在图G中搜索寻找从起始点和目标点的优化路径。 3.2基于改进PRM的战术路径规划框架 传统PRM方法在应用于机器人路径规划时,路径搜索 264 计算机工程 2012年5月5日 的优化指标是寻找到目标点距离最短的路径,即图G中各路 标点之间仅存在距离代价。 对于在城市作战环境下的CGF Agent来说,由于敌方威 胁的存在,路标点之间除了距离代价外,还存在威胁代价, 因此基于第2节的路径规划问题建模和综合路径代价函数, 在基本PRM方法基础上,为进一步反映路径规划的战术要 求,基于改进PRM的战术路径规划方法框架如图2所示。 _l…………一lL…………一 圈2基于改进PRM的战术路径规划方法框架 相对于传统PRM算法,本文的战术路径规划方法在以下 2个方面进行扩展: (1)在PRM构图阶段,将敌方威胁处理为自由区域,和 其他自由区域一起进行采样并建立连接关系形成节点连接关 系图,在距离代价基础上,通过引入战术代价计算,形成综 合路径代价图。 (2)在进行航路搜索时,依据的不仅是路标点之间的距 离,而是考虑距离代价和战术威胁代价后的综合路径代价。 3.3算法描述 综合上述设计,基于改进PRM的CGF Agent战术路径 规划算法的详细步骤描述如下: Stepl令迭代次数k=1,最大迭代次数为 rm 。 Step2若k<K…,则在规划区域内进行随机采样,得到 路标点集合V;否则,返回规划失败。 Step3将规划起点和规划终点添加到路标点集合。 Step4根据区域内的障碍分布,建立路标点集合V中各 个节点之间的连通关系,得到节点连接关系图G。 Step5根据威胁分布,计算图G中每个节点的距离代价 和威胁代价,得到综合路径代价图G 。 Step6采用Dijkstra算法搜索综合路径代价图G ,如果 成功,则转到Step6;否则,令k:k+1,返回Step2。 Step7如果规划成功,那么返回一条从起点到终点的代 价最小路径。 由于PRM方法本质上是一种随机规划算法,因此在算 法中设置迭代上限 …,增加了判断搜索是否成功的环节, 决定PRM方法能否成功的关键是要保证规划起点和规划终 点位于同一个连通图中。 4实验结果与分析 为验证本文方法的有效性,在Windows环境下建立了 CGF Agent战术路径规划仿真环境,采用Visual Studio 2008 环境实现编程。其中,路径规划区域分为400 ̄400的离散网 格, =0.7,仿真实验结果如图3所示。图3(a)显示了仿真 实验的一个典型二维城市街道场景。其中,CGF Agent位于 上方的起点,需要穿越该街道区域到达右下方的出口终点; 图3(b)显示了作战环境中的初始态势,存在2个敌方威胁, 其火力威胁范围如图中浅色区域所示;图3(c)显示了根据仿 真街道环境所构造出的概率地图;图3(d)显示了在上述概率 地图基础上,采用Dijkstra搜索得到的规划结果,规划时间 为93 ms,其中,Path1为传统的距离最短路径,Path2为考 虑了敌方威胁火力分布的战术路径。可以看出,Pathl距离较 短,却简单直接地穿越敌方火力覆盖区域,暴露在敌火力威 胁下的路径长度为197,而Path2路径更长,能使Agent更好 地利用障碍物的遮挡,暴露在敌火力威胁下的路径长度为 124,相比Path1暴露时间要短,能更有效地规避敌方火力的 威胁,体现出战术动作的特点。 (c)概率地图生成 (d)路径规划结果 图3仿真实验结果 为了验证算法的时间性能,在上述实验的条件下进行 100次仿真实验,统计每次规划所花费的计算时间,规划时 间统计结果如图4所示。本文实验运行环境为Intel 2.4 GHz 主频,2GB内存的普通PC机,PRM采样点数为300,规划 地图大小400 ̄400。从实验结果可以看出,100次仿真实验的 平均规划时间为72.94 ms,其中,最大规划时间为110 ms, 最小规划时间为15 ms。从规划时间代价角度可知,本文方 法能够满足CGF Agent在线路径规划的实时性需求,是一种 快速有效的战术路径规划方法。 实验编号 图4规划时问统计结果 5结束语 本文提出一种城市作战仿真中CGF Agent战术路径规划 方法。采用概率地图对城市战场环境进行拓扑化描述,有效 地减小了规划空间的复杂程度,使得路径规划能够满足实时 仿真的时间要求,在此基础上,通过在传统距离代价计算基 础上引入战术代价,使得路径规划结果能更好的利用障碍物 遮挡,从而更有效地规避敌方火力的威胁,反映战术任务的 特点和要求。实验结果表明该方法的有效性。今后可以将路 标点构造由二维空间扩展到三维空间,通过改进本文方法实 现动态战场环境中的三维战术路径规划。 (下转第267页) 第38卷第9期 韦金芬,宋保维,毛昭勇:多阶段实验数据融合的Bayes可靠性评定模型 267 用先验矩来确定( , )的联合共轭先验分布中的超参数 、 点估计和置信度下限如表1所示。 、 、 。 表1不同分位蒙条件下的点估计和置信度下限 第1阶段的实验信息为: (64.324 8,58.956 4,57.655 9, 61.659 7,59.496 1,61.095 2,59.482 3,59.414 3,58.790 3, 58.036 l,58.379 3,57.982 7,57.112 1,63.070 5,62.649 6)。运 用Bootstrap方法求出 的均值尼=60.2760和方差 = 由表1可知,对同样的多源信息数据,采用本文模型和 3.1484, 的均值 =1.4807和方差 =o.8407。这样就 文献【6]模型所得Bayes点估计均接近参数的真值,且接近程 可求得( , )的联合共轭先验分布中的超参数: 度一致。同时可以看到,2种模型对应的Bayes下限值也非 : =60.2760 常接近。这足以验证本文模型的有效性、合理性。 4结束语 =要-o.4 。s 本文基于多阶段实验数据融合数据方法,提出一种可靠 性Bayes评定模型。仿真结果表明,该模型简便易行,实现 =[ s s 思想符合人们对未知参数的认识从无到有,从少到多的循序 渐进的过程,且实验数据在各个阶段是个逐步精化的过程, : :1.1593 由此可见,其在可靠性实验分析等工程研究领域具有较好的 这样,就可得到第2阶段实验数据的先验分布: 应用前景和推广价值。 ( , )~N—IGa(9.2158,60.2760,1.1593,0.4703) 参考文献 结合第2阶段实验数据 (57.697 8,61.814 8,60.189 6, 【1】Aggarwal P.Bayes Predictor of One—parameter Exponential 61.009 8,60.714 9,59.792 5,62.014 6,59.099 2,59.222 6, 57.747 7,6 1.656 0,62.834 5,62.452 7,59.945 3,62.408 4, Family Type Population Mean Under Balnaced Loss Function[J]. 61.707 1,60.953 8,58.048 6,56 843 4,59.366 5)。根据Bayes Communications in Statistics Theory and Methods,2006,35(8): 理论,可得到第2阶段实验信息的后验分布,即: 1397一l408. Ⅳ一IGa(24.2158,59.8859,2.3945,15.4703) 【2】AliHA,EldesoukyAI,SalehAI.ANovel Strategyfor aVertical 可得到 和 的点估计 =59.8859, =2.6101。这 Web Page Classiifer Based on Continuous Learning Naive Bayes 样就获得现场实验数据的先验分布: Algorihtm[J].International Journal of Computers and Applications, 2007,29(3):259-277. ~u(/4, )=N(59.8859,2.6101) [3]张金槐,唐雪梅.Bayes方法[M].长沙:国防科学技术大学出版 最后,结合现场实验数据Z(57.420 4,58.617 4,56.610 3, 社,1990. 59.523 8,58.436 0,58.538 1,57.618 8),就可获得 的后验分 【4】 张士峰,蔡洪.Bayes分析中多源信息融合问题【J].系统仿真 布 l z)=N(58.428,0.468)。 学报,2000,12(1):54—56. 由文献【6】采用基于第2类极大似然估计原理(ML-II)的 【5]张湘平.小子样统计推断与融合理论在武器系统评估中的应用 多源验前分布融合方法所获得的后验分布为: 研究【D].长沙:国防科学技术大学,2003. N(58.473,0.466) [6】冯静,周经伦,孙权.Bayes分析中多源验前信息融合的 下面给出了采用不同方法的Bayes点估计和置信度分别 MLjI方法[J】_数学的实践与认识,2006,36(6):142—145. 为0.8、0.85、0.9时的Bayes下限R ,不同分位数条件下的 编辑刘冰 (上接第264页) 参考文献 [5]Remco S,William S,Arjen B.Killzone’s AI:Dynamic Procedural [1】Mikel D P.Computer Generated Forces in Distributed Interactive Combat Tactics[C]//Proc.of the Game Developers Conference. Simulation[EB/OL].(2010一l1-21).http://it4sec.how2manage.com/ Los Angeles,USA:[s.n.],2005. bg/node/1 579. 【6】Kavrak L,Svestka P,Latombe J C,et a1.Probabilistic Road Maps 【2】Douglas A R,MaR K'Paul D.Tactical Movement Planning for ofr Path Planning in High—dimensional Configuration Spaces[J]. Individual Combatants[C]//Proc.of the 9th Conference on IEEE Transactions on Robotics nad Automation,1996,l2(4):566- Computer Generated Forces and Behavioral Representation. 580. Orlnado,USA:[s.11.】,2000. [7】Liu Changan,Chang Jingang,Liu Chunyang.Path Plnaning for 【3】Arno K,Michiel R,Mark H O.Tactical Path Finding in Urban Mobile Robot Based on all Improved Probabilistic Roadmap Environments[EB/OL].(2010—10—21).http://www.cs.uu.nl/centers/ Method[J].Chinese Journal ofElectronics,2009,l8(3):395—399. give/movie/index.phP. 【8】孙汉吕,朱华勇.基于概率地图方法的无人机路径规划研究【J]. [4】贺毅辉,赵洲.基于战术背景的路径规划的研究[J].电脑知 系统仿真学报,2006,18(11):3050—3054. 识与技术,2008,3(7):l512—1514. 编辑刘冰