随着智能化水平的提高，移动机器人已成为国内外学者研究的热点。作为机器人领域核心研究问题之一——全遍历路径规划，在实际生活生产中有着广泛的应用，如地面清洁、目标搜索、矿产勘查及缺陷检测等^[1-5]。移动机器人全遍历路径规划主要需要解决2个问题：1)需遍历工作区域内除障碍物以外的全部区域；2)遍历过程中尽量避免重复遍历^[6-10]。迄今为止，针对移动机器人全遍历路径规划的研究已有大量的成果，但都集中于地面移动机器人，对爬壁机器人的研究较少^[11-14]。

文献[1]提出了一种全覆盖信度函数路径规划算法。使用不同的函数值表示障碍物、已覆盖栅格和未覆盖栅格；同时引入方向信度函数对栅格信度函数值进行优化；最后，机器人根据栅格信度函数进行遍历路径规划。该方法不仅能实现工作区域的全遍历，并且能够引导机器人快速有效地逃离死区；但该算法未对工作区域分块，对于面积较大的工作环境容易产生累积误差，增大了漏检率。文献[15]提出了一种精确单元分解法。首先，将工作区域分解为一系列子区域；接着，采用旅行商算法找出子区域的遍历顺序；最后，通过迂回运动依次遍历各子区域，直到达到全遍历为止。该方法能实现工作区域的全遍历，但是没有考虑机器人陷入死区的情况，当机器人陷入死区时，其运动路径可能会发生紊乱，加大重复遍历率。

本文根据储罐探伤爬壁机器人(以下简称机器人)工作环境的特殊性，结合单元分解、邻接矩阵及路径选择函数提出了一种基于栅格地图的矩形分解^[16]全遍历路径规划算法。首先，建立栅格环境模型，对每个栅格赋予x_i值来表示其栅格状态；接着，采用矩形分解法将工作环境划分为若干子区域，通过图的深度优先搜索算法和邻接矩阵确定各子区域的衔接顺序；最后，在子区域的遍历和切换过程中，引入方向函数y_i来判断机器人是否陷入死区，结合栅格的x_i值提出路径选择函数f_i，引导机器人快速逃离死区。

1 储罐壁面简化

机器人工作于圆柱形储罐外壁，由于储罐外壁是一个曲面，因此其工作环境是一个三维空间。机器人在储罐外壁工作时的俯视图如图 1所示。

目前国内外石化行业中常用的圆柱形储罐直径为24.0~40.0 m，高为9.6~16.3 m。本文以储罐直径为24.0 m、高为9.6 m，机器人机身宽度B=300 mm为基础进行计算。

$ \alpha = \arctan \frac{B}{{2r}} = \arctan \frac{{300}}{{24\;000}} \approx {0.716^ \circ } $

(1)

从式(1)可以看出：α的值很小，可忽略不计；并且随着储罐容积的增大，α值呈降低的趋势。因此，可近似看作机器人在竖直平面内工作，即简化为一个二维平面问题。

2 机器人遍历基本路径确定

机器人在罐壁工作时可按螺旋式或迂回式覆盖全部工作区域。螺旋式工作时，机器人在壁面的转向次数多且定位比较困难；而迂回式更易于控制和实现机器人对整个罐壁的全覆盖^[17-19]。因此，本文选择迂回式作为机器人的全覆盖方式。

本文将机器人视为一个质点，爬壁机器人简化模型如图 2所示。

机器人在储罐外壁的遍历运动为匀速直线运动和匀速回转运动两类，本节将根据漏检面积S_U分析直线运动及回转运动的遍历效率，以确定遍历基本路径。

1) 直线运动：机器人以某一恒定速度从起点直线移动到终点，如图 3所示。显然，直线运动漏检面积S_UL=0。

2) 回转运动：假定机器人超声波传感器的重叠面积为零(即以超声波阵列传感器宽度D的二分之一作为机器人质心c的转弯半径)，当机器人传感器扫过的最远处与障碍物边界相切(即如图 4所示距离障碍物边界为I)时进行回转运动。

则：

$ I = \sqrt {{D^2} + {{\left( {\frac{S}{2} + d + m + n} \right)}^2}} - \left( {\frac{S}{2} + d + m + n} \right) $

(2)

回转运动的漏检面积为：

$ \begin{array}{*{20}{c}} {{S_{{\rm{UR}}}} = \left( {S + 2I + 2n + 2m + 2d} \right)D - }\\ {\frac{{\pi I}}{2}\left( {S + I + 2n + 2m + 2d} \right)} \end{array} $

(3)

综上所述，机器人直线运动时不存在漏检，回转运动时存在部分漏检区域。为使漏检面积更小，应减少机器人回转运动次数。

3 基于栅格地图的单元分解全遍历路径规划算法

机器人需以尽可能高的覆盖率和尽可能低的重复率覆盖储罐外壁所有可达区域。由于储罐罐壁表面积较大(根据第1节的分析，其表面积为723.8~2 048.3 m²)，为了减小定位误差造成的漏检率，本文采用矩形分解法将储罐外壁划分为若干子区域，机器人依次遍历各子区域以完成对罐壁的全覆盖。

3.1 栅格环境建模

本文采用栅格地图来表示储罐外壁，方形栅格的大小为机器人前端超声波阵列传感器的宽度D；储罐外壁常见的障碍物有常压人孔、手孔、盘梯、接管及焊缝等。根据栅格是否被障碍物占据，赋予每个栅格一个表示栅格单元状态的x_i值，机器人在运动过程中实时更新x_i值。x_i的取值如公式(4)所示：

$ {x_i} = \left\{ {\begin{array}{*{20}{l}} { - \blacksquare ,}&{\text{障碍栅格}} \\ {1,}&{\text{自由栅格}} \\ {1 - i\left( {i = 1,2,3, \cdots } \right),}&{{\text{遍历过}}i{\text{次的自由栅格}}} \end{array}} \right. $

(4)

定义1：若栅格全部或部分被障碍物占据，则将此栅格定义为障碍栅格；若栅格未被障碍物占据，则将此栅格定义为自由栅格。

建立一个环境模型如图 5所示，其中白色部分为自由区域，黑色部分为障碍物区域；将此环境模型进行栅格化处理后得到栅格地图，如图 6所示。

3.2 单元分解

采用矩形分块的思想分解目标环境。图 6中，每个栅格可以用(x，y)来表示，x表示栅格所在的列数，y表示栅格所在的行数。矩形分块的具体步骤为：

1) 找出每个障碍物中x值最小的栅格，如果x值最小的栅格不止一个，则找出其中y值最小的栅格并记为M(x₁，y₁)；

2) 找出每个障碍物中x值最大的栅格，如果x值最大的栅格不止一个，则找出其中y值最大的栅格并记为N(x₂，y₂)；

3) 将每个障碍物以其M点和N点虚拟为一个矩形障碍物；

4) 以障碍物的M点为起点沿纵向做割线，直至到达地图边界或障碍物或其他的分割线；

5) 以障碍物的N点为起点沿横向做割线，直至到达地图边界或障碍物或其他的分割线。

将图 6的栅格环境地图进行如上的单元分解后得到的结果如图 7、图 8所示。

3.3 子区域衔接顺序的确定

将环境地图分解为若干子区域后，机器人需要做的是按照一定的方式将各子区域进行有效衔接，在最短时间内完成各子区域有序的遍历；同时要满足重复覆盖率小、路径最短的要求。

定义2：分块环境地图中，如果任意2个矩形子区域之间存在公共边或者公共点，定义这2个子区域相邻；反之则不相邻。

最短路径问题是图论的一个重要应用。有序的三元组G=(V, E, ω)称为一个加权无向图，其中：V=(v₁, v₂, …, v_n)为有穷非空集，称为顶点集，文中以每个子区域的中心作为顶点；E称为边集，文中以两相邻顶点间的连线作为无向图的边；ω为权重，文中以两相邻顶点间的距离作为权值。分块环境中各子区域的无向图如图 9所示。

对于有n个顶点的加权无向图，其邻接矩阵A=(a_ij)_n×n，其中：

$ {{a}_{ij}}=\left\{ \begin{align} &{{\omega }_{ij}},\ \ \ \ 两顶点相邻 \\ &0,\ \ \ \ \ \ \ i=j \\ &\blacksquare ,\ \ \ \ \ 两顶点不相邻 \\ \end{align} \right. $

(5)

则加权无向图G的邻接矩阵为：

$ \mathit{\boldsymbol{A}} = \left[ {\begin{array}{*{20}{c}} \begin{gathered} 0 \hfill \\ 19.24D \hfill \\ \hfill \\ \blacksquare \hfill \\ \blacksquare \hfill \\ \blacksquare \hfill \\ \blacksquare \hfill \\ \end{gathered} &\begin{gathered} 19.24D \hfill \\ 0 \hfill \\ 9.66D \hfill \\ 17.1D \hfill \\ \blacksquare \hfill \\ \blacksquare \hfill \\ \blacksquare \hfill \\ \end{gathered} &\begin{gathered} 9.66D \hfill \\ 20.5D \hfill \\ 20.5D \hfill \\ 16.8D \hfill \\ 17.1D \hfill \\ \blacksquare \hfill \\ \blacksquare \hfill \\ \end{gathered} &\begin{gathered} \blacksquare \hfill \\ 17.1D \hfill \\ 0 \hfill \\ 0 \hfill \\ 20.5D \hfill \\ 12.18D \hfill \\ 20.11D \hfill \\ \end{gathered} &\begin{gathered} \blacksquare \hfill \\ \blacksquare \hfill \\ 16.8D \hfill \\ 20.5D \hfill \\ 0 \hfill \\ \blacksquare \hfill \\ 12.18D \hfill \\ \end{gathered} &\begin{gathered} \blacksquare \hfill \\ \blacksquare \hfill \\ 17.1D \hfill \\ 12.18D \hfill \\ \blacksquare \hfill \\ 0 \hfill \\ 20.5D \hfill \\ \end{gathered} &\begin{gathered} \blacksquare \hfill \\ \blacksquare \hfill \\ \blacksquare \blacksquare \hfill \\ 20.11D \hfill \\ 12.18D \hfill \\ 20.5D \hfill \\ 0 \hfill \\ \end{gathered} \end{array}} \right] $

定义3：在无向图G中，仅经过每个顶点一次且权重最小的路径，称为最优全遍历路径。

按深度优先搜索算法可找出无向图G的最优全遍历路径，其过程如图 10所示。首先用加权邻接矩阵表示子区域无向图，任意设置一个起点，并置访问标志；然后扫描加权矩阵里起点所在的行，搜索与起点距离最近且未被访问过的顶点，并置访问标志；接着扫描加权矩阵里上一顶点所在的行，搜索与上一顶点距离最近且未被访问过的顶点，并置访问标志。若顶点存在，则继续向后扫描；若顶点不存在，则返回上一顶点重新搜索；重复以上步骤，直到所有顶点都被访问过，输出此顶点序列。按照这种算法，假设机器人从顶点①出发，则最优全遍历路径为:①→③→②→④→⑥→⑦→⑤。

3.4 各子区域遍历

本文采用迂回式规划遍历各子区域，根据第2节的分析，为减小机器人的漏检面积，应尽量减少爬壁机器人回转运动的次数。

定义4：当机器人周边的相邻区域均为边界、障碍物或者是已覆盖过的栅格时，爬壁机器人陷入死区。

如图 11所示，当机器人陷入死区后，为了让机器人以尽可能短的路径逃离死区，本文以机器人当前所在栅格位置与距离最近且未遍历栅格位置和下一步可能移动到的栅格位置的角度差作为移动的方向向导，引导机器人快速逃离死区。引入方向函数y_i，其定义为：

$ {y_i} = \cos \Delta {\varphi _i} $

(6)

其中移动方向角之差Δφ_i为：

$ \Delta {\varphi _i} = {\varphi _{\text{T}}} - {\theta _i} = \arctan \left| {\frac{{{y_{{\text{U}}i}} - {y_{{\text{p}}i}}}}{{{x_{{\text{U}}i}} - {x_{{\text{p}}i}}}}} \right| - \arctan \left| {\frac{{{y_{{\text{N}}i}} - {y_{{\text{p}}i}}}}{{{x_{{\text{N}}i}} - {x_{{\text{p}}i}}}}} \right| $

(7)

式中：Δφ_i是机器人当前栅格位置和下一步可能移动到的栅格位置连线与机器人当前栅格位置和最近未覆盖栅格位置连线的夹角，Δφ_i∈(0, π)；(x_pi, y_pi)是机器人当前所在栅格位置坐标；(x_Ni, y_Ni)是机器人下一步可能移动到的栅格位置坐标；(x_Ui, y_Ui)是距离机器人当前位置最近未遍历的栅格位置坐标；φ_T是机器人当前所在位置和最近未覆盖栅格位置之间连线与横坐标之间的夹角；θ_i是机器人当前栅格位置与下一步可能移动到的栅格位置之间连线与横坐标之间的夹角。

机器人移动方向函数如图 12所示。

为了使机器人避开障碍物并以尽可能短的路径逃离死区，本文根据栅格的x_i值和方向函数y_i，定义一个路径选择函数f_i，路径选择的原则是机器人始终向着路径函数值最大的方向运动。其定义为：

$ {f_i} = {x_i} + t{y_i} $

(8)

$ {U_i} \Leftarrow {f_{{U_i}}} = \max \left\{ {{f_i} = {x_i} + t{y_i},i = 1,2, \cdots ,k} \right\} $

(9)

式(9)中：U_i表示机器人下一个位置；t是一个权值常数，0 < t < 1；k是与当前栅格相邻的栅格个数。以图 11中机器人陷入死区时为算例，结合路径选择函数f_i(设置权值常数t=0.5)分析机器人逃离死区的具体路径。根据公式(4)计算机器人在死区位置时其周围栅格的x_i值，如图 13(a)所示；根据公式(6)和公式(7)计算机器人在死区位置时其周围栅格的方向函数值y_i，如图 13(b)所示；根据公式(8)计算机器人在死区位置时其周围栅格的路径选择函数值f_i，如图 13(c)所示。

由于机器人始终向着路径选择函数f_i值最大的方向移动以逃离死区，因此机器人下一步的移动位置为机器人正下方的栅格。进一步分析机器人陷入死区时每一步的逃离路径，表 1列出了图 11中机器人逃离死区过程中每走一步其周围栅格的路径选择函数值，以图 11左下角为起点，每个栅格的大小为D。图 14显示了爬壁机器人逃离死区并继续遍历当前子区域的过程，图中黑粗色线段表示爬壁机器人逃离死区的路径。

4 相邻子区域的切换

机器人完成当前子区域的遍历以后，需依次切换到下一相邻子区域进行遍历。本文为每个子区域设置4个关联栅格，以得到更短的切换路径，如图 15所示。4个关联栅格按逆时针顺序排列。假设爬壁机器人的工作环境被划分为z个子区域。

定义5：当前子区域遍历起始栅格为子区域进入栅格c_{i_in}；当前子区域遍历结束栅格为子区域出口栅格c_{i_out}。

根据机器人遍历各子区域所需转向次数的奇偶性，子区域进入栅格和出口栅格有以下不同的关系：

$ \left\{ \begin{gathered} {c_{i1}} \Leftrightarrow {c_{i2}},{c_{i3}} \Leftrightarrow {c_{i4}},\;\;\;\;转向次数为奇数 \hfill \\ {c_{i1}} \Leftrightarrow {c_{i4}},{c_{i2}} \Leftrightarrow {c_{i3}},\;\;\;\;转向次数为偶数 \hfill \\ \end{gathered} \right. $

(10)

其中子区域进入栅格和出口栅格分别位于“⇔”的两侧；如果进入栅格确定了，则出口栅格随之确定。

定义6：当前子区域遍历完成以后，以与当前子区域出口栅格欧式距离d_ij最短的相邻子区域的关联栅格作为该子区域的进入栅格。

$ {d_{ij\_\min }} = \min d\left( {{c_{i\_{\text{out}}}},{c_{j\_{\text{in}}}}} \right)\;\;\;\;i,j \in \left( {1,z} \right) $

(11)

相邻子区域的切换有以下2种情况：

1) c_{i_in}和c_{j_out}之间无障碍物阻隔。此种情况下，当前子区域遍历结束以后, 机器人根据d_{ij_min}确定下一相邻子区域的进入栅格，然后匀速直线运动到此栅格后开始下一子区域的遍历。无障碍物阻隔时机器人的移动路径如图 16所示。

2) c_{i_in}和c_{j_out}之间有障碍物阻隔。此种情况下，机器人首先根据d_{ij_min}确定下一相邻子区域的进入栅格；其次，根据公式(8)计算出机器人当前位置周围栅格的路径选择函数值f_i，以确定机器人从当前子区域的出口栅格运动到下一子区域进入栅格的路径，对于方向函数y_i，以相邻子区域的进入栅格坐标(x_{j_in}, y_{j_in})替换掉公式(7)中距离机器人当前位置最近的未遍历栅格坐标(x_Ui, y_Ui)进行计算即可。有障碍物阻隔时机器人的移动路径如图 17所示。

5 仿真分析

本文提及的算法是在栅格地图中对机器人进行路径规划研究，因此需对工作区域构建栅格地图。仿真实验工作区域设置为30D×30D的栅格地图，其中随机分布着各种形状的障碍物，如图 18所示。首先对仿真环境中的障碍物进行矩形化处理，结果如图 19。接下来根据矩形分块思想对环境进行分块，整个栅格环境被分解为9个大小不同的子区域，结果见图 20，建立表示各子区域重心间距离的邻接矩阵并以图的深度优先搜索算法确定各子区域的最优连接顺序为：①→③→⑤→⑦→⑨→⑧→⑥→④→②。为了讨论路径规划算法效果，将机器人视为质点，同时假设爬壁机器人是可以全方位运动的，所有的仿真实验设置参数t=0.5。机器人全遍历路径规划化仿真结果如图 21所示。

定义7：机器人按规划完成遍历后，已遍历面积S_c与可达区域面积S_v之比为遍历面积百分率J_c，即J_c=S_c/S_v；所有遍历重叠面积之和S_o与可达区域面积S_v之比为重复遍历率J_o，即J_o=S_o/S_v。

从图 21中可以得出机器人的遍历面积百分率及重复遍历率, 如表 2所示。

由仿真结果分析：提出的全遍历路径规划方法基本实现了对环境的全遍历，虽存在重复遍历情况，但重复遍历率较低且重复部分为机器人逃离死区的移动路径。

6 结论

本文采用矩形分解法将储罐罐壁划分为若干子区域，在环境拓扑图中找到了一种最优的子区域连接顺序；同时结合路径选择函数找出了爬壁机器人陷入死区时的最优逃离路径。仿真实验证明本文所提算法能够能够引导机器人以低重复率及高覆盖率实现工作区域的全覆盖，且能快速有效地逃离死区。