基于视野范围和遗传算法的三维地形路径规划

贺 娇，谭代伦

西华师范大学 数学与信息学院，四川 南充 637000

路径规划是智能技术中的热点研究问题，已在众多领域有所突破并初步得以应用，其中包括：无人机航迹规划[1-3]、移动机器人路径规划[4-6]、自主水下航行器路径规划[7-8]、景点旅游路径规划[9-10]、城市交通出行路径规划[11-12]等。路径规划研究在二维平面环境中取得了一定的成效，但随着生活的发展变化，考虑到实际操作角度，更多时候的路径规划需要在特定的三维场景下完成，故如何优化三维环境中最短路径的研究是具有重要意义且十分必要的。

三维空间环境中的路径规划是NP 难问题，由于三维地形路径规划问题中的空间复杂度以及地形不确定性等因素往往使得规划效果不佳，故如何对其进行更好的规划是极具挑战的。近几年，国内外专家学者做了很多的研究。郝燕玲等[13]采用栅格法划分三维空间中XY平面，以针对路径的表示，只要求得到每一栅格里的最大地形高度，而不对实际地形环境做任何处理；禹建丽[14]、何光勤等[15]引入碰撞罚函数，结合对各个障碍物的神经网络定义各路径点的碰撞罚函数，对各路径点的碰撞罚函数求和得到整条路径罚函数，以此规避不可行路径；李玉齐[16]提出一种立方体栅格的方法来描述三维空间障碍物，通过判断空间线与面的相交与否确定是否与障碍物发生碰撞，从而搜索三维避障路径；袁建华等[17]在三维空间中定义长方体障碍物，通过UAV 自身传感器建立可视区域，以当前位置为中心分别产生10 个同心球体，从中随机选取代价系数最小的节点组成子路径，结合滚动策略探知周围环境信息完成避障。

综合已有文献的研究成果，一种更接近人工智能的思路是借鉴自然界生物视觉系统的工作机制，为路径规划也定义某种视野范围，以更有效地克服由于地形不确定性所带来的干扰和影响，使路径规划过程总是沿着视野范围内行走，从而确保路径总是可行的，以此避开三维地形障碍，并将这种机制结合到遗传算法中，通过实验仿真求解三维地形路径规划问题，取得了较好效果。

1 三维地形与视野范围

目前，三维空间环境建模通常采用栅格法，即将空间的三个维度进行等距划分，形成空间中的网格块，并把它们看作是路径规划中的节点，以此构造路径。而三维空间环境的路径规划主要在三维地形的表面上行进，因此只需对经度和纬度这两个维度作网格化，第三个维度可直接取地形表面的海拔高度，不需作网格化处理。本文选取文献[18-20]中的一种随机三维地图，如图1。

图1 三维地形与视野范围Fig.1 3D terrain and sight range

图中三维地形的范围为21 km×21 km×2 km，对XY平面进行网格化，每个网格的长度和宽度均为单位1。点S为路径起点，点P为路径终点，点A为路径上任意一点。网格化后，连续变化的三维地形表面被简化为一个个的空间四边形，这些空间四边形在XY平面上的投影对应于每一个正方形网格。

自然界中，大部分生物依靠自身的视觉系统在三维地形表面上行走，每一次向前行进的距离，往往都是在根据视觉系统检测到的可行走范围内[21]。基于这种生物视觉仿生学原理[22]，本文将三维地形上从某点出发检测到的可行走范围定义为视野范围。在图1中，从点A发出的红色线段，是它能直接到达的下一网格点的行走路径，这些线段及其端点即可看作是从A点出发沿x轴正方向前进的视野范围。

设从路径起点S到路径终点P需经过n个中间节点，记中间节点集合为V={v1,v2,…,vi,…,vn-1,vn}，那么在三维路径规划中建立以总路径长度D为优化目标的数学模型如下：

其中，dvivi+1表示节点vi到vi+1的两点间距离。

2 视野范围的构建与检测

2.1 视野范围的构建

在三维地形路径规划中，检测出视野范围对形成一条完全可行的路径是非常关键的。对图1的点A，其视野范围可抽象为如图2所示的空间几何图形。

图2 点A 的视野范围示意图Fig.2 Spatial geometry of sight range

在图2 中，{B1,B2,…,Bp-1,Bp,Bp+1,…,B20,B21} 为从A点出发，向x轴正方向前进时所有可能的路径节点。可以看到，从点A可以直线到达点Bp，而其余的节点，能否以直线方式到达则需要检测和判断。

若从A点出发，要到达的下一个网格点是同一个网格内的对角顶点，如图3。此时可能有两种情形：一种是对角线BpC的空间位置比ABp+1低，在实际三维地形中相当于“山谷”，如图3（a），此时从点A能以直线方式到达点Bp+1，于是Bp+1在点A的视野范围内；另一种情形是对角线BpC的空间位置比ABp+1高，在实际三维地形中相当于“山脊”，如图3（b），此时从点A不能以直线方式到达点Bp+1，即BpC构成了地形障碍，则Bp+1点就不在点A的视野范围内。

图3 一个网格内的视野范围Fig.3 Sight range in a grid

由空间几何投影知识可知，要判断空间直线段ABp+1和BpC的位置关系，可以先找到它们在XY平面上投影线的交点E，过E点作XY平面的垂线，与ABp+1和BpC分别交于点E′和E″，比较E′和E″的第三维坐标zE′和zE″大小，即可判断出ABp+1和BpC的空间高低关系。

通常网格四个顶点A、Bp、Bp+1、C的三维坐标是已知的，其对角线在XY平面上投影的交点E的三维坐标也是容易计算的，则zE′和zE″可按下式进行计算：

若从A点出发，要到达的下一个网格点Bq需要跨越多个网格，则以ABp为基准，在点A左侧和右侧可能形成的视野范围投影图如图4（a）、（b）所示。

图4 跨越多个网格时可能的视野范围Fig.4 Possible sight range in multiple consecutive grids

对图4（a），可按以下公式计算Fi,Gi的坐标：

2.2 视野范围的检测

利用式（1）～（6）可以检测出三维地形中从某点出发的视野范围。为记录检测结果，定义如下0-1型变量：

根据3.1 节中视野范围构建过程，对三维地形上某点A及对应的下一网格基准点Bp，点A的视野范围检测算法步骤为：

（1）依次取点Bq∈{B1,…,Bp-1,Bp+1,…,B21}，计算投影点B′p和B′q之间的正方形网格个数npq。

（2）按公式（3）、（4）或（5）、（6）计算投影线A′B′q与所跨越网格的边线和对角线所有交点Fi,Gi的坐标。

（3）对所有交点Fi,Gi，按公式（1）计算其在XY平面上垂线与线段ABq的交点E′的海拔高度zE′。

（4）对所有交点Fi,Gi，按公式（2）计算其在XY平面上垂线与网格的边线或对角线的交点E″的海拔高度zE″。

（5）若zE′≥zE″，则TABi=1，否则TABi=0。

3 基于视野范围的遗传算法

三维路径规划是典型的组合优化问题，其路径节点较多，问题规模较大，近年来在求解方法上更多地选择了现代群智能算法，既能获得较高精度的近似最优解，也能加快求解速度。在各种群智能算法中，遗传算法的通用性、并行性、鲁棒性[23]均较强，已被成功应用于求解三维地形的路径规划。所提视野范围较好地解决了遗传算法求解三维地形的路径规划中回避地形障碍的问题，从而不必设计修复算子对不可行路径进行处理。为此，下面将结合视野范围机制对遗传算法进行设计。

3.1 编码方案

在遗传算法中，编码方案是将对问题的解空间转换为有利于遗传进化操作的基因编码。如图1，对给定的起点S和终点P，其沿地形行走的路径具有逐个网格依次前进的特点，故只需对不确定的y坐标进行编码，再利用z坐标判断是否避开地形障碍即可。

网格化后的y坐标是用自然数表示的，因此采用不重复的自然数编码方案。对图1，每一个遗传个体的基因编码可记为：

3.2 基于视野范围的种群初始化

遗传算法不能直接处理问题空间的参数，需要将其编码成为遗传空间的染色体。在三维地形路径规划中，由于存在地形障碍，所产生个体的基因（路径节点）很容易构成不可行路径。为此，引入视野范围机制进行检测和判断，可以很好解决这个问题。设种群规模为M，基因编码长度为N，则基于视野范围的种群初始化步骤为：

（1）初始化一个M×N的空矩阵，设置每一个体第一个基因编码为起点S的y坐标。

（2）根据2.2节的视野范围检测算法，搜索起点S的视野范围{v11,v12,…,v1i,…,v1k1}，并在其中随机选取一个路径节点v1i，将点v1i的y坐标填入下一个基因编码。

（3）以此类推，直至选取的最后一个基因编码为终点P的y坐标。

上述初始化中，路径的形成过程如图5。

图5 基于视野范围的路径形成过程Fig.5 Path formation process based on sight range

3.3 适应度函数

适应度函数用于评估和区分种群个体的优劣，是进行遗传选择的依据[24]。根据3.2节可知种群初始化方法所产生的种群个体都是可行路径，因此个体的适应度可以直接取路径中相邻节点的欧氏距离之和，即：

经迭代计算后，适应度最小的个体即为最短路径。

3.4 轮盘赌选择策略

轮盘赌策略是遗传算法的经典选择策略[25]，首先将个体适应度fi归一化并取倒数得到fi′；其次，计算个体的适应度占比pi=f′i/(∑fi)以及累积概率Pi=∑pi；最后随机产生一个随机数rnd∈(0,1)，选择满足Pi-1

3.5 重合点片段交叉策略

遗传算法的交叉策略是将两个随机个体的部分基因进行交换，从而生成新个体[26]。为保证被交换基因（子路径）的有效性，引入了一种重合点片段交叉策略：在两个个体中查找出两个基因重合点（相同位置的基因相同），将介于两个重合点之间的基因片段按交叉概率进行交换，从而生成两个新的子代个体。

3.6 基于视野范围的变异策略

在遗传算法中，变异策略有利于增加种群的多样性，能够尽量避免算法过快陷入局部最优[27]。采用片段基因变异方法，即以给定的变异概率改变个体的部分基因片段。考虑到基因变异后将会导致不可行路径的产生，因此结合视野范围机制进行片段变异，其主要步骤为：

（1）随机产生两个不同的自然数R1,R2∈(1,N)，且R1

（2）对当前个体，以第R1个基因点所对应的节点为视野中心，确定其视野范围，并在其中随机选取一个节点，取其y坐标作为下一个基因编码。

（3）以此类推，直至选取节点的y坐标为第R2个基因所对应的节点。

例如，有以下当前个体Yi，随机生成两个不同的自然数为R1=2,R2=9，经变异得Yi′。

3.7 算法流程设计

综合上述设计，基于视野范围的遗传算法流程图如图6。

图6 基于视野范围的遗传算法流程图Fig.6 Flow chart of genetic algorithm based on field of view

4 实验及仿真结果

近年来，较多文献选用蚁群算法求解三维路径规划。为验证所提算法的有效性和求解性能，对图1的三维地形图，下面选取标准蚁群算法与本文算法分别进行求解。图1 中，路径起点为S（1，10，0.65），路径终点为P（21，8，1）。

硬软件环境为AMD A8-45000M CPU/8 GB/Win7系统和Matlab R2018a。由于遗传算法的运行参数往往是通过先前经验或者反复的调试获得的，故设置遗传算法的种群规模、迭代次数、交叉概率和变异概率分别为100、100、0.8、0.3。

4.1 实验结果

按照图6的算法流程和上述算法参数编程，本文算法和标准蚁群算法求解的三维路径如图7所示。

图7 两种算法求得的最优路径Fig.7 Optimal path obtained by two algorithms

在图7 中，蓝色路径为标准蚁群算法所求，路径长度为27.5 km，红色路径为所提算法所求，路径长度为23.5 km，结果明显更优。

为便于更好地观察图7中的两条路径，将两种算法求得的三维路径投影至XY平面，如图8。

图8 三维最优路径在XY 平面的投影Fig.8 Projection of three dimensional optimal path in XY plane

结合图7和图8，可以看到，在路径的后半部分节点上，三维地形障碍较多、变化复杂，本文算法求得的最优路径更优于标准蚁群算法。

两种算法在求解三维地形最优路径时适应度的进化曲线如图9。在图9中，红色进化曲线下降更快，很快趋于平缓，最短路径长度取值更小，因此本文算法的寻优能力明显强于标准蚁群算法，收敛速度更快，所需迭代次数更少。

图9 两种算法的进化曲线Fig.9 Evolution curve of two algorithms

4.2 算法性能

为进一步测试本文算法求解三维路径规划问题的性能，降低由智能算法的随机导致的结果片面性，本文运用两种算法在相同实验环境中分别进行多次实验，统计两种算法的运行结果，随机选取三组实验结果在路径长度与迭代速度上进行对比，如表1。

表1 两种算法求得的最优路径长度比较Table 1 Comparison of optimal path length obtained by two algorithms

从表1可以看到，本文算法求解的最优路径长度均小于蚁群算法，且本文算法求得的最优路径长度比蚁群算法平均降低18.7%。说明本文提出的视野范围机制效果明显，一定程度上提高了选择下一路径节点的合理性，降低了路径长度。

记录随机选取的三次实验中两种算法求解时的进化曲线，统计两种算法寻得最优路径时的迭代次数，统计结果如表2所示。

表2 两种算法迭代速度比较Table 2 Comparison of iterative speed of two algorithms

从表2 可以看到，在三次随机实验中，本文算法均早于蚁群算法求得最优路径。说明本文提出的视野范围构建机制有效规避了不可行解的产生，明显提高了路径搜索效率，节省了寻优时间。

5 结束语

针对三维路径规划问题，本文模拟自然界生物的视觉系统提出了一种视野范围机制，利用几何投影方法构建了任意节点视野范围，以此达到规避地形障碍的目的，从而寻得可行路径；将视野范围机制引入遗传算法，提出了一种基于视野范围的遗传算法，通过实验仿真求解三维地形路径规划问题，不断对种群规模个个体进行迭代寻优。实验仿真结果表明视野范围机制求解三维地形路径规划问题具有良好的适用性，与蚁群算法的实验对比结果更加表明视野范围机制的路径规划效率较高。这对未来可移动智能设备更好地模拟自然界生物的各种实用功能提供了新的思路和方法。