基于改进的生物激励神经网络机器人路径规划算法

张 秦,段中兴

(1.西安建筑科技大学 信息与控制工程学院， 西安 710055 ;2.西部绿色建筑国家重点实验室， 西安 710055)

0 引言

机器人路径规划问题是移动机器人导航与控制研究的最基本环节，得到了广泛的研究和探讨。路径规划问题指的是在有障碍的环境中，寻找一条实现从起始点到目标点的最优路径。路径规划问题主要由3个阶段环境建模、路径搜索、路径生成构成[1]。路径规划问题根据环境信息的特点划分为静态环境路径规划和动态环境路径规划；又可依据对环境信息掌握程度的差异划分为全局路径规划和局部路径规划。当前，常见的路径规划方法有：占据栅格法[2]、人工势场法[3-4]、PSO算法[5]、A*算法[6]、生物激励神经网络算法[7-9]等。

传统占据栅格法将地图环境离散化为独立的正方形栅格，每个栅格有两种状态:空闲和被占据。thrun等指出在栅格定位中，栅格大小和定位误差与传感器误差有关，影响了栅格地图的精确度[10]。而岳伟韬等提出建立“有义地图率”来描述占据栅格地图的准确度，并通过理论推导,得到了有义地图率的理论计算方法，建立信息量和栅格大小的联系，用损失函数来评估占据栅格地图的精度[2]。但是此算法计算量较大，路径规划效率较低，首先需要获取全局地图环境。人工势场法是较为普遍的路径规划方法，但传统人工势场路径规划算法存在易陷入局部极小值，目标不可达等问题，于振中等建立改进的势场模型，采用计算势场强度的方法代替矢量力控制，将移动障碍物与机器人的相对速度引入到势场函数中，实现了动态环境下的路径规划，对于局部极小值的问题，引入了填平势场法来使机器人走出局部极小值点[11]。传统粒子群算法存在优化精度低和易早熟，且收敛速度慢、搜索停滞的问题，且在应用于路径规划中时效果不理想。基于此问题，对于PSO算法的研究主要集中在参数改进、种群结构等方面。康玉祥等依据梯度下降法中变量负梯度方向变化的原则，提出了改进的粒子速度更新模型，从而实现优化PSO算法的路径规划[5]。该算法，只适用于静态障碍物情况下的路径规划，搜索效率和搜索精度有待提高。晁永生等应用动态修改路径的A*算法和增量式A*算法分别应用于静态和动态环境下，结合规划时间与路径长度建立路径修改顺序模型生成最优路径[6]。

生物激励神经网络算法在机器人路径规划方面的应用，无学习训练过程，无事先预知环境信息，计算速度较快，对动态环境中的变化能够积极反应，获得了广泛而深入的研究和应用。20世纪50年代生物物理学家Huxley和Hodgkin提出了关于细胞膜的HH模型和神经细胞膜的电路模型，Grossberg改进HH模型并提出了Shunting网络模型并应用在运动控制、机器视觉等领域方向[12]。Jianjun Ni等将动态生物激励神经网络模型应用于水下移动机器人实时路径规划，该算法无需事先获得环境信息，且计算规模小，可用于实时动态环境下的路径规划[13]。Mingzhi Chen等对快速动态变化环境下的实时路径规划的问题进行研究，研究了GBNN模型的替代权值函数，以改善其在动态环境下的性能[14]。范莉丽等引入目标距离制导因素，改进点对点生物激励神经网络算法，但生成路径未实现最优或者次优的效果[15]。王耀南等针对生物激励神经网络存在的路径未达到最优问题，路径错判问题，在边界附近与障碍物之间的路径点中引入假想的障碍物相邻点，在位置决策中加入了转角最小因素，从而增大激励输入，优化路径[16]。代亚兰等针对未知环境下考虑传感器检测范围有限性与动态障碍物运动的不确定性，提出了基于动态威胁评估的改进生物激励神经网络算法，采用栅格法与虚拟目标点的滚动优化方式进行路径寻优，且进一步提出了基于直觉模糊集的动态属性决策方法[17]。以上改进后的生物激励神经网络方法在路径规划、全遍历路径规划以及轨迹跟踪等领域中取得了成功的应用。但由于神经元活性值状态方程的特点，机器人还会出现过多偏离路径，非最优路径等问题。本文提出了改进的生物激励神经网络算法(biologically inspired neural network)在点对点路径规划中的应用。在静态环境下，初始阶段路径修正策略与理想路径制导的选择机制能有效的解决路径偏离和路径非最优问题，平滑路径，提升路径质量。

1 生物激励神经网络算法

1.1 路径规划原理

在生物激励神经网络方法中，分流方程是核心，分流模型最早是由Grossberg提出，其用来理解个体对复杂的动态环境中出现的突发事件的实时适应行为。该模型的基本思想是建立一个神经网络拓扑状态结构，其动态神经活性值表示动态变化的环境。通过适当地定义来自变化的环境影响和内部神经活性值影响的外部输入，可以保证可移动区域神经活性值和障碍物的神经活性值分别保持在神经网络活动区域的峰值和谷值。可移动区域通过神经活动传播在整个状态空间中吸引机器人，而障碍物仅具有局部作用以避免碰撞。且所有神经元的活性值初始化为0，分流方程如下：

(1)

(2)

式中，变量xi为第i个神经元的活性值，A为正常数，表示衰减率；B为神经元活性值的上限，D为神经元活性值的下限；Ii为第i个神经元的外部输入，如果i处为目标点，则Ii=E，如果i处为障碍物，则Ii=-E，否则Ii为0，其E是一个远远大于B的正常数。

(3)

如果a≤r0则f(a)=0，如果0

由分流方程可得出正神经元活性值向外传播并影响全局状态空间，负神经元活性值只在局部发生作用，障碍物单元和目标单元的活性值大小分别与波谷和波峰相对应，生物激励神经网络路径规划算法原理可解释为：目标单元通过正神经元活性值在全局状态空间中的传播和影响作用吸引机器人向目标单元靠近，而障碍单元由于具有负的活性值而只能够作用在局部，排斥机器人的接近[16]。在点对点路径规划中，具体路径可表示为：

(4)

式中，k为第pq个神经元邻近处神经元的个数，也是所有可能的下一个位置的个数；xj为第j个相邻神经元的活性值。

路径生成过程：由起始单元开始，首先判断当前神经元是否为目标单元，若不是，再判断当前单元邻域各神经元的活性值大小，选择邻域神经元中具有最大活性值的神经元为下一单元的位置。当机器人移动至下一位置单元后，更新当前神经元位置，再由同样方法到达下一位置，依此循环直至到达目标单元。

1.2 生物激励神经网络路径规划存在的问题

现设置仿真环境及模型参数如下：A=10,B=D=1,E=100,u=1,r0=2的情况下的点对点路径规划时路径生成过程的仿真结果如图1所示。结果表明应用生物激励神经网络路径规划方法的机器人虽然到达了目标点，但是其所走路径较长，且移动机器人产生了路径偏离问题，而且转折次数较多，路径不够平滑。

图1 路径偏离问题

在图1中黑色实心点单元所构成的为障碍物单元，白色栅格为机器人可行走区域，五角星所在单元为起始单元，起始单元与目标单元之间用直线相连，表示无障碍理想情况下的最短路径，用灰色折线相连的实心点代表机器人的运动路径单元。图1(a)中，在初始阶段，机器人并未朝着目标单元(19,29)移动，而是向左上方移动，并且在(3,12)、(4,12)单元处出现了重复的路径单元；图1(b)中，在初始阶段，机器人依然先向着左上方移动，当移动到(7,7)单元处，出现转折，并朝向目标点(26,27)单元移动，在后续的路径出现不必要的转折，使路径的平滑度降低。结果表明虽然到达了目标单元，但是所生成路径长度较长，且路径平滑度较低，未实现最优或次优路径。

从实验分析可得出，应用生物激励神经网络方法的点对点路径规划存在一定的问题，起始单元与目标单元相距较远，目标单元对全局单元的活性值影响是随着时间的推移而向全局空间传播的。在起始阶段，由于当前位置单元的邻域栅格单元活性值为零，且未受到目标点单元活性值的影响，此时机器人按照人为设定行走规则沿左上方移动，直至活性值影响传播到当前位置的邻域神经单元，机器人被目标单元吸引而移动，最终到达目标单元。

2 改进生物激励神经网络路径规划算法

2.1 栅格法环境建模

在移动机器人的工作环境中，需要构建相应的路径规划环境模型。在静态已知环境下，利用栅格法对移动机器人进行环境建模，因为栅格法建模方法简单、环境描述能力强，适用于地图栅格化。将工作地图放置在正交直角坐标系中，将工作环境划分成若干个栅格单元，根据障碍栅格区域和自由栅格区域的不同，给栅格赋予不同的置信度，通过置信度的不同使机器人分辨障碍栅格区域和自由栅格区域。

2.1.1 栅格法环境建模步骤

1)选取栅格大小：

栅格大小是栅格法建模的关键因素，选取栅格较小，则环境地图分辨率较大，环境信息量大，决策速度慢；选取栅格较大，则环境地图分辨率较小，环境信息量小，决策速度快，但在密集障碍物环境中发现路径的能力较弱，本文栅格选取以机器人直径为栅格大小。栅格大小的确定，一般受以下因素的影响：①环境地图大小；②障碍物大小及规则情况；③机器人最大的横扫长度，要求扫描的横截长度大于栅格长和宽；④机器人运算能力及算法复杂度，保证机器人的工作效率。

2) 确定障碍物栅格：

当机器人进入陌生环境时，无法获取环境内障碍物信息，机器人首先遍历全环境地图，确定障碍物位置，并根据障碍物位置找到对应栅格地图中的序号值，并对相应栅格置信度进行修改。障碍物栅格的置信度为1，自由栅格的栅格置信度为0。

2.1.2 栅格法与神经网络拓扑型状态空间相结合

基于生物激励神经网络的路径规划算法定义的环境由一个基于栅格法的神经网络拓扑状态空间构成。将工作环境地图放置在直角坐标系中，以设定大小将地图环境分割成若干个栅格，将每个栅格表示为一个神经元，栅格置信度为神经元活性值，用来区分障碍物和可移动区域。将栅格置信度看为一个元素，这些元素就组成了一个二维矩阵，此二维矩阵就是工作环境的栅格模型。此工作环境被分割成均匀的栅格单元，将障碍物栅格的域置信度赋值为-1，可以移动的自由栅格赋值为零，因此工作区域栅格模型如下：

依据生物激励神经网络的路径规划算法，第i个神经元的活性值：

(5)

2.2 初始路径修正策略

由分流方程和实验可知，路径规划初始阶段自由神经元的兴奋输入相比于外部抑制的影响弱化，且兴奋输入的作用时间点滞后于外部抑制的作用时间，因此，在初始阶段生物激励神经网络的路径生成策略被弱化，而更趋向于外部设定的路径选择策略，范莉丽所提出的改进算法优化了初始阶段的路径选择，而由于加入目标距离制导的因素，却在全局的路径规划中，再次弱化了生物激励神经网络算法的作用。这一作用导致在生成下一栅格单元位置的决策中，增加了路径长度以及路径转折次数的增加。

针对生物激励神经网络点对点路径规划在初始阶段产生路径偏离，使生成的路径长度增加，引入初始路径修正策略来解决这一问题，即在初始阶段时各神经元的活性值为零，需等待目标单元活性值传播，通过检测起始点单元的外部兴奋输入大小和起始单元活性值大小是否满足条件，决定是否触发生物激励神经网络路径规划算法，选择下一最优神经元位置，从而实现初始路径修正；并将选取活性值最大的神经元与选取神经元距离目标点的欧氏测定的距离结合，找出活性值足够大且距离目标点足够近的神经元为机器人移动的下一位置。

(6)

(7)

由分流方程可知，随着时间的推移，目标单元活性值向全局传播从而影响到整个状态空间的单元，即对其他非障碍物单元产生兴奋输入。机器人每隔0.01 s检测一次[Ii]+，当检测到起始单元的外部兴奋输入 [Ii]+>0时，检测起始单元活性值是否满足xi

图2 初始阶段环境活性值分布图

2.3 路径选择机制

假定起始点单元与目标点单元之间无障碍物，则起始点与目标点之间的最短路径为两者用直线相连所经过的栅格单元；如图3(a)所示。然而在实际的路径规划情况下，路径规划的环境多样而复杂，其障碍物分为规则图形和不规则图形，为有效避开障碍物并使路径长度最优，路径平滑度最优，为此引入路径选择机制，即测定当前位置神经元周围相邻的八个神经元与无障碍理想环境下生成路径的欧氏距离，将该因素引入至路径选择策略中，选择距离理想路径尽量短，活性值较大，距离目标点较近的神经元作为机器人移向的下一位置单元。具体实现方法如下。

图3 路径选择机制示意图

如图3(b)所示，机器人当前位置所在单元，活性值为xi，其到理想路径的最短距离为di；当前位置单元周围相邻的单元，活性值为xj，其到理想路径的最短距离为dj；为了降低机器人的能耗，平滑机器人的移动路径，采用如下的路径选择机制：

(8)

当检测到当前位置相邻的各个单元无障碍物时触发该路径选择机制，若当前位置相邻的各个单元存在障碍物时，引入选择机制则会给全局路径规划造成路径长度增加的结果。

2.4 改进算法具体步骤

1)全局神经元活性值初始化为零；

2)设置起始单元和目标单元；

3)等待目标点活性值在整个状态空间的传播，根据分流方程计算得出当前位置单元及周围可行走的单元的活性值，每隔0.01 s判断起始点单元外部激励输入是否大于零，若发生变化，再判断起始点单元活性值是否小于某一邻域神经元活性值，满足则触发生物激励神经网络路径规划算法，反之，等待并再次判断；

4)判断当前位置神经元相邻单元是否存在障碍物单元，若无障碍物单元，触发结合路径选择机制的生物激励神经网络算法；若存在障碍物单元，触发结合目标制导的生物激励神经网络算法；确定下一单元位置，并更新当前单元；

5)判断当前位置是否为目标点，若没有到达目标点则跳转4)，否则结束。

图4 算法流程图

3 实验结果及分析

3.1 静态复杂环境实验

通过设计静态环境下的仿真实验验证了本文改进后的生物激励神经网络路径规划算法的规划效果。静态环境实验为验证改进型算法是否能够解决图1所示路径偏离问题，优化生成路径。仿真环境为静态复杂环境地图，机器人移动的起始单元(12, 4)，目标单元(19, 29)，依据传统生物激励神经网络算法，结合目标制导改进算法以及本文改进算法进行对比实验，实验结果如图5～7所示。以Matlab 2016a为仿真实验平台，实验环境为30×30的栅格地图，单位栅格长度：Δx=0.5 m，环境模型参数：A=10,B=D=1,E=100,u=1,r0=2A=10,B=D=1,E=100,u=1,r0=2。

图5 传统生物激励算法生成路径

图6 目标制导算法生成路径

范莉丽结合目标制导改进生物激励算法存在的问题：过分倚重目标与下一位置单元的距离因素，尤其在初始状态时，由于目标对各单元的激励传播需要一定时间，此时下一位置单元的选择，完全依据目标制导因素，而使生物激励活性值的影响减弱，因此在全局的路径规划产生了偏离，导致不必要的路径增加。

图7 本文改进算法生成路径

在静态复杂环境下以算法效率、路径长度、路径转折次数3个评价因素建立的由传统算法、目标制导改进算法和本文改进后的算法3个对比实验可以得出，本文改进后的算法有较为突出的表现，分别在3个评价因素上都有一定的提升和优化，相对于传统算法和范莉丽改进算法。本文改进算法在路径生成过程中，首先并未出现路径偏离问题，其次并未完全侧重目标制导，而是选择无障碍理想路径制导，使全局路径规划问题得到优化。

表1 静态环境下3种方法的仿真结果对比

从表1可知，相比于传统生物激励神经网络方法，本文改进算法规划路径长度减少28.2%，路径转折次数减少63%。相比于结合目标制导改进算法，本文改进算法规划路径长度减少15.2%，路径转折次数减少56%。该改进算法所生成的路径更趋近于理想路径，其路径所经过单元分布紧贴在理想无障碍路径两侧，较少的偏离理想路径。实验结果表明，该改进后的算法实现了解决路径偏离和优化路径问题的预期目标，在减少路径长度和路径平滑度上有了一定改进。

4 结束语

本文针对传统生物激励神经网络方法中出现的路径偏离和路径未达最优的问题，提出了基于路径修正和无障碍理想路径制导的生物激励神经网络算法。在复杂静态环境下，对于初始阶段的路径偏离问题，引入路径修正策略：每0.01 s检测一次起始单元外部激励输入及起始单元活性值大小是否满足条件，即当目标单元激励影响传播至起始单元时，触发生物激励神经网络路径规划算法，从而避免了初始阶段的路径偏离；对于路径未达最优问题引入路径选择机制，在生成下一位置的算法中结合无障碍理想路径的导向，引入实际路径单元与无障碍理想路径单元间的理想路径接近率使路径神经单元活性值增大，从而达到减少路径长度和转折次数的效果，使路径更加平滑。仿真实验结果表明，该改进基于生物激励神经网络路径规划算法不仅有效解决初始阶段路径偏离问题，而且提升了路径质量。基于此改进方法，将进一步研究其在未知动态环境下的应用,并将其应用于装配式建筑机器人的相关研究。