一种基于有限视场的移动机器人避障路径规划算法

2008-12-19陈建新

空间控制技术与应用 2008年4期

关键词：视场移动机器人障碍物

刘祥，陈建新

（1.北京控制工程研究所，北京 100190；2.空间智能控制技术国家级重点实验室，北京 100190）

一种基于有限视场的移动机器人避障路径规划算法

刘祥1，2，陈建新1，2

（1.北京控制工程研究所，北京 100190；2.空间智能控制技术国家级重点实验室，北京 100190）

提出一种基于传感器的移动机器人避障路径规划算法。考虑到传感器存在视场范围限制的问题，算法仅利用当前单一视场内的有限环境信息，采用两种搜索模式，以机器人当前的运动方向、障碍物边界端点数据及目标点所在方向为依据，在当前视场中搜索合适的路径。这两种搜索模式保证了路径最终收敛到目标点。最后，通过仿真实例验证了算法的有效性。

移动机器人；有限视场；避障；路径规划

1 引言

移动机器人的路径规划是指在具有障碍物的环境中，为移动机器人寻求一条从给定起始点到目标点的安全路径。根据对环境信息的了解，路径规划理论主要分成两大类：全局规划和局部规划。

全局规划需要先验的环境信息，在一定的评价标准下能够求解出最优路径。但算法在全局环境模型的构建和维护方面具有较大的计算负担，且复杂性较高，适合离线规划。常见的全局规划算法有基于栅格图的 A*算法［1］和 D*算法［2］等。

局部规划需要利用安装在移动机器人上的传感器（如激光测距仪、红外传感器和立体视觉系统等）获得局部的环境信息，按照一定的策略寻找合适的路径。相比于全局规划，局部规划能够在环境完全未知的情况下进行规划，实时性较高，但往往得到的路径会稍长一些，适合在线规划。

现有的局部规划算法中较常见的是Bug类算法。基于不同的传感器发展出了多种算法，主要有Bug1和 Bug2算法［3］，以及在此基础上衍生出的VisBug［4］、DisBug［5］、TangentBug［6］和 WedgeBug［7］等算法。Bug类算法有着共同的规划思想，就是将移动机器人的运动分为两种模式：当没有障碍物阻挡时直接朝目标前进；当传感器检测到障碍物时，则沿着障碍物的边缘行走，直到绕开障碍物，然后继续朝目标前进。Bug类算法的规划原理简单，对于路径规划中较难处理的局部极小值问题也能够容易地解决。

大多数Bug算法假设机器人的传感器能够获得全向的环境信息，这就需要机器人携带较多的传感器，在工程应用上不易实现。本文主要研究基于立体视觉的避障路径规划问题，针对传感器存在视场范围限制的问题，基于单一视场范围内的环境信息，设计一种移动机器人的局部避障路径规划算法，并通过仿真实例验证此算法的有效性。

2 算法描述

2.1 相关假设及符号定义

由于本文主要进行算法的理论性研究，暂不考虑环境建模的问题，这里假设机器人所处的环境为二值平面地图（即环境中的每个点或者包含于障碍物，或者处于自由空间），视机器人为一个质点。

为了方便描述，现将本文常用到的相关符号定义介绍如下：w为规划所得到的第 k个路径点为机器人在路径点wk处的行驶方向；d（a，b）为点 a到点b的欧式距离；为对应于和的视场，即当前规划时的视场区域，见图1。

图1 示意图

若从wk到目标点T的连线与的圆弧部分相交，记该交点为Tc。

定义目标点到达标志位T-reach，并将其初始化为False，当目标点可到达时置为True。

2.2 环境感知模块

为了能够采用合适的策略进行路径选择，需要从环境模型中提取有效的环境信息，将实现该部分功能的模块称为环境感知模块。

首先寻找出各个障碍物Oi的边界端点en（n=1，2，…），存储各边界端点 en坐标（xn，yn）、en相对于 wk的极角 ρn以及 en到 wk的距离 d（wk，en）。

表1 标志位置位原则

2.3 路径搜索模块

与其他Bug类算法类似，为保证规划路径能最终收敛到目标点，这里仍然采用两种搜索模式，分别记为趋向目标模式（M tT，motion-to-target）和障碍物边界跟随模式（BF，boundary following）。

在本算法中，两种搜索模式的选择由环境感知模块返回的标志位obst-block的取值来决定：

1）若 obst-block=T rue，则选择 BF模型；

2）若 obst-block=False，则选择 MtT模型。

2.3.1 M tT模式

由表1所示的标志位置位原则可知，在该模式中，obst-block=False，但reach的取值并不确定，下面分两种情况进行讨论：

2）否则，令机器人走到Tc位置处，即wk+1=Tc，然后，在w处进行下一步规划。k+1

图2 M tT模式示意图（reach=True）

图3 M tT模式示意图（Tc-reach=False）

2.3.2 BF模式

在BF模式中暂不考虑T的位置和方向，而是沿着障碍物的边界行走，直到绕开障碍物，再次寻找到能够直接朝目标前进的路线，然后转入 M tT模式。

为了避免机器人太靠近障碍物，在该模式中令机器人朝最佳端点仅行进1/3的距离，即在线段上选择下一个路径点 wk+1，使得 d（wk，wk+1）=，同时得到第 k+1个行驶方向，即然后，重新感知视场中的环境，进行下一步规划。

机器人在跟随障碍物边界时，由于视场范围有限，故可能会出现如图5所示的视场被某个障碍物完全阻挡的情况。

图4 BF模式（视场没被完全阻挡的一般情况）

图5 BF模式（视场被完全阻挡情况）

可见，一旦确定了跟随边界的转向方向，机器人会一直按照该方向沿障碍物行进，这样即使遇到了凹形障碍物并走进了其局部极小值点处，机器人仍然能最终脱离障碍物并继续朝目标前进。

2.4 算法流程

每步规划开始时，首先感知视场F（wk，v→k）中的环境，提取出有效的环境信息，然后根据标志位obst-block的取值选择MtT模式或 BF模式进行路径搜索。

算法大致的规划流程如下：

（1）初始化参数

1）令第一个路径点为w1=S，运动方向设定为

（2）判断 T-reach是否为 Ture

1）若是，则令 k=k+1，wk=T，算法结束；

2）若否，则转入（3）。

（4）判断 obst-block是否为 True

图6所示为算法进行规划时的大致流程图。

图6 算法流程图

2.5 算法特点

在Bug类算法中，趋向目标运动模式下机器人不仅直接朝目标前进，有时遇到障碍物后也沿着该障碍物的边界行走。由于大多数Bug算法以各障碍物边界端点到目标点的距离为依据来寻找合适的路径，而当机器人陷入了凹形障碍物的局部极小值点处，算法在障碍物边界上找不到比机器人当前位置距离目标点更近的点，只有这时才会调用障碍物边界跟随模式，指导机器人沿着障碍物边界行走并逐渐脱离局部极值点。

本文提出的算法虽然也将机器人的运动分为两种模式，但只利用当前视场范围内的环境信息进行规划（并不像WedgeBug算法那样频繁地要求摆动传感器以获得更多的信息），本文的算法与其他Bug算法相比，对两种模式的划分有所不同：当发现直接通向目标点的路线被阻挡时，就使机器人从趋向目标运动模式转入边界跟随运动模式，而且在边界跟随模式中并没有特别考虑局部极小值点情况，而是让机器人按照固定的方向沿着障碍物边界行走。这样，即使陷入某个局部极值点，也能指导机器人逐渐脱离障碍物。虽然由于环境信息的局限性使最终规划出的路径长度可能相对较长，但算法原理简单，结构清晰，占用系统资源少，具有较高的规划效率。

另外，不同于其他Bug算法以距离信息作为主要规划依据，本算法在搜索路径时主要考虑机器人当前的运动方向、目标点的方位以及视场中障碍物边界端点的方位等3方面因素，若目标点的方位处于当前视场，就直接沿该方向前进一个移动步长，否则就参照当前的运动方向及障碍物边界端点所在方向，选择最合适的跟随方向和移动距离。这样处理在保证规划路径收敛性的同时，也使规划出的路径比较平滑，易于路径执行。

3 仿真实例

利用MATLAB工具对上述算法进行仿真。仿真时，选取一张尺寸为15 m×15 m的地图，考虑到目前研制较成功的行星探测车所采用的导航传感器的视场角一般为40°～50°，故这里选取传感器的视场角为 θh=45°。

图7所示为R取1.5 m和2.5 m时的仿真结果，图中一系列的扇形虚线表示与路径上各个路径点相对应的视场区域，曲线为算法规划路径。可以看出，机器人虽然走进了凹形障碍物的局部极值点处，但并没有受其“吸引”，而是按照某个固定的方向（向左）沿着障碍物的边界行走，逐渐脱离该障碍物，并最终到达目标点。在图7（a）中，R较小，所以规划出的路径比较靠近障碍物；随着R的增大，由于“看”得较远，故路径会与障碍物保持一定的距离，如图7（b）所示。

图7 算法的规划结果

针对相同的情况，采用 TangentBug算法进行仿真规划，得出图8所示的规划结果。

TangentBug算法基于全向的环境信息进行避障规划，每步规划都是从一个圆形的视场中搜索路径，如图8中的圆形虚线就是与路径上各个路径点相对应的视场区域。

对R取不同值的情况进行仿真，并对比本文提出的算法和TangentBug算法规划的路径长度，结果如表2所示。

图8 采用TangentBug算法的规划结果

表2 路径长度比较

比较图7和图 8可知，当 R较小时，两种算法的规划结果基本一致；当R较大时，由于TangentBug算法能够获得360°的环境信息，故得到的规划结果较好。另外，由表 2可以看出，本文提出的算法得到的路径稍长一些。但本算法是基于有限视场进行的避障规划，利用的环境信息相对较少，不仅可以得到满足要求的路径，而且计算量小、规划效率高，因而更具实际意义。

4 结束语

本文考虑了移动机器人的传感器存在视场范围限制问题，基于Bug类避障规划算法，提出一种未知环境下利用有限视场内的环境信息进行避障的路径规划算法。算法主要包括两个模块：环境感知模块和路径搜索模块。其中，环境感知模块主要是分析视场内的环境，提取有效信息；路径搜索模块是基于获得的环境信息采用两种模式搜索安全路径，并保证规划出的路径能够最终收敛到目标点。

另外，本文主要从理论上研究了基于有限视场的避障路径规划问题，并没有考虑算法所需环境模型的构建问题，下一步计划结合具体的环境（如月球或火星表面环境），从三维重构、障碍物识别等方面进行环境建模的研究，进一步完善算法，使算法更贴近工程实际。

［1］ Nilsson N J.Pricinples of artificial intelligence［M］.Palo Alto，CA：Tioga Press，1980

［2］ Stentz A.Optimal and efficient path planning for partially-known environments［C］.IEEE International Conference on Robotics and Automation，San Diego，California，1994

［3］ Lumelsky V J，Stepanov A.Path-planning strategies for a point mobile automation moving amongst unknown obstacles of arbitrary shape［J］.Algorithmica，1987，3（4）：403-430

［4］ Lumelsky V J，Skewis T.Incorporating range sensing in the robot navigation function［J］.IEEE Trans on Systems，Man，and Cybernetics，1990，20（5）：1058-1068

［5］ Kamon I，Rivlin E.Sensory-based motion planning with global proofs［J］.IEEE Trans on Robotics and Automation，1997，13（6）：814-822

［6］ Kamon I，Rivlin E，Rimon E.A new range-sensor based globally convergent navigation algorithm for mobile robots［C］.IEEE International Conference on Robotics and Automation，Minnespolis，Minnesota，1996

［7］ Laubach S，Burdick J.An autonomous sensor-based path-planner for planetary microrover［C］.IEEE Conference on Robotics and Automation， Detroit，Michigan，1999

A Limited Field-of-View Based Obstacle Avoidance and Path Planning Algorithm for Mobile Robots

LIU Xiang，CHEN Jianxin
（1.Beijing Institute of Control Engineering，Beijing 100190，China；2.National Laboratory of Space Intelligent Control，Beijing 100190，China）

A new sensor-based obstacle avoidance and path planning algorithm for mobile robots is proposed.The field-of-view（FOV）constraint of sensors is considered，and only the local information of the environment in a single FOV is used.Two searching modes are employed to find a safe path in the current FOV，given the current moving direction，data of obstacle boundary endpoints and the orientation of the target.The two modes ensure the convergence to the target of the path.Simulations results demonstrate the effectiveness of the algorithm proposed.

mobile robots；limited field-of-view；obstacle avoidance；path planning

2008-02-18

刘祥（1984-），男，山东人，硕士，研究方向为空间机器人控制（e-mail：visualcity@163.com）。