1 引言
与平面路径规划相比，越野战场环境下的无人车路径规划主要有以下3个特点：一是地形建模困难，受地表质地、起伏坡度等因素影响，常规的二维栅格模型无法有效体现越野地形环境特点；二是约束条件多，越野战场环境下进行无人车路径规划，除了需要考虑建筑物、壕沟等阻碍通行的障碍物外，还需要考虑无人车机动性能、地表材质、地形坡度[1]、敌方火力分布和火力毁伤性能[2]等因素；三是目标函数难确定，约束条件多带来的困难就是目标函数难确定，不能直接以路径长度或者机动时间作为目标函数。因此，越野战场环境下的无人车路径规划技术受到较大挑战[3]。针对上述特点和困难，许多学者进行了不断地探索，其中吴天羿等[4]通过研究和分析地形坡度和地表属性对于车辆路径规划的综合影响，改进评价函数等方法设计了考虑坡度和粗糙度约束的路径优化算法。JI Y等[5]通过采集的越野地形信息进行随机采样路径规划，然后构建越野路径规划评价函数的方法进行越野环境下无人车路径规划。田洪青等[6]采用人工势能场算法对越野环境建模，评估车辆通行风险，提出了基于势能场模型的概率图算法。赵梦彤[7]融合通过性分级和推荐车速,设计以通过时间最短为目标的改进蚁群算法,得到兼顾通行效率、通过性和安全性的优化路径。巩绪生等[8]通过采用全局信息与局部信息、前期规划结果与当前规划相结合的方法，提出了一种越野环境下的动态路径规划方法。王坤等[9]通过建立通行禁忌表和坡度权值表，在缩小前期搜索范围的基础上实现了三维空间路径规划。
本文在以往学者研究的基础上，针对越野战场环境特点对战场地形环境和战场威胁进行建模，提出了针对越野战场环境的无人车路径规划算法，并通过仿真验证了算法的有效性。
2 越野战场环境建模
2.1 地形环境模型
越野战场环境下，对无人车路径规划有影响的地形环境因素主要有建筑物、独立石等独立突出障碍物，断崖、反坦克壕等线型障碍物，水塘、雷场等面状障碍物，以及地面坡度、地表质地等。常规的地形栅格模型以0和1分别表示某个栅格有无障碍物，无人车只能到达没有障碍物的位置，不能到达有障碍物的位置，对于某一个具体的位置，无人车能否到达是确定的。但是在立体空间中，无人车能否到达某一个具体位置是不确定的[10]，例如，图1中小方格的边长代表实地距离为1 m，方格中的数字为该方格中心位置的高程，可以看出，a21和a22虽然为相邻的两个方格，但是两者的高程差达到了10 m，无人车不可能从a21直接到达a22，而从a12直接到达a22却是可以的。为此，本文针对越野地形特点建立三维高程模型、坡度模型和地面可通性模型。
图1 高程栅格示意图
Fig.1 Diagram of elevation grid
2.1.1 三维高程模型
依据地形环境的高程信息建立战场三维高程模型，具体方法为：确定采样精度Sam，并均匀确定横向个数为n，纵向个数为m的采样点，以采样点所在位置的高程值作为采样值，得到一个m*n阶矩阵Amn，将矩阵Amn中元素aij所在行数i作为纵坐标，所在列数j作为横坐标，元素值作为垂直坐标，建立地形的三维高程模型，如图2所示。
图2 三维高程模型生成示意图
Fig.2 Generation of 3D elevation model
2.1.2 坡度模型
根据相邻采样点之间的平均坡度计算和生成作战地区的坡度模型，并用一个l(l=m*n)阶方阵Sll来表示，矩阵Sll中元素sxy的数值根据式(1)确定：
(1)
式(1)中: x和y为相邻高程采样点在矩阵A中对应元素的索引坐标值; θ1xy为采样点ay相对采样点ax的平均坡度; dxy为采样点ax和采样点ay之间的平面直线距离，如图3所示。adj(x,y)为采样点ax和采样点ay的相邻位置关系判定值，当ax与ay符合8邻域位置关系时令adj(x,y)=1，否则令adj(x,y)=0。
图3 坡度模型示意图
Fig.3 Schematic diagram of slope model
2.1.3 地面可通性模型
地面可通性模型用来描述当前位置与相邻位置之间是否能够满足无人车的直接通行条件，对无人车能否通行产生影响的因素主要有动力因素、车体结构因素和地表质地因素。其中，动力因素主要影响无人车的最大行驶坡度θ1max，车体结构因素主要影响无人车的适宜行驶地面类型、轮胎或履带抓地能力以及最大接近角θ2max、最大离去角θ3max和最大纵向通过角θ4max。为简化模型，本文认为无人车在最大设计行驶坡度范围内都满足轮胎或履带的抓地能力条件。地面可通性模型用一个l(l=m*n)阶方阵Tll表示，具体计算公式为
Txy=f(Sxy)*h(xf,x,y)*g(y)*adj(x,y)
(2)
式中: f(Sxy)是关于Sxy的函数，当采样点ax和采样点ay之间的平均坡度不大于无人车的最大设计行驶坡度θ1max时令f(Sxy)=1，否则令f(Sxy)=0。xf为路径规划过程中x的父节点位置索引坐标值，当x为起始点时，xf为x自身，h(xf,x,y)用来判定无人车由位置xf经x到达y的接近角、离去角和纵向通过角是否超过设计最大值，当未超过时令h(xf,x,y)=1，否则令h(xf,x,y)=0。g(y)为地表通行性函数，用来反应采样点ay处的地表质地能否满足无人车通行条件，当采样点ay处为河流、水塘、沼泽等无人车无法通行质地的条件时，令g(y)=0，否则令g(y)=1。adj(x,y)含义同式(1)。通过式(2)可以确定出所有采样点之间的可通过性，Txy=1表示无人车能够直接从位置x到达位置y，Txy=0表示不可到达。
2.2 战场威胁人工势场模型
越野战场环境下的路径规划，除了需要考虑地形环境和无人车机动性能外，敌方兵力兵器的分布位置和毁伤性能也是需要考虑的重要因素，在进行路径规划时，应尽量避开敌方兵力兵器的侦察范围和有效火力打击范围，而当无法避开时则尽量减少进入上述区域[11]。为此，本文根据敌方兵力兵器的分布位置和毁伤性能建立战场威胁人工势场模型，根据战场威胁人工势场模型可以确定作战区域内任意位置的受敌方威胁程度值，具体数值通过式(3)～式(6)来计算。
(3)
(4)
当lenk(i, j)≤LENk时
(5)
当lenk(i, j)>LENk时
φ2=LENk*(lenk(i, j)-LENk+1)
(6)
其中，(i, j)为任意采样点的下标值坐标，Thr(i, j)为该位置的受威胁程度值，Thrk(i, j)为敌方第k个火力点在位置(i, j)产生的威胁程度值，tar为敌方火力点数量值，LENk为敌方第k个火力点的有效射程，lenk(i, j)为敌方第k个火力点所在位置(xk,yk)与位置(i, j)之间的直线距离，αk为敌方第k个火力点的相对威胁程度值，βk为敌方第k个火力点受压制程度值，Ik(i, j)为敌方第k个火力点与位置(i, j)的通视判定函数，当两者可通视时令Ik(i, j)=1，否则令Ik(i, j)=0，通视判定方法如图4所示，φ1和φ2为距离修正常数。
图4 通视判定方法示意图
Fig.4 Intervisibility judgment
3 路径规划算法设计
3.1 A*算法基本原理
A*算法[12]是常用的路径规划算法之一，具有原理简单、搜索效率高等优点[13]，它在Dijkstra算法的基础上引入了贪婪算法，是一种依据图搜索的智能启发式算法[14]。A*算法进行路径搜索的代价函数可以表示为[15]
F(xj)=G(xi)+ΔG(xj)+H(xj)
(7)
式中： xi为父节点位置；xj为子节点位置； F(xj)为子节点位置xj的综合代价值；G(xi)为从起点Start到达位置xi的实际代价值；ΔG(xj)为从父节点xi到达子节点xj的实际代价值增量; H(xj)为从子节点位置xj到达终点End的启发代价值。
A*算法进行路径规划的基本步骤为：
1) 建立2个空列表openlist和closelist，将起始点Start加入openlist当中。
2) 遍历openlist列表中的点，找到综合代价值F(x)最小的点xi，将点xi从openlist中删除，并将点xi添加到closelist当中。
3) 按照一定规则找出所有可以从点xi直接到达的相邻点xj(j=1,2,…)，并计算出所有点的实际代价值G(xj)。
4) 如果点xj(j=1,2,…)已经存在于closelist当中，则忽略该点。
5) 如果点xj(j=1,2,…)不在openlist当中，则将该点添加到openlist中。
6) 如果点xj(j=1,2,…)已经存在于openlist当中，则比较新计算出的实际代价值G(xj)和历史记录的实际代价值G(xj)old，如果新得到的值更优，则将xi设置位xj的父节点，并更新各代价值，否则，不更新父节点和各代价值。
7) 循环步骤2)至步骤6)，直至将终点End添加到openlist当中，表示已经找到路径，或者openlist为空，表示不存在起点至终点的路径。
3.2 本文路径规划算法
经典A*算法中，G(x)一般取值为从起始点Start到达当前位置x实际已经走过的路程，H(x)一般取值为当前位置x与终点End之间的欧氏距离或者曼哈顿距离，只要起始点Start和终点End之间存在路径，经典A*算法总能找到一条从起始点到达终点的最短路径。但是在越野战场环境中，受无人车机动性能的影响，经典A*算法规划出的最短路径可能无法满足无人车的行驶要求，同时受战场敌情威胁的影响，为避免无人车暴露在敌情威胁下，往往需要绕行一定路程才能到达目标位置[16]。为此，本文在经典A*算法的基础上提出了一种针对越野战场环境的融合地形信息和战场威胁人工势场的路径规划算法，并将代价函数表示为
F(y)=G(x)+ΔG(x,y)+H(y)
(8)
μ=1+(1+|Sxy|)λ+γ*Thr(y)
(9)
其中: μ为代价值修正因子；λ为坡度影响系数，该值反映的是坡度对规划路径的影响程度，λ值越大则坡度的影响程度越大，算法对坡度越敏感，规划出的路径越平缓，越适合无人车行驶，反之，则规划出的路径起伏程度越大，越不适合无人车行驶。γ为战场威胁程度值影响系数，γ值越大则战场威胁程度值影响越大，规划出的路径受到的威胁程度越小，路径也就越安全，反之，规划出的路径越危险。为了简化算法，本文假设正负坡度对无人车机动影响程度是相同的，因此在式(9)中对Sxy取绝对值。运用本文提出的路径规划算法进行路径规划的流程如图5所示。
图5 算法流程框图
Fig.5 Algorithm flow chart
4 仿真分析
4.1 仿真条件设置
本文使用MATLAB R2016a进行编程和仿真，按照5 m的精度对某地区长750 m，宽250 m的范围进行高程采样。无人车机动参数设置见表1，敌情参数设置见表2,假设敌方不同目标相对威胁程度和被压制程度相同，算法参数设置见表3。
表1 无人车机动参数设置
Table 1 Maneuver parameter of unmanned vehicle
序号参数参数值/rad1θ1max0.558 52θ2max0.698 13θ3max0.698 14θ4max0.436 3
表2 敌情参数设置
Table 2 Parameter of enemy
序号参数参数值1敌方目标数32目标1坐标(06,20)3目标2坐标(26,05)4目标3坐标(37,20)5LEN1600 m6LEN2500 m7LEN3600 m
表3 算法参数设置
Table 3 Parameter of algorithm
序号参数参数值1λ1.32γ1003起始点坐标(03,150)4终点坐标(40,045)5Sam5 m6n507m150
4.2 仿真结果分析
根据本文构建的战场威胁人工势场模型能够得到作战区域内每个位置受到的敌方威胁程度值。图6是以灰度值图像颜色的深浅表示受到的威胁程度大小绘制的战场威胁程度平面图，图6中，颜色越深代表该位置越危险，反之则越安全。
图6 战场威胁程度示意图
Fig.6 Schematic diagram of battlefield threat degree
图7为传统A*算法、考虑坡度因素、考虑敌情因素和同时考虑坡度及敌情因素4种条件下规划出的路径结果示意图，图7中，黄色路径是使用经典A*算法规划出的路径，绿色路径是考虑坡度影响的条件下规划出的路径，白色路径是考虑敌情影响的条件下规划出的路径，红色路径是同时考虑坡度及敌情条件下规划出的路径，蓝色倒三角标记位置为敌方火力点所在位置，红色圆点标记位置为敌方可以通视位置。表4表示了4条路径的总长度、途经危险区长度、危险区长度占总长度百分比3个指标。
图7 仿真结果示意图
Fig.7 Schematic diagram of simulation results
表4 4条路径指标
Table 4 Comparison of path indicators
路径区分路径总长度/m危险区长度/m危险区占比/%经典A*算法574.85140.9024.51考虑坡度因素637.25188.2229.54考虑敌情因素588.1727.544.68同时考虑坡度和敌情因素586.2536.666.25
由图7和表4可知，在不考虑坡度及敌情影响的条件下，经典A*算法按照八邻域搜索机制以路程最短为目标进行起始点至目标点的路径规划，规划出的黄色路径虽然路程最短，但起伏程度在4条路径中最大，极不适宜无人车行驶，且暴露在敌方火力下的路段占总路段长度的24.51%，实用性最差。考虑坡度影响的条件下规划出的绿色路径整体走势较为平缓，较为适宜无人车行驶，但路径总长度较大，且暴露在敌方火力下的路段占总路段长度的29.54%，在4条路径中最危险，实用性较差。考虑敌情威胁影响下规划出的白色路径途径危险区的长度占总长度的比例最小，为4.68%，在4条路径中最安全，但路径起伏仍较大，不适宜无人车行驶，实用性较差。同时考虑坡度和敌情的条件下规划出的红色路径，总长度较短，整体起伏较小，对无人车行驶性影响较小，暴露在敌方火力下的路段占路径总长度的6.25%，综合考虑，在四条路径中实用性最高。
5 结论
提出了针对越野战场环境的无人车路径规划算法，通过仿真验证了算法的有效性。仿真结果表明：提出的地形环境建模方法能够有效保留和反映地形环境信息，规划出的路径实用性强；构建的战场威胁程度人工势场模型能够有效体现敌方火力的影响，使无人车避免或者减少遭受敌方火力打击；提出的针对越野战场环境路径规划算法能够综合地形、敌情、无人车机动性能等条件影响，规划出距离短、起伏小、安全可行的最优路线。
[1] 孙玉泽.无人轮式车辆越野路面全局路径规划与轨迹跟踪[D].长春：吉林大学,2020.
Sun Y Z.Global path planning and trajectory tracking of unmanned wheeled vehicles on terrains[D].Changchun:Jilin University,2020.
[2] 刘雅.融合战场态势的车辆路径规划方法与实现[J].指挥信息系统与技术,2021,12(03):91-95.
Liu Y.Vehicle route planning method integrated battlefield situation and its implementation[J].Command Information System and Technology,2021,12(03):91-95.
[3] 胡宇辉,王旭,胡家铭,等.越野环境下无人驾驶车辆技术研究综述[J].北京理工大学学报,2021,41(11):1137-1144.
Hu Y H,Wang X,Hu J M,et al.An overview on unmanned vehicle technology in off-road environment[J].Transactions of Beijing Institute of Technology,2021,41(11):1137-1144.
[4] 吴天羿,许继恒,刘建永.基于改进蚁群算法的越野路径规划[J].计算机应用,2013,33(04):1157-1160.
Wu T Y,Xu J H,Liu J Y.Cross-country path planning based on improved ant colony algorithm[J].Journal of Computer Applications,2013,33(04):1157-1160.
[5] Ji Y,Tamura Y,et al.Adaptive motion planning based on vehicle characteristics and regulations for off-road UGVs[J].IEEE Transactions on Industrial Informatics,2018,15(01):599-611.
[6] 田洪清,王建强,黄荷叶,等.越野环境下基于势能场模型的智能车概率图路径规划方法[J].兵工学报,2021,42(07):1496-1505.
Tian H Q,Wang J Q,Huang H Y,et al.Probabilistic roadmap method for path planning of intelligent vehicle based on artificial potential field model in off-road environment[J].Acta Armamentarii,2021,42(07):1496-1505.
[7] 赵梦彤.越野环境地面无人平台航迹规划[D].北京：北方工业大学,2021.
Zhao M T.Path planning method for ground unmanned platform in cross-country environment[D].Beijing:North China University of Technology,2021.
[8] 巩绪生,史美萍,李焱,等.越野环境建模与动态路径规划[J].计算机应用,2006(12):3039-3042.
Gong X S,Shi M P,Li Y,et al.Field environment modeling and dynamic path planning[J].Computer Applications,2006(12):3039-3042.
[9] 王坤,汪晗,吴波.基于禁忌表的最优越野路径规划[C]//第八届中国指挥控制大会论文集.北京：2020:380-385.
Wang K,Wang H,Wu B.Optimal off-road path planning based on tabu table[C]//Proceedings of the 8th China Command and Control Conference.Beijing:2020:380-385.
[10] Qi Z,Shao Z,Ping Y S,et al.An improved heuristic algorithm for UAVpath planning in 3D environment[C]//Second International Conference onIntelligent Human-Machine Systems andCybernetics.IEEE,2010(02):258-261.
[11] Liu K,Qin F,Xu H,et al.Research on path planning of gas pipeline inspection based on multi-rotor UAV[J].Journal of Chongqing Technology and Business University(Natural Science Edition),2021,38(06):34-41.
[12] Gold B，Harrel S.Computingthe shortestpath：A*searchmeetsgraphtheory：MSR-TR-2004-24[R].Redmond：MicrosoftCorporation,2003.
[13] Duchon F,Babinec A,Kajan M,et al.Path planning with modified a star algorithm for a mobile robot[J].Procedia Engineering,2014,96(07):59-69.
[14] 裴翦,李艳萍,雷雨,等.基于改进A*算法的室内路径规划算法[J].信息技术与信息化,2021(05):51-54.
Pei J,Li Y P,Lei Y,et al.Indoor path planning algorithm based on improved A* algorithm[J].Information Technology and Informatization,2021(05):51-54.
[15] Zhang Y,Li K,Huang C.Path planning method for two-dimensional code mobile robot based on improved ant colony algorithm[J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition),2021,33(03):491-497.
[16] Song R,Liu Y C,Bucknall R.Smoothed A* algorithm for practical unmanned surface vehicle path planning[J].Applied Ocean Research,2019,83(09):9-20.