中国科技核心期刊      中国指挥与控制学会会刊     军事装备类重点期刊
Command Control and Simulation

Command Control and Simulation >

2025 , Vol. 47 >Issue 3: 34 - 39

DOI: https://doi.org/10.3969/j.issn.1673-3819.2025.03.004

Intelligent Unmanned Combat

An Improved Scene Adaptive PRM Path Planning Algorithm

  • YANG Jingzhao ,
  • WANG Chao † ,
  • ZHANG Yu
Expand
  • College of Intelligence Science and Technology, National University of Defense Technology, Changsha 410073, China

Received date: 2024-07-20

  Revised date: 2024-09-27

  Online published: 2025-05-28

Fold

Abstract

Aiming at the contradiction between fineness, dynamics and planning real-time when planning ground unmanned equipment paths in dynamic and complex environments, a ground unmanned equipment path planning algorithm based on risk fusion cost map and adaptive PRM is proposed. Firstly, the risk fusion cost map is established based on the multi-factor environment scene, the scene adaptive PRM probabilistic road map is constructed through the mechanisms of Gaussian convolution adaptive sampling, nonlinear probability enhancement and secondary sampling strategy, and the local planner is utilized to dynamically update the weights of the probabilistic road map, so as to realize the optimized search of global low-risk cost paths. Simulation results show that the method can better realize the balance of fineness, dynamics and real-time planning in dynamic and complex environments.

Key words： PRM; adaptive sampling; gaussian convolution

Cite this article

YANG Jingzhao , WANG Chao , ZHANG Yu . An Improved Scene Adaptive PRM Path Planning Algorithm[J]. Command Control and Simulation, 2025 , 47(3) : 34 -39 . DOI: 10.3969/j.issn.1673-3819.2025.03.004

1 问题描述

战场环境下,无人装备战术行动路径规划需要考虑通行障碍、毁伤风险、油料消耗、时间消耗等多种约束。通常的路径规划解决方案中,首先以栅格法、自由空间法、可视图等方法构建环境图形,再以搜索算法或蚁群算法、遗传等算法进行路径优化。
在城市战场等高复杂度、高分辨率的环境下,栅格法、自由空间法、可视图等方法存在搜索效率低或建图复杂度较高的问题,不利于在动态复杂的战场环境中快速使用。以概率路图算法(PRM)和快速随机生成树(RRT)为代表的路径规划技术,通过使用概率采样,明显降低了建图和搜索的算法复杂度和时间代价,在实践中表现出较好的性能[1-4]。
PRM算法在自由空间中随机采样并连接邻域点构成无向图,再通过在无向图中进行优化搜索的方式实现行动路径的规划。这种方法将连续空间中的规划问题转化到拓扑空间进行,大幅减少了路径搜索计算复杂度,同时建图过程受环境复杂度的影响也较小,在路径规划领域取得较好效果。但传统PRM算法在包含较多狭窄通道的环境中,采用的均匀采样策略使得通道内采样点数相对不足,算法收敛速度及对可行解搜索的成功率会明显下降[5-7],因此,近年来相关研究提出了多种改进PRM算法。AMATO N M提出的(obstacle-based PRM)OBPRM方法通过增加在障碍物边界处的采样点来改善PRM性能[8];HSU D通过采用RBB(randomized bridge builder)桥采样策略提高了在窄通道区域的采样密度[9];BOOR V采用高斯采样策略增大在障碍物边界处的采样密度[10];李敏提出了一种基于距离变换识别不同区域后,以不同密度进行区域采样,以提高窄通道内的采样率[11];邹善席[12]通过随机节点生成函数在自由空间生成随机节点,取代落在障碍物中的节点,在采样节点数目不变的情况下,提高自由空间中的节点数目;李琼琼[13]设计了一种以空间主轴线为参考轴的伪随机采样策略,优化采样点的生成方式。
本文针对军事场景环境复杂、通行代价多样的问题,研究设计了风险融合代价地图,并通过高斯卷积自适应采样等策略进行概率路图构建和路径规划,实现了一种改进PRM算法。该算法以较小的时间增量代价,提升了复杂军事场景环境下的路径规划性能。

2 风险融合代价地图

风险代价地图在影像地图基础上,融合了与作战相关的多语义图层,是无人装备作战规划的基础数据。风险代价地图的构建采用层次建模融合的方式,其中底层是空间层,主要是通过DEM、DSM或其他方式建立的影像地图。中层是定位层,起到连接空间层和实体的作用,该层存储未分类/已分类实体类型,及其在影像地图中的位置关系等属性。顶层为属性层,该层主要存储与作战相关的通行能力、火力等属性。

2.1 通过能力层

通过能力主要以通行速度(米/分)衡量,受地形、路面、天气状况综合影响。通过能力数据以战场速度热力图为展示手段,其基本计算式为
V=Ro×te×we
其中,Ro为路面基础通行能力(由地面铺装状态、地面障碍物状态等确定),te为地形因子(由数字高程模型DEM获取),we为天气因子(由气象侦察信息获取)。

2.2 火力威胁层

火力威胁主要以单位时间内的杀伤力衡量。在地面装备路径规划中,火力威胁计算以对地面无人车辆的毁伤概率/分钟为标准计算。考虑敌方装备对车辆的通视性、杀伤概率、射程、射速等属性,从而评价该区域受威胁程度。表1以分钟为单位,计算敌对实体的威胁。
表1 火力威胁计算

Tab.1 Fire threat factor

实体类型 装备 火力威胁
步连班 火箭筒,对车辆目标杀伤率70%,射速1发/分钟; 0.7
坦克 主炮,杀伤概率50%;射速6发/分钟, 0.984
自行迫击炮 破甲弹,杀伤概率40%;射速6发/分钟 0.953
不可通
行区域		 碰撞失能 1

2.3 风险代价融合定义

战场环境下的路径规划通常需要考虑动力消耗、时间消耗、威胁等要素,并通过手动设置权值进行设计影响要素的平衡[14]。该设计将威胁与时间独立考虑,忽略了两者的相互影响。因此,定义一种风险代价融合方法,将通行速度、燃料消耗和实体威胁等要素融合为统一的风险代价,公式如下:
Icost=min(r0+1-(1-r ) ξ υ,1)
其中,r0为栅格基础风险,反映通过一个栅格点的动力消耗等基础风险;r为当前栅格点火力威胁值,υ为当前栅格通行能力数值,ξ为风险积累调节系数(可近似取栅格代表的地理里程)。上式的启发意义在于风险会随着通行时间指数积累,并实现了单地图对多要素代价的融合。

3 改进PRM算法

3.1 传统PRM算法

传统PRM算法包含离线建图、在线查询两个阶段[15]。

3.1.1 离线建图阶段

离线建图阶段主要任务是从地图自由空间中随机选取候选节点集V,并通过最近邻搜索寻找每个节点邻居节点集合,然后经两点间路径局部规划构成地图中的边集E,最终形成概率路图G(V,E)。概率图生成算法流程伪码如下:
算法1 概率图生成算法

Alg.1 Probability graph generation algorithm

Input:
Output:
V←⌀;E←⌀;
for i=0…N_Sample do
qi←sample from Cfree
V←V ∪{qi}
for i=0…N_Sample do
U←Neighbors(qi,r,k)
for each
u∈U, in order of increasing ‖u-qi‖
if qi and u are not connected in G then
if the local planner finds a path between qi and u
E←E∪{Edge(qi,u)}
显然,PRM算法核心在于第3行自由空间采样和第11行通过局部规划生成边的过程。

3.1.2 在线查询阶段

在线查询阶段是在给定初始点和目标点的条件下,基于建图生成的概率路图G(V,E),采用Dijkstra、A*等搜索算法或蚁群等仿生优化算法,找到一条连接初始点和目标点的低代价通行路径。
由于传统PRM算法生成的概率路图中各节点由均匀随机采样生成,当环境中存在密集障碍物或较多的狭窄通道时,可能出现查询算法找到的通行路径代价较高,或者无法找到可行解的情况。

3.2 改进PRM算法

3.2.1 高斯卷积采样概率生成

传统PRM算法对所有自由空间进行均匀采样。但事实上,在开阔区域构建一个优化的路图所需要的采样点较少,而在狭窄通道或密集障碍区所需的采样点较多,这一特性促使研究者开发了各种基于环境的采样方法:桥检测、几何变换、高斯采样等。但是,桥采样忽略了其他障碍区的采样;几何变换计算量较大,且仍然要进行区域检测;高斯采样需要逐点随机进行障碍物相交判决,操作较为复杂且仅能处理“0/1”障碍,对风险积累或通行路况导致的“灰色”障碍区不能进行处理。
在风险调整代价地图中,将障碍物和风险区域同等看待,因此,在地图采样中,障碍物间的狭窄通道、风险区间/风险区内的狭窄通道,都希望能以较高的密度进行采样,以期获得更低代价的通行路径。
二维代价地图的高斯卷积模板为

F(i,j)=α· e - [ ( i - k - 1 ) 2 + ( j - k - 1 ) 2 ] / 2 σ 2

其中,α为归一化系数,k为模板尺寸。在对整个代价地图Icost进行卷积后,剔除障碍物和其他禁行区域OBS,那么障碍物和高代价区域周边的采样概率将得到提升。此时新的地图形式为

Iprob_base=(Icost⊗F)∩ O B S ¯

3.2.2 采样概率非线性提升

高斯卷积会增加障碍物、风险区等高代价区域及周边栅格的数值,这一数值处于(0,1)区间。但若将其直接用于采样概率生成,则狭窄通道区域与靠近障碍物的一般区域采样率差距不大,不能完全体现狭窄通道采样的重要性。因此,研究在Iprob_base地图上,对各点采样概率进行非线性提升并归一化,其形式如下:

Iprob= e x p [ - T × ( 1 - I p r o b _ b a s e ) ] S U M ( e x p [ - T × I p r o b _ b a s e ) ] )

超参数T决定了不同Iprob_base数值下的概率提升幅度。T越大,Iprob_base数值高的点会得到越大的概率提升,从而在一般障碍区采样概率变化不大的情况下,实现了对狭窄通道和高密度障碍区等重点区域采样率的显著提升。如图1所示,(a)为未经高斯卷积采样的代价地图,灰度越高表明代价越大(矩形区域代表建筑物,圆形区域代表各类火力威胁,条带区域代表道路);(b)和(c)分别为高斯卷积概率地图、非线性提升概率地图,灰度越高代表采样概率越高。
图1 高斯卷积采样概率地图

Fig.1 Gaussian convolution sampling probability map

从图1可以看出,代价地图经归一化高斯卷积后,提高了其狭窄、密集障碍区域和风险区域的采样概率,在此基础上,通过非线性概率调整,狭窄通道、密集障碍和风险区域共同形成通道,隘口区域采样概率得到了明显提升,并一定程度提升了风险区域内的采样概率。
显然,对通道、隘口,特别是风险区内的通道、隘口进行加强采样,可使得所建概率路图易于通过查询得到总体风险代价更小的路径。

3.2.3 二次采样策略

在PRM算法采样过程中,狭窄空间区域采样点密度影响关键路径的可行性,而自由空间区域采样点的密度则主要影响路径代价的优化程度。若通过整体采样概率调整提升狭窄空间路径规划能力,相对而言其自由空间路径寻优能力会一定程度下降。因此,算法采用一种均匀采样与固定比例概率提升采样相结合的二次采样策略,通过采样权重系数ξ控制关键区域的概率提升采样点比例,以实现算法在自由空间路径寻优能力影响较小的情况下,提升算法整体寻优能力。
二次采样策略应用步骤如下:
(1) 以基础概率P0=ξ·P1,对自由空间区域进行采样,获得概率点集V0,其中,ξ为采样权重系数,用于控制对非关键自由空间与关键区域的采样比例,使关键区域采样点数与其他自由空间采样概率达到平衡;
(2) 以高斯提升概率P1=Iprob对自由空间区域进行二次采样(此时非关键自由空间采样概率极低,采样点基本来源于狭窄通路和风险区域等),获得概率点集V0;
(3) 以合成采样点集V=V0+V1为输入,通过局部规划构成概率路图G(V,E),以供在线查询得到路径规划成果。
如图2所示,条带区域为道路,圆形区域为风险覆盖圆域,矩形为建筑区域。图a)、b)、c)分别对应占总采样数10%、30%和70%三种二次采样策略得到的采样点集V分布情况。可以看出,二次采样占比越高,采样点在窄通道和高风险区就越密集。
图2 二次采样点分布

Fig.2 secondary sampling point distribution

3.2.4 建图和查询

在完成采样点生成后,算法进行局部规划建图操作,由于采用了风险调整代价地图,算法支持多影响要素条件下的单次规划寻优。

4 仿真实验与结果分析

仿真实验平台采用Python3.8,Numpy1.19.5,Opencv4.2处理器为英特尔i5-10400@2.9GHz,内存16GB。实验地图分辨率为512×512(单位:像素,下同),采用OpenCV4.2绘制而成,其中,建筑边长为1~25随机生成,建筑数量200个;风险区域为半径10~80的随机圆形,数量10个;道路为宽10-30,贯穿整幅图像的矩形,数量为6条,道路区域通行速度为普通区域1.25倍。路径规划起始点和终点分别在地图顶部和底部1/4区域内自由空间中随机选取。图3为改进PRM路径规划结果示意图。
图3 改进PRM路径规划结果

Fig.3 Improved PRM path planning results

在包含风险区域时,风险区威胁数值设定不同,带来的路径代价优化程度也不同。因此,区分无风险区域和有风险区域两种情况进行对比分析。
(1)无风险区域实验
无风险区域实验主要考察比较传统PRM和改进PRM在不同采样点数情况下可通行解的达到率、规划路径平均里程、算法耗时,结果见表2。
表2 无风险区域实验结果

Tab.2 Results of the experiment in the risk-free area

算法 实验
次数		 采样
点数		 可行解
达到率		 平均
里程		 算法
耗时
PRM 200 950 99% 554.7 9.3 s
改进PRM 200 950 100% 543.8 9.6 s
(2)有风险区域实验
包含风险区域时,风险区威胁值设为0.4,障碍区威胁值设为1,其他区域基础风险设为0.004。实验主要考察比较传统PRM和改进PRM在不同采样点数情况下可通行解的达到率、规划路径平均代价、算法耗时,结果见表3。
表3 有风险区域实验结果

Tab.3 Experimental results of the risk area

算法 实验
次数		 采样
点数		 可行解
达到率		 平均
代价		 算法
耗时
PRM 200 950 100% 9.18 9.3 s
改进PRM 200 950 100% 8.75 9.6 s
从表2和表3可以看出,在不考虑风险区域情况下,改进算法可实现约2%的路径总长度优化,并一定程度提高可行道路求解的稳定性;在考虑风险区域时,改进算法可实现约4.7%的总代价优化。算法只在地图构建时稳定增加0.3 s耗时,不影响实时道路查询效率。

5 结束语

本文针对复杂军事场景,研究人员提出了一种改进PRM算法,包括定义构建风险融合代价地图,并设计一种高斯卷积和非线性概率提升相结合的自适应采样方法,实现对军事场景中复杂地形或威胁构成的狭窄区域、隘口地区进行自适应高概率采样,从而降低路径寻优代价。
仿真实验结果表明,相对传统PRM算法,改进算法以较小的时间增量,实现了复杂区域条件下的低风险路径规划。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
KARAMAN S, FRAZZOLI E. Sampling-based algorithms for optimal motion planning[J]. The International Journal of Robotics Research, 2011, 30(7): 846-894.

[2]
LI M, SONG Q, ZHAO Q J, et al. Route planning for unmanned aerial vehicle based on rolling RRT in unknown environment[C]//2016 IEEE International Conference on Computational Intelligence and Computing Research (ICCIC). Chennai, 2016: 1-4.

[3]
SANTIAGO R M C, DE OCAMPO A L, UBANDO A T, et al. Path planning for mobile robots using genetic algorithm and probabilistic roadmap[C]// 2017IEEE 9th International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment and Management (HNICEM). Manila, 2017: 1-5.

[4]
SUDHAKARA P, GANAPATHY V, SUNDARAN K. Probabilistic roadmaps-spline based trajectory planning for wheeled mobile robot[C]// 2017 International Conference on Energy, Communication, Data Analytics and Soft Computing (ICECDS). Chennai, 2017: 3 579-3 583.

[5]
Hsu, David, Kavraki, Lydia E, et al. On finding narrow passages with probabilistic roadmap planners[C]// Proceedings of the Third Workshop on the Algorithmic Foundations of Robotics on Robotics: The Algorithmic Perspective: The Algorithmic Perspective, Houston, Texas, USA, 1998: 141-153.

[6]
CORTES J, SIMEON T, LAUMOND J P. A random loop generator for planning the motions of closed kinematic chains using PRM methods[C]// Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No. 02CH37292). Washington.DC 2002: 2 141-2 146.

[7]
VELAGIC J, DELIMUSTAFIC D, OSMANKOVIC D. Mobile robot navigation system based on Probabilistic Road Map (PRM) with Halton sampling of configuration space[C]//2014 IEEE 23rd International Symposium on Industrial Electronics (ISIE). Istanbul. 2014: 1 227-1 232.

[8]
AMATO N M, BAYAZIT O B, DALE L K. OBPRM: an obstacle-based PRM for 3D workspaces[C]// Proceedings of the Third Workshop on the Algorithmic Foundations of Robotics on Robotics: The Algorithmic Perspective: The Algorithmic Perspective, Houston Texas, USA, 1998: 155-168.

[9]
HSU D, JIANG T T, REIF J, et al. The bridge test for sampling narrow passages with probabilistic roadmap planners[C]// 2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422). Taipei. 2003: 4 420-4 426.

[10]
BOOR V, OVERMARS M H, VAN DER STAPPEN A F. The Gaussian sampling strategy for probabilistic roadmap planners[C]// Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No. 99CH36288C). Detroit. 1999: 1 018-1 023.

[11]
李敏, 周远远, 黄鲁. 基于距离变换的PRM路径规划算法[J]. 信息技术与网络安全, 2018, 37(3): 74-79.

LI M, ZHOU Y Y, HUANG L. Distance transform based PRM path planning algorithm[J]. Information Technology and Network Security, 2018, 37(3): 74-79.

[12]
邹善席, 王品, 韩旭. 基于PRM改进的路径规划算法[J]. 组合机床与自动化加工技术, 2019(1): 1-3.

ZOU S X, WANG P, HAN X. Improved path planning algorithm based on PRM[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2019(1): 1-3.

[13]
李琼琼, 徐溢琪, 布升强, 等. 基于修正PRM算法的智能车辆路径规划研究[J]. 森林工程, 2022, 38(5): 179-186.

LI Q Q, XU Y Q, BU S Q, et al. Smart vehicle path planning based on modified PRM algorithm[J]. Forest Engineering, 2022, 38(5): 179-186.

[14]
姚远, 周兴社, 张凯龙, 等. 基于稀疏A*搜索和改进人工势场的无人机动态航迹规划[J]. 控制理论与应用, 2010, 27(7): 953-959.

YAO Y, ZHOU X S, ZHANG K L, et al. Dynamic trajectory planning for unmanned aerial vehicle based on sparse A* search and improved artificial potential field[J]. Control Theory & Applications, 2010, 27(7): 953-959.

[15]
KAVRAKI L E, SVESTKA P, LATOMBE J C, et al. Probabilistic roadmaps for path planning in high-dimensional configuration spaces[J]. IEEE Transactions on Robotics and Automation, 1996, 12(4): 566-580.

Options
Outlines

/

〈 〉