自主移动机器人避障技术研究现状*

晋晓飞， 王 浩， 宗卫佳， 王鹏程， 王 策

(1.南京航空航天大学 仿生结构与材料防护研究所，江苏 南京 210016；2.南京航空航天大学 自动化学院，江苏 南京 210016; 3.南京航空航天大学 航天学院，江苏 南京 210016)

0 引 言

自主移动机器人的智能避障指机器人通过传感器检测到障碍物并采集其状态信息，按照一定的算法进行的路径规划，从而避开障碍物，最终到达目的地。如何让机器人判断障碍物，并躲避，是机器人避障中的2个关键问题[1，2]。

自主移动机器人的避障问题分为2类：障碍物环境信息完全已知和障碍物环境信息未完全已知。前者机器人避障属于全局路径规划；后者或完全未知情况下的机器人避障属于局部路径规划[3～5]。大多情况下，机器人所处外部环境动态未知，传统避障算法在这些情况下将出现很多缺陷。

近些年研究提出的智能避障算法在很大程度上弥补了传统算法的不足，本文按照传统避障算法与智能避障算法对自主移动机器人避障技术进行分类，分析优缺点，并介绍了一些改进的算法。

1 自主移动机器人避障技术

1.1 传统避障算法

传统避障方法主要实现机器人无碰撞全局路径规划，经典的算法有以下几种：

1.1.1 人工势场法

人工势场法于20世纪80年代由 Khatib O等人[6]提出，将移动机器人的运动当作一个质点在一种抽象的人造势力场中的运动：目标点对质点产生引力，而障碍物对质点产生斥力，依据合力确定移动机器人的运动方向和路径。人工势场法具有结构简单、容易实现的优点，且规划后的路径比较平滑。不过这是一种局部寻优的方法，对于相对复杂的动态环境，不合理的势场方程容易使机器人陷入局部最小点。

Huang Y等人[7]提出了带记忆功能的沿墙(Wall-following)方法帮助机器人跳出局部最小点。徐飞[8]提出了一种基于相对速度的改进人工势场法，针对传统路径规划中局部最小点问题，提出了设置中间目标点的方法，给机器人一个外力以避免其在局部最小点处停止或者徘徊，确保机器人能够逃出最小点陷阱并顺利到达目标位置。

1.1.2 栅格法

Borenstein J和Koren Y[9]提出了基于栅格法的机器人避障，主要原理是将机器人的工作环境分割成为一系列具有二值信息的栅格单元，且将累积值放入每个矩形栅格中，累积值越高表明存在障碍物的可能性越大。栅格大小决定了算法的性能。若选择栅格较小，环境信息存储量即变大，机器人决策速度变慢，抗干扰能力变差；若选择栅格较大，环境信息存储量变小，决策速度变快的同时却降低了分辨率，导致了机器人在复杂障碍物环境下的通过能力减弱，增加碰撞风险。

Zhao K K等人[10]提出了基于射频识别( radio frequency identification，RFID) 系统的栅格法,借助网格划分、信息处理和无线通信，计算机计算出最短路径，并以标签的形式存储，通过标签和机器人之间的通信，机器人通过与后台支持数据库交互完成路径规划，路径规划效率大幅提高。华剑锋等人[11]提出了变分辨率栅格模型的方法，模型基于四叉树思想构建，不仅考虑了地形表达数据冗余度和精度，而且有效消除了地物“边缘效应”的影响，在此基础上，设计了一种启发式有向路径规划算法，既可以在连续空间中规划出最优路径，又可以提高路径规划的计算效率。

1.1.3 A*算法

尼尔森等人在1980年提出了A*算法[12]，是一种应用很广的启发式搜索算法。利用空间启发式信息，通过对比选择恰当的评估函数，通过动态搜索策略，求出移动机器人的最优规划路径。A*算法在全部已知且比较简单的环境中，搜索速度非常快，并能找到最优路径。但A*算法搜索路径的优化性较差，对于比较复杂的未知环境，搜索效率不高。

刘斌等人[13]提出了一种基于A*算法的动态多路径规划方法，结合A*算法与矩形限制搜索区域算法[14]，给出了一种求解单一优化路径的动态路径规划算法。同时提出了一种重复路径惩罚因子，可以利用其一次搜索出多条优化路径。方昕等人[15]将A*算法与栅格法进行有效结合，改进A*算法采用多个栅格包络障碍物方式，利用顶点外延节点生成路径来构造连通图。在此基础上，引入了平滑度概念，将算法应用于二维空间进行机器人路径规划，提高了算法搜索效率。

1.1.4 可视图法

Janet J A[16]将目标、障碍物以及机器人的各个顶点看作节点，再将所有节点进行组合相连，连线称为弧，并且设定各节点之间连接而成的弧均不能穿越障碍物，将弧看作可视的。该方法直观易懂，可得到最短的路径；但当移动机器人的起点或终点发生变化时，需要重构可视图，如果环境中障碍物较多，重构地图的过程会很复杂，搜索路径的时间就会加长。

杨淮清等人[17]提出了一种基于可视图法的移动机器人路径规划算法，将复杂轮廓的障碍物近似看成矩形或者多个矩形的组合体，以此建立障碍物边界地图，实现了路径规划。陈超等人[18]利用射频识别系统，通过超高频射频识别系统与低频射频识别系统的联合运用实现准确定位，将可视图法与A*算法相结合，提出了一种路径规划算法，在提高搜索效率的同时保证了规划路径的可行性。

1.1.5 自由空间法

自由空间法通过将移动机器人路径规划转变为在自由空间内的路径寻找解决路径规划问题，采用自定义的几何形状构建地图环境，同时将地图环境表示为连通图，最终通过对图的搜索实现了路径规划[19，20]。自由空间法原理简单，在起点和终点发生变化时，仅需重新定位，不需重绘整幅地图，易于实现；但当环境中存在复杂障碍物时，连通图会变得很复杂，算法实现困难，并且不能保证生成最优路径。

卢晓军等人[21]提出了一种基于自由空间的路径规划方法，结合启发式A*算法进行路径搜索，产生从初始位置到目标位置的最优路径。

1.1.6 拓扑法

拓扑法将移动机器人的运动空间划分为具备拓扑特征的一系列节点，并构建拓扑关系网，在所构建关系网上连接出起点和终点间的几何路线，最终将几何路线转化为移动机器人的几何路径[22]。拓扑法缩小了搜索范围，且不需要获得移动机器人在环境中的精确定位，对位置误差的处理具有很好的鲁棒性。但建立整个拓扑网络是个复杂的过程，且当环境中障碍物发生变化时难以快速准确地修改拓扑网络。

吴海涛等人[23]提出了一种基于邻接矩阵网络拓扑树构建的路径寻优方法，引入路网节点间邻接关系，将路网按照其节点邻接关系归类划分为以路网节点间邻接值为表征的路网拓扑进化树，同时对路径寻优问题中目标节点进行动态回溯分类，在限定路网搜索区域的同时采用分支定界搜索策略进行搜索优化，降低了搜索算法的时间复杂度。

此外，目前还有快速扩展随机树(rapidly-exploring random tree，RRT)算法、遗传算法等。RRT算法采用随机查询采样搜索，经过一个优化策略对外部空间进行信息采样，执行最佳路径策略；RRT算法对全局环境有较大的依赖性，且实时性较差[24]。遗传算法是由美国的Holland J H[25]提出的一种随机搜索算法。遗传算法将希望求解的问题进行编码，初始阶段随机生成候选种群，以适应度函数的形式评估种群的性能，并且在此基础上繁殖、交叉和变异[26]。遗传算法属于多点搜索算法，有更多机会寻找到全局最优解。但遗传算法只适用于全局路径规划，在复杂环境中若路径个体编码不合适，会导致进化速度缓慢；若遗传算子的选择不合理，不会有明显的进化效果。

1.2 智能避障算法

单一的传统避障算法在未知或者部分已知的环境中存在着较为明显的缺陷，开发适合动态未知环境的避障算法是自主移动机器人避障技术中亟需解决的问题。智能避障算法能够克服传统算法的缺陷，使机器人有效躲避障碍物。目前，较为新颖的几种智能算法有：

1.2.1 基于神经网络的机器人避障方法

Mihai D和Gheorghe M[27]研究了一种基于神经网络的新避障方法解决机器人在包含静态和动态障碍物的环境中自主移动的问题，规划出了自主移动机器人在不确定的包含静止和移动实体的工作空间内的无碰撞轨迹。该方案使用“Q学习”和“神经网络规划器”解决路径规划问题。如图1所示，Pos网神经网络是一个多层感知器，接收作为初始输入的P向量，P向量包含机器人当前位置、时间样本t，Q值矩阵，输出三值矢量(X,Y,t)。如果到达目标前发生碰撞或者步数已达到最大值，则Pos网神经网络重新开始权值初始化和迭代。该方法可以在计算轨迹之前设置机器 人的速度，在时间受限的应用中具有很大的优势。

图1 Pos网路径规划结构[27]

齐方远[28]研究了基于神经网络避障和 GPS定位的移动机器人自主运动方法，构建了基于BP神经网络和距离信息的移动机器人避障模型，并在此基础上提出了室外环境下移动机器人的自主运动方法。该避障模型效果较好，自主运动模型亦具备一定的自主运动能力。

1.2.2 基于可视性二叉树算法的机器人避障方法

Abdulmuttalib T R[29]提出了一种动态环境中机器人避障的新方法，可视性二叉树算法。为规划机器人的路径，算法依赖于机器人和目标之间的所有完整路径集合的构建，考虑机器人和圆形障碍物之间的内部和外部的可见切线。使用这些路径创建可视性二叉树，选择出最短优化路径。

1.2.3 基于滚动时域控制算法的机器人避障方法

Giuseppe F和Walter L[30]提出了滚动时域策略，用于解决动态环境中线性定常系统所描述的自主移动机器人的路径规划问题。滚动时域的方法即对于所有可能的障碍物场景，预先计算精确可控集内的椭圆近似序列，并在线分析，确定适当的控制动作使机器人完成避障。如图2所示，虚线椭圆代表可控集序列，沿箭头方向增加，经障碍物序列、场景切换序列、障碍物切换系列等滚动时域，实现避障路径规划。无论遇到任何障碍物，所产生的框架均能保证均匀的最终边界并且满足约束条件。

图2 滚动时域算法避障原理[30]

1.2.4 基于神经控制器的机器人避障方法

Nacer H和Boubekeur M[31]针对全向自主移动机器人提出了一种基于神经控制器的自主导航和避障策略。机器人规划一个路径，从初始点开始移动到目标点。将二阶多项式整体性规划方法应用到机器人沿理想路径情况下的运动，利用神经控制避免机器人与静态或动态障碍物之间发生碰撞。如图3所示，机器人从A点出发前往目标，期望路径(desired path，DP)即最短路径是两点之间的直线，但在这条路径附近有静态和动态障碍物，所以要使机器人沿DP方向规划路径，同时又要避免障碍物垂直于DP。神经控制器的设计是基于“感应矢量”和“间隙矢量”的概念。“感应矢量”是一个二进制向量，提供了有关障碍物的检测信息，“间隙矢量”提供了一个机器人可能通过的最近间隙的信息。

图3 神经控制器路径规划[31]

1.2.5 基于混合算法的机器人避障方法

Pai N S等人[32]设计了一种基于模糊理论和可拓理论的全向自主移动机器人。模糊理论用于调整控制电机转速的脉宽调制(pulse width modulation,PWM)信号，纠正机器人移动时出现的路径偏差问题。可拓理论用于建立机器人避障模型，建立多种移动模型以处理不同类型的障碍。机器人安装有超声波距离传感器估算障碍物的距离。如果遇到障碍，相关函数将进行评估，机器人将自主选择最合适的模式来避开障碍。系统流程如图4所示。

图4 系统流程[32]

Chen W J等人[33]提出了一种用于自主移动机器人的路径跟踪方法，包括路径规划和控制器设计。在路径规划中，使用B样条代替A*算法创建平滑和避障路径，减少了碰撞的可能性，B样条曲线如图5所示。在控制器设计中，将遗传算法和模糊逻辑组合在一起用于对在某一环境中运动的移动机器人的速度调控。

图5 B样条曲线(n=4,k=3)[33]

An P[34]提出了基于无线传感器网络的移动机器人的避障策略。该算法以模糊控制和神经网络控制理论相结合，使用数学模型表达难以描述的规则，大幅提高了机器人躲避障碍物的实时性、准确性和稳定性。

1.3 传统避障算法与智能避障算法性能对比

综合上文所述算法可以看出，传统避障算法局限性较大，不适合复杂未知的动态环境，而智能避障算法则在这方面表现出了巨大的优势。部分传统避障算法与智能避障算法性能对比如表1所示。

2 自主移动机器人避障技术展望

随着智能机器人技术的成熟，自主移动机器人将在工业、农业、医疗、服务等行业中得到广泛的应用，将来更会在城市安全、国防和空间探测领域等有害与危险场合得到很好的应用。自主移动机器人的避障技术是实现机器人智能性的一个重要方面，将会是机器人领域内的研究热点。

未来移动机器人避障算法的研究中，将多种算法的优点结合，整合出具有多重优势的混合算法，以实现机器人躲避障碍和路径规划的高效、实时与智能，这种避障模式将会是未来机器人避障技术的发展趋势。另外，多传感器信息融合技术可以使机器人建立更加准确的外部环境模型，未来，多传感器信息融合技术必定有更多的应用。此外，多机器人系统联合协作避障也将是未来研究的热点[35～38]。

表1 部分传统避障算法与智能避障算法性能对比

3 结束语

详细介绍了传统避障算法和智能算法的基本原理，优缺点，并进行了总结对比；对未来移动机器人避障技术进行了展望。

参考文献:

[1] 金 娟.自主移动机器人轨迹跟踪与避障控制研究[D].长沙：湖南大学,2015.

[2] 吕玉彬.基于多传感器融合的机器人导航系统中的避障研究[D].长沙：湖南大学,2012.

[3] 刘东辉.自主移动式机器人路径规划研究[D].大庆：东北石油大学,2013.

[4] John F C,Ming C L.An opportunistic global path planner,robo-tics and automation 1990[C]∥Proceedings of 1990 IEEE International Conference,1990:1554-1561.

[5] Kohtaro S,Masaki F,Jens S G,et al。Obstacle avoidance and path planning for humanoid robot using stereo vision[C]∥Proceedings of the 2004 IEEE International Conference on Robotics and Automation,2004:592-597.

[6] Khatib O.Real-time obstacle avoidance for manipu-lators and mobile robots[J].The International Journal of Robotics Research,1986,5(1):90-98.

[7] Huang Y,Hu H,Liu X.Obstacles avoidance of artificial potential field method with memory function in complex environment[C]∥The 8th World Congress on Intelligent Control and Automation(WCICA),2010:6414-6418.

[8] 徐 飞.基于改进人工势场法的机器人避障及路径规划研究[J].计算机科学,2016,43(12):293-296.

[9] Borenstein J,Koren Y.Real-time obstacle avoidance for fast mobile robots[J].IEEE Transactions on Systems,Man and Cybernetics,1989,19(5):1179-1187.

[10] Zhao K K,Zhou Y M,Song Z B,et.al.A grid method for robot path recognition based on RFID technology[C]∥2016 the 12th World Congress on Intelligent Control and Automation(WCICA),2016.

[11] 华剑锋,张 丰,杜震洪,等.基于变分辨率栅格模型的启发式有向搜索最优路径算法[J].浙江大学学报:理学版,2016,43(1):51-56.

[12] 王利敏.基于A*算法和B样条函数的月球车路径规划研究[D].长春：吉林大学,2016.

[13] 刘 斌，陈贤富，程 政.一种基于A*算法的动态多路径规划算法[J].微型计算机与应用,2016,35(4):17-20.

[14] 许震洪.动态路径诱导系统的最优路径算法研究及相关软件实现[D].南京:南京理工大学,2004.

[15] 方 昕，吕方兴.一种改进A*算法的智能机器人路径规划[J].信息技术，2015(9):40-42.

[16] Janet J A,Luo R C,Kay M G.The essential visibility graph:An approach to global motion planning for autonomous mobile ro-bots[C]∥IEEE International Conference on Robotics and Automation,1995:958-1963.

[17] 杨淮清，肖兴贵，姚 栋.一种基于可视图法的机器人全局路径规划[J].沈阳工业大学学报，2009,31(2):225-230.

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

[19] Brooks R A.Solving the find-path problem by good representation of free space[J].IEEE Trans on Syst Mans on Cyb,1983,13(2):190-197.

[20] Ghodgaonkar D K,Varadan V V,Varadan V K.A free space method for measurement of dielectric constants and loss tangents at microwave frequencies[J].IEEE Tran Instrum Meas,1989,38(3):789-793.

[21] 卢晓军，李 焱，贺汉根.一种基于自由空间法的虚拟人行走规划方法[J].计算机工程与科学，2005,27(8):60-69.

[22] Thrun S.Learning metric-topological maps for indoor mobile robot navigation[J].Artif Intel,1998,99(1):21-71.

[23] 吴海涛,张贵军,洪 榛,等.进化树拓扑路网构建及多停靠点路径规划方法研究[J].计算机学报，2012,35(5):964-971.

[24] 胡远航.未知环境下自主移动机器人避障研究[D].哈尔滨：哈尔滨工程大学,2013.

[25] Holland J H.Adaptation in natural and artificial systems:An introductory analysis with applications to biology,control,and artificial intelligence[M].2nd ed.Cambridge:MIT Press,1992.

[26] 马永杰，云文霞.遗传算法研究进展[J].计算机应用研究,2012,29(4):1201-1206.

[27] Mihai D,Gheorghe M.Neural networks based reinforcement learning for mobile robots obstacle avoidance[J].Expert Systems With Applications,2016 (62):104-115.

[28] 齐方远.基于神经网络避障和GPS 定位的移动机器人[D].北京：北方工业大学,2015.

[29] Abdulmuttalib T R,Abduladhem A A,Mattia F.Path planning with obstacle avoidance based on visibility binary tree algori-thm[J].Robotics and Autonomous Systems,2013,61:1440-1449.

[30] Giuseppe F，Walter L.The obstacle avoidance motion planning problem for autonomous vehicles:A low-demanding receding horizon control scheme[J].Systems & Control Letters,2015,77:1-10.

[31] Nacer H，Boubekeur M.Toward safety navigation in cluttered dynamic environment:A robot neural-based hybrid autonomous navigation and obstacle avoidance with moving target tra-cking[C]∥The 3rd International Conference on Control,Engineering and Information Technology(CEIT),2015.

[32] Pai N S,Hsieh H H,Lai Y C.Implementation of obstacle avoidance control for an autonomous omni-directional mobile robot based on extension theory[J].Sensors,2012,12:13947-13964.

[33] Chen W J,Jhong B G,Chen M Y.Design of path planning and obstacle avoidance for a wheeled mobile robot[J].International Journal of Fuzzy Systems,2016,18(6):1080-1091.

[34] An Peng.Obstacle avoidance strategy of mobile robot based on wireless sensor network[J].iJOE,2016,12(11):10-15.

[35] 常 建，吴成东，李 斌.移动机器人避障方法综述[J].仪器仪表学报，2010,31(8):439-442.

[36] Antonio S,Renato Z.Planning and obstacle avoidance in mobile robotics[J].Robotics and Autonomous Systems,2012,60:628-638.

[37] 张玉婷，邹彤雯，王艳丽,等.自主移动机器人避障算法研究及展望[J].黑龙江科学,2013,4(7):59-61.

[38] 杨 兴.室内自主导航移动机器人路径规划研究[D].太原：中北大学,2016.