移动机器人路径规划技术研究

移动机器人路径规划技术研究

摘要: 研究移动机器人路径规划问题。针对传统移动机器人路径规划算法搜索时间长, 效率低, 寻优能力差等问题, 提出了一种基于粒子群算法的机器人路径规划方法。该方法首先采用神经网络描述机器人工作环境,在此基础上通过坐标变换建立新地图; 然后将机器人路径表示为粒子位置, 并以路径长度为粒子群的适应度值; 最后粒子之间的相互协作, 不断更新粒子位置和速度, 获得一条从起始点到目标点全局最优路径。在 MATLAB平台上对该方法进行了仿真, 实验结果表明, 基于粒子群的机器人路径规划方法提高了路径规划的计算效率和可靠性, 可应用于机器人的实时导航。 关键词: 移动机器人; 粒子群算法; 路径规划

0 引言

移动机器人是集环境感知、动态决策、行为控制与执行的多功能于一体的综合性系统 ,目前广泛应用于航空航天、军事侦查、安全医疗和家庭服务等行业. 移动机器人的研究涉及到许多领域 ,包括光学、机械、微电子、自动控制和人工智能等,由于其作业环境的复杂性 ,决定了路径规划技术在移动机器人研究中的重要地位. 本文系统的阐述了移动机器人路径规划技术的研究现状和发展趋势

1 路径规划

路径规划是移动机器人研究领域的核心问题之一。所谓路径规划是指移动机器人在有障碍物的工作环境中, 搜索一条从起始状态到目标状态的最优或次最优路径, 使机器人在运动过程中能无碰撞地、安全绕过所有的障碍物, 同时所经过的路径较短。移动机器人路径规划方法可以分为全局路径规划和局部路径规划两种, 全局路径规划方法通常可以找到最优解,

但首先需要知道准确的全局环境信息。到目前为止, 针对全局路径规划问题, 国内外学者对其进行了大量的研究, 并相应产生了许多方法。传统的路径规划算法有人工势场法和可视图法等。人工势场法的基本思想

是将机器人看成处于一个虚拟力场中的“点”, 规划目标点对机器人有吸引力, 机器人对障碍物有排斥力, 在吸引力和排斥力的合力决定机器人运动方向。该方法具有实时性好、计算量小的特点, 但由于在规划过程中存在陷阱区, 很容易导致规划失败。可视图算法的基本思想是首先根据障碍物几何特征将工作空间中的可行区域映射为一个加权图, 然后利用图搜索策略在这个空间进行搜索, 根据图搜索算法的完备性理论, 完全能够规划出最优路径, 但由于图搜索算法比较复杂,可视图算法有潜在的组合爆炸危险。因此, 这些方法自身都存在一定的缺陷, 使得路径搜索出现计算量过大、效率不高、寻优能力差等难题, 不能满足路径规划的计算效率和可靠性要求。近年来, 出现了一些启发式路径规划算法如遗传算法和神经网络算法, 并得到了广泛的应用。但是遗传算法和神经网络法都存在局部最优的缺点, 导致寻优的路径质量不可靠。为了提高了移动机器人路径规划性能, 进一步丰富路径规划的方法, 需要不断的引入新的算法。粒子群优化算法 ( particle swarm optimization algorithm, PSO)是一种模拟鸟群时示的仿生算法, 具有算法简

洁、易于实现和鲁棒性好等优点, 对种群大小不敏感, 收敛速度快, 非常适合于实时性要求较高、复杂的移动机器人路径规划求解问题。针对当前移动机器人路径规划求解问题中存在的一些问题, 将粒子群算法引入到路径规划中, 提出一种新的移动机器人路径规划算法。该方法将路径规划分为两步, 首先用自由空间法建立规划环境模型, 间的线段不穿过障碍物 ,即称直线是可视的 ,如此生成的图称之为可视图. 由于可视图中所有线段均“可视”,所以搜索最优路径的问题就转化为通过这些“可视”的线段从起始点到目标点最短距离的问题 ,还可以通过优化算法来删除一些不必要线段以简化视图 ,提高搜索效率. 用可视图法对移动机器人进行路径规划 ,由于忽略了用图论方法寻求一条无碰次优路径, 然后用粒子群算法优化次优路径, 得全局最优路径。

2 全局路径规划

全局路径规划 ,又称为静态或离线路径规划 ,作业的环境信息完全已知 ,主要方法有:栅格法、可视图法、链接图法、概率路径图法、拓扑法等. 2. 1 栅格法

栅格法是由 W. E. Hovcden 在 1968 年提出的. 栅格法将机器人的工作空间分解成一系列具有二值信息的网格单元 ,多数情况下采用四叉树或八叉树来表示 ,通过启发式优化算法搜索安全路径. 在栅格法中 ,栅格大小的选取将直接影响算法的性能. 栅格选的小 ,环境的分辨率就高 ,在密集障碍物或狭窄通道中发现路径的能力强 ,但环境信息的储存量大 ,规划时间长 ,降低了系统的实时性;栅格选的大了 ,环境信息储存量小,决策速度快 ,抗干扰能力强 ,但环境的分辨率低 ,在相应环境中发现路径的能力变差. 一般来说选定的栅格大小通常与机器人的移动步长相适应. 栅格法用栅格记录规划空间信息 ,其一致性和规范性使得空间中邻接关系简单化 ,在赋予环境中每个栅格一个通行因子后 ,路径规划问题就变成寻求两个栅格间最优路径问题. 常用的启发式搜索算法有 A 3 算法和 D 3 算法. 2. 2 可视图法

可视图法的基本思想是将机器人视为一点 ,然后把机器人起始点、目标点和多边形障碍物的所有顶点用线段进行组合连接. 如果起始点与障碍物顶点之间、目标点与障碍物顶点之间以及障碍物与障碍物顶点之

机器人尺寸 ,易造成机器人通过障碍物时与障碍物的摩擦甚至碰撞,且该方法缺乏灵活性,不能解决障碍物为圆形的路径规划问题 ,也不适用于三维及以上空间. 2. 3 链接图法

链接图法用于移动机器人的路径规划基于以下两点假设:(1)移动机器人可视为在二维平面中运动 ,机器人用点来表示;(2)规划环境的边界及障碍物可用凸多边形描述.链接图的构造方法是:

1)依次连接所有障碍物顶点 ,做不与障碍物交叉的链接线 ,并删除一些没有必要的链接线 ,保证链接线与障碍物边界所围的每个自由空间是面积最大的凸边形.

2)设置各链接线的中点为可能的路径点 ,并将机器人的起始点和目标点链接到所有可能的路径点上.用链接图法进行路径规划具有灵活多变的特点 ,起始点和目标点的改变不容易造成连通图的重构;算法 的复杂程度与障碍物的数量成正比 ,而且并不是在任何情况下都能获得最短路径. 2. 4 概率路径图法

概率路径图法(PRM)是 90 年代初期由 M. H. Overmars , P. Svestka 等人提出 ,该算法通过在构型空间中随机采样构建 Roadmap 图 ,然后通过查询得到移动机器人的路径规划序列. PRM 算法的 Roadmap 图是以某种概率技术来构造的 ,这跟以前的 Roadmap 图方法以确定方式构造的形式有很大的不同. 算法通过在构型空间中进行采样 ,对采样点进行碰撞检测 ,测试相邻采样点是否连接来表示路径图的连通性. PRM 算法的一个巨大优势在于:其复杂程度主要取决于路径搜索的难度 ,而跟整个规划空间的维数和大小无关. 然而当规划的路径需要经过密集的障碍物或者需要经过

狭窄的通道时 ,传统的 PRM 方法的效率变的低下 ,后来提出了一种采用分阶段混合采样策略的改进的 PRM 法 ,有效的解决了这一问题. 2. 5 拓扑法

拓扑法是由清华大学研究者提出的一种路径规划算法. 其基本思想是先将规划空间分为自由空间、半自由空间和障碍空间的子空间 ,然后搜索每个子空间及与其相连的子空间 ,计算彼此之间的连通性 ,如此则建立了拓扑网络. 路径规划是在拓扑网络上搜索从起始点到目标点的最短的路径 ,即判断拓扑网络的连通性 ,从而大大减小了高维空间路径规划的难度. 用拓扑法进行路径规划 ,一般不需要移动机器人的准确位置 ,这对于机器人移动过程中产生的位姿误差有很好的包容能力 ,但建立拓扑网略的过程非常复杂 ,特别是当空间中障碍物发生改变时 ,拓扑网的重构问题有待解决.

3 局部路径规划

局部路径规划 ,又称为动态或在线路径规划 ,作业环境部分未知或完全未知 ,主要方法有:人工势场法、模糊逻辑算法、遗传算法、蚁群算法、免疫算法等. 3. 1 人工势场法

人工势场法[10]是由 Khatib 和 Krogh 提出的一种虚拟力场法. 它的基本思想是将移动机器人所处的空间虚拟称一个存在力的场地 ,并且把这种力分为引力和斥力 ,移动机器人所受的引力是由目标点产生的 ,随距离的增大而减小 ,斥力是由障碍物产生的 ,并随距离的减小而增大 ,整个势场是引力和斥力的矢量叠加. 机器人沿着“势峰”间的“势谷”前进 ,从而绕过障碍物到达目标点. 人工势场法结构简单 ,便于底层的实时控制 ,且无需大量的计算 ,自动生成较光滑的路径 ,在实时避障和平滑轨迹控制方面得到了广泛的应用 ,但也存在着以下几个方面的缺陷:存在陷阱区域;通过狭窄通道时摆动;在障碍物前震荡;动态环境适应性差;求出的路径可能不是最优路径. 为了克服上述缺陷 ,已经研

究出了一些改进方法 ,如重新定义势函数 ,减少或使之没有局部极小点;在局部极小点处引入一个“填平势场”来引导移动机器人走出局部极小点;还可以利用如模拟退火法、遗传算法、粒子群算法等搜索算法跳出局部极小点 .

3. 2 模糊逻辑算法

模糊逻辑算法是根据经验 ,通过查表来得到规划信息 ,实现局部路径规划. 由于模糊逻辑算法基于实施传感信息 ,在处理动态变化或者未知环境下的路径规划问题显示出巨大的优越性 ,具有较好的实时性 ,且克服了势场法容易产生局部极小值的问题 ,避开了传统算法中对环境信息依赖强的缺点 ,但对于模糊隶属函数以及模糊控制规则的设计 ,目前还没有系统的理论方法 ,主要靠经验 ,因此隶属函数和控制规则的设计成为实现模糊逻辑算法的关键.

3. 3 遗传算法

遗传算法是一种基于自然选择和群体遗传机理的搜索算法 ,它基于达尔文“物竞天择 ,适者生存”的进化原理 ,模拟了自然界的生存法则. 遗传算法是一种全局优化算法 ,其算法流程是:首先初始化路径种群 ,将路径个体表述为路径上一系列的点 ,并进行参数编码;然后对参数编码的字符串采用抽象出来的几个算子进行选择、复制、交叉、变异遗传操作;经过特定进化次数或者达到优化目标即停止进化 ,输出当前优的个体.遗传算法主要的优点是:

1)遗传算法是一种多线程的搜索算法 ,可同时对多个可行解进行遗传操作 ,从而产生新的可行解 ,一定程度上避免了陷入局部极小点.

2)整体搜索策略和优化计算不依赖于梯度信息 ,只需可行解目标函数的值 ,因而解决了一些其他优化算法无法解决的问题 ,避免了复杂的理论推导.遗传算法是一种多线程的搜索算法 ,可同时对多个可行解进行遗传操作. 文献[17]给出了一种基于粗糙集约简决策规则和删除冗余属性的方法 ,大大减小了遗传算法初始种群的规模 ,提高了规划效率.

3. 4 蚁群算法

蚁群算法是 20 世纪 90 年代意大利学者 M. Dorigo , V. Maniezzo , A. colorni 从生物进化的机制中受到启发 ,通过模拟自然界中蚂蚁搜索路径的行为而提出的. 其原理可表述为:蚂蚁在觅食途中会留下一种外激素 ,蚂蚁利用外激素与其他蚂蚁进行交流和合作. 经过某条路径的蚂蚁越多 ,外激素的强度就会越大 ,而蚂蚁择路偏向选择外激素强度大的路径. 蚁群算法的提出 ,最初是为了求解旅行商问题 ,近些年的研究发现 ,蚁群算法在求解复杂优化问题时具有优势 ,是一种新型的无启发式优化算法 ,具有较强的发现路径的能力.蚁群算法可使规划出的路径具有较强的鲁棒性 ,它是一种基于种群的分布式进化算法 ,具有并行性 ,易与其他启发式算法结合 ,从而改善算法的性能 ,但蚁群算法的研究刚刚起步 ,没有系统的分析方法和坚实的数学基础 ,参数的选择多靠试验和经验 ,计算时间长 ,实时性差 ,有待进一步的研究. 3. 5 人工免疫算法

人工免疫算法是模仿自然界生物免疫系统的一种仿生智能算法 ,是通过学习生物免疫系统的功能、原理及特征并结合相关计算方法和理论而提出的. 目前的免疫算法都是根据特定的问题提出的 ,Ishiguro 提出了一种互联耦合人工免疫网络模型 ,由此开创了免疫算法应用于移动机器人路径规划的新领域. 由于进化方法通常存在“早熟收敛”和“收敛速度慢”等问题 ,后来应用基于免疫进化非选择机制进行移动机器人的路径规划 ,在进化过程中避免了糟糕个体的产生 ,加快算法的收敛速度 ,同时也能在进化过程中通过随机加入路径来维持群体的多样性 ,防止早熟收敛.

4 移动机器人路径规划技术未来展望 随着计算机、传感器技术以及人工智能的发展 ,路径规划技术已取得大量的成果. 相比之下 ,全局路径规划的研究已经比较成熟 ,动态路径规划的研究还在发展阶段 ,很多理论与方法还需要在今后的研究中不断的完善. 从目前的研究动向来看 ,路径

规划技术有以下发展趋势:

1)路径规划的性能指标要求的提高. 这些性能指标包括实时性、安全性、可达性、鲁棒性等. 评价一种路径规划方法的好坏应当通盘权衡几种指标]. 一种好的路径规划方法既要能规划出好的路径 ,又要能达到移动机器人系统实时性的要求 ,还要保证由于动态环境的不确定性、传感器采集信息的不完整性或者移动机器人自身结构的限制和缺陷等因素所带来的干扰下的安全性和鲁棒性. 因此 ,如何使路径规划的性能指标达到更好是目前算法研究的一个重要课题.

2)传统的路径规划方法与智能算法的交叉融合. 新的智能算法如模糊控制、遗传算法、神经网络逐渐引入到路径规划中来 ,促使了各种方法的融合发展 ,各种方法取长补短 ,催生一些更优秀的算法. 因此如何把各种方法的优点融合到一起以达到更好的效果亦是一个有待探讨的问题.

3) 基于功能行为的路径规划方法. 传统的基于认知环境模型的功能规划方法必须建立在精确环境地图模型的基础上 ,难以适应动态多变环境中的路径规划 ,缺乏自主性和灵活性. 近年来发展起来的基于反应式行为的方法是一种从感知到动作的直接映射 ,类似于人的膝跳反射 ,提高了机器人对环境变化的适应力和反应速度 ,但缺乏必要的理性.后来提出的基于功能行为的方法实现了以上两类方法的优势互补 ,既提高了移动机器人的反应速度 ,又使其具有较高的理性和学习能力.

4)多传感器集成与信息融合技术. 移动机器人在未知或动态环境中进行路径规划所需要的信息都是由传感器检测得到的. 由于单个传感器采样精度和范围有限 ,难以保证检测信息的完整、可靠 ,不足以决策其行为 ,于是多传感器集成和信息融合技术在移动机器人路径规划上得了广泛的应用. 多传感器所获得的信息具有冗余性、互补性、实时性和低代价性 ,可以快速并行分析现场环境. 信息融合技术通过一定的技术手段 ,总结融合了多传感器数据资源 ,使决策系统得到更全面的信息 ,获得对环

境的正确理解. 多传感器集成与信息融合技术的发展和应用大大提高了机器人对环境的理解程度 ,增强了移动机器人路径规划的可靠性和鲁棒性.

5)多移动机器人路径规划. 随着机器人工作范围的不断扩大和工作任务越来越复杂 ,单个机器人很难完成人们所规定的任务 ,这就需要多个机器人之间进行合作和协调 ,既提高了机器人工作的效率 ,又可以解决因工作环境发生变化或机器人系统局部出现故障时所造成的工作停滞 ,这些都显示了开展多机器人系统以及多机器人路径规划研究工作的必要性. 多机器人路径规划比单个机器人路径规划要复杂的多 ,从目前国内外研究的现状来看 ,规划多机器人路径需要更多考虑机器人之间的协调和合作式的路径规划。

5 结论

移动机器人的全局路径规划和局部路径规划并没有本质上的区别 ,很多方法既适用于全局规划又可用于局部规划. 无论采用哪种方法进行路径规划 ,基本上都要遵循以下两步:(1)环境建模;(2)搜索路径. 随着空间探测和无人战争的发展需要 ,移动机器人的研究也越来越注重于在崎岖地形和存在大量障碍物的复杂环境中自主导航 ,为了满足这种要求 ,路径规划技术将会向着高维自由度机器人、多机器人协调、动态未知环境中的规划发展,这些都有待于进一步深入的探索和研究.

参考文献:

[1] 方建军 ,何广平.智能机器人[M].北京 :

化学工业出版社 ,2004.

[2] 张捍东 ,郑睿 ,岑豫皖.移动机器人路径

规划技术的现状与展望[J ].系统仿真学报 ,2005(2).

[3] 李磊,叶涛,谭民,等.移动机器人技术研究

现状与未来[J].机器人 ,2002 ,24(5). [4] 魏宁 ,刘一松.基于栅格模型的移动机器

人全局路径规划研究[J].微计算机信息 ,2008 ,24(11).

[6] 杨淮清 ,肖兴贵 ,姚栋.一种基于可视图

法的机器人全局路径规划算法[J].沈阳工业大学学报 ,2009 (2) :2252229.

[7] 陈家照 ,张中位 ,徐福后.改进的概率路

径图法[J].计算机工程与应用 ,2009(10).

[8] 陈阳舟 ,崔平远 ,居鹤华.基于扫描法在

线构造拓扑图的路经规划算法[J].计算机仿真 ,2006 (4)

[9] 肖本贤 ,余雷 ,李善寿 ,等.逃逸人工势

场法局部极小值策略的研究[J].系统仿真学报 ,2007 (19).

[10] 张建英 ,赵志萍 ,刘暾.基于人工势场

法的机器人路径规划[J].哈尔滨工业大学学报 ,2006 (8).

[11] 卢瑾.基于遗传算法的机器人路径规划

研究[D].杭州 :浙江工业大学 ,2006. [12] 肖晓明 ,陈志兴 ,高平安.动态确定基

因数的遗传算法路径规划[J].计算机应用研究 ,2009 (7).

[13] 王杰 ,周永年 ,刘金锋.提高移动机器

人路径规划效率的方法[J].计算机工程与应用 ,2009 (20) .

本文来源：https://www.bwwdw.com/article/u6sm.html