三维地形下基于Hopfield神经网络的路径规划算法

徐 炜 周兰凤* 章民融

1(上海应用技术大学计算机科学与信息工程学院 上海 201418)2(上海市计算技术研究所 上海200040)

0 引 言

路径规划问题，即按一项或多项优化规则，如最小工作代价、最短行走路程、最短行走时间等，寻找一条从起始状态到达目标状态的最优无碰路径[1]。复杂地形下的路径规划是近几年研究的热点问题。目前，研究路径规划的算法主要有D*算法[2-3]、遗传算法等，这些算法相对来说单一且仅针对于简单的地形，在复杂的三维地形中无法适用。神经网络算法在最近几年的研究中逐渐迅速并且适用于解决复杂的地形输入问题[4]，禹建丽等[5]通过对神经网络在路径规划上的应用，解决了最短路径规划问题。但这些算法对于起伏地势较大的三维特殊地形中，依旧缺少对起伏地势以及障碍物的考虑。

综上所述，虽然很多人都对路径规划问题有所研究，但是，并没有考虑在复杂地形下的起伏地势以及障碍物对路径规划的影响[6-7]。也就是说，诸多的路径规划算法与具体的真实复杂地形存有脱节的现象[8]。本文利用了当下研究较为流行的神经网络算法，并且考虑到复杂的三维地形环境中地形以及障碍物等问题，将神经网络与地形函数模型相结合，为自主导航研究奠定了基础。

1 地形函数模型

1.1 地形预处理

导航车在复杂的三维地形行进过程中，要避开障碍物以及起伏变化较大的地势，以达到最优的路径[9-10]。由于地势的复杂性，无法对其直接进行计算，故地形的预处理是进行建模的第一步。

为此，本文在研究中将高低起伏的地势转化为规则的圆柱体，将障碍物转化为球体，便于导航车在行进过程中避开这些障碍物，寻找到一条最优的路径。规则几何体的函数形式如下：

(1)

式中：x0、y0和z0表示地势起伏以及障碍物的中心点坐标；a、b和c是常数用来控制障碍物的大小；x、y和z用来表示地形的三维坐标值。式(1)可以根据不同的p、q和r值来描述不同的几何图形。当p=q=r=1时，表示的是一个球体，即此时的路径需要避开的是障碍物；当p=q=1且r>1时，表示的是一个圆柱体，即此时的路径需要避开的是高低起伏的地势。

1.2 地形函数

地形函数模型旨在导航车行进的过程中，为避开高低起伏的地势以及障碍物而建立的一种易于处理的模型。不同的地势一定具有不同的函数模型。本文主要运用流函数的基本思想，即将从障碍物周围的流动现象中学习，地形被视为边界条件，通过使用流体力学计算规划区域中的流场分布来建立。流动控制方程如下：

▽2Φ=0

(2)

式中：▽是微分符号，此方程式为拉普拉斯方程式，Φ为规则几何体的函数形式，即式(1)。

流动控制方程的边界条件之一是在障碍物表面即：

(3)

式中：n表示障碍物表面向外的单位法向量。

边界条件之二是在无限远处：

▽Φ=μ∞

(4)

式中：μ∞表示导航车在行进过程中的速度。将式(1)的规则几何体的函数形式分别代入式(2)、式(3)和式(4)求解，将得到一个适用于避开障碍物和起伏地势的地形函数模型。

2 连续型Hopfield神经网络

Hopfield神经网络是一种递归型、结合存储系统和二元系统的神经网络，由Hopfield等采用模拟电子线路实现，并成功地求解了优化组合问题中一些最具有代表性的问题，也开启了信息处理中运用人工智能技术的新方法。该网络中神经元的激活函数为连续函数，因此，也被称为连续型Hopfield神经网络[11-12]。在连续型Hopfield神经网络中，各神经元一般采用并行工作方式，输入和输出均为模拟量。

在生物系统中，由于神经元i的细胞膜输入电容ci、跨膜电阻Ri和确定阻抗Rij=Wij-1,Wij为i与j之间的权重，状态Ui会滞后于其他神经元的瞬时输出Vi，所以神经元的输出将是0、1之间的连续值，而不是离散模型的二值。连续性Hopfield神经网络中，组成电路的基本器件如图1所示。

图1 Hopfield神经网络的电路基本器件图

其主要由以下几部分组成：

(1) 带有同向和反向输出端的运算放大器，且具有饱和非线性特性的S型输入输出关系，即：

(5)

式中：U0相当于输入信号的放大倍数，也控制激活函数的斜率，当U0趋近于0时，f就成为二值阈值函数。

(2) 放大器的输入电容Ci和输入电阻Ri的乘积为神经元的时间常数，该时间常数表示了神经元的动态特性。

(3) 网络神经元连接的权值：

(6)

式中：Rij为连接电阻。

(4) 外加偏置电流Ii相当于神经元的阈值θi，整个电路系统的动态方程式为：

(7)

若式(7)有解，那么系统状态的变化最终会无限接近稳定。在对称连接和无自反馈的状态下，可定义系统的能量函数为：

(8)

式中：T代表网络神经元连接的权值；V和I分别表示某个神经元的电压和电流；f常取双曲线正切函数。稳态时，可忽略最后的积分项得到：

(9)

至此，有了Hopfield神经网络的模型的状态方程和能量函数，可以来尝试解决三维地形下的路径规划问题。

3 三维地形建模

为有效地建立三维地形的模型，本文在研究中引入高度图作为输入数据的方法。高度图是创建三维地形的标准方法，它是一个二维数组值[13]。数组中的每个值表示该值位置处的地形高度[14]。例如，图2显示了高度图的单元格和每个单元格的值，而图3显示了该地图生成的地形线框视图。

图2 高度图的单元格和值

图3 生成的地形的线框视图

三维地形的建立需要基于高度图并且迭代地使用不同的算法。本文选择山丘算法构建三维地形模型。其基本算法步骤如下：

步骤1将所有高度值初始化为零；

步骤2在地形上或附近选择随机点，以及在某个预定的最小值和最大值之间的随机半径，选择这个最小值和最大值将使地形变得粗糙或者光滑；

步骤3在具有给定半径的点的中心上升起山丘；

(一)离合词“A了个B”的概念重组之后表示的是动词的量，表次数；而网络词“A了(嘞)个B”则是纯形式，概念重组之后仍继承的是指向决定体的意义，只是因为音节的增多而使得语气缓和，风格幽默。如“出了个丑”表示的是出丑的量，一次。又如：

步骤4返回步骤2，并根据需要重复迭代多次，选择的迭代次数将影响地形的外观；

步骤5规范地形。

至此，三维地形的模型建立完成。将运用此三维地形进行路径规划算法的研究。

4 三维地形下路径规划算法

连续型Hopfield神经网络在处理数据时是同步进行的。若将一个路径规划问题的目标函数转换成连续型Hopfield神经网络的能量函数，把问题的变量对应于网络中神经元的状态，那么，连续型Hopfield神经网络就能够很好地应用于路径规划问题。并且，将地形函数模型考虑进能量函数内，那么，Hopfield神经网络就能够更好地处理三维地形的障碍物以及起伏地势的问题。当网络的神经元状态趋于平衡点时，网络的能量函数也趋于最小值，网络由初状态向稳态收敛的过程就是路径的最优解过程。

本文设计了Hopfield神经网络的能量函数与目标函数相对应，因此网络的能量函数包含目标项及约束项两部分，将网络的能量函数定义为：

(10)

式中：V表示神经元的输出；N表示神经元数量；A、B、C和D为权值。

除此之外，为了能够更好地处理三维地形中的障碍物以及起伏地势的问题，必须加入地形函数模型信息：

(11)

由式(11)和式(12)两部分的结合可以得到路径规划问题的网络能量函数：

(12)

具体的算法步骤如下：

步骤1创建三维地形图；

步骤2初始化网络；

计算Vxi(t)；

步骤5计算网络能量函数E；

步骤6若迭代次数p>10 000，则结束程序,否则,p=p+1,返回步骤3。

5 实验结果与分析

实验在Unity 2018中进行。首先使用山丘算法建立三维地形图，如图4所示。其中，规则几何形状代表行进路径中的障碍物，其余部分是起伏地形。未对起伏的地形和障碍物进行处理之前，使用Hopfield神经网络的路径如图5所示，可以看出此路径不能避开起伏的地形和障碍物。然后，利用地形函数模型对起伏的地形和障碍物进行处理，且并入Hopfield神经网络算法中进行路径规划的路径如图6所示，可以看出该路径有效地避开了起伏的地形和障碍物。

图6 加入地形函数模型的路径图

6 结 语

本文以Hopfield神经网络为背景，研究三维地形下的一种有效的路径规划问题。利用山丘算法建立三维地形模型，在这个三维地形中，首先对起伏的地形以及障碍物进行处理,得到地形模型函数，然后在Hopfield神经网络算法中集成此地形函数模型。实验表明，在复杂的三维地形中该算法可以避开起伏的地形和障碍物，寻找到一条有效路径。本文研究也为无人驾驶的自主导航奠定了基础。