未知环境下机器人避障及动态目标追踪*

崔宝侠， 宋佳瑞

(沈阳工业大学 信息科学与工程学院， 沈阳 110870)

机器人避障及动态目标追踪是智能机器人技术的重要分支和研究热点[1].避障算法共分为已知环境下的全局避障算法和未知环境下的局部避障算法两类[2]，已知环境下的机器人避障通过对已知的障碍物分布信息进行地图建模就可以实现，目前较为成熟的已知环境下的全局避障算法主要有以下几种：可视图法、栅格法、自由空间法和蚁群算法等[3-6]，这些算法在要求必须求出全局最优解的问题中是可以考虑的，获取的环境信息越详细、准确，规划出的路径越贴近最优，通常这些算法的实时性非常不好，并且计算过程繁琐、步骤多，对于障碍物位置会发生变化的环境适应性差，导致速率和效率很低.而未知环境下机器人避障的具体过程就是首先由探测器探测障碍物信息，之后将探测到的信息交给处理器处理，根据探测到的不同信息选择不同的避障策略.

目前应用于未知环境下且被研究最为广泛的局部避障算法有以下几种：神经网络算法、模糊逻辑算法、人工势场法和遗传算法等[7-10]，虽然这些算法避障的实时性相对于全局避障算法要好很多，对未知环境的适应性较强，但是依然存在着不同方面的局限性.人工势场法由于实时性好、反应速度快、运算量小、建模容易、对未知环境适应性强等优点而被广泛使用.但同时人工势场法也存在局部最小点和无法到达目标点等缺陷.

1 基于人工势场法的避障方法分析

人工势场法最初是由Khatib于1985年提出的，其核心思想是将机器人的运动假想成在抽象的合力势场中的运动.在机器人工作空间中假想出无数条引力和斥力的场强线，使得机器人在类似于充满“磁场”的空间中运动，目标点对机器人产生的作用力就像“磁铁”一样吸引着机器人，把它想象成引力.而障碍物与机器人的作用力就好像磁铁同极之间的作用力一样，把它想象成斥力.机器人就是在这种引力和斥力的合力驱动下进行运动，每行走到一个位置就去计算当前位置机器人所受的合力大小以及合力的方向，边行走边去探测周围的环境信息，属于反应式机器人避障算法.该方法的提出让机器人的避障规划问题与代数问题和几何学问题相结合，将抽象的问题具体化，便于专家研究和学者分析，为机器人避障规划研究工作做出了巨大贡献.图1为人工势场法的受力分析示意图.

图1 人工势场法受力分析示意图Fig.1 Schematic diagram of force analysis inartificial potential field method

传统人工势场法的引力势场函数和斥力势场函数分别为

(1)

(2)

对式(1)、(2)分别求负梯度可得引力计算公式和斥力计算公式，即

(3)

(4)

相比其他算法，人工势场法的优点主要表现在实时性强、便于分析和建模，可以在未知环境下应用，无需先验知识[11].而正是由于其反应式的避障特性导致其忽略了大部分的全局信息，人工势场法的局限性主要表现在目标不可达问题和局部极小值问题.

1) 目标不可达问题.目标不可达问题是指机器人在行进至距离目标点较近的位置时，目标点附近存在一个或多个障碍物，并且目标点和机器人同时处在障碍物的影响范围之内时所产生的机器人到达目标点失败的现象.随着机器人与目标点之间的距离缩短，机器人所受的引力越来越小，机器人所受的斥力大小与障碍物的距离成反比.目标点附近的障碍物会导致在机器人所受引力减小的过程中，对机器人产生的斥力越来越大，机器人很可能会被“推”回来，向远离目标点的方向运动.而在反方向运动的同时，机器人在这个瞬间再一次远离了障碍物和目标点，机器人所受的引力又在增加，斥力又在减小，因此，就出现了机器人由于所受合力为零且速度不完全为零，在目标点附近不停地徘徊震荡，却永远不会刚好停止在目标点上的现象.图2为机器人在陷入目标不可达问题时的受力分析图.

图2 人工势场法目标不可达示意图Fig.2 Schematic diagram of unreachable targetin artificial potential field method

2) 局部极小值问题.所谓的传统人工势场法的局部极小值问题是指机器人在行走的过程中，在距离目标点较远的情况下，机器人所受的单个障碍物的斥力或者多个障碍物的斥力合力与目标点对机器人的引力大小相等，方向相反，机器人在未到达目标点之前所受合力为零，机器人会误以为当前的路径结点为全局势场最小点，即目标点.当机器人陷入局部极小值时，存在以下两种情况.

第一种情况：机器人和障碍物都距离目标点较远时，机器人、障碍物和目标点在同一条直线上且障碍物位于机器人和目标点中间，此时机器人所受的目标点的引力还是非常大的，而由于机器人距离障碍物很近，机器人所受的斥力也非常大，因此产生了引力和斥力大小相等，方向相反的情况，机器人陷入局部极小值点，示意图如图3所示.

第二种情况：机器人所在位置的附近存在两个或者两个以上的障碍物，障碍物之间具有一定距离，机器人与目标点的连线上不存在影响范围包含机器人的障碍物，目标点对机器人的引力会和机器人所在位置附近的每个影响范围都包含机器人的障碍物的斥力合力大小相等，方向相反，同样会形成局部极小值问题，导致机器人在速度不完全为零的情况下，由于惯性在障碍物通道中徘徊震荡不前进.在机器人的避障环境中，相对于第一种局部极小值情况，第二种更加常见，几乎存在于大部分地图中，机器人在第二种局部极小值情况下的受力示意图如图4所示.

图3 人工势场法局部极小值示意图1Fig.3 Schematic diagram 1 of local minimum valuein artificial potential field method

图4 人工势场法局部极小值示意图2Fig.4 Schematic diagram 2 of local minimum valuein artificial potential field method

2 算法改进与应用

2.1 重新定义斥力方向

文献[12]对传统人工势场法进行了改进，在斥力场函数中加入了机器人与目标点距离这一项，使得机器人在靠近目标点过程中，目标点附近的障碍物对机器人产生的斥力场逐渐减小，保证了目标点为机器人所在势场的全局最小点.改进公式为

(5)

Frep= -Urep(W)=

(6)

改进后的斥力由两个分力组成，分别为

(7)

(8)

式中：Frep1为机器人所受斥力的第一个分量，其方向由障碍物指向机器人，作为机器人远离障碍物的动力；Frep2为斥力的第二个分量，其方向由机器人指向目标点，和引力的方向相同；n为机器人与目标点距离的指数因子.

虽然改进斥力场函数的人工势场法解决了目标不可达问题，但仅仅是调整了目标点附近障碍物在机器人靠近目标点过程中对机器人产生斥力的大小，对解决机器人在距离目标点较远的障碍物周边陷入局部极小值点的问题是无效的.

当机器人在陷入目标不可达问题时，机器人距离目标点较近，由于目标点附近的障碍物对机器人的斥力合力和目标点对机器人的引力大小相等、方向相反，引力方向与各个障碍物的斥力合力方向夹角为180°.在机器人陷入局部极小值点时，距离目标点较远，机器人附近的单个障碍物对机器人的斥力或者多个障碍物对机器人的斥力合力与目标点对机器人的引力大小相等、方向相反，机器人所受的引力和各个障碍物斥力合力的夹角同样为180°.实际上引力与斥力分力的夹角是多种情况的，并不一定是固定值，但是通过分析在改进斥力场函数的人工势场法条件下障碍物的分布情况，可以总结出机器人受力情况规律，机器人所受的每个障碍物的斥力的第一个分力Frep1与引力Fatt的夹角大于90°的情况下可能会产生目标不可达问题或者局部极小值问题.为了使机器人在运行过程中每一时刻所受的引力和每个障碍物给予的斥力的每一个分力的夹角都不大于90°，重新定义了人工势场法斥力分力的方向.

将工作空间中的障碍物假设为圆形，改进原理为斥力分力的大小采用式(7)、(8)求解，但仅仅是模的大小相等，方向却不同.将每个障碍物对机器人产生的斥力Frep分解为Frep1和Frep2两个方向的分力，Frep2的方向与改进斥力场函数的人工势场法相同，为从机器人指向目标点，与引力的方向一致，不同的是将Frep1的方向重新定义为与机器人和障碍物圆心连线垂直的方向，单纯的垂线是没有方向的，改进算法中Frep1的方向为与引力方向夹角不大于90°的方向.重新定义斥力分力方向的目的就是从根本上消除产生每种类型的局部极小值问题和目标不可达问题的可能性，Frep2的方向与引力方向同向，则夹角为0°，将Frep1又重新定义为与引力方向夹角不大于90°的方向，则机器人在到达目标点前永远不会出现引力方向与斥力分力方向夹角大于90°的情况.同理引力Fatt与两个斥力分力的合力Frep的夹角也不大于90°，也就是说机器人在到达目标点前不可能会出现局部极小值和目标不可达两种问题.图5为在重新定义了斥力分力的方向后，机器人的受力分析图.

图5 斥力改进示意图1Fig.5 Schematic diagram 1 for improvementof repulsive force

但有以下两种特殊情况除外：

1) 当机器人、障碍物和目标点位于同一条直线上，并且机器人位于障碍物与目标点之间时，定义Frep1与Frep2同向，均指向目标点，示意图如图6所示.

图6 斥力改进示意图2Fig.6 Schematic diagram 2 for improvementof repulsive force

2) 当机器人、障碍物和目标点在同一直线上，且目标点位于机器人与障碍物之间时，定义Frep1与Frep2同向，均指向目标点，示意图如图7所示.

图7 斥力改进示意图3Fig.7 Schematic diagram 3 for improvementof repulsive force

上述两种状况斥力分力之一Frep1所定义的方向与引力方向一致，其目的是为了防止当机器人、障碍物和目标点位于同一条直线上时，机器人在避障的过程中以及行走至目标点的过程中产生不必要的转弯和抖动，增加行走的路径长度和避障的时间.由图5～7可知，机器人在重新定义斥力分力方向的人工势场法条件下所受的引力和各个斥力的分力夹角永远不会大于90°.

2.2 重新定义人工势场引力公式

由于在实际应用中，目标点大部分是具有速度和加速度的，例如导弹的跟踪拦截.在重新定义了斥力分力方向后，为了完成机器人在避障的同时进行动态目标追踪的工作，在引力势场函数上加入机器人与目标速度之差和加速度之差的因子，使得加速度之差的变化也会导致引力函数的变化，不再仅仅讨论目标加速度为0的匀速运动.为了预防引力的大小瞬时突变，产生与障碍物碰撞，会一直保持对机器人产生适宜的牵引力，使得机器人路径更加平滑，长度短，机器人行走路线更加合理.重新定义人工势场引力表达式为

(9)

Fatt= -grad(Uatt)=

-Kaqq-qgoal-Kavv-vgoal-

Kaaa-agoal

(10)

式中：Kaq、Kav、Kaa为三个增益系数；Uatt和Fatt分别为引力势场函数和引力函数；q和qgoal分别为机器人和目标点的位移大小；v和vgoal分别为机器人和目标点的速度大小；a与agoal分别为机器人和目标点的加速度大小.根据不同的环境地形、障碍物的分布以及密集状况灵活地选择引力和斥力增益系数以及障碍物影响范围.改进算法流程如图8所示.

3 仿真结果分析

对不同障碍物分布的环境分别进行仿真，与现有的改进人工势场法进行对比，并将地图中的障碍物数量不断增加，使得障碍物越来越密集.通过对不同障碍物分布情况的仿真结果进行对比，从而体现该算法的可行性和优势.

图9为多障碍物环境，目标匀速直线运动，并且避障空间较大.利用文献[12]中的改进人工势 场法进行避障及动态目标追踪会使得机器人陷入局部极值点停止不前，并且由于目标在不断向右运动，机器人不会灵活调整方向，导致停止在该点不追踪动态目标以及避障.图9中的曲线为机器人运动轨迹，直线为动态目标点运动轨迹，黑白相间的圆为障碍物，仿真为动态图，本文中的图示为到达规定步数停止之后的最后状态图.

图8 算法流程图Fig.8 Flow chart of algorithm

图9 改进人工势场法的机器人动态目标追踪及其避障

Fig.9Dynamictargettrackingandobstacleavoidanceofrobotwithimprovedartificialpotentialfieldmethod

图10～12分别为利用本文改进思想的人工 势场法在障碍物逐渐密集以及数量越来越多的仿真图示.相对于图9，图10的障碍物更加密集，而且目标改变为做匀加速运动，该环境下目标的运动要考虑加速度，所以利用式(9)、(10)计算引力，利用重新定义斥力分力方向的人工势场法去 计算合力的大小和方向，仿真结果显示该算法可行.

图10加入优化思想后的机器人避障及其目标追踪过程仿真图示1

Fig.10Simulationdiagram1fordynamictargettrackingandobstacleavoidanceofrobotafteraddingoptimizationidea

图11加入优化思想后的机器人避障及其目标追踪过程仿真图示2

Fig.11Simulationdiagram2fordynamictargettrackingandobstacleavoidanceofrobotafteraddingoptimizationidea

图11中不仅目标做变加速运动，而且在图10的基础上将障碍物位置稍加变动，在机器人追踪目标的关键路径点上设置障碍物，而且目标加速度一直在变化，增加避障物及其目标追踪的难度系数，仿真结果显示该改进算法依然可行.

图12显示在机器人的起点处，障碍物就开始尽力封堵机器人的路线，使得机器人无法从左侧直接绕过障碍物追踪动态目标，并且目标做变加速运动，仿真结果显示该算法依然可行.

通过对比不同环境下的仿真结果，不断改变环境、障碍物的分布以及密集程度，增加机器人避障及其追踪的难度系数，验证了该算法的可行性. 该算法的优势在于障碍物可以随机设置，在极小的避障空间内也可以追踪到动态运动的目标，同时解决了传统人工势场法产生的局部极小值问题和目标不可达问题.

图12加入优化思想后的机器人避障及其目标追踪过程仿真图示3

Fig.12Simulationdiagram3fordynamictargettrackingandobstacleavoidanceofrobotafteraddingoptimizationidea

4 结 论

本文将改进人工势场法应用到机器人动态目标追踪及避障中，并且将机器人受到的斥力分力方向重新定义，提高避障的灵活性，使得机器人可以灵活调整方向，消除了机器人在某一点不停抖动停滞不前的现象.把二者加速度之差加入公式中，提高了引力控制的精确性，使得机器人受到的引力不会过大而导致避障失败，并且根据不同障碍物分布情况灵活选择人工势场法的计算参数、引力斥力增益系数和障碍物影响范围.综合多方面优化改进人工势场法，在前人优秀成果中加入了优化改进思想，可以用来解决静态目标环境下的避障问题，只需将目标点的速度和加速度设置为0，引力公式变为传统人工势场法引力公式即可.在多障碍物以及障碍物密集的复杂地形下，该方法的避障实时性强、灵活，不用预知地图情况，障碍物可随机设置，只要有避障空间和避障的可能性，该算法完全可以实现机器人在未知环境中高效、独立、自主地避障及其动态目标追踪.

参考文献(References)：

[1] 胡小平，谢珂，左富勇.基于改进人工势场法的机械手避障规划 [J].测控技术，2012，31(10)：109-111.

(HU Xiao-ping，XIE Ke，ZUO Fu-yong.Obstacle avoidance path planning for manipulator based on improved artificial potential field [J].Measurement & Control Technology，2012，31(10)：109-111.)

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

(LI Yi-ming.Research on obstacle avoidance of mobile robot based on artificial potential field method [D].Hefei：Hefei University of Technology，2013.)

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

(CHEN Chao，TANG Jian，JIN Zu-guang，et al.A path planning algorithm for seeing eye robots based on V-graph [J].Mechanical Science and Technology for Aerospace Engineering，2014，33(4)：490-495.)

[4] 朱磊，樊继壮，赵杰，等.基于栅格法的矿难搜索机器人全局路径规划与局部避障 [J].中南大学学报(自然科学版)，2011，42(11)：3421-3428.

(ZHU Lei，FAN Ji-zhuang，ZHAO Jie，et al.Global path planning and local obstacle avoidance of searching robot in mine disasters based on grid method [J].Journal of Central South University(Science and Technology)，2011，42(11)：3421-3428.)

[5] 李刚.自由空间激光通信网路由最优路径选择方法研究 [J].激光杂志，2017，38(2)：132-136.

(LI Gang.Research on routing of free space laser communication networks optimal path selection method [J].Laser Journal，2017，38(2)：132-136.)

[6] 蒲云花，陈世平.改进蚁群算法在移动自组网中的研究 [J].计算机应用研究，2015(2)：574-578.

(PU Yun-hua，CHEN Shi-ping.Research of improved ant algorithm for mobile Ad Hoc networks [J].Application Research of Computers，2015(2)：574-578.)

[7] 杨忠，刘华春.基于BP神经网络的扫地机器人寻路算法 [J].电脑知识与技术，2017，13(10)：156-158.

(YANG Zhong，LIU Hua-chun.A sweeping robot path pathfinding algorithm based on BP neural network [J].Computer Knowledge and Technology，2017，13(10)：156-158.)

[8] Kim C J，Chwa D.Obstacle avoidance method for wheeled mobile robots using interval type-2 fuzzyneural network [J].IEEE Transactions on Fuzzy Systems，2015，23(3)：677-687.

[9] Yu Z Z，Yan J，Zhao J，et al.Mobile robot path plan-ning based on improved artificial potential field method [J].Journal of Harbin Institute of Technology，2011，43(1)：349-354.

[10]Zhou L F，Hong B R.A knowledge based genetic algorithm for path planning of a mobile robot [J].Acta Electronica Sinica，2006，34(5)：911-914.

[11]崔宝侠，周钰雨，段勇.机器人在未知环境条件下的动态避障 [J].沈阳工业大学学报，2016，38(6)：657-661.

(CUI Bao-xia，ZHOU Yu-yu，DUAN Yong.Dynamic obstacle avoidance of robot in unknown environment [J].Journal of Shenyang University of Technology，2016，38(6)：657-661.)

[12]王会丽，傅卫平，方宗德，等.基于改进的势场函数的移动机器人路径规划 [J].机床与液压，2002(6)：67-68.

(WANG Hui-li，FU Wei-ping，FANG Zong-de，et al.Path planning of mobile robot based on improved potential field function [J].Machine Tool and Hydraulic，2002(6)：67-68.)