复杂动态环境下自主机器人路径规划研究*

王志中

(重庆建筑工程职业学院，重庆 400072)

0 引言

机器人路径规划是机器人能够自主完成任务的基本保证，路径规划就是机器人在已知或未知环境中找到一条最优的无碰路径[1]。相对较优的规划路径不仅可以减少机器人磨损，还可以提高工作和生产效率，具有很高的现实经济意义。

目前机器人路径规划问题，从对工作环境的掌握程度来讲，分为全局路径规划和局部路径规划，全局路径规划包括栅格法[2]、拓扑图法、可视图法[3]等，局部路径规划包括人工势场法[4]、模糊逻辑控制法[5]、智能算法[6-7]等，以上路径规划方法都能规划出一定意义下的最优路径，但是都存在使用局限性或算法缺陷，栅格法、可视图法等不适于动态环境，人工势场法存在局部极值陷阱、目标不可达等问题。对于本文研究的工厂车间环境这种特殊的环境，没有合适高效的路径规划方法。

本文路径规划背景是机器人工作在工厂车间中，在车间中物品摆放相对固定，但可能临时堆放杂物或其他物品，而且可能有工人来回走动，也就是说工厂车间环境是复杂的动态环境，针对以上分析将工厂车间障碍物分为三类：相对固定的物品作为固定静态障碍物、临时堆放的静态障碍物、可移动的动态障碍物。针对工厂车间的特殊环境，本文提出了全局路径规划和局部路径规划相混合的规划方法，从规划结果可以看出，本文提出的混合规划方法不仅能够规划出最优路径，而且能够准确避开动静态障碍物、克服了徘徊和震荡现象。

1 加权A*算法的全局路径规划

1.1 机器人简介

本文使用的机器人为北京博创兴盛科技有限公司生产的旅行者II号机器人，此机器人行走方式为轮式行走，转向通过两轮转速差实现，转速差值不同转弯半径也就不同。自身带有超声波、激光、红外等传感器，用于测距和感应人体，可以满足本文实验需求。

1.2 环境建模

对于车间的固定静态障碍物，本文使用改进A*算法的全局规划方法，首先使用栅格法对工作环境进行建模。栅格大小对路径规划性能影响较大，若栅格较小，环境分辨率就高，但是需要存储和处理的数据量急剧增加，规划速度慢；若栅格较大，抗干扰能力强、规划速度快，但是容易产生碰撞，尤其在复杂环境中。记栅格边长为l，则：

(1)

确定栅格大小后，使用栅格划分工作环境，对栅格内的障碍物进行膨化处理，即栅格内只要存在障碍物此栅格即为障碍物栅格，如图1所示。

图1 障碍物的膨化效果

栅格的表示方法有直角坐标法和序号法，两种方法可以相互转换。

1.3 A*算法分析与改进

A*算法是一种启发式搜索算法，记机器人当前栅格为n，它的评价函数f(n)包括两部分：一是起始点到当前栅格的消耗g(n)，二是从当前栅格到目标点的消耗h(n)，即：

f(n)=g(n)+h(n)

(2)

其中，h(n)在评价函数中起关键作用，它几乎包含了所有的启发信息。针对栅格环境建模方法，评价函数一般使用曼哈顿距离建立[8]。

式(2)中h(n)几乎包含所有的启发信息，若启发信息太强，虽然可以降低路径规划工作量，但是也容易陷入局部最优路径；若启发信息太弱，会导致路径搜索工作量极大。所以为了平衡工作量和陷入局部最优问题，本文提出了加权A*算法，即：

f(n)=g(n)+w×h(n)

(3)

式中，0≤w≤1为权值，w=0时启发信息为0，算法变为随机式搜索算法，w=1时加权A*算法退化为传统A*算法，因此通过合理选择权值w就可以避免陷入局部最优，同时减少搜索复杂度。

1.4 仿真验证

为了验证加权A*算法在路径规划中的性能，给定如图2a所示的工厂车间，建立的栅格模型如图2b所示，图中白色栅格为可行驶栅格，黑色栅格为障碍物栅格，S为路径起点，G为路径终点。

(a)车间示意图 (b)车间栅格模型

分别使用Dijkstra算法、A*算法、权值分别为0.3、0.7的加权A*算法进行路径规划，结果如图3所示。

(a)A*算法规划结果 (b)Dijkstra算法规划结果

(c)权值0.3规划结果 (d)权值0.7规划结果

图3不同算法的路径规划结果

经计算4种算法得到的最优路径长度相同，均为37.7。本文针对车间的复杂动态环境，提出了全局规划和局部规划结合的混合规划方法，在局部路径规划中用到了全局路径规划的拐点作为子目标点，所以在此将拐点个数作为评价规划性能的重要指标。统计各算法拐点数和规划耗时，如表1所示。

表1 各算法路径规划结果

从表中数据可以看出，4种算法的耗时都是ms级，且相差不大，所以算法耗时水平大致相同。路径拐点越多则机器人转弯负担越重、损耗越大，且拐点越多则路径越不顺畅，严重影响工作和生产效率，所以从拐点数量的角度讲，权值为0.7的加权A*算法具有最好的规划性能，本文选用w=0.7的加权A*算法与后文的局部路径规划方法进行混合规划。

2 改进人工势场的局部路径规划

对于工厂车间的临时堆放障碍物和动态障碍物，需要机器人根据自身传感器实时监测环境信息，并做出路径规划决策。局部路径规划方法很多，人工势场法原理简单、易于编程实现，所以本文使用人工势场法进行局部路径规划。

2.1 人工势场法简介

人工势场法就是将空间环境视为一个势场模型，目标点对机器人产生引力势场，障碍物对机器人产生斥力势场，机器人在两个势场的合力下向目标点运动[9-10]。

(4)

式中，η为斥力势场系数，ρ(q,qobs)为机器人当前位置与障碍物位置的距离，ρ0为障碍物的斥力作用距离。机器人所处位置的势场记为U(q)，则U(q)=Uatt(q)+Urep(q)，机器人受到的引力记为Fatt，斥力记为Frep，合力记为Fq，则：

Fq=Fatt+Frep=-▽Uatt(q)-▽Urep(q)

(5)

式中，▽Uatt(q)、▽Urep(q)分别表示势场Uatt(q)、Urep(q)的梯度。机器人就是在合力Fq的作用下向目标移动。

2.2 改进人工势场法

传统的人工势场法存在两个方面的问题：①目标在障碍物附近时，目标不可达；②存在受力平衡点时的局部极小值陷阱。

(1)目标不可达问题及解决方法。当目标点附近存在障碍物时，机器人接近目标的过程中，引力越来越小而斥力越来越大，这样就容易使机器人在目标点附近的势场极小值点停下，而无法到达目标。目标不可达时机器人、目标点、障碍物的位置关系如图4所示。

图4 目标不可达位置关系

分析引力势场函数和斥力势场函数可知，目标不可达问题主要因为机器人接近目标时，引力逐渐减小而区域稳定，但是斥力却逐渐增大成为不稳定因素，因此本文在斥力势场函数中引入机器人与目标点距离因子ρ(q,qg)，使斥力势场在目标点位置也最小，从而使机器人可以稳定在目标点位置，即改进的斥力势场函数为：

分析上式可知，改进的斥力势场函数可以保证目标点斥力场为0，而引力场也为0，这样就确保了机器人在目标点处的平衡和完全可达。

(2)局部极小值问题及解决方法。局部极小值问题就是机器人在此处受力平衡，所以机器人在极小值点停滞或徘徊，而无法朝目标点前进，典型的两种极小值情况如图5所示。

图5 局部极小值位置关系

对于局部极小值问题，本文使用增设虚拟目标的方法解决。机器人在行驶过程中，当检测到自身合理为0而又没有达到目标时，就在目标附近的合适位置增设虚拟目标，由于虚拟目标的引力使机器人摆脱局部极小值，当机器人摆脱局部极小值区域后系统自动撤销虚拟目标，机器人在实际合力作用下继续向目标点移动。

在此重点介绍虚拟目标的增设方法。首先辨别使机器人陷入局部极小值的所有障碍物，计算每个障碍物与机器人连线和水平线的夹角θi，计算目标点与机器人连线和水平线夹角θ，根据夹角大小计算机器人与目标点连线左右的障碍物数量，将虚拟目标增设在障碍物较少的一侧，从而引导机器人从环境简单区域驶向目标点。虚拟目标增设位置记为(VG_x,VG_y)，则：

(6)

式中，(xrobot,yrobot)为机器人当前位置坐标，Δθ为角度增量，且对∀θi，|Δθ|≤|θ-θi|，这样可以保证虚拟目标与实际目标距离适中，防止机器人走冤枉路。

2.3 仿真结果

前文中提到将车间障碍物分为三类：一是固定静态障碍物，二是临时堆放的障碍物，三是动态障碍物，对于局部路径规划来讲，固定障碍物和临时堆放障碍物的路径规划是一致的，因此对基于改进人工势场法的局部路径规划验证分为两种情况；一是静态障碍物情况下路径规划，二是动态障碍物情况下的路径规划。

(a)第一次规划 (b)第二次规划

分析图6可以得到三个结论：①在静态环境下，改进人工势场法能够完成起点到终点的路径规划；②两次规划的路径差别很大，因为机器人虚拟目标的增设位置不完全一致，这也符合路径规划的实时性；③从图中可以明显看到路径中存在来回震荡和徘徊的部分，这是因为传感器探测范围有限，只能根据有限的信息进行局部规划。

(2)动态障碍物情况下的路径规划。当机器人检测到环境中存在动态障碍物时，规避策略为：若机器人与动态障碍物距离大于机器人半径4倍时，则机器人正常行驶，若机器人与动态障碍物距离在机器人半径的2～4倍之间时，机器人半速前进，若机器人与动态障碍物距离小于机器人半径2倍，则机器人停止，待两者距离在机器人半径2倍以上之后再行进。图中ms1、ms2为两个动态障碍物的起点，mg1、mg2为两个动态障碍物的终点。规划结果如图7所示。

(a)机器人停止等待 (b)路径规划结果

图7a给出了机器人与动态障碍物距离过近而停止不前的情况，图7b为机器人在动态环境下最终的路径规划结果，圈内为机器人陷入局部极小值位置，通过增设虚拟目标而逃脱。分析图7可以得出两点结论：①在动态环境下，改进人工势场法能够完成起点到终点的路径规划；②从图中可以明显看到路径中存在震荡和徘徊的部分。

3 混合路径规划方法

由图6和图7可知，在动态和静态环境下，改进人工势场法规划的路径中都包含震荡和徘徊的部分，为了使路径更加平滑并克服往返现象，本节提出了全局规划和局部规划相结合的混合规划方法，就是使用加权A*算法进行全局最优路径规划基础上，再使用改进人工势场法进行局部路径规划。

3.1 改进人工势场算法缺陷及解决方法

使用改进人工势场法进行局部路径规划时存在以下几个问题：①机器人只能依据自身传感器感知到的环境进行局部路径规划，而没有挖掘固定的全局障碍物分布信息；②增设虚拟目标只能保证机器人可以摆脱局部极值点，而没有考虑路径规划效率；③机器人在障碍物近处行进时，位置的稍微改变会引起较大的合力变化，使路径容易震荡和徘徊。

为了解决以上问题，本文将全局路径规划的拐点作为局部路径规划时的子目标点，依次以拐点作为局部路径规划的目标点，直到到达实际目标点。提出这种解决方法主要有以下原因：①全局路径规划时充分使用了全局障碍物分布信息，使用全局路径规划的拐点作为子目标，使局部路径规划时充分利用了全局障碍物分布信息；②改进人工势场法规划的不平滑区域和徘徊区域大都在路径拐点处；③减少原目标点在整个路径规划中的影响，从而消除原目标点产生的局部极小值点。

3.2 混合路径规划实现步骤

基于以上分析，混合路径规划的实现步骤为：

Step1：使用栅格法对机器人工作环境建模；

Step2：使用加权A*算法进行全局路径路径规划，找到规划路径的拐点和实际目标点作为局部路径规划的子目标点；

Step3：依次以子目标点为目标使用改进人工势场法进行局部路径；

Step4：判断当前子目标是否为实际目标，若是则路径规划结束，输出最优路径；否则转至Step3。

4 仿真验证

使用图2给出的车间环境进行实验验证，使用图3d中全局路径规划的拐点和实际目标点作为子目标点。针对工厂车间特殊环境，需要设计三组实验进行路径规划的验证：①验证固定静态障碍物情况下，增设子目标点和不增设子目标点的规划结果；②验证临时堆放障碍物情况下，路径规划结果；③验证动态障碍物情况下，路径规划结果。

(1)对于静态障碍物情况下，增设子目标和未增设子目标的路径规划结果如图8所示。

(a)未增设子目标 (b)增设子目标

可以看出，将全局路径规划的拐点作为子目标，可以使路径更加平滑，而且路径中不存在徘徊和震荡现象，这极大地减小了机器人行走负担，极大提高了机器人工作效率。

(2)对临时堆放障碍物情况下路径规划进行验证。为了验证机器人避开临时堆放障碍物的效果，在图3d规划的最优路径上放置3处临时障碍物(红圈内)，使用混合路径规划方法得到的路径如图9所示。

图9 临时堆放障碍物时路径规划结果

可以看出，使用混合路径规划方法，由于路径中增设了子目标，使得路径非常平缓，而且没有震荡和徘徊现象；其次，混合路径规划方法能够准确避开障碍物且轨迹不偏离最优路径。

(3)动态障碍物情况下，使用混合路径规划的结果如图10所示。

图10 动态障碍物时路径规划结果

将图10与图7b的规划结果进行比较，可以看出混合路径规划方法得到的路径很好地解决了路径徘徊和震荡问题，减小了机器人转弯和变速负担，提高了机器人使用寿命和工作效率。

5 结论

针对工厂车间环境相对固定、存在临时堆放障碍物和动态障碍物的情况，本文将栅格法与加权A*算法结合进行了机器人全局路径规划，改进了人工势场法用于机器人局部路径规划，而后将全局路径规划和局部路径规划相结合，提出了混合路径规划方法。通过分析可以得出以下结论：①通过合理选择权值，加权A*算法可以平衡路径规划工作量和陷入局部极值问题；②改进人工势场法有效解决了传统方法目标不可达和局部极值陷阱的问题；③混合路径规划方法使用增设子目标的方法，有效解决了改进人工势场法路径徘徊和震荡问题，使路径更加平稳。

[1] Fakoor M, Kosari A, Jafarzadeh M. Humanoid Robot Path Planning with Fuzzy Markov Decision Processes[J]. Journal of Applied Research & Technology, 2016, 14(5):300-310.

[2] 柴寅, 唐秋华, 邓明星,等. 机器人路径规划的栅格模型构建与蚁群算法求解[J]. 机械设计与制造, 2016(4):178-181.

[3] 陈超, 唐坚, 靳祖光,等. 一种基于可视图法导盲机器人路径规划的研究[J]. 机械科学与技术, 2014, 33(4):490-495.

[4] 杨柳, 张洪, 高忠国. 基于人工势场法的移动机器人路径规划研究[J]. 机床与液压, 2011, 39(9):68-70.

[5] 付宜利, 顾晓宇, 王树国. 基于模糊控制的自主机器人路径规划策略研究[J]. 机器人, 2004, 26(6):548-552.

[6] 余勇. 基于改进蚁群算法的移动机器人路径规划研究[J]. 机械传动, 2016,40(7):58-61.

[7] 王海英. 智能优化算法研究及其在移动机器人相关技术中的应用[D]. 哈尔滨:哈尔滨理工大学, 2007.

[8] 张紫辉, 熊岳山. 未知环境下基于A*的机器人路径规划算法[J]. 计算机工程与科学, 2012, 34(11):141-147.

[9] Liu S, Zhang Q, Zhou D. Obstacle Avoidance Path Planning of Space Manipulator Based on Improved Artificial Potential Field Method[J]. Journal of the Institution of Engineers, 2014, 95(1):31-39.

[10] 李奕铭. 基于人工势场法的移动机器人避障研究[D]. 合肥:合肥工业大学, 2013.