未知环境中移动机器人的路径规划与探索算法

高 扬，邹 丹，胡大伟，王来军，杨京帅

（1.长安大学 汽车学院,陕西 西安 710064；2.西北工业大学 明德学院,陕西 西安 710072）

未知环境中移动机器人的路径规划与探索算法

高 扬1，邹 丹2，胡大伟1，王来军1，杨京帅1

（1.长安大学 汽车学院,陕西 西安 710064；2.西北工业大学 明德学院,陕西 西安 710072）

未知环境中移动机器人如何快速到达目标，如何尽量获取环境信息以绘制地图，是常见问题，也是难点问题。针对此二问题，论文综述了路径规划、探索算法领域的相关研究成果，指出了它们的特点与不足。最后对路径规划、探索算法的发展趋势进行了展望。

移动机器人;局部路径规划;自由路径;盲区

移动机器人是一种在复杂环境下工作的具有自规划、自组织、自适应能力的机器人，无需外部干预即能自主移动至目标以完成任务。自第一个移动机器人Shakey用于人工智能研究以来，在国防、航天、消防、工业、交通、科研等众多领域，移动机器人受到广泛关注与应用，其应用环境也由陆地延伸到了空间、水下等领域。正是源于其广阔的市场前景，移动机器人技术的发展也备受各国重视。各发达国家、地区围绕不同领域的移动机器人技术均各有侧重，例如美国主要侧重于对各种室外移动机器人的研究，日韩等国则主要侧重于人形机器人方面的研究，欧洲地区这侧重于城市、建筑环境中的移动机器人研究。

现实中移动机器人通常需工作于未知环境，即：无预知环境信息，也无额外定位信息来源的环境。此类未知环境中移动机器人如何以某种指标最优的方式到达目标，是制约其走向实用的一大难点问题。与此同时，路径规划等多种上层任务往往依赖环境地图，如何尽可能的获取环境信息以绘制地图是制约移动机器人发展的另一问题。目前，在实际应用时多使移动机器人先以其他方式引导(例如人为介入)实现对环境的绘图，待绘成地图后再进行路径规划、自主移动并完成任务。有鉴于此种模式需要额外的绘图工作准备，近年来也有学者提出一类探索算法, 该类算法部分采用路径规划思想，以实现自主绘制地图为目标，寻找最有利于绘图的机器

人移动路径。因此后文将分别介绍路径规划算法及探索算法。

1 路径规划

移动机器人技术日益受到各国重视，围绕不同领域各国、各地区均各有侧重(如表1所示)[1]。自从1968年Nilsson利用启发式搜索算法为机器人寻找一条无碰、最短路径开始，路径规划技术已成为机器人学领域的研究热点。依据所用信息层次不同，现有路径规划算法可分成全局式、局部式和复合式3大类。

表1 世界主要国家、地区的移动机器人技术研究特点Tab.1 Character of the research of robotic in the world

1）全局路径规划

全局路径规划利用预知的全局环境信息，可在事先建好的环境模型中寻优，以获得全局范围内的最优路径。作为较早提出的方法，全局路径规划可以保证路径的可达性及最优性。进一步，此类方法可分解为两大部分：对构型空间的描述方法，以及在构型空间中搜寻最优路径的搜索算法[2]。典型方法中前者主要有：可视图(VisibilltyGraph)、Voronoi图、栅格图、顶点图(Vertex graph)、拓扑图等。后者则主要包括：图搜索类算法(从起始点出发向目标点搜索的算法)，如各种贪心算法、Dijkstra 算法、以A*为代表的各种启发式搜索算法、可以在动态图上搜索到最短路径的D*算法(改良Dijkstra 算法)、D* Lite算法等[3]；各种随机采样类算法；在各种可行单元间搜索最优组合的单元分解法；一些智能算法如神经网络、遗传算法、蚁群算法、粒子群算法等。

可以看出：全局路径规划依赖准确的全局环境模型，一旦环境信息发生变化则需重新规划，难以适应频繁变化的地图。虽然有学者针对此问题，提出一系列对全局路径进行局部修订的算法[4]，但对地图变化范围较大的未知环境仍然难以适应。此外，由于算法通常运算量较大需离线运行，也难以对地图及机器人感知信息的变化及时反应。

2）局部路径规划

局部路径规划通常并不规划一条完整的路径，而是规划机器人的最优运动，建立机器人运动与感知信息间的映射关系，将局部范围内的最优路径信息隐含在对机器人运动的控制命令中，力图通过连续的局部最优实现全局优化。此类方法通常是在线使用的反应式算法，仅依赖传感器所得局部环境感知信息，常用算法有：人工势场法、模糊控制方法、矢量场图类方法(VFH)、神经网络法、动态窗口法、bug算法等[5]。

由于对环境信息依赖较小，此类方法对未知环境表现出较强的适应能力，已有针对未知环境中路径规划问题的研究也多集中于此类方法。然而由于缺乏对全局信息的利用，形成了只顾眼前的短视机制，导致局部路径规划通常不能保证到达目标，也不能保证获得全局最优路径，有可能陷入死区、局部最小等问题。

3）复合路径规划

近年来有学者将前两类方法取长补短加以结合，提出一类复合式路径规划方法。此类方法利用全局路径规划保证全局范围的最优性与可达性，利用局部路径规划在线运行提供对局部环境的适应能力，因而兼具两者的优点。已有研究包括：Zhuoning Dong 等人利用A*算法与势场法结合提出一种复合式路径规划算法[6]；Urdiales C等人认为在未知环境中，应充分利用局部路径规划的高适应性与鲁棒性，只需使其在总体上保持与全局路径一致即可，并提出一种基于子目标的复合式路径规划算法[7]；Shuzhi Sam Ge等人在路径跟踪行为与障碍物边缘跟踪行为间依情况不同而切换，并以此提出一种复合式规划方法[8];Xiaoyu Yang等利用模糊控制器选取子目标点，以引导局部路径规划[9]; Wooden D等人将机器人路径规划划分为上下两层：上层负责全局的任务，下层负责应对局部环境[10]。

由于同时利用了全局、局部环境信息，已有复合式路径规划算法表现出一定优势，但仍然存在不足，例如：全局层规划仍采用传统全局路径规划算法，并未考虑到SLAM技术绘制所得增量式地图带来的影响；全局路径规划庞大的运算量仍然会影响到复合路径规划的效率；全局规划与局部规划分别进行，未考虑到两层规划方法间的相互影响，且使得两种规划结果的融合存在一定困难。

2 未知环境中的探索算法

探索算法主要研究如何利用已有信息选择下一步移动目标，或者规划下一运动以使机器人移动至未知区域，获得更多环境信息，以便绘制环境地图。早期的探索算法主要采用随机行走以及沿墙行走等简单策略。现有研究多将探索算法归结为三类：未知区域驱动类算法、基于Next Best View(NBV)的探索算法、基于路径规划的探索算法。

未知区域驱动算法利用感知信息，识别未知区域，并引导机器人向该区域移动。典型如基于边界的探索算法，识别未知区域与已知区域间的边界，并引导机器人向最近边界移动，从而获取新的环境信息，扩大地图范围。

NBV源于机器视觉领域，表示下一步的最佳视野。基于NBV的探索算法对下一步的候选视点定义性能函数，根据当前已获取信息及性能函数选择下一步的最佳视点使机器人具有最佳的感知信息，从而利用最佳视点引导机器人对未知环境的探索行为。对此类算法的研究主要集中于候选视点的生成方法以及性能函数的构建两方面。

其中最佳视点的生成可以分为3种[11],分别是前沿(Frontier)理论，随机算法和这两种方法的混合算法。前沿理论总是倾向于将候选位置设在已探测区域和未探测区域的边界上。此类方法容易给机器人获得较大的信息收益，然而也正因此使其容易增加定位困难，降低机器人定位精度。随机算法在一定范围内随机生成视点，再进行筛选。此类方法应用简单，然而难以平衡计算量与后续的搜索最优视点效果。对性能函数的构建一般则考虑信息收益、路径成本和定位的不确定性，构建各种效用函数。

基于路径规划的探索算法则主要从已有路径规划算法出发，以路径覆盖的区域面积最大为目标进行路径规划。例如基于栅格地图的harmonic function方法，基于RRT路径规划的方法等[12]。

3 结束语

作为移动机器人技术的核心，路径规划算法与探索算法事实上存在某种相似性。两者的目标均为路径，但规划路径的目标有所不同，且探索算法也部分借鉴了路径规划的研究成果。路径规划方面，如何在保证可达性的同时减少计算量，提高规划速度，提高对动态环境的适应能力，是其重点发展方向。此外，如何在三维环境中提高规划能力，减少对环境信息的依赖也将是其一大发展方向。探索算法方面，如何以某种指标最优的方式引导机器人移动，使其绘制全局地图将始终是其主要研究方向。

事实上，路径规划，定位，地图绘制作为移动机器人三大核心技术存在相互依赖的特性。未知环境中，机器人的定位必须依赖环境地图，而对地图的绘制又反过来依赖于机器人定位结果，因此定位与绘图间相互依赖，互相影响。其次，机器人欲实现以某种指标最优的方式到达目标，需进行路径规划结果，而各种路径规划算法又不同程度依赖于环境地图与定位信息。反之，地图的绘制要求机器人必须在移动中感知环境，而机器人的移动却又受控于路径规划或探索算法的结果。因此绘图、定位与路径规划间相互依赖。从影响来看：一方面，定位精度、绘图效果直接影响到路径规划效果；另一方面，已知路径规划结果有助于定位时降低搜索范围，提高精度，并进一步改善绘图效果。因此未知环境中，定位、地图绘制与路径规划间互相依赖，互相影响。如何进一步利用三者间相互依赖的特性可能是未来进一步需要考虑的课题。

[1] Fox D. International assessment of research and development in robotics[R].Arlington,VA,USA:World Technology Evaluation Center,2006.

[2] Sariff N, Buniyamin N. An overview of autonomous mobile robot path planning algorithms:4th Student Conference on Research and Development ＂Towards Enhancing Research Excellence in the Region＂.2006[C]. Shah Alam, Malaysia:IEEE,2006:183-188.

[3] Sun X, Yeoh W, Koenig S. Moving Target D* Lite:International Joint Conference on Autonomous Agents and Multiagent Systems(AAMAS).2010[C]. 2010:67-74.

[4] Nasrollahy AZ, Javadi H. Using Particle Swarm Optimization for Robot Path Planning in Dynamic Environments with Moving Obstacles and Target:UKSim 3rd European Modelling Symposium on Computer Modelling and Simulation.2009[C].Athens, Greece:IEEE,2009:60-65.

[5] Yang G, Shu-dong S. Local Path Planning of Mobile Robots in Dynamic Unknown Environment Based on Prediction of Collision:International Conference on Measuring Technology and Mechatronics Automation.2009[C].Zhangjiajie, Hunan, China: IEEE Computer Society,2009:84-88.

[6] D Z, C Z, Z R, Z R. A hybrid approach of virtual force and A*search algorithm for UAV path replanning:IEEE Conference on Industrial Electronics and Applications (ICIEA).2011[C].Beijing: IEEE, 2011:1140-1145.

[7] Urdiales C,Perez EJ,Sandoval F,Vazquez-Salceda J.A hybrid architecture for autonomous navigation using a CBR reactive layer:IEEE/WIC International Conference on IntelligentAgent Technology.2003[C].Banff,Canada:Int. Assoc. of Science and Technology for Development,2003:225-232.

[8] Ge SS, Lai X-C, Al Mamun A. Sensor-based path planning for nonholonomic mobile robots subject to dynamic constraints[J].Robotics and Autonomous Systems,2007,55(7):513-526.

[9] Xiaoyu Y, Moallem M, Patel RV. A layered goal-oriented fuzzy motion planning strategy for mobile robot navigation[J].IEEE Transactions on Systems,Man, and Cybernetics,Part B:Cybernetics,2005,35(6):1214-1224.

[10] Wooden D, Powers M, MacKenzie DC, Balch T, Egerstedt M.Control-driven mapping and planning:2007 IEEE/RSJ International Conference on Intelligent Robots and Systems,IROS 2007.2007[C].San Diego,CA,USA:IEEE,2007:3056-3061.

[11] 王立.机器人室内未知环境探测规划研究[D].杭州: 浙江大学, 2010.

[12] Julia M, Gil A, Reinoso O. A comparison of path planning strategies for autonomous exploration and mapping of unknown environments[J].Autonomous Robots,2012,33(4): 427-444.

Path planning of mobile robots in unknown environment

GAO Yang1, ZOU Dan2, HU Da-wei1, WANG Lai-jun1, YANG Jing-shuai1
（1. School of Automobile, Chang An University, Xi’an 710064, China; 2. Ming De College, Northwestern Polytechnical University, Xi’an 710072, China）

Either to reach the destination or mapping the environment quickly in unknown environment is a hard and common problem for a mobile robot. Thus this paper proposed an overview to the path planning and discovery algorithms which are designed for that two problem separately. Finally the trends of them are described.

mobile robot; local path planning; free load; discovery

TN83

A

1674-6236(2014)03-0001-03

2013–05–20 稿件编号：201305214

中央高校基金(CHD2011JC176,HD2011JC105);国家自然科学基金(51108040);博士后基金(2013M531999)

高 扬(1982—)，男，陕西西安人，博士，讲师。研究方向：计算机控制，机器人技术，物流工程技术。