·1224 工程科学学报，第42卷，第9期 2.3各子区域遍历 陷人死区 2.3.1BINN算法 机器人生成全覆盖的路径为： BINN算法是一种在线规划算法，该算法将每 Pnxpa max xj+cyjj=1.2,....k (5) 个栅格看作一个神经元，整个栅格地图变为由神 经网络组成的拓扑状态空间，其中神经元的活性 其中，c是一个正常数，代表方向权重的选择，y是 和机器人上一步所在位置pp、当前所在位置Pe、下 值由下式表示： 一步所在位置P相关的函数，y函数定义为： dxi =-Axi+(B-x 为149 (6) -(D+x)[° (1) 式中，△9；∈0，，它表示当前移动方向与下一移动 式(1)为分流方程，通过该方程可以计算出 方向之间的夹角.全覆盖路径规划过程如图6所示 栅格地图中每个神经元的活性值.式中：为第个 Begin 神经元的活性值；t是时间量；A、B和D为非负常数， 其中A代表衰减率，B代表神经元活性状态的上限， Initialize the neural network map D代表神经元活性状态的下限；k为与第个神经元 直接连接神经元的个数：为外部输入，可定义为： Calculate the current neuron activity value E,目标点 E,障碍物 (2) Adjacent neuron activity N Dead zone, 0,其他 is greater than current neuron? stop and waiting 其中：E是一个远远大于B的正常数+∑w） Y 和[分别表示兴奋输入和抑制输入，w=fd), Move to the next position d是第个神经元与第个神经元所在位置处在状 态空间中的欧几里得距离，为任意的单调减函 Complete coverage? 数，f可定义为 f(a)= uldij 0<dij<ro (3) End 0 d≥ro 图6BNN算法流程图 式中，和ro均为正常数，代表当前神经元与周边 Fig.6 Flow chart of BINN algorithm 神经元之间的侧向连接，0<”<1.神经元只在一 2.3.2子区域内部遍历 个小范围(0，o)内有局部连接，这个范围被称为神 在区域分解和子区域遍历顺序确定后，关键 经元的接受域，该接受域确保当前神经元周边 步骤是完成对子区域内部的遍历.BNN算法是一 8个神经元均在局部连接范围，每个栅格的长度 种在线规划算法，不需要学习过程，适合处理未知 为1，o的范围在（V2,2V2)之间，根据文献25]， 情况.由于矿区废弃地结构复杂，环境中可能存在 o的值取2.神经元间的连接权重是对称的，即 未知障碍物或移动障碍物等一系列现象，为了在 后期的工作中能够较好地应对突发状况，本文采 BNN算法既可以完成点对点路径规划又可 用BNN算法完成对每个子区域内部全覆盖 以完成全覆盖路径规划.机器人生成点对点的路 2.3.3区域路径转移 径为： 当前子区域内部覆盖完成之后到下一子区域 pn xpa maxxj.j=1.2.....k (4) 内部覆盖之前需要子区域间的路径转移，从而使 该路径生成过程为：机器人在当前位置选择 移动机器人按照子区域规划序列完成对所有子区 邻接神经元中具有最大活性值的神经元栅格作为 域的覆盖.针对该问题，本节主要使用BNN算法 下一位置，到达下一位置后，下一位置成为新的当 规划从上一个子区域遍历终点到下一个子区域遍 前位置，以此类推，直到到达目标点栅格.如果周 历起点的最短路径搜索，并计算该算法在最短路 边8个邻接神经元的活性值都不大于当前栅格的 径和时间消耗方面的总代价.因此，定义一系列由 神经元活性，则机器人待在原地保持不动，机器人 点组成的转移路径P:2.3    各子区域遍历 2.3.1    BINN 算法 BINN 算法是一种在线规划算法，该算法将每 个栅格看作一个神经元，整个栅格地图变为由神 经网络组成的拓扑状态空间，其中神经元的活性 值由下式表示： dxi dt =− Axi +(B− xi)   [Ii] + + ∑ k j=1 wi j[ xj ] +   −(D+ xi)[Ii] − （1） xi i t A B D A B D k i Ii 式（1）为分流方程[24] ，通过该方程可以计算出 栅格地图中每个神经元的活性值. 式中： 为第 个 神经元的活性值； 是时间量； 、 和 为非负常数， 其中 代表衰减率， 代表神经元活性状态的上限， 代表神经元活性状态的下限； 为与第 个神经元 直接连接神经元的个数； 为外部输入，可定义为： Ii =    E, 目标点 − E, 障碍物 0, 其他 （2） ( [Ii] ++ ∑k j=1wi j[ xj ]+ ) [Ii] − wi j = f ( di j) di j i j f f 其中：E 是一个远远大于B 的正常数； 和 分别表示兴奋输入和抑制输入， ， 是第 个神经元与第 个神经元所在位置处在状 态空间中的欧几里得距离， 为任意的单调减函 数， 可定义为 f ( di j) = { u/di j 0 < di j < r0 0 di j ⩾ r0 （3） u r0 u 0 < u < 1 (0,r0) i r0 ( √ 2,2 √ 2 ) r0 wi j = wji 式中， 和 均为正常数， 代表当前神经元与周边 神经元之间的侧向连接， . 神经元只在一 个小范围 内有局部连接，这个范围被称为神 经元 的接受域，该接受域确保当前神经元周边 8 个神经元均在局部连接范围，每个栅格的长度 为 1， 的范围在 之间 ，根据文 献 [25]， 的值取 2. 神经元间的连接权重是对称的，即 . BINN 算法既可以完成点对点路径规划又可 以完成全覆盖路径规划. 机器人生成点对点的路 径为： pn ⇐ xpn = max{ x j , j = 1,2,··· , k } （4） 该路径生成过程为：机器人在当前位置选择 邻接神经元中具有最大活性值的神经元栅格作为 下一位置，到达下一位置后，下一位置成为新的当 前位置，以此类推，直到到达目标点栅格. 如果周 边 8 个邻接神经元的活性值都不大于当前栅格的 神经元活性，则机器人待在原地保持不动，机器人 陷入死区. 机器人生成全覆盖的路径为： pn ⇐ xpn = max{ xj +cy j , j = 1,2,··· , k } （5） c yj pp pc pj yj 其中， 是一个正常数，代表方向权重的选择， 是 和机器人上一步所在位置 、当前所在位置 、下 一步所在位置 相关的函数， 函数定义为： yj = 1− ∆θ j π （6） 式中， ∆θ j ∈ [0,π] ，它表示当前移动方向与下一移动 方向之间的夹角. 全覆盖路径规划过程如图 6 所示. Begin Initialize the neural network map Calculate the current neuron activity value Adjacent neuron activity is greater than current neuron? Move to the next position Complete coverage? End Dead zone, stop and waiting Y N Y N 图 6    BINN 算法流程图 Fig.6    Flow chart of BINN algorithm 2.3.2    子区域内部遍历 在区域分解和子区域遍历顺序确定后，关键 步骤是完成对子区域内部的遍历. BINN 算法是一 种在线规划算法，不需要学习过程，适合处理未知 情况. 由于矿区废弃地结构复杂，环境中可能存在 未知障碍物或移动障碍物等一系列现象，为了在 后期的工作中能够较好地应对突发状况，本文采 用 BINN 算法完成对每个子区域内部全覆盖. 2.3.3    区域路径转移 P 当前子区域内部覆盖完成之后到下一子区域 内部覆盖之前需要子区域间的路径转移，从而使 移动机器人按照子区域规划序列完成对所有子区 域的覆盖. 针对该问题，本节主要使用 BINN 算法 规划从上一个子区域遍历终点到下一个子区域遍 历起点的最短路径搜索，并计算该算法在最短路 径和时间消耗方面的总代价. 因此，定义一系列由 点组成的转移路径 ： · 1224 · 工程科学学报，第 42 卷，第 9 期