面向越野路径规划的多层次六角格网通行模型

陈占龙,吴贝贝,王 润,戴薇薇,徐道柱,马 超

1. 中国地质大学(武汉)计算机学院,湖北 武汉 430078; 2. 国家地理信息系统工程技术研究中心,湖北 武汉 430078; 3. 中国地质大学(武汉)地质探测与评估教育部重点实验室,湖北 武汉 430074; 4. 湖北省地质环境总站,湖北 武汉 430034; 5. 中国地质大学(武汉)地理与信息工程学院,湖北 武汉 430078; 6. 西安测绘研究所,陕西 西安 710054; 7. 地理信息工程国家重点实验室,陕西 西安 710054

越野环境下的路径规划起初应用于军事领域,通过对战场环境的分析,指挥机动车辆、人员在战场中的行动[1-5],随着科学技术的不断进步、人类需求的不断提高,其逐渐应用于民用交通、抗震救灾及民事生产等民生领域[6-10]。特别是近些年自然灾害增多,灾区救援争分夺秒,尽早规划出通往灾区的可通行路径对救援十分必要[11]。越野环境地域广阔,地势起伏不定,地表覆盖类型多样,目前多数研究主要考虑环境因素约束,而路径规划问题通常还存在有限的处理时间、内存和计算能力等性能约束,伴随着规划区域的扩大,通行模型数据规模增加,路径规划效率受限[12-13]。因此,如何在大规模越野场景中实现顾及多种环境因素约束的高效率越野路径规划方法就成为本文的研究重点。

通行环境场景建模是越野路径规划的基础,将复杂的野外通行环境量化为路径规划算法所需要的影响因子,便于算法感知通行环境[14]。通行模型常用拓扑法、栅格法、可视图法和构型空间法等构建,其中栅格法使用简单,可以同时对不规则的障碍物进行表达,能够处理较为复杂的越野环境情况,也便于对多种影响因素进行叠加分析计算,本文也采用栅格法构建通行模型[15-16]。栅格单元形状一般为正三角形、正四边形和正六边形3种,在越野环境中,通行对象运动没有路网的约束,前进方向多样,因此具有更多通行方向、更一致领域关系的六角格网更适用于越野通行环境场景建模[17]。通行模型格网数据规模的增大会严重影响路径规划算法的计算效率,六角格网相较于三角和四角格网,拥有更高的平面覆盖率,使用六角格网作为栅格形状可以相对减少通行模型格网数量[18]。但对于大范围的通行模型构建,格网数据规模依旧是巨大的,路径规划效率仍会陷入瓶颈。为了解决这类问题,文献[19—21]提出应用层次空间推理思想,将大规模路网进行分级或分层处理,缩减问题空间,利用“分而治之”的方法,将问题细分求解,有效缓解了路径规划在大规模路网中效率低下的问题。然而越野场景通常路网稀疏,不能依靠路网层次结构对其进行分层处理以降低数据规模,提升规划效率。据此,本文充分发挥层次空间推理思想在问题规模缩减方面的作用,在区域广阔的无路网野外环境中,依靠多层次格网剖分系统构建多层次六角格网通行模型,减少格网数据规模,提升路径规划效率。

越野环境路径规划算法需要有效兼顾多种约束条件并具有良好的运行效率,目前常用算法主要包括Dijkstra算法、A*算法、蚁群算法、遗传算法和粒子群算法等[22]。其中A*算法作为启发式搜索算法,可以将约束条件作为启发因素,缩小搜索范围以提高算法效率,常被应用于需要考虑多约束条件的越野路径规划,本文也采用A*算法进行路径规划[23]。算法核心在于如何将选取合适的启发因素,以得到合理的代价估计。文献[24—25]将地形坡度、地表覆盖等多种环境影响因子作为算法启发因素,有效模拟真实越野环境,提升路径规划效率。据此,本文提出一种面向越野路径规划的多层次六角格网通行模型,该模型由普通六角格网通行模型,历经多层次格网压缩及邻接关系重构生成。同时,本文在A*算法的基础上,依据通行模型格网的多层次特点,针对通行环境中的各种约束条件优化其启发函数,构建适用于大规模越野场景的路径规划算法。基于此模型,本文以地形和地表覆盖类型为例,选取遍历格网数、路径格网数及算法执行时间等8个指标,在算法运行效率和算法可靠性两个方面进行对比试验,说明本文提出的多层次六角格网通行模型相较于普通六角格网通行模型能够有效缩减格网数据规模,保持规划路径质量,提升路径规划效率。

1 多层次六角格网通行模型的构建

普通六角格网通行模型的构建是生成多层次通行模型的前提。以格网地图为基础,结合影响因子量化生成的通行能力,构建出普通六角格网通行模型,经格网层次压缩及邻接关系重构生成多层次通行模型。由于多层次通行模型与普通六角格网通行模型的格网地图结构不同,所以还需要优化路径规划算法使其适配多层次通行模型,流程图如图1所示。

1.1 普通六角格网通行模型

通行模型的构建首先须生成格网地图,然后分析量化影响因子,为格网赋予相应的通行能力。

1.1.1 六角格网地图生成

格网地图通常由形状为正三角形、正四边形或正六边形的格网组成,适用于不同的应用场景[26-27]。如图2所示,正六边形与相邻格网只有1种邻接关系且有6个通行方向,正三角形有2种邻接关系和6个通行方向,正四边形有2种邻接关系与8个通行方向。在路径规划中,由于正六边形具有更一致的邻接关系,拥有更多的等距通行方向个数,方便算法处理邻接关系,利于影响因子量化,因此,本文采用正六边形作为格网地图中的格网形状。

图2 3种多边形邻接关系与通行方向Fig.2 Adjacency relation and passage direction of three polygons

本文参照开源算法Uber-H3[28]构建了多层次格网剖分系统,如图3所示。在该系统中,任意一个地理坐标在每个格网层次中都具有唯一的格网索引与之相对应,通过格网索引可以获取到任意格网的邻接格网,不同层次的格网在范围上具有上下层涵盖关系。

图3 多层次格网剖分系统Fig.3 Hierarchy grid system

1.1.2 影响因子量化

影响因子量化是对影响通行对象通行的地质地形要素进行分析,用于对复杂丰富的越野环境进行抽象和简化,以实现对实际地质地形的量化模拟[29-30]。越野环境下的路径规划,不同的通行对象涉及不同的影响因子,针对轮式车辆为通行对象,本文将影响因子分为地形和地表覆盖类型两种,具体分类见表1[31-33]。

表1 越野路径规划影响因子分类

为了建立贴近通行环境的影响因子量化模型,本文将量化规则分为单因子量化和多因子量化。单因子量化得出格网是否能通行,用于筛选出不可通行的格网;在格网可通行的基础上,多因子量化用于计算格网通行能力。

(1) 单影响因子量化。通过确定单一影响因子的格网面积占比或存在与否,判断格网通行性。本文将建筑物和水系进行单影响因子量化,判断规则为

(1)

式中,sb和sw为建筑物与水体在对应格网中所占面积;HS代表硬质路面;S为对应格网面积;p为不可通行的影响因子在格网中所占面积比例的阈值。建筑物和水体在格网中所占面积比例之和小于阈值p时,格网可通行;大于等于阈值p,且格网中不存在硬质路面时,格网不可通行。依据实际应用场景和通行对象类型,本文设定p值为0.5。

(2) 多影响因子量化。当格网的通行性为可通行时,对多种影响因子进行综合量化,得到格网通行能力。坡度会影响车辆的通行速度,坡度越大,车辆受到爬坡阻力越大,通行速度越小。量化规则Ws为

(2)

式中,h为相邻格网之间的高程差;d为相邻格网之间的中心点距离;λs为坡度对车辆通行速度的影响系数。

硬质路面、土质路面、草地和森林的土质松软程度和地面粗糙程度各不相同,对车辆通行速度也存在着不同的影响。在本文中,它们的量化规则分为两种:①当格网中存在硬质路面时,格网通行能力不受地表覆盖类型影响;②当格网中不存在硬质路面时,使用土质路面、草地和森林在格网中的面积占比与对于车辆速度的影响系数的乘积之和来表示它们对于格网通行能力的影响能力。量化规则Wc为

(3)

式中,S为对应格网面积;HS代表硬质路面;st、sg、se分别为土质路面、草地和森林在对应格网中的面积;λh、λt、λg、λe分别为格网中覆盖类型为硬质路面、土质路面、草地和森林时对车辆速度的影响系数。

综合以上两种量化规则,得出格网n处的通行能力量化模型为

(4)

式中,Wc(n)为格网n处地表覆盖类型对格网通行能力的影响能力。为了方便使用,还需要对Wc(n)进行归一化操作

(5)

式中,Wcmin、Wcmax为Wc(n)的最小值和最大值。

因此,根据式(4)和式(5),可以得到顾及多种影响因子的格网通行能力量化模型

(6)

1.2 多层次通行模型构建

多层次通行模型的构建需要经历格网层次压缩与邻接关系重构两个过程。其具体步骤为:①将格网地图中的所有格网作为初始集合S1。②对S1中的格网进行格网层次压缩,将被压缩的格网组成集合S2,再对S2进行邻接关系重构;将S2从S1中删除,生成集合S3。③将S2作为步骤②中的S1,重复步骤②。当S2为空时,将步骤②每次生成的集合S3合并,生成多层次通行模型。

1.2.1 格网层次压缩

基于相邻格网层级之间的涵盖关系,本文提出了多层次格网压缩算法,该算法将通行能力相似的邻接子格网合并为父格网。设一组邻接子格网集合C的通行能力为si(i=1,2,…,n),σ为C中所有格网通行能力的相似度

(7)

当相似度大于或等于格网相似度阈值ρ时,即σ≥ρ,表明集合C中所有格网表达的通行环境相似,可以被压缩为父格网,则压缩后生成的父格网通行能力为W

(8)

在本文所构建的多层次格网剖分系统中,n取值为7,ρ综合对比试验结果及本文应用场景取值为0.80。

1.2.2 邻接关系重构

在多层次格网地图中,由于原先格网邻接关系失效,路径规划算法不能够正确运行,因此需要重新构建格网邻接关系。设格网T的子格网为集合A,A的邻接格网为集合U,则格网T的邻接格网集合B={x:x∈Uandx∉A},如图4所示,橙色部分为集合B。再将格网T增添到B中格网的邻接格网集合,邻接关系重构完成。

图4 邻接关系求解Fig.4 Solving adjacency relation

在多层次格网地图中,不同尺寸格网会出现部分未覆盖或格网重叠的问题,如图5所示,这些问题会导致地理坐标不能映射到格网或映射格网冲突。为了解决这个问题,基于多层次格网剖分系统地理坐标与格网映射机制,本文在进行地理坐标映射时采取从格网地图最低层级逐级向上转换策略,正确计算地理坐标对应的格网索引,消除格网地图逻辑上空缺与重叠部分。

图5 多层次格网地图Fig.5 Multi-hierarchy grid map

如图6(a)所示,在获取坐标点a所在格网时,虽然格网A与格网B存在叠加关系,但依照最低层级逐级向上转换策略,坐标点a会被定位到格网B;在获取坐标点b所在格网时,会首先得到格网C,而格网C已被压缩为父格网A,所以坐标点b被定位到格网A。实际上,格网A所覆盖的区域为区域B,如图6(b)所示。

图6 多层次格网坐标点与格网对应关系及格网覆盖区域Fig.6 Correspondence between coordinates and grid in multi-hierarchies grid maps and grid coverage area

1.3 路径规划算法

A*算法作为启发式算法,通过对启发函数的设计,可以减少无谓的路径搜索,缩小搜索范围,提高搜索效率[34],其启发函数可以表示为

F(n)=G(n)+H(n)

(9)

式中,F(n)为当前格网n的综合估计值,当需要遍历下一个格网时,算法总会选取综合估计值优先级最高的格网;G(n)为当前格网n距离起始点的实际代价;H(n)为当前格网n距离终点的预估代价。

为了适应多层次格网地图格网大小不一的特点,本文摒弃通过格网数乘以格网大小计算当前格网G(n)的方式,转而采用从起点到当前格网n所经过格网距离之和计算G(n),如式(10)所示

(10)

式中,Di为从起点格网到当前格网n所经过的第i段路径,如图7所示。

针对越野环境下的路径规划,本文选取格网通行能力与相邻格网间的坡度值作为启发因素。H(n)为当前格网n到终点格网goal的欧氏距离与启发因素的累加的乘积

H(n)=(Ws(n,p)+Grid(n))·ρ(n,goal)

(11)

式中,Ws(n,p)为n格网处坡度对格网通行能力的影响能力,求解过程中的邻接格网为当前格网n与它的前驱格网p;Grid(n)为当前格网n的通行能力值;ρ(n,goal)为当前格网n到终点格网goal的欧氏距离。

此外,为了保证启发因素量纲统一,且H(n)估计值不能大于当前格网n到终点格网goal的实际值[35],须先对其进行归一化操作

(12)

(13)

综上可得综合两种影响因子的A*算法综合估计值函数

ρ(n,goal)

(14)

2 试验结果与分析

2.1 试验区域

本文选取贵州省毕节市黔西县境内部分区域,如图8所示,该区域中的地表覆盖类型主要为森林与土质路面,四方山峦绵延,中部地势平坦开阔,较适宜作为试验区。其中遥感影像数据为谷歌卫星影像,空间分辨率为0.6 m;数字高程数据为美国国家航空航天局NASA提供的DEM数据,空间分辨率为30 m;土地利用分类数据为2020年GlobeLand(http:∥www.globallandco ver.com/)全球土地覆盖,空间分辨率为30 m。

图8 试验区区位Fig.8 Location of experimental area

2.2 多层次通行模型结果

2.2.1 影响因子的计算

为了更好地模拟通行环境,建立贴近通行环境的通行模型,基于1.1.2节影响因子量化,本文构建了坡度、硬质路面、土质路面、草地和森林对于车辆速度的影响系数λs、λh、λt、λg、λe,见表2、表3。Ws与Wc的取值范围由影响系数确定,由表3可知,Wsmax与Wcmax取值为1,Wsmin与Wcmin取值为0。

表2 坡度影响系数

表3 地表覆盖类型影响系数

2.2.2 多层次通行模型的生成

生成多层次通行模型首先需要确定基础格网分辨率,格网分辨率的确定需要综合考虑地图比例尺、研究区域范围大小、应用需求等因素。图9展示了不同格网分辨率的通行模型,其中线要素为不同等级的公路,在本文中均被表示为硬质路面地表覆盖类型。对比不同格网分辨率的通行模型可以发现,当格网分辨率为R=9时,通行环境可以得到很好的模拟,如图9(c)所示。以硬质路面为例,在基础格网分辨率采用R=9时,硬质路面经过的格网都表现出了最佳的通行能力。而当基础格网分辨率为R=8、R=7或更低时,格网的表达的通行能力较为粗糙,如图9(b)右下角所示,格网并没有体现出硬质路面所带来的通行能力提升。在此格网分辨率生成的通行模型中进行路径规划,规划出的路径会出现没有优先经过硬质路面的情况。虽然格网分辨率越大,格网量化精度越高,所表达的通行环境越精细,如图9(d)所示,硬质路面经过的格网同样表现出了最佳的通行能力;但当格网的分辨率超过地理环境的实际分辨率时,会出现格网量化时没有坐标点相对应的情况。在图9(d)中,没有坐标点映射的区域存在格网缺失,因此无法进行路径规划研究。综上本文以R=9为基础格网分辨率构建多层次通行模型。

图9 不同格网分辨率通行模型对比Fig.9 Comparison of traffic models with different grid resolutions

采用第1.2节多层次通行模型构建方法生成多层次通行模型,如图10所示。由图10可以看出,一些通行能力相似的格网都被压缩为了更高层次的格网,通行环境细节也没有丢失。表4所示为不同参数通行模型格网数量,可以看出以多层次通行模型格网数量仅为R=9的普通通行模型的53.75%。

表4 不同格网分辨率通行模型格网数量

图10 多层次通行模型Fig.10 Multi-hierarchy traffic model

2.3 通行模型有效性评价

本文使用多层次六角格网通行模型与普通六角格网通行模型进行对比,路径规划算法均为A*算法,启发因素一致,两种通行模型如图11所示。

图11 通行模型对比Fig.11 Traffic model comparison

为了讨论多层次六角格网通行模型对于越野路径规划的影响,以及基于该模型规划路径的合理性,本文选取5组起点O和终点D,并展示了O3D3的路径结果。5组OD均距离较远且地表覆盖复杂,其中O2D2位于海拔较高且坡度多变的多山地带,如图12所示。

图12 越野路径规划结果Fig.12 Results of off-road path planning

对比两条路径可以发现,PN与PO在起点处路径基本一致,说明在没有格网层次压缩的区域,多层次通行模型与普通通行模型规划路径质量相同;中部区域通行环境多变,存在多个格网被压缩的现象,格网邻接关系发生变化,PN与PO在p1处产生了分歧。其中,PN折向右下方,以保证尽量沿着硬质路面前行,有较好的通行环境,但路径不够平滑,拐点较多,对于考虑转弯半径的通行对象,会影响其通行或行进速度;而PO路径笔直,经过的格网通行难度较低且通过格网数少,因此路径平滑且长度较短;最后,靠近终点时,PN与PO所经过的区域通行难度相似,以路径最短前行,说明启发函数中的距离因素有效引导了通行对象的行动。

(1) 算法效率对比。本文以遍历格网数、路径格网数、算法执行时间指标对算法效率进行定量分析,其结果如图13所示。格网层次压缩算法降低了通行模型格网数量的规模,极大地缩小了算法的搜索空间,使得基于多层次六角格网通行模型的路径规划算法相较于普通六角格网通行模型,遍历格网数平均减少了47%。本文提出的路径规划算法在寻找路径的过程中,需要在待遍历格网集合中选择通行能力值最大的格网进行,因此待遍历格网集合越小,路径规划算法的执行效率越高。试验结果表明,基于多层次六角格网通行模型的算法效率较普通通行模型明显提高,其算法执行时间大大降低,平均减少了57%;在路径格网数量上,由于O2D2和O4D4经过的区域格网通行能力的相似度较低,被层次压缩的格网数量较少,所以两种通行模型在路径格网数量上相差不大,但也有16%的数量缩减。

图13 算法运行效率对比Fig.13 Comparison of algorithm operation efficiency

(2) 算法可靠性对比。本文选择路径地表覆盖类型占比、路径长度、拐点、坡度平均值与标准差作为定量指标,使用余弦距离来量化两种通行模型在地表覆盖类型占比分布相似度,综合对比规划路径的优劣。由图14和图15可以看出,两种通行模型在通行环境上基本相似,地表覆盖类型占比分布相似度平均值高达98.75%,路径长度平均相差6%,但基于多层次六角格网通行模型的路径坡度的平均值与标准差更小,拐点更少,路径平坦顺滑,更易通行。具体来说,在O3D3中,PN与PO地表覆盖类型占比指标分布相似度为99.5%,PO在路径长度、坡度的平均值和标准差指标上更低,且PO的拐点仅为PN的一半,PO在确保与PN相似路况的前提下,规划了更短、更平坦、更顺滑的路径,充分体现了基于多层次六角格网通行模型规划路径的有效性。另外,虽然O4D4在多层次六角格网通行模型上拐点较多,但路径坡度的平均值与标准差更小,路径更加平坦;O2D2在多层次六角格网通行模型上路径坡度的平均值与标准差较大,但路径拐点更少,路径更加顺滑,通过的格网地表覆盖土质路面更多。由此可以看出,本文提出顾及多种影响因子的越野路径规划算法是可靠的。

图14 路径地表覆盖类型占比Fig.14 Proportion of path land cover type

图15 算法结果质量对比Fig.15 Comparison of quality of algorithm results

综上,不同于通行环境相对简单的基于路网的路径规划,越野条件下的通行环境复杂,没有道路网约束且规划区域广阔。本文针对这种特点建立了顾及地形与地表覆盖类型两类影响因子的多层次六角格网通行模型,选取遍历格网数、路径格网数及算法执行时间等8个指标衡量多层次六角格网通行模型的优越性。试验结果表明,在通行环境局部相似度高的大规模越野环境中,本文提出的建模方法有效减少了路径规划应用的所需计算时间与存储空间,缩减程度均达到近50%,其规划路径结果也是可以被接受的。

3 总 结

面对大规模越野环境下路径规划效率低下的问题,本文提出了多层次六角格网通行模型,并基于该模型实现了顾及多影响因子的越野路径规划算法。基于多层次格网剖分系统,普通六角格网通行模型历经相似格网压缩,邻接关系重构,最终生成了多层次六角格网通行模型,并对A*算法启发函数进行优化,使其具有更高的效率与可靠性。试验表明,本文提出的通行模型在大规模越野场景中能保持良好的整体性能,相较于普通六角格网通行模型,有效降低了通行模型的格网数据规模,减少了算法的运行时间。

本文在实现多层次六角格网通行模型时,多层次格网压缩算法仅考虑了格网的通行能力作为压缩标准,压缩后的格网不能完全拟合真实通行环境。因此,后续工作还需在格网相似程度的多因素判断方法上进行探索,进一步优化多层次六角格网通行模型。