王迪，李彩虹，郭娜，张宁

(山东理工大学 计算机科学与技术学院，山东 淄博 255049)

在有障碍物的环境中，按照一定的评价标准，寻找一条安全无碰的绕过障碍物、从起始点到目标点的路径，是移动机器人路径规划要解决的问题。路径规划用于GPS导航、水下导航系统、无人机、移动机器人避障系统等，具有广泛的应用领域及较高的应用价值。

路径规划分为全局路径规划和局部路径规划，即环境信息已知的和环境信息未知的路径规划。全局路径规划算法有蚁群算法、遗传算法、A*算法、栅格法等，局部路径规划算法有模糊控制[1]、人工势场法、神经网络[2]等，其中人工势场法以其简单的原理、少量的计算、实时性好以及平滑的路径等优点得到广泛应用。但是传统人工势场法存在局部极小点和目标不可达的问题。局部极小点问题是移动机器人因在某一范围内产生势场的局部极小点而无法到达目标点。目标不可达问题是移动机器人在障碍物或目标点前因斥力大于引力使得移动机器人无法到达目标点。国内外学者针对局部极小点问题提出了两种解决方案。一种方案是将人工势场法与其他算法结合起来克服人工势场法的缺陷。韩伟[3]提出了模糊人工势场法来解决局部极小点问题；刘芳[4]将人工势场法与免疫算法相结合来解决因局部极小值而陷入死锁的情况；Chen等[5]加入混沌优化方法对人工势场法进行改进，解决了局部极小点和目标不可达问题。另一种方案是在传统人工势场法的基础上做改进。纪迪[6]采用多方向沿墙走的方法，从五个方向中选出合适的方向跳出局部极小点陷阱；温素芳等[7]提出障碍物影响范围分层的思想，使移动机器人顺利到达目标点；鲁新军等[8]提出水流解决法；梁献霞等[9]提出通过扇区划分的方法在合适的位置添加虚拟障碍物，从而改变合力大小，打破局部极小点僵局；Lee等[10]提出了NP-APF，即在无障碍物的环境设置虚拟目标点来克服局部极小点和路径无效率问题。

本文采用基于人工势场法的左转势场法和虚拟目标点法解决移动机器人在障碍物前震荡、无法到达目标点的缺陷。通过计算移动机器人当前位置与之前走过位置的距离来判断移动机器人是否陷入局部极小点陷阱。在未陷入局部极小点陷阱时移动机器人沿其所受的引力与斥力的合力方向每次移动一个步长，若陷入局部极小点陷阱则通过改变移动机器人的移动方向，使其跳出局部极小点陷阱，顺利到达目标点。

1 人工势场法

传统人工势场法路径规划是由Khatib于1986年提出的一种虚拟力法[11]。该方法将机器人、目标点、障碍物看做质点，目标点对机器人产生引力，障碍物对机器人产生斥力，由引力与斥力的合力决定机器人的下一步前进坐标。实质是在移动机器人运动的环境中人为地定义一个势力场，目标点产生的引力场与障碍物产生的斥力场叠加，共同对移动机器人产生作用，使移动机器人绕开障碍物到达目标点。人工势场定义为

U=Uatt+Urep

(1)

式中:U为势场和;Uatt为目标点对移动机器人产生的引力场;Urep为障碍物对移动机器人产生的斥力场。定义目标点对移动机器人的引力和障碍物对移动机器人的斥力分别对应引力场和斥力场的负梯度，根据偏导得出人工势场对机器人的作用力F的大小为

F=Fatt+Frep

(2)

式中：F为合力；Fatt为目标点对移动机器人产生的引力；Frep为障碍物对移动机器人产生的斥力。

1.1 引力场

设目标点的位置为EP，机器人的位置为X，引力势场函数定义为

(3)

式中：k为引力增益系数；‖X-EP‖为机器人到目标点的欧几里得距离。目标点对机器人的引力为引力势场函数的负梯度，即

Fatt=k‖X-EP‖

(4)

1.2 斥力场

设机器人的位置为X，在传统人工势场法的斥力场函数中添加了机器人与目标点之间的距离[12]。添加机器人与目标点的距离可以保证目标点处的势场为全局最小点，添加距离后的斥力势场函数定义为

(5)

式中：m为斥力增益系数;d为机器人与障碍物的距离;d0为障碍物影响距离;da为机器人与目标点之间的距离。障碍物对机器人的斥力为

(6)

1.3 受力分析

根据目标点对移动机器人的引力和障碍物对移动机器人的斥力的合力决定移动机器人前进的方向。其中，五角星代表机器人，方形代表障碍物，十字代表目标点。受力分析如图1所示。

图1 移动机器人受力分析图Fig.1 Force analysis diagram of mobile robot

2 解决局部极小点的方法

当移动机器人遇到某范围内势场或合力的局部极小点时就陷入了局部极小点陷阱。局部极小点陷阱体现为移动机器人在某一范围内反复震荡。根据沿墙走的思想，使移动机器人沿着障碍物前进，绕开障碍物，跳出局部极小点陷阱。本文采用了两种方法来解决局部极小点问题：一种是左转势场法,另一种是虚拟目标点法。

2.1 左转势场法

移动机器人进入局部极小点陷阱时，传统的人工势场法以及单纯地改变势场函数不能很好解决这个问题，如图2所示，这是比较经典的局部极小点问题。其中五角星为机器人的起始位置，十字是目标点，方形是障碍物，移动机器人、障碍物、目标点在一条直线上，虽然合力不为零，但是引力与斥力分量Frep1方向相反，移动机器人未靠近障碍物时引力大，斥力为零，合力方向指向引力方向，靠近障碍物时斥力分量Frep1大，合力方向指向Frep1方向，陷入了局部极小点陷阱，导致移动机器人一直在小范围内上下移动。左转势场法利用移动机器人自带的传感器(扫描角度为360°)来躲避障碍物，通过计算目标点、障碍物与移动机器人的距离，计算移动机器人受到的各个力的大小和方向。当检测到移动机器人在某一范围内徘徊时，根据此时移动机器人所受到的斥力分量Frep1的方向，向左偏转90°移动，移动机器人就跳出了局部极小点陷阱。此时移动机器人所受斥力的分量Frep1的方向如图3所示。

图2 局部极小点情况 Fig.2 Local minimum case

图3 移动机器人所受斥力分量 Frep1方向 Fig.3 The direction of the repulsive force component Frep1 received by the mobile robot

基于左转势场法的移动机器人遇到局部极小点陷阱时，下一步移动位置的公式为

(7)

式中:(xi+1,yi+1)为移动机器人下一步移动位置的坐标；(xi,yi)为当前移动机器人所在位置的坐标；h为步长;ang(Frep1)为Frep1的角度。此时移动机器人的移动方向如图4中箭头所指方向，此种方法在遇到U型障碍物和一字型障碍物时都能很好地避开。因为障碍物的影响距离与移动机器人步长大小悬殊，所以移动机器人不会碰到障碍物。

图4 左转势场法移动机器人移动方向Fig.4 The direction of movement of a mobile robot in the left-turn potential field method

采用左转势场法的基本流程如图5所示。

图5 左转势场法流程Fig.5 Flow chart of the left-turn potential field method

2.2 虚拟目标点法

基于上一小节的思想，当移动机器人在障碍物前陷入局部极小点陷阱而徘徊时，在移动机器人所受斥力分量Frep1方向向左偏转90°的方向上的合适位置添加一个虚拟目标点，此时忽略目标点对移动机器人的引力和障碍物对移动机器人的斥力，使移动机器人沿虚拟目标点的引力方向移动，移动后撤销虚拟目标点，恢复障碍物与目标点的作用。重复此步骤，直到移动机器人跳出局部极小点陷阱。虚拟目标点法与左转势场法的区别是移动机器人在陷入局部极小点陷阱时，虚拟目标法中的转向是因为移动机器人受到虚拟目标点的引力作用，而左转势场法是强制转向，此时不受任何力的作用。移动机器人陷入局部极小点时，采用虚拟目标点法的下一步移动位置由式(7)计算，移动机器人所受斥力分量Frep1的方向及下一步移动方向如图6所示。虚拟目标点法流程如图7所示。

图6 移动机器人所受斥力分量Frep1的方向及其移动方向Fig.6 The direction of the repulsive force component Frep1 received by the mobile robot and the moving direction of the mobile robot

图7 虚拟目标点法流程Fig.7 Flow chart of the virtual object point method

3 仿真与分析

本文利用Matlab模拟现实生活中的移动机器人在前进过程中遇到障碍物时如何避开障碍物到达目标点的情形，分别在一字型障碍物、U型障碍物以及混合型障碍物环境中进行。图8是移动机器人遇到一字型障碍物时分别基于改进势场函数的人工势场法、左转势场法、虚拟目标点法规划路径的仿真图，其中，红色十字是虚拟目标点。图9为一字型障碍物环境下基于左转势场法、虚拟目标点法时障碍物产生的斥力分量Frep1的大小，可以看出障碍物前形成了局部极小点陷阱。图10为移动机器人遇到U型障碍物时分别基于改进势场函数的人工势场法、左转势场法、虚拟目标点法的仿真图，与只改进势场函数的人工势场法比较，后两种方法能够绕开障碍物且路径比较平滑。图11为U型障碍物环境下移动机器人基于左转势场法、虚拟目标点法进行路径规划时障碍物产生的的斥力分量Frep1的大小，可以看出在U型障碍物内形成了局部极小点陷阱。图12为混合型环境中移动机器人采用左转势场法和虚拟目标点法规划的路径仿真图。由路径仿真图可以看出，移动机器人可以快速绕过由散点障碍物、U型障碍物和一字型障碍物等混合组成的障碍物环境，较平滑地到达目标点。

(a) 基于人工势场法 (b) 基于左转势场法 (c) 基于虚拟目标点法图8 移动机器人遇到一字型障碍物时基于不同方法的路径规划Fig.8 Path planning diagram based on different methods when mobile robot encounters a linear obstacle

(a)基于左转势场法 (b) 基于虚拟目标点法图9 移动机器人遇到一字型障碍物时受到的斥力分量Frep1的大小 Fig.9 The magnitude of the repulsive force component Frep1 when mobile robot encounters a linear obstacle

(a) 基于人工势场法 (b)基于左转势场法 (c)基于虚拟目标点法图10 移动机器人遇到U型障碍物时基于不同方法的路径规划Fig.10 Path planning diagram based on different methods when mobile robot encounters a U-shaped obstacle

(a)基于左转势场法(b) 基于虚拟目标点法图11 移动机器人遇到U型障碍物时受到的斥力分量Frep1的大小Fig.11 The magnitude of the repulsive force component Frep1 when the mobile robot encounters a U-shaped obstacle

(a)基于左转势场法(b) 基于虚拟目标点法图12 混合环境下移动机器人的的路径规划 Pig.12 Path planning of mobile robot in a mixed environment

4 结束语

本文设计了左转势场法和虚拟目标点法的避障策略来解决移动机器人采用传统人工势场法路径规划存在的局部极小点陷阱问题。通过在Matlab平台上仿真可以看出，这两种方法规划的路径均能走出局部极小点陷阱且路径规划效果较好。左转势场法无需外力，通过强制转向来跳出局部极小点；而虚拟目标点法相当于将路径划分为若干个阶段，虚拟目标点是移动机器人前往目标点的中转站。尽管两种方法的最终路径规划效果一样，但是相对而言，左转势场法比虚拟目标点法更适合于障碍物密集的环境，在需要频繁采取转向策略的环境下，左转势场法计算简单，移动方向专一，速度快。两种方法都是通过转向策略跳出局部极小点，方法是对称的，无论是向左转还是向右转，都能解决相同的问题，但这两种方法在遇到近似封闭的障碍物环境时无法到达目标点，存在局限性。