移动机器人全覆盖路径规划是地形探测、地面资源勘探、地面清洁、战地侦查等任务的重要组成部分^[1-3]。作为移动机器人领域核心研究问题之一，全覆盖路径规划一直受到广泛关注。移动机器人完成全覆盖路径规划需要解决3个问题^[4-7]：1)需遍历工作区域内除障碍物以外的全部区域；2)在遍历过程中有效避开所有障碍物；3)在遍历过程中要尽量避免路径重复，缩短移动距离。迄今为止，关于全覆盖路径规划的方法多种多样，各有优劣，主要的方法可以分为：行为覆盖法^[8-9]、区域分割法^[10-12]、神经网络法^[13-16]等。

2000年Balch等^[8]提出一种移动机器人行为覆盖路径规划方法，机器人根据简单的移动行为，尝试性地覆盖工作区域，如果遇到障碍物，则执行对应的转向命令。这种方法是一种以时间换空间的低成本策略，如不计时间可以达到全覆盖。该算法无需了解整个作业区全貌，也不用依赖过多的传感器，处理器运算量也很小，是一种性价比很高的方案。但是，行为全覆盖算法工作效率低，路径规划策略过于简单，面对复杂地形机器人经常无法逃离死区^[9]。

为了使机器人能够逃离死区，同时减少算法的计算量，Jin等^[10]提出一种基于时空信息的全局导航与局部导航组合的算法。该算法一方面能够通过局部计算代替不必要的全局计算，减少了实时决策时局部最优导航的计算量；另一方面通过分层的方式使机器人能够逃离死区。但是在局部与全局的转换过程中，当周围没有未覆盖的区域时，机器人需要扩大邻近区域的面积来寻找未覆盖区域，这将导致覆盖效率的降低，尤其是当未覆盖区域距离机器人较远时^[11-12]。

近年来，神经网络算法被应用到全覆盖路径规划中^[13-14]。利用神经网络的自学习、并行性等特性，增强机器人的“智能”，提高覆盖效率。受神经网络结构与栅格地图单元类似的启发，加拿大学者S. X. Yang ^[15-16]等提出一种基于生物启发神经网络的移动机器人全覆盖路径规划算法，将需要全覆盖的二维栅格地图单元与生物启发神经网络的神经元一一对应起来，机器人实现全覆盖的实时路径规划是由神经元的活性值和机器人的上一位置产生的。该算法完全根据栅格地图单元的性质(未搜索单元、已搜索单元还是障碍物)，决定神经元的输入，直接计算神经元的活性值，不存在神经网络学习过程，算法实时性好，同时可以自动避障与逃离死区。

最近，Yan^[17]等在文献[15-16]的基础上，进一步将生物启发神经网络应用到水下机器人全覆盖路径规划中。该算法根据声呐传感器获取的信息，利用信息融合技术构建动态水下环境地图，根据水下感知的环境地图性质确定生物启发神经网络中神经元的活性值，水下机器人通过比较邻近神经元活性值进行路径规划，完成对工作区域的全覆盖，该方法将水下环境的地图构建与全覆盖路径规划有机结合，得到一套完整的水下机器人感知环境与全覆盖搜救方法。

但是基于生物启发神经网络的全覆盖算法计算量大，同时此种方法中神经网络模型的衰减率等参数没有最优值，在实现算法时只能通过反复实验确定，参数的设定存在人为不确定因素，从而影响其在线应用^[18]。

对此，本文在栅格地图的基础上，引入方向信度函数的概念，提出一种移动机器人全覆盖信度函数路径规划策略。该策略计算量小、路径重复率低，使得机器人不仅能够完成工作区域全覆盖任务，而且能够快速逃离死区。算法包括3个部分：1)根据地面环境的状态对栅格地图进行赋值，使用不同的函数值表示障碍物、已覆盖栅格和未覆盖栅格；2)引入方向信度函数对栅格信度函数值进行优化；3)机器人根据栅格信度函数进行覆盖路径规划。本文提出的基于栅格信度函数的移动机器人全覆盖路径规划算法能够实现动态工作区域的全覆盖，与生物启发神经网络算法相比有更短的覆盖路径。

1 基于栅格信度函数的全覆盖路径规划算法

全覆盖路径规划是指移动机器人以尽可能低的路径重复率遍历工作区域中的全部可到达点，它包含两个方面的技术指标，即区域覆盖率和路径重复率。本文以弓形路径移动方式为基础，引入方向信度函数对机器人移动路径进行优化，完成对工作区域的全覆盖的同时降低路径重复率。

1.1 栅格位置性质函数

为了避免机器人与障碍物发生碰撞，防止机器人对同一栅格单元重复覆盖，将对栅格地图进行赋值。依据每个栅格的性质赋不同的信度函数值，表示出每个栅格的状态信息^[19-22]。本节以二维的栅格地图为例说明怎样对栅格进行信度赋值。图1(a)显示的是一个二维的栅格地图，工作区域被分成了9个栅格，其中黑色栅格表示被障碍物占领，白色栅格表示自由空间，P_c表示机器人当前所在的位置。根据式(1)对栅格位置性质函数x_j赋值，如栅格6表示障碍物，则被赋值为- $\infty $ ；栅格1、2、3、4、5、7、8表示自由未被覆盖单元，则被赋值为1；栅格P_c表示已被覆盖单元，则被赋值为0.5。

${x_j} = \left\{ {\begin{array}{*{20}{l}}{1,\quad \text{该单元未覆盖}}\\{0.5,\quad \text{该单元被覆盖}}\\{ - \infty ,\quad \text{该单元是障碍物}}\end{array}} \right.$

(1)

式中x_j表示第j个栅格的位置性质函数值。同时为了避免同一个栅格的反复覆盖，在此约定栅格被多覆盖一次，其位置性质函数值就减少0.5。假如栅格P_c被覆盖过一次，其位置性质函数值为0.5；如果栅格P_c被覆盖了两次，其位置性质函数值为0。

1.2 方向信度函数

为了降低路径重复率，提高覆盖效率，对机器人的移动路径进行优化，引入方向信度函数 ${y_j}$ 。 ${y_j}$ 定义为

${y_j} = \left\{ {\begin{array}{*{20}{l}}{1 - \displaystyle\frac{{\Delta {\theta _j}}}{\text{π} },\quad \text{机器人未陷入死区}}\\{\cos \Delta {\varphi _j},\quad \text{机器人陷入死区}}\end{array}} \right.$

(2)

式(2)中方向信度函数的定义分为两种情况，当机器人未陷入死区时， ${y_j}$ 是机器人当前位置与下一位置移动方向角之差 $\Delta {\theta _j}$ 的函数，是关于前一位置 ${p_p}$ 、当前位置 ${p_c}$ 和可能为下一位置 ${p_j}$ 的函数。此时方向信度函数为 ${y_j} = 1 - \displaystyle\frac{{\Delta {\theta _j}}}{\text{π}}$ ，机器人移动方向角之差 $\Delta {\theta _j}$ 表示为

$\begin{array}{c}\!\!\!\!\!\!\!\!\! \Delta {\theta _j} = \left| {{\theta _j} - {\theta _c}} \right| = \\\!\!\!\!\!\!\!\!\! |a\tan 2({y_{{p_j}}} - {y_{{p_c}}},{x_{{p_j}}} - {x_{{p_c}}}) - a\tan 2({y_{{p_c}}} - {y_{{p_p}}},{x_{{p_c}}} - {x_{{p_p}}})|\end{array}$

(3)

式中： $({x_{Pc}},{y_{Pc}})$ 、 $({x_{Pp}},{y_{Pp}})$ 和 $({x_{Pj}},{y_{Pj}})$ 分别为地图上机器人的当前位置、前一步和下一步的位置坐标； ${\theta _c}$ 是机器人前一步和当前位置之间的角度； ${\theta _j}$ 是机器人当前位置和下一步位置之间的角度； $\Delta {\theta _j} \in [0,{\text{π}}]$ ，如图2所示，若 $\Delta {\theta _j} = 0$ ，则机器人沿着直线移动；若 $\Delta {\theta _j} = {\text{π}}$ ，则往相反方向移动。假设在图1的栅格地图中，机器人当前在中心栅格位置，前一步在栅格5的位置，图1(b)给出了机器人各个相邻栅格的方向信度函数值，即机器人下一步可能移动的8个邻近栅格的优化函数值。

机器人陷入死区是指它的周边相邻区域，或者是边界，或者是障碍物，或者是已覆盖过的区域。只有从死区逃离出来，才能继续完成全覆盖任务，而逃离死区的路径，直接决定着全覆盖的路径重复率。当机器人陷入死区后，为了让机器人以尽可能短的路径逃离死区，本文提及的算法不再以当前位置与下一步位置的移动角之差作为方向向导，而是将当前位置与距离最近未覆盖栅格位置和下一步位置的角度差作为移动的方向向导，引导机器人快速逃离死区。机器人陷入死区后的方向信度函数定义为 ${y_j} = \cos \Delta {\varphi _j}$ ，其中移动方向角之差 $\Delta {\varphi _j}$ 为

$\begin{array}{c}\Delta {\varphi _j} = \left| {{\varphi _T} - {\theta _j}} \right| = |a\tan 2({y_{{T_j}}} - {y_{{p_c}}},{x_{{T_j}}} - {x_{{p_c}}}){\kern 1pt} - \\{\kern 1pt} \;\;\;\;\;\;\;\;\;a\tan 2({y_{{p_j}}} - {y_{{p_c}}},{x_{{p_j}}} - {x_{{p_c}}})|\end{array}$

(4)

式中： $\Delta {\varphi _j}$ 是关于机器人当前位置和下一可能位置连线与机器人当前位置和最近未覆盖栅格连线夹角，如图3所示。 $({x_{Tj}},{y_{Tj}})$ 为距离当前位置最近未覆盖栅格的位置； ${\varphi _T}$ 是机器人当前位置和最近未覆盖栅格位置之间的角度。式中 $\Delta {\varphi _j} \in [0,{\text{π}}]$ ，当前位置与最近未覆盖栅格位置和下一步位置的角度差越小，方向信度函数越大，使得机器人移动方向始终指向最近未覆盖的栅格。

1.3 路径选择策略

在栅格地图中，全覆盖路径规划问题就演变为寻找机器人的下一个移动位置，只有准确找出了该位置，才能使机器人自主规划出一条切实可行的无碰撞且重复率低的移动路径。为了避开障碍物并且能够完成工作区域的全覆盖，根据栅格位置性质函数和方向信度函数，定义一个综合栅格信度函数 ${F_j}$ ，路径选择的原则是机器人始终向着综合栅格信度函数值最大的方向运动。其定义为

${p_j} \Leftarrow {F_{{P_j}}} = \max \{ {F_j} = {x_j} + c{y_j},{\kern 1pt} \;\;\;j = 1,2,\cdots \!,k\} $

(5)

式中： ${p_j}$ 表示机器人下一个行驶位置； $c$ 是一个权值常数， $0 < c < 1$ ； $k$ 是与当前栅格 ${p_c}$ 相邻的栅格个数。根据式(5)可以发现机器人选择下一步路径的时候，同时考虑了栅格的状态位置和转向，使得规划出来的路径尽可能保持直行，减少转向。针对图1所示的栅格地图进行路径选择，首先根据式(1)确定每个栅格的位置性质函数 ${x_j}$ ；由于机器人此时没有进入死区，再根据式(2)和(3)计算出每个栅格的方向信度函数 ${y_j}$ (如图1(b)所示)；最后根据式(5)计算出每一个栅格的综合信度函数(如图4所示)，机器人选择综合信度函数值最大的栅格5作为下一步运行的位置。

为了进一步说明机器人的路径选择策略，图5显示了二维环境中基于栅格信度函数路径选择策略的路径规划效果(设置参数 $c = 0.5$ )。如图5(a)所示，机器人从起点(1,1)出发，在方向信度函数 ${y_j} =$ $ 1 - \displaystyle\frac{{\Delta {\theta _j}}}{\text{π}}$ 的约束下，上下迂回来选择路径，保证了路径的规整和方向改变最少的效果。从栅格位置性质函数值来看，机器人覆盖过一次的地方，函数值变为0.5，而未覆盖过的地方，函数值为1，维持栅格位置性质函数值最高，“吸引”机器人前往。当机器人运动到(2,20)时，右边出现障碍物，而根据本文算法的定义障碍物的位置信度函数值为- $\infty $ 。由于机器人总是选择栅格信度函数值最大栅格作为下一步移动位置，因此在路径规划过程中将自动规避这些障碍物区域。图5(b)显示了当机器人移动到(20,12)时陷入死区。此时方向信度函数调整为 ${y_j} = \cos \Delta {\varphi _j}$ ，保证机器人向着未覆盖的区域移动。图5(c)显示了机器人逃离死区的过程，图中黑色线段表示机器人逃离死区的路径。通过图5中机器人路径的选择过程可知，本文提及的栅格信度函数全覆盖算法不仅能够使机器人躲避障碍物，而且可以快速的逃离死区。

进一步分析机器人未陷入死区时每一步路径选择，表1列出了图5(a)中前6步机器人邻近位置的栅格信度函数值。如表所示，机器人初始位置是(1,1)，由于靠近边界只有3个邻近栅格可以作为下一步的位置，根据式(1)、(2)、(5)计算出其邻近栅格信度函数值分别为1.375、1.250和1.500，根据路径选择策略选择最大值1.500对应的 $(x,y + 1)$ 作为下一步的位置，即取(1,2)为机器人的下一步移动位置。随即(1,2)作为机器人的当前位置继续选择路径。按照上述过程，(1,3)、(1,4)、(1,5)、(1,6)、(1,7)依次作为机器人第3步、第4步、第5步、第6步、第7步的位置。

当机器人陷入死区以后，采用 ${y_j} = \cos \Delta {\varphi _j}$ 的方向信度函数逃离死区。表2列出了图5(c)机器人逃离死区过程中的栅格信度函数。如表所示，机器人移动到(20,12)时陷入死区，此时离机器人当前位置最近的未覆盖栅格是(20,10)，根据式(1)、(2)、(5)计算出其邻近栅格信度函数值分别为– $\infty $ 、–0.646、0.500、0.147和–0.500，根据路径选择策略选择最大值0.500对应的 $(x - 1,y)$ 作为下一步的位置，即取(19,12)为机器人的下一步移动位置。随即(19,12)作为机器人的当前位置继续选择路径。按照上述过程，机器人依次选择(18,12)、(17,12)、(16,12)、(15,11)作为移动位置。当机器人移动到(16,10)时逃离死区。

2 仿真实验分析

仿真实验设置工作区域的大小为 $100\,\,\,{{m}} \times $ 100 m，其中随机分布着各种形状的障碍物。本文提及的算法是在栅格地图中对移动机器人的全覆盖路径规划进行研究，因此需对工作区域构建栅格地图。仿真实验中设每个栅格面积为 $5\,\,{{m}} \times 5\,\,{{m}}$ ，那么工作区域被构建为 $20 \times 20$ 的栅格地图。为了讨论路径规划算法效果，将每个机器人都视为质点，不考虑其形状，同时假设机器人是可以全方位运动的。所有的仿真实验设置参数 $c = 0.5$ 。本节通过动态障碍物环境中仿真实验，证明本文提及的栅格信度函数算法能够自动避开障碍物、逃离死区完成对工作区域的全覆盖。同时，通过与生物启发神经网络算法的比较，本文提及的算法有更高的覆盖效率。

2.1 动态障碍物环境中全覆盖路径规划

工作区域中，动态障碍物对机器人的路径规划具有不容忽视的影响，尤其是机器人在执行地面全覆盖式的地形勘探和数据测量等任务时，动态障碍物的出现不仅威胁机器人安全，还会妨碍其对整个区域的全覆盖效果。本节针对动态障碍物对区域全覆盖的影响进行研究。如图6(a)所示，机器人从(1,1)位置出发执行全覆盖任务。障碍物3是动态的，起初在地图上占据着相关区域，机器人无法对该区域进行覆盖，如图6(b)所示。

随着机器人任务的继续执行，当机器人移动至300步时，障碍物3离开(图6(b)所示)，地图上相关区域的栅格性质函数值变为1。当机器人移动到(20,4)时，正好执行完障碍物3离开前的地图覆盖，如图6(c)所示。但是此时由于障碍物离开留下的区域需要覆盖，因此根据快速逃离死区的规则，机器人从(20,4)再度出发，前往最近未覆盖栅格(14,11)，此时机器人采用 ${y_j} = \cos \Delta {\varphi _j}$ 方向信度函数策略，以尽量短的路径到达未覆盖的区域。图6(c)中黑色线段为(20,4)到未覆盖区的移动路径。当机器人到达未覆盖栅格(14,11)之后，机器人恢复为 ${y_j} = 1 -$ $ \displaystyle\frac{{\Delta {\theta _j}}}{\text{π} }$ 的方向信度函数规则，继续执行区域覆盖任务直至完成，最终路径效果见图6(d)。由此可见，栅格信度函数值能够跟随环境地图信息的变化而变化，从而指导机器人执行新区域覆盖任务。因此本文提及的算法能够实现动态障碍物环境中的全覆盖路径规划。

2.2 不同算法的比较

为了进一步考察本文所提算法的性能，本节将与其他算法对区域覆盖率、路径重复率、总行程等指标进行比较。图7显示了两种不同算法对20×20且存在不规则障碍物的栅格区域进行全覆盖路径规划的结果。采用文献[17]的生物启发神经网络全覆盖方式得到的路径规划效果如图7(a)所示。采用本文提及的栅格信度函数算法的路径规划结果如图7(b)所示。两种路径规划方法进行效果对比的评价指标如表3所示。通过图7和表3的结果可知，虽然两种方法的区域覆盖率均达到100%，但是机器人逃离死区的路径有较大的区别。生物启发神经网络算法由于陷入死区的位置离未覆盖区域较远，神经元的活性传递需要较长时间，使得机器人长期停留在死区，需要更长的路径才能逃离死区。而栅格信度函数算法在机器人陷入死区后能通过调整方向信度函数的方法快速的逃离死区。图7中黑色线段显示了两种不同算法逃离死区的路径。虽然两种算法在未陷入死区前机器人移动路径相同，但是由于逃离死区的路径不同，导致两种算法的重复覆盖栅格数，路径重复率、总行程等指标的差异。从表3可见生物启发神经网络算法的重复覆盖的栅格有39块，而栅格信度函数算法只有23块；生物启发神经网络算法的路径重复率几乎是本文算法的2倍；总行程后者比前者少16步。结果表明基于栅格信度函数的算法可以有效降低路径重复率，缩短行程，对于机器人来说路径规划更适合控制，更节省能源。

3 结束语

本文采用栅格信度函数算法解决了移动机器人全覆盖路径规划问题。仿真实验证明本文所提算法在二维障碍物环境中，不仅能够实现动态障碍物工作区域的全覆盖，而且还能够快速逃离死区，降低了机器人路径的重复率，提高了覆盖效率。限于篇幅，本文未讨论实际的二维环境栅格地图的构建以及机器人的形状、转向幅度、定位对全覆盖路径规划的影响，后续研究将把栅格地图构建与全覆盖路径规划结合，研究移动机器人对真实环境的感知与路径规划方法。