1.   引言

随着移动机器人的发展，移动机器人的导航算法成为热点问题，导航算法帮助移动机器人在有障碍物的环境中避障且朝向目标自主移动。目前常见导航算法有：遗传算法^[1]，通过模拟达尔文生物进化论的遗传学机理和生物进化过程而不断寻求最优解的一种导航算法；蚁狮算法^[2]，一种仿生优化算法，该算法通过模拟捕食蚂蚁的蚁狮来寻求比较精确的全局最优解；以及人工势场法^[3] (Artifical Potential Field Method, APFM)。

人工势场法通过建立势能函数进行导航，因此人工势场法运算简便、快捷，能够得到最优路径且路径平滑。但移动机器人会不慎进入凹形障碍物内部产生局部最优点，难以自行走出。针对人工势场法易陷入局部最优点的问题，Park等人^[4]和况菲等人^[5]将人工势场法和其他算法相结合；Lee等人^[6]提出NP-APF(New Point-Artificial Potential Field)算法，通过创造子引力点，提高人工势场法性能。Rostami等人^[7]通过改变引力斥力函数，解决机器人局部最优点问题。但上述算法均存在移动机器人行走路径过长的缺点，不具备实际应用的前景。

相较于人工势场法，A-Star(A*)^[8,9]算法不存在局部震荡问题，该算法运用灵活，适用于多种场景，且可求解最短路径，现被广泛应用于静态路网导航，但其相对于APFM计算速度慢，且得到路径并非最优路径。在A*算法的改进方案中，田景文等人^[10]将遗传算法与BP神经网络算法相结合，胡中华等人^[11]用A*算法进行路径规划获得拐点，再利用人工势场法将各个拐点作为子目标点进行路径规划，这些改进的A*算法均降低了A*算法复杂度，但是无法实现大型凹型障碍物的有效避障。

本文针对大型凹形障碍物避障导航研究中存在的问题，基于人工势场法和A*算法，提出了一种组合导航算法。本文算法定义了多个运行状态，在无障碍物环境中算法采用人工势场法进行路径导航，确保移动机器人获取最优路径。在感知到机器人陷入局部震荡区后，依据切换条件，移动机器人的路径规划算法切换为A*算法，跳出局部震荡区，驶离障碍物内部。当移动机器人离开大型凹形障碍内部后，移动机器人便将导航算法转换为人工势场法，以此来保证路径最优且平滑。算法的主要贡献包括：

(1) 通过定义多运行状态，在避障时依据状态切换条件进行状态切换，解决大型凹形障碍物避障算法中存在的局部震荡问题。

(2) 以速度和运行时间为切换条件，缩减导航时间。

章节安排如下：第2节对本文所采用符号的说明，并简要介绍人工势场法和A*算法的基本原理；第3节介绍本文算法的障碍物模型，对本文所提组合导航算法进行了详细描述；第4节对组合导航算法进行正确性分析和复杂度分析；第5节对组合导航算法的仿真结果进行分析，第6节总结了本文所做的工作。

2.   基础知识

2.1   符号说明

本文的数学符号采用了通常的表示方法，表1、表2和表3给出了特殊符号的定义。

表 1  人工势场法符号含义

符号	符号含义	符号	符号含义
${\rm{obs}}$	障碍物	${\bf{X}}{\rm{d}}$	目标位置
${U_{{\rm{Xd}}}}(x)$	引力势能	${U_{{\rm{obs}}}}(x)$	斥力势能
${U_{{\rm{art}}}}(x)$	总势能	${{F}}$	合力
${{{F}}_{{\rm{Xd}}}}$	吸引力	${{F}}_{\rm{obs}}$	排斥力
$j$	移动机器人感知到的 周边障碍物的个数

下载: 导出CSV 

| 显示表格

表 2  A*算法符号含义

符号	符号含义	符号	符号含义
$g(\cdot )$	从初始节点到当前移动机器人 所在节点node的启发式评估代价	$h(\cdot )$	从当前移动机器人所在节点node到 目标节点的启发式评估代价
$(x_{\rm{start}},y_{\rm{start}})$	初始节点坐标	$(x_{\rm{goal}},y_{\rm{goal}})$	目标节点坐标
$(x,y)$	移动机器人实时位置坐标

下载: 导出CSV 

| 显示表格

表 3  模型描述符号含义

符号	符号含义	符号	符号含义
$O_1$	障碍物的左端点	$O_2$	障碍物的右端点
$2\alpha$	障碍物的长	$\beta$	障碍物的宽
$v_t$	移动机器人的实时线速度	$a$	移动机器人在运行态时的最大速度
$\Delta d$	移动机器人在某段时间内的移动距离	$S_{\rm{obs}}$	所有障碍物总面积
$S_{\rm{map}}$	地图面积	$\rho$	障碍物密度

下载: 导出CSV 

| 显示表格

2.2   人工势场法和A*算法

人工势场法将移动机器人的工作环境看作2维势能场^[12]，机器人在势能场中运动，目标点提供引力，引导机器人运行至目标点，工作环境内的障碍物提供斥力，引导移动机器人远离障碍物。

移动机器人的控制可以通过人工势能场来实现，总势能公式为

对于人工势能场来说移动机器人受到的合力${{F}}$为

其中，${{F}}_{\rm{Xd}}$为吸引力，由$U_{\rm{Xd}}(x)$产生，吸引移动机器人到达目标点${\rm{X}}{\rm{d}}$。${{F}}_{\rm{obs}}$为排斥力，由$U_{\rm{obs}}(x)$产生，使机器人远离障碍物。$U_{\rm{obs}}(x)$是非负连续的可微函数，当移动机器人接近障碍物表面时，其值趋近于无穷大。为避免机器人不在障碍物附近却仍被影响的情况，该势场的影响范围仅限于围绕障碍物的给定区域。若移动机器人周边的障碍物不止1个，则移动机器人在人工势能场的势能为多个障碍物的合势能

相应地，移动机器人受到的合力为

力${{F}}_{\rm{Xd}}$与力${{F}}_{\rm{obs}}$分别为沿着引力势能与斥力势能下降最快的方向，因此该算法保证机器人所行走路径平滑。

A*算法^[13]是启发式算法的一种，最初来源于迪杰斯特拉算法^[14]，同时A*算法借鉴了最佳优先搜索算法的某些思想，该算法不能保证找到一条最短路径，但该算法运用启发式函数可快速地导向目标节点。

在A*算法中首先建立两个列表，分别为open list和close list。其中close list用来存储移动机器人已走过的节点，而open list存储移动机器人下一步可行走的节点，A*算法选取子节点中$f(\cdot )$最小的节点，其中

有关于$g(\cdot )$与$h(\cdot )$则用机器人与起始点和机器人与目标点之间的欧几里得距离来计算

3.   针对大型凹形障碍物的组合算法描述

3.1   障碍物模型

本文中地图和移动机器人都为2维正方形，单体大型凹形障碍物的长不可超过地图边长的$1/3$，同时移动机器人的边长不超过单体大型凹形障碍物的长的$1/3$，所有障碍物在地图上服从均匀分布。

典型大型凹形障碍物建模图如图1所示，图1中起点为机器人的起始点，终点为目标点，$O_1$和$O_2$分别为障碍物左右端点，凸起方向朝向目标点。障碍物模型主要以椭圆形的上半部为主。依据椭圆公式，障碍物的方程有

图 1  障碍物建模图

下载: 全尺寸图片 幻灯片

式中，$(x_{\rm{cen}},y_{\rm{cen}})$表示椭圆障碍物圆心在地图上的$X$,$Y$轴坐标，$2\alpha$为障碍物的长，$\beta$为障碍物的宽。

3.2   组合算法描述

针对两种算法的优缺点，本文的组合算法对它们二者进行了综合，将机器人的运行过程分为运行态、切换态和避障态3种状态。机器人在运行态下使用人工势场法导航，当机器人感受到自身在某一位置停留或震荡，则进入切换态，机器人感知此处并非目标点时将转至避障态，导航算法转换为A*算法，利用A*算法使移动机器人离开大型凹型障碍物内部后(激光雷达检测前方无障碍物)将移动机器人转至运行态，以此来保证机器人行走的路径为最优路径节省计算时间。组合算法流程图如图2所示。

图 2  组合算法流程图

下载: 全尺寸图片 幻灯片

4.   算法分析

4.1   正确性分析

运行态：在人工势场法合力场中，移动机器人按梯度下降最快的方向运行，以此保证路径最优。

避障态：A*算法不断搜索周围栅格，寻找未被障碍物侵占的栅格，因此只要起始点与终点间有可行路径，则该算法一定能够导航成功。

切换态：当移动机器人满足下面其中一条件时，便从运行态切换至避障态。以下两条件共同保证移动机器人陷入局部最优点后算法可做出及时调整。

切换态条件1：速度条件$v_{\text{实时}} \le a/4$，即移动机器人的速度小于运行态最大速度的$1/4$；

切换态条件2：假设在时刻$t$时，经过时间$\Delta t$后，移动机器人的位置变化为$\Delta d$。若$\Delta d \le v_t\Delta t$，移动机器人在某时间段内的位置移动小于实时速度与时间之积，判定移动机器人此时处于切换态。

4.2   复杂度分析

若地图表示为$n \times n$矩阵，运行态需计算每个矩阵元素的斥力与引力之和，则运行态复杂度为$O({n^2})$。避障态分为内循环与外循环，外循环每次从open list中取出点，复杂度为$O(n)$。内循环将它的邻接点放入open list中并排序，复杂度为$O(n\lg n)$，则避障态的复杂度为$O({n^2}\lg n)$，切换态的判定复杂度为$O(1)$。则算法的整体复杂度为$O({n^2}\lg n)$，胡中华等人^[11]所提出的组合算法，算法复杂度为$O({n^2}\lg n){\rm{ + }}O({n^2})$，且该算法无法在具有大型凹型障碍物环境下完成导航规划。

5.   仿真分析

5.1   组合算法与人工势场法比较

本节对提出的针对大型凹形障碍物的组合算法的有效性进行仿真验证。仿真中采用前文所描述模型。在仿真过程中，将移动机器人看作一个小正方形，在人工势场法中，引力系数与斥力系数为$1:1$。在A*算法中：$f(\cdot ) = g(\cdot ) + h(\cdot )$, $g(\cdot )$与$h(\cdot )$比例为$1:1$。

将地图设置为正方形，地图中均已标明起始点与目标点，各图中黑色为障碍物，蓝色为移动机器人的路径。由图3(a)、图3(b)可见，人工势场法不能使移动机器人到达目标点，本文提出的针对大型凹形障碍物的组合算法可有效避开障碍物到达目标点。图3(c)为算法采用差速驱动的AGV车辆作为模拟对象在v-rep中的仿真，由各个长方体模拟构建障碍物，紫色为移动机器人路径。通过对虚拟仿真结果的分析，在拥有大型凹型障碍物的环境中，本文所提出的算法可有效的实现无碰撞导航规划。

图 3  针对大型凹形障碍物仿真结果

下载: 全尺寸图片 幻灯片

5.2   组合算法与A*算法比较

组合算法与传统A*算法相比更加简便，运用传统A*算法的导航路线如图4, A*算法导航所得到的路径中有大量转折点，且路径较长，可见，组合算法无论在路径的平滑度方面与机器人行走距离上都更优。

图 4  针对大型凹形障碍物的A*算法的仿真结果

下载: 全尺寸图片 幻灯片

5.3   组合算法与其他改进算法的比较

图5为沈文君的改进人工势场法^[15]，本文将该算法放入类似的地图中模拟，其中红色线条为导航产生的路径，彩色虚线为各个障碍物位置，黑色虚线为障碍物影响范围，图5中目标点与起始点均已标注，可见，该算法并不能完成本次导航，本文算法更具有优越性。

图 5  针对大型凹形障碍物的改进人工势场法算法的仿真结果

下载: 全尺寸图片 幻灯片

5.4   组合算法在其他场景下的避障

组合算法不仅可以针对大型凹形障碍物进行避障，还可以在其他场景下进行避障如图6。人工势场法无法完成该类型的导航任务。各图中黑色为障碍物，蓝色为移动机器人的路径。

图 6  组合算法在其他场景下的运行结果

下载: 全尺寸图片 幻灯片

人工势场法不能完成导航，在此不做数据比较，本文所提算法与A*算法、改进的人工势场法^[15]比较数据如表4，数据说明了在图3所示环境中组合算法比A*算法时间节省52.57%，路程缩短32.05%，且改进人工势场法无法完成导航。

表 4  算法性能比较

算法	时间(s)	路径长度(m)
A*算法	22.40	1040.69
改进人工势场法[15]	无穷大	无穷大
本文组合算法	10.62	707.09

下载: 导出CSV 

| 显示表格

6.   结束语

本文针对大型凹型障碍物的避障提出了一种组合算法，在尽可能地保证移动机器人行走的路径为最优路径的前提下，通过转变算法让移动机器人离开局部最优点，且运行路径更短更接近最优路径，弥补了人工势场法不完备的缺陷，且组合算法比A*算法在时间上平均快63.69%，路径上平均短52.04%。但此种算法也有局限性，它仅能处理障碍物密度$\rho < 37\% (\rho = {S_{{\rm{obs}}}}/{S_{{\rm{map}}}})$的地图且仅针对长宽比在1.40～2.85内的障碍物，对于长宽比超过此范围的障碍物，后续将研究填补凹形障碍物并将其视为凸型的方法来进行移动机器人避障。