自主移动机器人路径规划方法研究综述

皇甫淑云 唐守锋 童紫原

摘要：自主移动机器人路径规划问题是智能控制和机器人学研究的核心内容之一。系统分析了当前移动机器人路径规划方法的主要研究成果。对移动机器人路径规划模型进行描述，介绍了人工势场法等传统方法，阐述遗传算法等智能算法，讨论了算法融合问题，对移动机器人路径规划的发展趋势进行了展望。

关键词：路径规划；传统规划；智能规划；算法融合；移动机器人

DOIDOI：10.11907/rjdk.181628

中图分类号：TP301

文献标识码：A 文章编号：1672-7800（2018）010-0001-05

英文摘要Abstract：The path planning problem of autonomous mobile robots is one of the core contents of intelligent control and robotics research， and it is a global research hotspot in recent years. This paper systematically summarizes the main research results of the current mobile robot path planning methods， which are mainly divided into two categories： traditional methods and intelligent methods. Firstly， the path planning model of mobile robot is described. Secondly， the traditional methods such as the artificial potential field method are introduced. The intelligent algorithms such as genetic algorithms are summarized， and the fusion of the algorithms is also discussed. Finally， the development trend of path planning for mobile robots is predicted.

英文關键词Key Words：path planning；traditional planning；intelligent planning；deep integration；mobile robot

0 引言

机器人技术是现代科学理论与实践综合交叉的成果。20世纪60年代末，斯坦福研究院（SRI）研制了自主移动机器人，路径规划方法是其关键核心技术[1]。移动机器人路径规划技术，就是机器人在遵循一些优化指标（比如时间最短、路程最优和能耗最低等）前提下，在运行环境中规划出从起始点到目标点不发生碰撞的最优路径[2]。

移动机器人路径规划实质上是满足一定约束条件的优化问题，其算法设计过程具有复杂性、随机性、多目标性和多约束性等特点[3]。根据路径规划环境是否随时间变化，将移动机器人的路径规划分为动态规划和静态规划[4]。根据机器人路径规划的目标范围，又可分为全局路径规划和局部路径规划。本文在移动机器人路径规划模型基础上，将路径规划方法分为传统方法和智能方法，阐述各种方法的优缺点，讨论算法的深度融合问题，并对移动机器人路径规划发展趋势进行展望。

1 移动机器人路径规划模型

在移动机器人的二维或三维工作空间中，解决路径规划问题必须定义物体（包括障碍物和机器人）的几何模型[5]。路径规划问题最初研究的是二维空间（如地面机器人），根据能量守恒原理，利用二维空间的辐射热传导方程建模进行路径规划问题的求解[6]。

2.1.4 可视图法

可视图法（Visibility Graph ，VG）由Nilsson[11]于1968年提出，常用于多边形障碍物的工作环境。首先，将环境中多边形或不规则障碍物分解为多个矩形，机器人视为一个质点（忽略机器人大小和外形），然后将机器人起点和矩形组成的障碍物各顶点以及目标位置点用线段连接，连接的线段不能穿过矩形障碍物，最后得到所有的遍历路径，如图4所示。

利用可视图法构建环境地图简单方便，能够搜索到最短路径，适合障碍物较少且不发生改变的环境。当障碍物位置和个数发生变化时，就需要重新构建环境地图，且计算量随着障碍物个数的增加而变大。针对以上不足，学者提出了Voronoi图法[12]和切线图法[13]。

2.2 智能路径规划方法

近年来，路径规划问题在求解过程中变得复杂化，具有较强的随机性，仿生智能算法应运而生并取得了长足发展。

2.2.1 基于遗传算法的机器人路径规划

遗传算法（Genetic Algorithm ，GA）是模拟自然界生物进化提出的一种智能算法[14]。算法核心思想是模拟生物在自然环境中不断进化时，个体之间遗传、杂交、变异和自然选择等现象。遗传算法求解路径规划是将路段描述成一系列中途点，并将其转换为二进制串。首先将路径群体初始化，其次进行遗传操作（如选择、交叉、复制、变异），最后经过若干代进化后停止进化，根据规划要求完成解空间搜索，输出当前最优个体[15]，见图5。

遗传算法具有全局搜索能力强、鲁棒性好和操作简单等优点，但当算法编码较长时，会导致收敛速度慢、计算量大，故不适合求解复杂的路径规划问题。

2.2.2 基于人工神经网络算法的机器人路径规划

人工神经网络算法（Artificial Neural Network，ANN）在20世纪40年代后期出现 [16]。如图6所示，人工神经网络是一种非线性网络系统，模拟大脑中相互连接的神经元网络，具备并行性和分布式特点。该方法不仅用于路径规划，还应用于环境建模、传感器信息交互融合、机器人系统控制等领域[17]。

人工神经网络算法采取分布式计算，拥有较强的实时性和学习性。求解路径规划问题时，计算量少且收敛速度快，容易实现。但由于算法初期反馈信息不足，需要经过一段时间的权重调整才能得到理想的优化结果。

2.2.3 基于模糊逻辑法的机器人路径规划

模糊逻辑法（Fuzzy Logic， FL）采用反射机制模拟驾驶员的驾驶经验，利用不同类型的传感器感知障碍物和机器人状态，通过模糊规则控制机器人寻径速度和转向角度，从而实现局部路径规划。H Chang等[18]建立一个模糊推理模型解决机器人路径规划问题，具体步骤如图7所示。

利用模糊逻辑法进行机器人路径规划，可在动态环境中迅速规划出有效路径，即对环境有较强的适应性。但随着障碍物增多，该方法计算量也会增大，搜索效率变低。

2.3 算法融合与分析

如何将算法深度融合以提高避障效率，取得寻径的最佳效果，是当前移动机器人路径规划问题的重点。

2.3.1 传统方法结合

传统的栅格地图法、人工势场法、可视图法和拓扑图法等不适用于所有情况下的路径规划问题，每种算法都有局限性。根据传统方法特点，一些学者相继提出改进或派生算法，证明了在某些特定条件下算法的实用性，有效提高了路径规划效率。针对传统人工势场法局部极值问题和目标不可达问题，欧阳鑫玉等[19]先在斥力势场函数中增加最小安全距离，建立改进人工势场模型，然后采用栅格法对改进的人工势场法作辅助决策，使机器人尽快脱离局部极小值并成功到达目标点。

2.3.2 智能有效方法结合

随着三维空间对移动机器人的需求增加，传统方法的实时性降低，计算量加大，一系列智能有效规划算法被提出。例如，关于遗传算法与蚁群算法的路径规划问题，单独使用的情况较少，一般利用进化计算进行优化处理，再与其它算法结合完成路径规划任务。潘昕等[20]针对三维空间中水下潜航器（AUV）的全局路径规划存在时间较长、搜索效率低等问题，提出了一种基于遗传蚂蚁混合算法。王辉等[21]针对智能停车库自动导引运输车（AGV）存取路径规划问题，提出了一种基于粒子群遗传算法的自适应混合算法，具有较好的收敛性和较强的全局搜索能力。

2.3.3 传统方法与智能方法结合

人工智能系统的日益成熟推动了传统方法与智能方法的结合，如栅格法与遗传算法、粒子群算法等的融合，人工势场法与蚁群算法、遗传算法以及ANN等的融合。卢路秋[22]提出了基于多阶模糊系统人工势场路径规划方法，设计了冲突消解策略，减少了路径规划时间和长度。刘亮[23]提出了势场蚁群路径规划算法，初期引入势力场启发信息影响系数，降低蚁群搜索的随机性，增强势力场函数的引导作用，后期则相反。该方法避免了早熟现象，搜索时间短，精度较高。姜英杰等[24]利用栅格遗传算法对变电站巡检机器人进行全局路径规划。周文明等[25]针对移动机器人局部路径规划问题，改进势力场函数，引入神经网络模糊系统，使系统速度加快、鲁棒性好。 3 算法对比与分析

目前在移动机器人路径规划领域，传统方法由于简单实用仍是首选，但传统方法在路径优化及路径搜索方面尚待完善，比如基于采样的改进算法[26]（RRT*）。不同于其它传统方法，人工势场法在实时动态环境中易于实现，且规划效果良好，但容易出现目标不可达和局部极值问题。

人工智能技术应用于路径规划，克服了传统方法的不足。基于生物智能的路径规划方法不需建立复杂的环境模型，收敛稳定且为随机搜索，大大提高了寻优效率，比如遗传算法、蚁群算法和粒子群算法等自然启发法能用于复杂环境下的路径规划问题，但自然启发法计算代价高、耗时長。神经网络法是另一种智能算法，它模拟生物的神经结构处理信息，具有信息分布式存储和并行处理特点，但实时性一般。因此，为了取得最佳路径规划效果，以上方法通常相互结合，如传统算法、智能算法和混合算法等。移动机器人路径规划方法性能比较如表1所示。

4 移动机器人路径规划发展趋势

移动机器人路径规划研究已取得显著进展，但在某些领域仍具有一定的局限性，一些核心技术如工作环境建模、导航定位和故障检测等亟需开发。根据过去的研究情况和发展趋势，笔者认为未来自主移动机器人路径规划技术发展方向有以下几个方面：

（1）多机器人协调作业。对于复杂的环境，单个机器人路径规划技术已不能满足任务需求，使用多机器人移动具有良好的安全性、可靠性和协调性。

（2）硬件系统更新换代。随着科技的发展，使用高速度处理芯片（如ARM、DSP和FPGA等）将提高规划效率，大大节省路径规划计算和检测时间。

（3）多传感器信息融合技术。通过合理利用多个传感器采集、处理信息，提高机器人路径规划的鲁棒性和精准性。如空中无人机编队飞行、足球机器人比赛和水下机器人的合作搜救与观察等[27]。

（4）新的智能算法或混合算法。路径规划方法应拥有良好的实时性和响应速度，能够适合各种复杂场景。目前智能算法优于传统算法，具有自组织、自学习等优点，但单一的智能算法会有全局搜索能力不强、容易陷入局部最优解等不足。将多种智能算法有效结合可以取长补短，改善优化效果。探索新的智能算法是路径规划技术发展的方向之一。

（5）高维环境和复杂环境下的路径规划技术。将二维空间的大量路径规划方法推广到三维空间，但机器人在三维空间中的运动学和动力学约束及环境建模问题很复杂，部分算法难以扩展。

（6）不断提高衡量路径规划优劣的相关性能指标。这些性能指标由算法的实时性、准确性和可达性组成。移动机器人所处的环境是不断变化的，如果算法没有良好的实时性能，在遇到突然出现的障碍物时就会反应迟缓，无法完成避障。高效及准确性可使机器人快速准确到达目标点，减少搜索时间，提高路径规划算法效率。可达性是路径规划最基本的要求，如果通过算法搜索出的路径不具备可达性，则该路径毫无意义。

5 结语

路径规划技术是国内外学者的研究热点。本文在移动机器人路径规划模型基础上，将路径规划方法分为传统方法和智能方法，阐述了各种方法的优缺点，并讨论了算法的深度融合问题，比较了几种典型方法性能，最后展望了移动机器人路径规划发展趋势，以期为当前智能移动机器人路径规划技术的发展与研究提供参考。

参考文献：

[1] 鲍庆勇，李舜酩，沈峘，等.自主移动机器人局部路径规划综述[J].传感器与微系统，2009，28（9）：1-4.

[2] FRAZZOLI E， DAHLEH M A， FERON E. Real-time motion planning for agile autonomous vehicles[J]. American Control Conference，2001. Proceedings of the IEEE，2001，25（1）：43-49.

[3] SU W， MENG R， YU C. A study on soccer robot path planning with fuzzy artificial potential Field[J].International Conference on Computing， Control and Industrial Engineering. IEEE Computer Society， 2010，1（7）：386-390.

[4] 戴博，肖晓明，蔡自兴.移动机器人路径规划技术的研究现状与展望[J]. 控制工程，2005，12（3）：198-202.

[5] 成伟明，唐振民，赵春霞，等. 移动机器人路径规划中的图方法应用综述[J]. 工程图学学报，2008（4）：6-14.

[6] 康亮. 自主移动机器人运动规划的若干算法研究[D]. 南京：南京理工大学，2009.

[7] HE X， CHEN L. Path planning based on grid-potential fields[J]. International Conference on Computer Science and Software Engineering. IEEE，2008（2）：1114-1116.

[8] 赵晓东，鲍方. 清洁机器人路径规划算法研究综述[J]. 机电工程，2013，30（11）：1440-1444.

[9] SARIFF N， BUNIYAMIN N. An overview of autonomous mobile robot path planning algorithm[C].4th Student Conference on Research and Development， 2006：183-188.

[10] 徐晓东. 移动机器人几何—拓扑混合地图构建及定位研究[D]. 大连：大连理工大学，2005.

[11] 马丽莎. 基于数字高程模型栅格地图的移动机器人路径规划研究[D].杭州：浙江大学，2012.

[12] TAKAHASHI O， SCHILING R J. Motion planning in a plane using generalized Voronoi diagrams[J]. IEEE Transactions on Robotics & Automation，1989，5（2）：143-150.

[13] 吴天明.移动机器人导航技术现状与展望[J]. 河南科技，2014 （17）：132-133.

[14] 巩敦卫，朱美强，郭西进.一种新的基于混沌变异解决早熟收敛的遗传算法[J]. 控制与决策，2003，18（6）：686-689.

[15] 蔡漫漫.自主式移动机器人路径规划算法研究[D].青岛：青岛科技大学，2017.

[16] YE J. Tracking control of a nonholonomic mobile robot using compound cosine function neural networks[J]. Intelligent Service Robotics，2013，6（4）：191-198.

[17] 刘晓磊，蒋林，金祖飞，等.非结构化环境中基于栅格法环境建模的移动机器人路径规划[J].机床与液压，2016，44（17）：1-7.

[18] CHANG H， JIN T. Command fusion based fuzzy controller design for moving obstacle avoidance of mobile robot[M].Future Information Communication Technology and Application. Springer Netherlands，2013：905-913.

[19] 歐阳鑫玉，杨曙光.基于势场栅格法的移动机器人避障路径规划[J].控制工程，2014，21（1）：134-137.

[20] 潘昕，吴旭升，侯新国，等.基于遗传蚂蚁混合算法的AUV全局路径规划[J].华中科技大学学报：自然科学版，2017，45（5）：45-49.

[21] 王辉，朱龙彪，朱天成，等.基于粒子群遗传算法的泊车系统路径规划研究[J].工程设计学报，2016，23（2）：195-200.

[22] 卢路秋.基于模糊人工势场法的多移动机器人路径规划研究[D].天津：天津工业大学，2015.

[23] 刘亮.基于势场蚁群算法的移动机器人路径规划研究[D].南昌：南昌大学，2013.

[24] 姜英杰，吕学勤，段利伟.栅格遗传算法的变电站巡检机器人路径规划[J].科技与创新，2015（6）：12-14.

[25] 周文明，张崇巍.基于模糊神经网络势场法的机器人动态路径规划[J].微型机与应用，2011，30（11）：89-91.

[26] ELBANELBANHAWI M，SIMIC M. Sampling-based robot motion planning：a review[J]. IEEE Access，2014，2（1）：56-77.

[27] 朱大奇.移动机器人路径规划技术综述[J].控制与决策，2010，25（7）：961-967.

（责任编辑：杜能钢）