钟灿灿，陈万米

(上海大学机电工程与自动化学院，上海 200444)

0 引言

路径规划是移动机器人研究的一个重要方向，指的是在移动机器人的运动环境中，为移动机器人寻找一条从起始点到终止点的无碰撞路径[1-4]。针对该方向，国内外学者提出了许多改进算法。栅格法对传统的八邻域节点进行改进，缩短了路径长度，显著减少了时间[5]。人工势场法提出自适应调节算法，很好地克服了目标不可达的问题[6]。行为分解法提出自适应神经模糊控制系统对隶属度函数、模糊控制规则进行优化，以达到更好的控制效果[7]。但这些改进算法中全局路径规划器反应很差，局部路径规划器易陷入局部死区陷阱[8]，不能使移动机器人很好地完成任务。

为了更加有效地解决移动机器人的路径优化问题，将全局路径规划算法与局部路径规划算法相结合，构造混合式路径规划算法，弥补了栅格法、人工势场法和行为分解法的缺点，并充分利用各自的优点来解决移动机器人的路径优化问题。

1 问题描述

目前，移动机器人的导航技术虽然取得了不错的成绩，但是大部分导航技术研究中的环境比较结构化。当移动机器人的工作环境为非结构化的家庭环境时，其中存在的墙壁、家具、门等大量障碍物，以及房门关闭与否，都会严重影响移动机器人的工作，造成导航技术无法达到预期的效果[9]。对此，将慎思式行为与反应式行为相结合，把全局路径规划放到慎思层中，把局部路径规划和执行放到反应层中，可以有效地解决这个问题。

慎思层路径规划利用已知的全局静态环境地图信息，为移动机器人的路径规划提供较优序列。但其规划时间较长，对实时信息的反应速度较慢。反应层路径规划能对环境中的突发情况作出快速反应，但缺乏智能性，因此需要与慎思层规划方法结合使用。

1.1 慎思层路径规划

慎思层具有执行规划与高级决策等功能，需要高级的信息处理方式。慎思层的主要作用是负责全局路径规划。全局路径规划主要包括两个方面：环境地图的构建和路径搜索策略。

1.1.1 环境地图的构建

假设移动机器人的工作环境为普通的室内环境，且已知整体的环境信息，采用传统的栅格法进行地图构建。这种方法将移动机器人的工作环境按照固定栅格的大小进行划分，采用八邻域模型的运动方式。栅格划分的数学模型如式(1)所示。

G(i,j)={(xG,yG)|xG≥(i-1)×l,xG

(1)

式中：G(i,j)为直角坐标系法表示的栅格单元，i为栅格地图中的第i行，j为栅格地图中的第j列；(xG,yG)为全局环境坐标系下的坐标；l为栅格的长度。

模型建立后，需要对其进行状态信息编码。每个栅格的状态信息码如式(2)所示。

(2)

式中：0表示该栅格没有障碍物，为自由区域；1表示该栅格中存在障碍物，为障碍物区域；x表示该栅格为连接两个相邻子工作区域的关键区域，为动态区域，具有不确定性。

首先，将环境信息进行栅格化处理，确定哪些栅格状态信息码为0或x；然后，将状态信息码为0或x的相邻区域连接起来，构成一个“连接图”；最后，找出初始点与目标点所在的单元栅格，并在连接图中搜索连接初始点和目标点单元栅格的路径。采用合适的路径搜索策略，能够找到最优的路径。

1.1.2 路径搜索策略

在基于栅格法的路径规划算法中，所用到的搜索算法为广度优先搜索(breadth first search,BFS)。该搜索方法从起点到终点寻找到的路径由两两相邻的、不重复的栅格组成。建立一个路径链表P，将目标栅格添加到P中。以P链表中的当前栅格为中心，从8个方向上搜索相邻栅格中状态信息码为0或x的栅格，开通数条路径链表(如P1、P2，...，Pn),标记状态信息码为x的单元栅格为动态栅格，并进行搜索[10]。判断是否将起点栅格添加到P中，并选出P0～Pn中的最小值。该值即较短路径Pbest。

1.2 反应层路径规划

反应层负责对慎思层规划的路径进行局部路径规划，细化整个全局路径，弥补全局路径规划需要掌握全部障碍物信息和不可预见事件的缺点。因此，在反应层中用到人工势场法或行为分解法。

1.2.1 人工势场法

子目标点或目标点对移动机器人产生的作用力就像磁铁一样，吸引着移动机器人，可把它想象为引力。而障碍物与移动机器人的作用如同磁铁同极一样，将其视为斥力。移动机器人在引力与斥力的合力驱动下运动，由子目标点或目标点的引力场和障碍物的斥力场共同合成的总势场决定移动机器人的运动方向[11]。人工势场法流程如图1所示。

图1 人工势场法流程图

人工势场法极易出现目标不可达的情况，具有不稳定性。

1.2.2 行为分解法

为了解决移动机器人易陷入局部死区陷阱问题，采用行为分解法。基于行为分解法的局部路径规划实时感知环境信息，更易处理一些非结构化的环境。行为分解法将整个局部路径规划分为奔向目标行为、避障行为和搜索行为等[7]。

①奔向目标行为。

奔向目标行为是指在当前移动机器人发现目标点或者子目标点之间的连线上，不存在会与障碍物发生碰撞的情况时，移动机器人的行为。

当xt≠xr时：

(3)

当xt=xr时：

(4)

则奔向目标时机器人的转向角αt为：

(5)

式中：(xr,yr)为移动机器人在全局环境坐标系下的位置;θr为移动机器人的运动方向与横坐标的夹角;(xt,yt)为目标点在全局环境坐标系下的位置;θt为目标点与横坐标的夹角。

奔向目标行为结束条件：在奔向目标的过程中，当满足其他行为激活条件时，移动机器人切换为其他行为条件；当满足其他行为的结束条件时，重新切换为奔向目标行为。

②避障行为。

通过超声波传感器检测移动机器人周围的障碍物信息。如果与障碍物的距离小于最近的距离dmin=0.1 m，调用避障行为函数，使移动机器人沿着障碍物边缘运行，实行避障行为。当移动机器人环境满足下述情况1或情况2时，移动机器人需切换到避障行为。

移动机器人车身前面有9个超声波传感器，分别为S1、S2、…、S9。S5处于移动机器人的正前方，超声波传感器的检测范围为5 cm～5 m。

情况1：障碍物在移动机器人前进方向的右侧。

条件1：S6∨S7∨S8∨S9≤dmax。

条件2：min(S5,S6,S7,S8,S9)≥dmin。

条件3：(S1=∞)∧(S2=∞)∧(S3=∞)∧(S4=∞)。

条件1～条件3中：“∧表示“与”；∨ 表示“或”；Si表示第i个超声波检测到的距离值，i=1，2，…，9。条件1成立说明移动机器人前进方向的右侧出现障碍物且距离障碍物较近。条件2成立说明移动机器人还没有碰到障碍物。条件3成立说明移动机器人的左侧没有障碍物[12]。

情况2：障碍物在移动机器人的左侧或正前方。

条件1：S1∨S2∨S3∨S4≤dmax。

条件2：min(S1,S2,S3,S4,S5)≥dmin。

条件3：(S6=∞)∧(S7=∞)∧(S8=∞)∧(S9=∞)。

当情况2满足条件1～条件3时，说明移动机器人左侧存在障碍物，应向右旋转以避免碰撞。

避障行为结束条件：条件1或条件2被满足。其中：条件1为Si=∞，i=1，2，…，9；条件2为子目标。目标点或障碍物位于移动机器人的两侧。

当障碍物在移动机器人的右侧，目标点位于前进方向的左侧时，由于移动机器人左侧没有障碍物，移动机器人放弃沿障碍物行走的行为，向左旋转并切换到奔向目标行为。

③搜索行为。

行为分解法流程如图2所示。

图2 行为分解法流程图

当动态栅格区域中存在障碍物时，需要判断是否存在可行的区域。如果不存在可行的区域，那么表示两个相邻的子工作区域是死区，需上传报警信息，移动机器人停止运动。当动态栅格区域存在障碍物且存在可运行的区域时，移动机器人沿着障碍物一侧边缘运行。移动机器人驶离动态栅格区域，由搜索行为切换为奔向目标行为[13]。

反应层接收到子目标点的位置信息，进行局部路径规划，初始状态为奔向目标行为。检测到障碍物并小于设定的最小距离时调用避障行为，到达分段点由序列发生器提供下一子目标的位置信息，在动态栅格区域采用搜索行为。循环往复，直到到达目标点。当不同的行为处理不同的事物时，多个行为之间往往为了争夺控制器而发生冲突。行为分解法中采用基于行为优先级的仲裁方法来处理不同行为之间的优先级问题[14]。

2 算法设计

针对两个相邻子工作区域易陷入死区陷阱的问题，使用慎思层与反应层相结合的混合式规划方法，把基于栅格法的规划应用于慎思层中，把人工势场法或行为分解法放到反应层中。移动机器人路径规划总流程如图3所示。

图3 移动机器人路径规划总流程图

移动机器人路径规划步骤如下。

①构建环境地图，将移动机器人的工作环境进行栅格化处理。

②对栅格信息进行BFS，寻找较优路径，并将标记状态信息码为x的动态栅格作为子目标点。

③如果全局路径规划中不含有动态栅格，则直接进行单一的局部路径规划。否则，以动态栅格作为分割点，将较优路径分割成几个路径，每段路径的结尾为一个子目标点，每个子目标点都可以作为一个要达到的目标，然后通过排序器下传到反应层。

④当检测到动态区域存在障碍物时，说明两个相邻的子工作区域可能是封闭的状态，或者半封闭的状态。若动态区域障碍物之间的最大距离大于移动机器人的宽度，则证明存在可行区域，处于半封闭状态。若存在可行区域，移动机器人要搜索可行区域。如果处于完全封闭的状态，则移动机器人上传报警信息，停止路径规划。

⑤反应层采用人工势场法或行为分解法进行局部路径规划，到达子目标点，给出下一子目标点。返回步骤④，循环直到到达目标点。

3 试验分析

对基于栅格法与人工势场法和基于栅格法与行为分解法进行验证。在Vrep平台中建立了室内移动机器人导航模型，仿真环境为30×30区域。图4所示为移动机器人部分三维环境模型。由图4可知，移动机器人在有限的区域中运动。其中：Pioneer3代表移动机器人；Bill代表目标点；Plant代表静态障碍物；Cupboard代表墙壁。上、下两个Cupboard之间的区域为动态栅格区域，假设为两个相邻房间的房门区域。

图4 移动机器人部分三维环境模型

移动机器人从起点Pioneer3(1.805 5,2.800 0)出发。慎思层利用栅格法进行栅格化之后，对运行环境信息进行全局路径规划，为反应层提供子目标点。反应层利用局部路径规划方法执行慎思层规划的路径，快速响应移动机器人工作环境中碰到的各种障碍物，例如Plant与Cupboard，到达目标点Bill(7.150 0,5.005 0)。

表1所示为移动机器人的环境信息数据。

表1 环境信息数据

3.1 封闭的区域环境

假设动态栅格区域全被Plant占领，则认为两个相邻的子工作区域处于封闭的状态，无法连通。当移动机器人到达分段的动态栅格区域时，检测动态栅格里的障碍物信息。如果移动机器人没有检测到障碍物或者存在可运行的区域，继续规划下一段局部路径。如果移动机器人没有检测到可行的区域，即动态栅格区域被障碍物Plant占领，则认为处于全封闭状态。方法1与方法2在封闭的区域环境下的运行轨迹如图5所示。如未检测到可行区域，则上传报警信息，停止路径规划。

图5 在封闭的区域环境下的运行轨迹

3.2 半封闭的区域环境

当动态栅格区域未全被障碍物Plant占领，认为两个相邻的子工作区域处于半封闭的状态，可以连通。

3.2.1 不可达情况

方法1与方法2在目标点被障碍物包围时的运行轨迹如图6所示。移动机器人在动态栅格区域检测并运行到可行进路线，但检测到目标点Bill被障碍物包围，无法到达目标点。此时，上传报警信息，停止路径规划。

图6 在目标点被障碍物包围时的运行轨迹

3.2.2 可达情况

混合式路径规划算法的移动机器人运行轨迹如图7所示。

图7 混合式路径规划算法的移动机器人运行轨迹

由图7(a)可知，方法1的运动距离为7.500 m，运动所花时间60.100 s。依靠单一传感器的效果不稳定。为更好地达到避障效果，在移动机器人车身前面放置视觉传感器。视觉传感器观测界面如图8所示。分别为在轨迹点a1、a2、a3、a4处所观察到的环境信息。

图8 视觉传感器观测界面

由图7(b)可知，方法2的运行长度为7.900 m，移动机器人在运行轨迹b1点处驶出了动态栅格区域，在原地旋转了一定角度搜寻目标点，所花时间为70.040 s。

为验证算法的有效性，每组试验重复20次。表2所示为两种算法的仿真结果。由表2可知，本文提出的混合式路径规划算法能够取得较好的效果，移动机器人能够规划出一条较优路径，且路径比较短。移动机器人并不会在起始点所在的子工作区域内徘徊，而是直接朝向动态栅格所在的位置移动，规划出的路径符合人类的行走习惯。

表2 两种算法的仿真结果

4 结论

为了研究移动机器人在非结构环境下的路径优化问题，在Vrep平台建立了移动机器人导航模型，提出慎思层与反应层相结合的混合式路径规划算法。在栅格法中对栅格状态标记作出了改进，在基于栅格法与行为分解法的混合式路径规划算法中根据模型特点构造避障行为与搜索行为[15]，并对两种算法进行验证。仿真试验结果表明，混合式路径规划算法能很好地指挥移动机器人到达目标点。在设计的混合式路径规划算法中，移动机器人反应层采用行为分解法进行局部路径规划时，如果某些控制器不具有科学性，就会影响移动机器人的控制判断。在两种算法的验证中，设计的障碍物都是静止的状态，未考虑动态障碍物。这两个问题都是现在研究的热点领域，后续研究将继续改进移动机器人的路径规划算法，进一步提高算法的实时性与鲁棒性。