基于改进蚁群算法的移动机器人 路径规划研究

来源: 未知 作者:paper 发布时间: 2020-03-06 14:09
论文地区:中国 论文语言:中文 论文类型:工程管理
摘要 移动机器人的诞生,不仅能提高自动化行业生产效率,降低生产 成本,而且还可以替代人类去一些危险环境或者人类不可到达的区域 进行工作,极大地推动了社会发展进步。国内
摘要
移动机器人的诞生,不仅能提高自动化行业生产效率,降低生产 成本,而且还可以替代人类去一些危险环境或者人类不可到达的区域 进行工作,极大地推动了社会发展进步。国内外许多专家纷纷投入到 移动机器人的技术研宄中去,其中路径规划技术是研宄重点,是移动 机器人能够从起始位置准确无误走到工作位置并自主完成各种任务 的基础,多年来众多学者对此进行了大量研究并提出了相应的解决方 案,然而在复杂环境下路径规划依旧是一个难点,难以取得理想的效 果。
蚁群算法在解决全局寻优问题方面取得不错的效果,广泛应用于 各个领域,但是在复杂环境下蚁群算法路径规划容易出现收敛速度 慢,求得的解非最优的问题,为此分析问题的缘由进行改进优化。该 方法首先依据起始点和目标点位置信息选择全局有利区域增加其初 始信息素值,不均匀分配信息素初始值以提高前期蚂蚁搜索效率;接 着增加避障策略,避免蚂蚁搜索路径过程中盲目搜索产生大量交叉路 径并有效减少蚂蚁死锁数量;最后采用动态参数控制的伪随机转移策 略,提出优质蚂蚁信息素更新规则,自适应调整信息素挥发系数,提 高算法全局性,根据规划好的路径信息进行二次规划。实验结果表明 改进蚁群算法收敛速度明显加快,能够找出全局最优解,有效降低移 动机器人能耗损失。
基于二维平面路径规划的研究基础上,将三维立体空间划分为一 个个平面,再将每个平面栅格化,釆用信息素存储在路径节点的方式 替代原先存储在路径的方式,降低信息素存储空间,并以分层前进的
搜索方式展开三维空间路径规划研宄。针对三维环境复杂、地貌多变 的特点,增加避障策略,改进路径启发信息,构造新的启发函数,依 据起始点和目标点位置信息以及前进方向,不均匀分配路径节点信息 素初始值,提高前期蚂蚁搜索效率;每次迭代完成后依据优质蚂蚁更 新规则,拋弃未走到目标点的死锁蚂蚁,设定迭代阈值,当算法趋向 于收敛时自适应调整信息素挥发因子,避免算法陷入停滞状态。通过 实验对比分析说明该改进算法在三维环境下能够安全快速有效地寻 找到一条最优路径,不仅有效降低算法收敛次数,而且具有较高的全 局搜索能力。

目录
第1章绪论 1
U课题研宄背景与意义 1
1.2移动机器人研究现状 1
1.2.1国外移动机器人发展研宄现状 1
1.2.2国内移动机器人发展研究现状 2
1.2.3移动机器人的发展趋势 4
1.3路径规划一般步骤 5
1.3.1环境建模 5
1.3.2路径搜索 5
1.3.3路径平滑 5
1.4论文研宄内容与章节安排 5
第2章移动机器人路径规划 7
2.1移动机器人导航技术 7
2.2环境建模 9
2.3移动机器人路径规划方法 10
2.3.1传统路径规划算法 10
2.3.2智能路径规划算法 11
2.4移动机器人路径规划技术难点 12
2.5本章小结 13
第3章基于改进蚁群算法路径规划 14
3.1基本蚁群算法 14
3丄1基本原理 14
3丄2数学模型 15
3.2基于蚁群算法路径规划 16
3.2.1栅格法建立环境模型 16
3.2.2路径规划实现步骤 17
3.2.3实验与结果分析 18
3.3基本蚁群算法的改进思路 19
3.3.1基本蚁群算法缺陷分析 19
3.3.2基本蚁群算法改进途径 20
3.4改进蚁群算法路径规划 21
3.4.1初始信息素不均匀分布 21
3A2转移概率改进   21
3.4.3信息素更新规则 23
3.4.4二次路径规划 24
3.4.5改进蚁群算法路径规划实现步骤 24
3.5改进蚁群算法路径规划实验与结果分析 26
3.5.120mx20m仿真环境… 26
3.5.230mx30m 仿真环境   27
3.6本章小结 30
第4章三维环境下移动机器人路径规划   31
4.1三维环境下路径规划意义 31
4.2三维环境建模   31
4.3三维环境下移动机器人路径规划 32
4.3.1搜索模式 32
4.3.2信息素表示   32
4.3.3启发函数设计     33
4.3.4信息素更新规则 34
4.3.5初始信息素分布优化 34
4.4改进算法步骤   35
4.5实验与结果分析  36
第1章绪论
1.1课题研究背景与意义
随着机器人技术的快速发展,从原先只能执行单一重复动作的笨重机器人, 发展到具有一定人工智能并且能完成一系列复杂动作的轻巧智能型机器人,多年 来机器人在各行各业得到了广泛的应用,不仅能提高生产效率,降低生产成本, 而且还能替代人类去一些人类不可到达或者危险的区域进行工作,极大地推动了 社会发展进步[1】,尤其在如今的工业制造中人口红利逐渐消失,人力劳动成本不 断加大的趋势下,在一些重复操作技术含量低的岗位上机器人取代人类是必然的 趋势。如今随着信息化、工业化的不断融合,以机器人科技为代表的智能产业蓬 勃发展,也是各个国家科技创新的的重点发展领域。
移动机器人由于其能够移动,不局限于固定的一个工作地点,大大提高了机 器人工作效率,是使用最多的一类机器人,广泛应用于各个行业。路径规划技术 是移动机器人领域的关键技术,是其自主移动完成各种任务的保障,也是所有移 动机器人进行智能化应用研究的一切前提[2]。路径规划是指依据路径最短、时间 最优、能耗最低等一条指标或多条指标为移动机器人规划一条从指定点到任务点 的安全避障线路,在不同的应用场合,周围环境也不尽相同13],加上各种现场条 件限制的因素,并没有哪一种全能的路径规划算法适应于全部场合。如何快速高 效地规划一条安全路径是其完成任务的关键W。目前国内外对移动机器人路径规 划领域做了大量的研究并有了不错的成果,对不同的应用场合也提出了不同的解 决方案,但是在复杂环境下路径规划,至今仍然是难点,因此本文对此课题的研 宄,具有一定的理论研究意义和工程实用价值[5]。
1.2移动机器人研究现状 1.2.1国外移动机器人发展研究现状
国外很早就展开了对机器人的研宄,以美国为首率先制造出机器人应用到工 业生产中去[6】,之后整个欧美国家都在钻研机器人技术,发展十分迅速。1968 年,美国研制出了世界上首个移动机器人Shakeyt'结束了人为控制机器人进行 移动的时代,其能够感知周围环境,寻找路线行走,能够简单的自主导航定位, 为今后的移动机器人发展奠基了基础[8]。

图1-丨Shakey移动机器人 2003年美国成功发射的机遇号火星探测器,标志着人类在移动机器人技术 方面实现巨大突破,在科学发现和工程实施方面都取得了空前的成功,开启了伟 大的太空探索时代。2017年波士顿动力公司研发出双足机器人Handle,创造性 地提出将车轮和腿合二为一,从而同时具备二者的优势,双腿带轮可以快速行驶, 灵活度非常高⑼。垂直跳跃高达可达1.2米,可以轻易跳过障碍物。
1.2.2国内移动机器人发展研究现状
相对于其他发达国家来说,我国对移动机器人的技术研发较迟,初始研发阶 段甚至在某些关键领域技术一片空白,但是在国家大力扶持以及众多科研人员的 不懈努力下,移动机器人发展十分迅速,取得世界瞩目的成就,在某些领域甚至 己经挤进世界领先行列[1GUooo年我国第一个仿人形机器人“先行者”诞生问世, 可以进行简单操作并能够快速行走[n],尽管在技术层次同其他发达国家还有不小
的差距,但是仿人形机器人的研制成功使得在当时研究移动机器人领域的先进国
家中终于有了中国的一席之地。

2013年我国发射月球车“玉兔号”并成功登陆月球[12],配备一些先进的科 学探测仪器进行月球表面探测调查任务,在此之前成功发射并登陆的月球车只有 前苏联和美国两个国家。

2015年,在汇聚世界先进技术的美国消费电子展会上,阿尔法机器人二代 瞩目登场,如图1_6所示。相比于一代阿尔法机器人,二代阿尔法机器人具有更 好地人机交互体验和智能化,灵活多变可以完成许多复杂动作,配备下载多种 APP学习软件,并且具备自主分析与智能决策的功能。二代阿尔法机器人的研制 成功使机器人真正称为陪伴我们生活的亲密伙伴,它的成功也标志着我国智能移 动机器人的发展取得了重大的进步,技术性的突破。

1.2.3移动机器人的发展趋势
如今移动机器人在各个领域中发挥的作用越来越大,人们对其技术要求和性 能也越来越高,总结移动机器人的未来发展趋势如下:
1、 智能化和灵巧化。移动机器人技术近些年来取得了一次又一次的技术性 突破,再也不是原先笨重、呆板、反应迟钝的,而是朝着更加智能化人性化的方 向发展,这依赖于对周围环境感知、自然语言处理、人机交互、深度学习以及智 能决策等先进技术的应用,同时,随着机械加工精度的提高使得机器人硬件方面 更加灵活,之前一些笨重、庞大的移动机器人将转换成小巧体形[13]。
2、 友好的人机交互。移动机器人最终目标以服务人类为宗旨,在此基础上, 智能移动机器人在未来将具有很好的人性化体验,不再是人类单一地发送指令, 移动机器人一味地执行命令,而是附带各种反馈信息以及智能语音等交流『14]。
3、 多移动机器人协同工作。诸如物流AGV、自动化生产等领域,任务繁多, 同时每个岗位都需要机器人或者人类进行作业,单个移动机器人效率低下,不可 避免的需要多个移动机器人之间相互协作[15]。
4、 特种移动机器人。除了工业制造业应用之外,还有许多领域由于其特殊 需求,如在侦查巡逻、医疗手术、教育服务等领域通用的移动机器人根本满 足不了需求,并且这类移动机器人需求量很大。因此,研制出专用移动机器人是 未来的必然趋势。
1.3路径规划一般步骤
1.3.1环境建模
环境建模是其能够自主移动的必备条件,只有先建立好环境模型,让移动机 器人感知周围环境,分析当前工作地点,知道自己处在什么地方,才能进行并及 时釆取合理的决策,以实现安全、无碰撞的自主移动、路径规划将周围环境 用一组组数据进行抽象表达,建立二维或者是三维的工作空间,得到移动机器人 能够理解分析的环境数据,使其能够分析当前环境信息。
1.3.2路径搜索
路径搜索是指在环境模型中使用相应算法为移动机器人寻找一条行走路线, 依据全局信息己知或未知可分为全局规划和局部规划两种方式,每种方式都有各 自的优势,根据不同的适应场合,选取合适的方式或者结合两种方式的优势才能 最大程度提高路径规划效率^1。根据己知的环境信息,即离线地图的模式下搜索 一条路线的方式为全局路径规划,这种方式简单易实现,但是可移植性差,一旦 环境发生变化,离线地图也需随之重新设计更改^9]。局部规划是指移动机器人依 靠传感器检测来获取周围的环境信息I2'依据这些实时检测得来的数据信息,计 算分析当前环境,这种方式对于实时性要求更高,相对难度也更大[21],而且仅仅 依靠各种传感器获得的局部信息容易产生局部极点,并不难保证最终能获得全局 最优路径。
1.3.3路径平滑
实际应用场合中,由于工作环境的特殊、地形复杂等因素,通过相应的算法 为移动机器人搜索得到的路径,由于其路线严格按照算法事先设定好的搜索方向 进行行走,会发现最后搜索得到的最优路径不平滑,即路线存在过多的转弯节点, 这种情况下通常需要对算法寻到的路径做进一步处理操作,使其变成一条平滑路 &22h
1.4论文研究内容与章节安排
本文以理论推导和仿真实验相结合的方式进行移动机器人路径规划的研究, 设计了一种改进的蚁群优化算法路径规划方法。
本文内容分为五个章节进行说明,每章内容如下:
第一章为绪论,介绍了本课题的研宄背景与意义,论述了国内外的移动机器
人发展现状与未来发展趋势,分析了一般路径规划步骤并点明本文研究内容。
第二章概述了路径规划常用的几种导航方式、环境建模方式以及搜索算法, 并分析它们的适应性、优缺点,最后指出其未来发展趋势。
第三章为改进蚁群算法的路径规划研究,详细论述了基本蚁群算法原理,指 出其在求解全局寻优问题方面的优势,进而建立数学模型和环境地图进行路径规 划研究,分析其存在的不足之处以及从如何可以改进优化。该方法首先依据起始 点和目标点位置信息不均匀分配初始信息素浓度;接着增加避障策略,对蚂蚁信 息素更新策略提出优质蚂蚁更新原则并采用动态参数控制的伪随机转移策略,自 适应调整挥发系数;最后进行二次路径规划进行路径平滑措施等来改进蚁群算 法,通过这些改进措施,有效减少蚂蚁死锁数量,降低收敛次数,提高蚂蚁全局 搜索能力。
第四章在前面研宄内容基础上,釆用栅格法扩展至三维空间,针对三维环境 复杂多变、地貌特殊等因素,更改妈蚁信息素存储方式并且釆用分层前进的搜索 模式进行三维空间下路径规划研宄。结合二维平面路径规划的研宄,不均匀分配 初始信息素,依据优质蚂蚁更新规则,并且构造新的启发函数,有效提高算法全 局寻优能力。
第五章为总结与展望,明确本文的研究成果,并指出其研宄不足之处以及对 后续研究工作的展望。
第2章移动机器人路径规划
2.1移动机器人导航技术
如何在工作环境中找到一条最优路线并且使移动机器人安全可靠达到目标 点,仅凭路径规划算法是不够的,还需要相应的“载体”实现它,即导航技术来 进行自主移动。移动机器人利用各种传感设备将采集到的数据转换成其可识别的 环境信息,迅速处理计算分析当前可行路径最优解,实现其自主安全可靠地从一 个地方行走到另一个地方@]。
1、磁导航。磁导航原理是在移动机器人身上安装磁导航传感器,并在移动 机器人的工作空间中对固定行驶的路线布置磁条等能够产生磁场的装置,引导移 动机器人在事先布置好的磁条路线行走。这种导航方式简单易实现且成本低廉, 技术应用很成熟,抗千扰能力强,缺点是灵活性差,移动机器人行走线路的固定 化,使得移动机器人任务需求一旦发生任何改变或者更改行驶路线,则需要花费 大量时间重新布置场地。

图2-1磁导航示意图

2、惯性导航。惯性导航最初应用于航空、军工等领域,随着技术发展应用 领域扩大,如今在国民经济各个领域中发挥出了巨大而的作用。惯性导航主要依 靠惯性元件测量载体运动的数据信息,进而求得移动机器人的位置由于惯性 导航是采用自身测量信息进行连续定位方式,不借助外力的导航方式,不用和外 界进行信号接收,也不用向外辐射东西,所以是目前几种常用的导航方式中最具 隐蔽性的。但是惯性导航随着时间累计,定位误差也在不断加大,需要定期纠正, 无法作为独立的导航方式,但是和其方式相结合,充分发挥两种方式的优势,却
是一种很好的辅助定位技术。
3、激光导航。激光导航方式是市场上应用较多的一种方式,成熟稳定,通 过测量激光从发出到接受的时间来计算距离,通过多个点位的测距,最终确定自 身位置。激光导航优点在于控制精度高,性能好,缺点是价格较贵,且对环境要 求高[25】。

图2-3视觉导航扫地机器人

4、视觉导航。视觉导航技术先通过图像采集环境数据信息[261再转换成移 动机器人可以识别的环境信息,再对当前所处位置进行分析计算,建立全局环境 信息[2\视觉导航路线灵活多变,适应于很多应用领域成本较低,但是实际工况 中,如果数据处理速度低下,或者算法不够好,视觉测距会出现位置漂移现象, 与实际结果产生一定偏差,除此之外,视觉导航对光照的要求较高。
2.2环境建模
环境地图构建是移动机器人行驶的基本前提,需要知道移动机器人工作空间 中地形面貌、障碍物、工作点等环境信息,如果不知道周围环境移动机器人就如 同一个盲人,无法进行感知和路径规划f28]。
栅格法的原理是将周围环境看成一个二维平面,将平面分成一个个等面积大 小的具有二值信息的栅格,每个栅格中存储着周围环境信息量,并且每个栅格分 为自由空间和障碍物空间两种状态,代表着移动机器人可以通过或者不能通过, 依据移动机器人定位信息,在这些环境栅格化的环境中通过相应的算法搜索路 径,在整个栅格地图中行走便可记录一条完整路线[29]。栅格法简单易于实现,最 大程度保留了整体环境信息,方便移动机器人进行路径规划,但是栅格划分的精 度依赖于环境的复杂度,合理地划分栅格大小是关键。


图24栅格法地图


可视图法首先将障碍物扩展至多边形区域,然后将工作环境除了起始点和目
标点外用不规则图形全部进行区域划分,所有顶点和起始点以及目标点之间的连 线就是可行路线。可视图法的优势在于直观描述环境情况,对障碍物大小、分布 区域、路线长短一目了然。但是随着障碍物数量增加,可视图中路线也会成倍增 加,导致建模过程缓慢且算法计算量大大增加@]。
拓扑图法。拓扑图法将环境描绘成一张拓扑意义的图,不需要精确地表述环 境信息,只需要采用节点和连线描绘关键地点,节点之间的连线即移动机器人可 以行走的路线。这种环境表达方式方便移动机器人进一步的路径和任务规划,而 且存储空间小,对这种采用节点、连线的地图直观显示,可以结合很多智能算法 进行高效搜索路径。但是由于拓扑图法抽象度高,是在识别拓扑节点的基础上进 行路径规划,如果工作空间中有两个相似的地方,即周围环境特征信息不明显的 情况下,拓扑法将很难确定这是否为同一节点,难以进行路径搜索。
2.3移动机器人路径规划方法
在完成环境地图建立以后,接下来就是为移动机器人在工作空间中搜索一条 从自身所在位置到工作位置的可行路径,这是移动机器人完成各种任务前提。如 果不能准确、快速地到达指定工作位置进行作业,一切移动机器人应用都是空谈 无用的。移动机器人最优路径问题不仅仅是为简单规划一条可行路线,还要使得 这条路线最大程度上符合距离最短、时间最优、能耗最低等指标。最初提出的一 些传统算法有效解决了最短路径问题,但随着环境规模变大地形复杂以及任务多 项指标性要求,传统的路径规划算法难以取得理想的效果,于是涌现出一些智能 优化算法,每种算法在不同的性能指标下都有各自的优势[31]。
2.3.1传统路径规划算法
Dijkstra算法。Dijkstra算法采用贪婪的寻路策略,即在每次寻路中都会贪婪 寻找与该点距离最近的点,从而一步步贪婪到目标点,直至求得整个完整路径。 其特点就是以最快的速度解决最短路径问题,但是由于在寻路过程中一味只考虑 当前计算结果,不考虑之后会不会出现更好地最优路径,从而导致所求结果通常 不会是全局最优解。
A*算法。在Dijkstra算法的基础上增加启发式信息,搜索过程中不再一味的 贪婪当前最优解,属于深度优先搜索,是比较流行的启发式搜索算法之一,常用 来解决点对点的寻路问题[32]。A*算法性能的好坏直接取决于启发函数的设计, 如果启发函数过小,算法的搜索效率低,启发函数为零,就变成Dijkstra算法了。
如果启发函数过大,算法搜索能力下降,尽管会找到一条路径,但却不会是最优 路径。
模拟退火算法。通过判定求得的新解是否优于当前解,从而进行替代完成一 次迭代,其最大的特点是加入了随机因素,能够以一定概率跳出当前局部最优解, 是爬山算法的升级版,有效解决NP复杂性问题,但是算法性能受参数影响极大, 执行时间长[33]。
人工势场法。它将移动机器人的工作环境设计成一种充满引力和斥力的力 场,通过二者作用力的结合实现运动控制。人工势场法有着非常明显的优势,就 是简单、易于实现,也便于我们的观察。但是由于引力和斥力的直接作用,容易 造成局部极小值陷入陷阱区域,在相近的障碍物群中不能够识别路径以及障碍物 附近目标不可达到等缺点[34]。
禁忌搜索算法。它通过禁忌表的建立,以直进不退原则,禁止循环搜索,但 又存在赦免规则允许接受劣质解。类似于我们想要去找一个东西时,通常对己经 找过的地方不会再去寻找一次,而是会去下一个地方继续寻找(禁忌表法则), 但是当一遍找完后发现还是没有找到,于是开始在最有可能的地方再找一次(赦 免规则)。禁忌搜索算法可以单独作为一种搜索策略和其他算法相结合,有效提 高其他算法搜索效率。
2.3.2智能路径规划算法
蚁群算法。研究发现蚁群个体寻路过程中会分泌信息素,能够在小范围内被 其他蚂蚁所感知进而进行决策,最终整个蚁群自发聚拢到最短路径上[35】。蚁群算 法是基于多主体的智能算法,有效解决全局寻优问题,但是在复杂环境下难以取 得理想的效果[36]。
遗传算法。遗传算法属于进化算法的一种,将所需求解问题的解空间看作是 个体,适应度高的个体才能生存下来参与繁殖,即选择优质解淘汰劣质解。经过 多次迭代后,从最初的低等生物不断进化到高等生物,留下来的都是适应度很高 的个体。遗传算法适应于非线性复杂问题易与其他算法相结合,缺点是算法 各种参数选取困难,编程计算复杂,容易陷入“早熟”。
神经网络算法。神经网络算法由大量神经单元依据某种网络结构组成,几乎 超越了其他所有机器学习算法能力[38],广泛应用于各种领域,但是收敛速度慢, 神经网络结构选择不一。
2.4移动机器人路径规划技术难点
随着市场需求增加,投入使用的移动机器人也越来越多,为了更好地提高移 动机器人工作效率,适应各种工作场合,要求路径规划算法具有更高的实用性和 可靠性,目前存在以下难点:
1、 移动机器人的应用领域很多,工作场景也并非都是一成不变,在简单环 境下求解路径规划可以取得不错的效果,但是在复杂多变的环境下很难求的全局 最优解。
2、 目前路径规划技术主流方向是研究动态环境下移动机器人如何自主完成 任务,如何利用传感器高效、准确无误地获取周围环境信息并将其传递给移动机 器人进行路径规划是要解决的难题。
路径规划技术的未来发展除了对算法本身做改进外,还可以从下面几个方向 进行研究:
1、 混合算法的研究。随着环境复杂性增大以及任务多项指标要求,一些传 统的路径规划方法难以取得理想的效果,涌现出一些智能优化算法,在不同的性 能指标下每种算法都有各自优势,但是没有哪一种算法可以应付各种应用场合, 导致算法的求解效果并不是很理想,因此将多个算法有效结合,利用各自的特性, 取长补短,是提髙路径规划效率的一个方法。
2、 多传感器信息融合。在复杂多变的环境下,周围各种移动障碍物,想要 快速规划一条安全路线,移动机器人对周围环境信息的获取至关重要,环境信息 越完整移动机器人效率越高,单一的传感器获取的信息不足以反映真实环境,导 致移动机器人错误的决策。
3、 环境建模技术的优化。目前众多学者研宄了大量路径规划问题,提出来 许多可行有效的路径规划算法,甚至在这这些算法基础上加以改进优化,使其搜 索效率更高,但是大多数算法的改进都只局限于自身的改进优化,却忽略了环境 建模技术的优化和改进,一个好的地图模型不仅能够提高路径算法精确度,还能 直接影响算法的搜索性能。
4、 多机器人路径规划。如今已进入自动化、智能化时代,很多岗位已经解 放人类双手,用机器完全代替,某些领域中移动机器人发挥的作用也越来越大。 在物流搬运行业或流水线生产车间等应用场合中,任务需求量很大、工艺繁多, 单个移动机器人根本完成不了任务,而多个移动机器人在执行任务时不仅需要快 速到达目标点,还要避免在行驶过程中和其他移动机器人相撞[39]。多机器人协同 作业路径规划既要确保安全性,又要确保其工作效率。
2.5本章小结
本章主要论述了移动机器人路径规划所必须的几个环节,首先需要对其导航 定位,使其能够行走,随后建立几种电子地图模型并分析其优缺点,最后根据环 境信息使用相应的算法搜索路径,移动机器人想要在任务空间中成功地从一个地 方达到另一个地方进行作业,上述环节缺一不可。


第3章基于改进蚁群算法路径规划
3.1基本蚁群算法
3.1.1基本原理
研究发现在蚂蚁觅食行为中,总会找到最短路线,原因是蚂蚁会沿途分泌信 息素,并且能够在小范围内被其他蚂蚁感知进行决策,信息素的多少与蚂蚁走过 的路经长度成反比。一开始蚂蚁会随机地搜索路径,在路径上分泌的信息素也随 着路经长短而不一样,当另外一只蚂蚁在相同的岔路口进行决策时,会倾向于信 息素大的方向。随着大量个体的不断搜索,最终整个蚁群能够自发地聚拢在最短 路线上
蚂蚁觅食行为原理图可由图3-1所示,尸点W点代表着蚂蚁巢穴和食物地 点,蚂蚁会随机寻找食物并且分泌信息素,再找到食物之后便会搬运食物返回巢 穴。在往返搬运食物过程中,由于路线很多,一幵始蚂蚁会随机选取其中一条路 线,无论左边还是右边都有曲折路线,毫无疑问中间路线是最短的,但是蚂蚁一 幵始并不知道。久而久之,蚂蚁会发现中间路线上残留的信息素最多,于是吸引 着其他蚂蚁来走这条路线,最终蚁群会发觉到中间路线是最短路线并朝着这条路 线往返搬运食物。

蚁群算法具有如下特征:
分布式计算。蚁群算法将全局寻优的问题分配给每只蚂蚁去独立解决处理,
然后将所有结果进行综合处理分析,即每个个体独立求解问题,因为蚁群存在大 量个体也就意味着很强的随机性,通过所有个体求得的解来进行对比分析,最终 蚁群总会找到一个最优解,并不会因为某个个体死亡或者求得的解太差而影响最 终结果[41]。
自组织性。蚁群中的每个个体蚂蚁都随机地搜索路径,并没有来自外部的干 扰,通过蚁群走过路径上的信息素来感知路径搜索是否最优,经过一段时间后, 蚁群自发地倾向于选择路径上信息素最大的路径,即最短路径
正反馈。蚁群算法整个搜索核心是围绕着信息素进行开展的,由于路线距离 越短,信息素越多,进而吸引着越多的蚂蚁来选择这条路线,蚂蚁越多来这条路 路线行走,信息素又累积增加,这个过程使得算法处于正反馈状态,最终蚁群会 找到最短路线。
3.1.2数学模型
在第f次迭代中,蚂蚁A:由节点/选择下一节点」•的状态转移概率为:
(3-D
其中表示下一步全部可达路径节点的集合,a为信息启发式因子,取 值越大,信息素指导作用越强[43】。为期望启发式因子,/?越大,蚂蚁决策受路 径距离信息影响越大,贪婪当前效果[44]。&为路径(/,刀的信息素浓度,〜为启 发函数,&为当前节点i和待选节点y的欧氏距离,《越小,则~越大,则^越 大[45]。
由于算法只受路径距离和信息素两个因素综合影响决定的,而正反馈特性使 得信息素是不断累积的增加,可以想象,当到达一定时间后,路径上信息素值会 变得很大,会减弱甚至完全消除启发函数作用。为了避免这种情况发生,设定在 蚁群完成一次迭代后,即/ + 1时刻在路径上信息素按式(3-3)、(34)进行更新 处理。
(3-3)
(3-4)
*=i
其中p为信息素挥发系数,目的是减弱路径上信息素,设定/>取值范围为
A〜⑷表示蚂蚁在路径(/,力上的信息素增量,初始时刻
Az^(0) = 0[47】。
根据△<(/)的不同求法,有以及如/-■办三
种不同的基本蚁群算法模型。
在- Cycfc模型中
其中0为信息素强度,^表示蚂蚁Jfc所走路径的总长度,可以看出三种模型的不 同之处根本在于信息素增量计算方式不同,模型从整体信息考虑,而 如/ - 01扣《吻模型和」咐-£>e/iw_〇;模型从局部信息考虑,由于- Cyc/e模型求 解路径规划问题效果最好,因此本文使用d咐-模型t48]。
3.2基于蚁群算法路径规划 3.2.1栅格法建立环境模型
栅格法将环境描述为大小相同的单元网格,方便处理障碍物边界问题,也方 便对数据进行存储、操作,是目前使用最多的环境建模方式。由于其建模方法简 单易实现,因此本文选用栅格法进行地图建模[4\为了确保机器人移动过程中安 全,障碍物的大小依据机器人占地面积大小的一半划分,未沾满一个栅格的按一 个栅格进行处理。在用栅格法建立环境模型时,为了将环境信息转换成移动机器
人可以识别的数裾,采用坐标法和序号法两种方式标记环境地图信息,序号法将 栅格地图中一个个栅格从序号1依次累加直到标记到最后一个栅格。坐标法将栅 格地图划分为二维平面坐标,假设栅格规模为JC行和7列,即一个二维数组矩阵 胃依据序号法标记第i个栅格得到的位置坐标为二者之间的关 系如式3-8所示,式中,a是一个单元栅格的边长。
xi =ax[mod(/,^)-a/2] yt = ax^x + a / 2 - ceil (^i /
图3-2八叉树搜索策略


传统蚁群算法路径规划中,移动机器人移动策略是依据栅格上下左右四个方 向进行搜索,即四叉树搜索策略。这种搜索方式优点在于算法设计简单,但是路 线易发生偏移,且转弯较多,路经长度增加,越是复杂环境下,四叉树搜索法缺 陷极其严重[s°]。为此,本文采用八叉树搜索策略如图3-2所示,移动机器人搜索 过程中可以朝附近八个方向进行搜索,相邻栅格之间的自由移动,使得路径搜索 效率大幅提高。
3.2.2路径规划实现步骤
步骤1:初始化起始位置和目标位置以及蚂蚁数量m、最大迭代次数I等 算法参数,采用栅格法抽象表达环境模型。
步骤2:初始化蚂蚁禁忌表、路径长度等信息,蚂蚁从起始点出发开始搜索 路径,按照转移概率公式(3-1)寻找下一可达路径节点,蚂蚁每走一步同时记录妈 蚁走过的节点以及路线长度,一直循环到蚂蚁选取的节点为目标点或者没有可选 节点停止搜索。
步骤3:当蚁群完成一次迭代后,对路径上信息素按式(3-3)、(34)进行全局 更新。
步骤4:判断蚁群迭代次数是否达到上限,如果没有达到上限,接着进行下 一次迭代搜索,如果到达上限,结束搜索,保存最优路径信息。
步骤5:输出最优路径信息,算法结束。
算法流程图如图3-3所示。


图3-3基本蚁群算法路径规划流程图
3.2.3实验与结果分析
本文所有实验算法运行环境为:windows7 64bit; matlab2016a;处理器 i54590CPU;内存4GB,实验各参数取值如表3-1所示。
表3-1实验参数设置



收敛曲线变化趋势 58
56 1 丨

0 5 10 15 20 25 30 35 40 45 50

选代次数
图3-5基本蚁群算法收敛结果
采用图2-4所示的20x20环境模型进行实验仿真,结果如图34、3-5所示, 从实验结果可以看出蚂蚁搜索路径在第8次迭代时就找到了全局最优路径 38.9706,但是之后却并没有收敛于此,反而在第18次迭代时收敛于局部最优解 41.1232,明显看出算法收敛速度慢且收敛于局部最优值。
3.3基本蚁群算法的改进思路 3.3.1基本蚁群算法缺陷分析
蚁群算法具备较好的全局搜索能力,在解决路径规划方面具有不错的效果,
但是也存在算法收敛速度慢以及容易陷入局部最优值等问题。总结归纳由以下原 因造成:
1、 由于初始信息素值相同,前期蚂蚁决策选择哪一条路线时信息素起的作 用很微弱,可以忽略不计,蚂蚁路径搜索甚至朝着相反的方向行走,这是导致蚁 群算法前期搜索效率低下的关键原因。
2、 蚁群算法中参数个数多并且具有一定的关联性,尽管蚁群算法如今在很 多领域都应用,但是至今仍没有明确计算的一组参数数据可以适应于任何环境场 合,因此选取合适的参数对算法的性能影响很大。
3、 如果强调算法快速收敛,那么必然会导致算法解空间的多样性变小,不 能保证求得全局最优解,如果要强调算法解的多样性,那么收敛速度就会变慢, 如何寻求收敛性和解空间多样性的平衡点是关键。
4、 蚁群一次迭代结束后会对信息素进行更新,随着蚁群多次迭代,所有可 行路线中蚂蚁只会在几条最优路线中搜索,正反馈的机制尽管最后能淘汰掉较差 的路线,但是并不能保证最终寻到的是全局最优解,也有可能是局部最优解。
5、 蚁群算法由于禁忌表的限制以及复杂环境下障碍物的影响,使得蚁群搜 索只能前进不能后退,很容易造成“死锁”现象。
3.3.2基本蚁群算法改进途径
上节内容分析了基本蚁群算法自身存在缺陷的原因,可以对蚁群算法釆取如 下几种途径进行改进:
1、 从初始信息素分布入手,在算法前期不均匀分配初始信息素,加强先验 路径信息指导全局寻找最路径能力。
2、 至今没有一组适应于各种场合下的算法参数值,也没有相应的参数计算 公式,大多依据经验法选取,合理的选择算法中的参数值是提升算法性能的一个 方法。
3、 蚂蚁的概率转移只受信息素和路径距离两个因素的影响,忽略了障碍物 因素,可以增添新的搜索策略,改进转移概率公式,在选择最优路径的同时尽可 能提高算法解空间的多样性。
4、 信息素更新方式过于单一,每一次迭代完成后只一味地全局信息素更新 存在很大的盲目性,依据优胜劣汰法则,找出求得的最优解和最差解分别进行针 对性处理,避免所求得的解非最优解。
5、合理利用基本蚁群算法的正反馈特性,同时加入一些负反馈机制,增强 算法的全局搜索能力。
3.4改进蚁群算法路径规划 3.4.1初始信息素不均匀分布
由于初始信息素值相同,前期蚂蚁搜索节点时,很大程度上取决于路径距离 信息进行决策,蚂蚁在搜索每一个路径节点时偏向于最短路径,但是却忽略了全 局路径信息,导致在前期搜索中蚂蚁可能会选择与终点方向相背的区域行走或者 走回路,使得前期搜索时间较长且寻得的路径长度增大。为此本文划定以起始点 s和目标点r两个点为对角顶点的矩形区域或者两点之间的连线为全局地图有 利区域,如图3-6所示,增加该区域信息素初始值,表示为:
其中&为信息素初始值,C为大于r。的常数,;C为地图矩阵序号,7?为全局 有利区域,设定全局有利区域信息素初始值为C,其他区域信息素值不变。依据 •S点与T点位置信息可知,不管移动机器人如何行驶,最优路线往往是一条从;?点 到r点方向的路径,其移动总体方向是朝着目标点出发点的^1。因此初始信息素 不均匀分布有利于减少蚂蚁盲目搜索路径,提高收敛速度。
(3-9)
f (C, xeR 其他
图3-6信息素不均匀分配


3.4.2转移概率改进
蚁群算法是一种随机启发式搜索算法,在前期迭代中不可避免会产生大量的 交叉路径,而且由于算法禁忌表的限制,蚂蚁在寻路过程中只能前进不能后退, 使得前期搜索中大量蚂蚁个体会陷入死锁状态,最终“迷失”,没有走到终点就
停止搜索了。如图3-7所示A、B、C三条路径,由于蚂蚁陷入死锁,停留在最 后搜索到的一个路径节点,并没有安全无误到达目标点,路径搜索效率低,尤其 当环境规模变大地形复杂时,蚁群算法死锁现象更为严重。
10
8 7 6 5 4 3 2 1 0
0123456789 10
图3-7蚂蚁陷入死锁路径
蚁群算法的求解思路是让整个蚁群经历多次迭代,每次迭代求得的最优解都 是建立在之前所有迭代累计解的基础上计算的,最终求得全局最优解。因此前期 算法求得的解越多且解的质量越好,算法求得的全局最优解概率越大且收敛速度 越快。蚁群算法中不可避免出现死锁蚂蚁,究其根本原因是由于妈蚁在搜索路径
时不可避免会遇到周围的节点都是己走过的或者存在障碍物的情形,蚂蚁不可通 过,只能停留在原地。为此搜索初期采取避障策略,增加避障因子为:
式中〇7.为与节点y相邻且存在障碍物的栅格总数,^指与节点y相邻且被禁 忌表限制不能通过的栅格总数,^为与节点y相邻栅格总数,^为避障系数,取
值为一个小的正数。通过增加避障策略,蚂蚁每次迭代搜索路径时尽可能避免周 围障碍物,蚂蚁死锁的数量明显减少。采用参数自适应伪随机转移策略:

N -N
qO = S-^一~江 (3-13)
^max
其中1为最大迭代次数,义为当前迭代次数,^为调整系数,取值范围 为(0.5,1)。算法前期取值较大使得蚂蚁根据全局路径信息选择有利路径,后 期㈧取值较小有利于蚂蚁随机搜索。
3.4.3信息素更新规则
提出优质蚂蚁更新规则,即蚂蚁每一次迭代完成后,只选择到达目标点上的 蚂蚁,抛弃陷入死锁的蚂蚁,按式(3-14)对其更新信息素,避免路径上信息素盲 目更新。另外在每一次迭代中,同样能够走到目标点的蚂蚁,其经过的路径也不 尽相同,并不是每只蚂蚁都能寻找到最优路径,为此在蚁群一次迭代完成后除了 选择更新优质蚂蚁之外,还要对最优蚂蚁和最差蚂蚁按式(3-15)、(3-16)分别进行 信息素加强和削弱处理[52]。


式中7为信息素增幅比例系数,取为小于1的正数,为了避免信息素过多或者过
小陷入停滞状态,限定信息素值
= ^,当 ^(/)>、时,〜(r) = rmax。
蚂蚁寻找路径时主要通过信息素进行交流,而挥发因子的取值显得十分重 要,设定如果蚁群算法求得的最优解在连续r次迭代内都相同,采用自适应调整 挥发因子p大小,避免最终求得的解非最优解,p按式(3-17)做自适应调整,并 且如果连续T次求得的最优解小于历史最优解,加强对历史最优蚂蚁按式(3-15) 进行信息素更新。
p(/ + l) =
I为P的最小值,^为信息素衰减系数,为一个小于1的正数。

3.4.4二次路径规划
目前移动机器人路径规划大多是采用栅格法建立环境理想地图模型下仿真 设计,没有考虑到移动机器人实际行走时能耗的损失以及运行时间,且环境地图 模型的设定直接限定了路径规划的精确度[5~。本文基于此提出二次路径规划策 略,第一次路径规划完成后,再进行第二次路径规划,第二次路径规划调整移动 机器人行驶方向,不再固定直线方向或者转弯,优化地图模型的设定,使得移动 机器人在工作环境中更加灵活的行使。
方法如下:通过改进蚁群算法求得路径信息进行第二次路径规划,依次将起 始节点与后面所有不在同一条直线的节点连接,判断所得路径是否安全无碰撞路 径,如果不存在则选取第二个节点依次判断,如果存在安全无碰撞路径,则选取 最大的节点作为规划后的新路径节点,将原先规划好的中间节点全部删除,同时 以此节点继续和后面所有节点连接,判断所得路径是否是安全无碰撞路径,一直 到选取的节点为目标点结束。如图3-8所示,红色细线轨迹为第一次规划的路径, 蓝色粗线轨迹为第二次规划的路径。通过对比可以看出,经过二次路径规划的路 径可以减少移动机器人转弯次数,降低移动机器人运行时间和能耗。
机器人运动轨迹


012 3 456789 10
仙、X
图3-8两次路径规划结果对比 3A5改进蚁群算法路径规划实现步驟
步骤1:初始化起始点和目标点位置信息以及蚂蚁数量m、最大迭代次数 I、调整系数5等算法所需参数,采用栅格法建立环境地图模型,找出全局有 利区域,增加其信息素初始值。
步骤2:初始化蚂蚁路径、禁忌表等信息,蚂蚁从起始点出发幵始搜索路径,
按照转移概率公式(3-10)、(3-12)寻找下一可达路径节点,蚂蚁每走一步更新路径 长度,一直循环到蚂蚁选取的节点为目标点或者没有可选节点停止搜索。
步骤3:所有蚂蚁完成一次搜索后,依据优质蚂蚁更新规则对其进行信息素 更新,同时限定信息素上下限值&⑷
步骤4:设定迭代阈值,即连续T次求得最优解没有变动时,为防止算法陷 入停滞状态,则按式(3-17)改变挥发因子p的大小。
步骤5:判断蚁群迭代次数是否达到上限,如果没有达到上限,接着进行下 一次迭代搜索,如果到达上限,结束搜索,保存最优路径信息。
步骤6:进行第二次路径规划,输出最优路径信息,算法结束。
算法流程图如图3-9所示。

图3-9算法流程图


3.5改进蚁群算法路径规划实验与结果分析
改进蚁群算法分为两次路径规划,其中第一次采用前后左右相邻斜对角八个 方向规定移动机器人运动路线,第二次则优化地图模型,调整移动方向。为了增 加应用效果说明,设定栅格大小为lmxlm,移动机器人平均速度0.5m/s,考虑 安全因素,设定移动机器人到达每个节点^/2m (栅格中心点到栅格顶点的距 离)处需减速为0.2W“,另外在每个节点处需要转弯设定耗时2s。为了对比不 同环境下改进蚁群算法性能,采用20mx2〇m和30mx30m两种环境模型,并且 采用基本蚁群算法和本文改进蚁群算法以及参考文献[51]算法进行实验对比分 析。
3.5.1 20mx20m仿真环境
在20mx20m环境模型下本文改进算法和基本蚁群算法路径规划结果如图 3-10、3_11所示,其中图3-11蓝色细线轨迹为第一次规划的路径,红色粗线轨 迹为第二次规划的路径。
在复杂环境下,基本蚁群算法的寻到的最优路径并不理想,在越复杂的环境下基 本蚁群算法的不足体现得越明显。
图3-15文献[51]算法规划的路径
实验数据如表3-3所示,基本蚁群算法在第30次迭代中找到了全局最优值
45.1127m,却并没有收敛于此,参考文献[51]算法在第10次迭代收敛于全局最 优值43.3553m,改进蚁群算法在第一次路径规划时于第8次迭代收敛并找到全 局最优值42.3898m,相比基本蚁群算法和参考文献[51]算法迭代次数分别减少了 84%、71%,转弯数量分别减少58%、20%,路经长度分别减少6%、2%,移动 机器人行驶耗时分别减少32%、7%。图3-18为三种算法优质解数量对比,通过 对比可以看出在复杂环境下本文改进算法改善死锁蚂蚁方面依旧取得不错的效 果,极大降低了死锁蚂蚁数量。实验结果充分表明本文算法的优越性,在复杂环
境下依然具有较高的全局性以及快速收敛性。由于转弯次数和行驶时间的减少, 使得移动机器人能耗最大可能降低,且环境规模越大,地形越复杂,优越性越明
显。

图3-16改进算法规划的路径

表3-3 30wx30w环境实验结果对比



0 5 10 15 20 25 30 35 40 45 50
迭代次钕

图3-17三种算法收敛曲线对比
0 5 10 15 20 25 30 35 40 45 50
迭代次数
图3-18三种算法优质解数量对比


3.6本章小结
本章首先介绍了基本蚁群算法原理,给出其数学表达式,釆用栅格法建立环境 模型分析路径规划具体实现过程并且进行仿真实验,指出基本蚁群算法进行路径 规划存在的问题以及可以从哪几个方面进行改进优化,这些都为下文改进蚁群算 法和实验仿真做好铺垫和准备。该方法利用起始点目标点位置信息,初始化各条 路径信息素分配不均匀,减少蚂蚁前期盲目搜索路径,提高算法收敛次数;增加 避障策略,修改转移概率,有效减少死锁蚂蚁数量,提出优质蚂蚁更新规则,自 适应调节信息素挥发因子,提高了全局搜索能力;通过二次路径规划,减少了节 点数量,有效地降低了移动机器人的运行能耗,并且突破常规栅格法地图模型的 局限性。研究成果可广泛用于物流行业中AGV小车的路径规划,结合动态更新 电子地图,也可将此成果应用到多移动机器人的调度和路径规划中。
第4章三维环境下移动机器人路径规划 4.1三维环境下路径规划意义
移动机器人的出现,大量应用于各行各业中,例如深海探索、煤矿探测、航 天航空等领域,这些应用场合不仅仅都是在二维环境,更多是处在三维环境下, 而且在三维环境下工作更贴近人们日常实际生活,因此,从实用性以及未来发展 趋势来看,三维环境下路径规划的研究显得十分重要。目前,大部分路径规划研 究都是基于二维平面环境,对于环境复杂、规模较大的三维空间存在一些局限性, 而且由于三维环境特殊地貌的影响,路径规划的难度也随之加大。本章将在前面 研宄内容基础上,建立三维空间模型,研宄全局三维环境下路径规划问题[55】。 42三维环境建模
不同于二维环境下环境建模,三维环境更为复杂,因此合理的将三维环境抽 象表达出来是移动机器人在三维环境中自主作业的关键,在前面章节研究内容基 础上,釆用栅格法将二维空间扩展到三维空间,方法是将三维立体划分为一个个 平面,再将每一个平面栅格化。


如图4-1所示,构造三维空间MCD-EFG7/,建立空间坐标系(9- 其中点和原点重合,^45与尤轴重合,乂B与7轴重合,以原点0沿:T轴方向 将必进行《等分,沿尤轴方向将必进行m等分,沿Z轴方向将进行/等分, 即可将三维立体空间ZBCD-划分得到《个平面,每个平面可划分为mx/ 个栅格。至此空间可由《xmx/个栅格来表示,空间中任一个栅格 都对应一个路径节点,蚁群算法则在这些节点中进行路径规划设计与仿真研宄。 4.3三维环境下移动机器人路径规划 4.3.1搜索模式
在三维空间中,由于选择节点范围的扩大,导致算法搜索变得异常复杂,而 且三维空间大量路径节点遍历会很容易出现蚂蚁死锁现象。为此,在三维立体空 间采用一种分层前进与栅格平面法相结合的搜索模式,如图4-2所示。设定移动 机器人从起始点尸5出发,沿着尤方向为主前进方向,规定移动机器人每次最大 横向移动距离为凡^,每次最大纵向移动距离为,即设置蚂蚁对下一个路径 节点的搜索存在一个可视区域,避免蚁群在三维空间下遍历每一个节点。首先蚂 蚁从起始点尸s出发,在第一个平面搜索到可行节点接着在第二个
平面搜索到第二个可行节点p2〇c2,&,&;),蚂蚁依次在各个平面选择路径节点, 直到搜索到目标点仏结束,即可搜索到一条最优路径。

图4-2三维空间搜索模式

4.3.2信息素表不
在前面章节中己经介绍如何用栅格法建立环境模型,如何表示蚂蚁路径上信 息素以及每次迭代更新方式,但是这些都是基于二维空间栅格法研究的,并不适 用于三维空间。因为在二维平面栅格中,蚂蚁搜索路径时,与之相邻的节点只有 几个,信息素表示也是由两个节点之间的路径方式来存储,如果换算成三维环境 下,首先蚂蚁在当前节点搜索下一路径节点时会有mx/个路径节点,两个平面之 间就会有/«2></2种连接路线,如图4-3所示。为了避免占用太大存储空间,为此 在进行三维空间蚁群算法路径规划时,更改信息素存储方式,设定将信息素存储 在路径节点上,则相邻两个个平面只会有mx/种节点选择方式,极大降低了存 储空间和计算量[56]。


4.3.3启发函数设计
启发函数是整个蚁群算法重要组成部分,其作用是利用距离信息引导移动机 器人选择最短路径,对算法的收敛性、稳定性以及最优性至关重要。不同于二维 平面搜索路径,三维环境体现的是空间距离,且在三维空间中蚂蚁前期搜索容易 盲目地选择节点,忽视节点周围障碍物因素,同样会遇到死锁问题,为此增加避 障策略,设计新的启发函数,蚂蚁在当前节点a搜索下一个节点a + 1的转移概率 公式如式4-1所示,


其中^㈣为a和a+1两个节点之间的信息素,丹^+1为《和a+1两个节点之
间的启发函数信息,D1为当前节点a到下一节点的距离的倒数,D2为下一 节点a + 1到目标点的(?距离的倒数,仏,乂人)为当前节点a坐标,(。,人+1入+1) 为下一节点a + 1坐标,fe,丨,为目标点G坐标,#为当前节点可探索范围内 节点总数量,为当前节点可探索范围内不可行节点的数量,叫、%、%为 相应的权值。通过引入避障策略以及对启发信息函数的改进,有效提高算法的全 局搜索能力。
4.3.4信息素更新规则
所有蚂蚁一次迭代完成后,路径节点信息素按式(4-6)、(4-7)进行更新,
Tijk (^ +1) = (1 - P)rijk (O+Ar^ (/, / +1) (4-6)
= (4-7)
W=1
釆用改进蚁群算法在二维环境下路径规划方式,将此更新策略应用到三维环 境下,即蚂蚁完成一次迭代后,釆用优质蚂蚁更新策略按式(4-8)只选择更新达到 目标点的蚂蚁上路径信息素,抛弃陷入死锁的蚂蚁,避免信息素盲目更新,干扰 蚂蚁对路径选择的判断,然后分别找出每次迭代中最优蚂蚁与最差蚂蚁,分别按 式(4-9)、(4-10)对其路径上的信息素进行加强与减弱。为防止算法陷入停滞状态, 设定在算法求得的最优解在连续r次迭代内都相同,为避免最终求得的解非最优
4.3.5初始信息素分布优化


在蚁群算法搜索前期,信息素正反馈作用很微弱[57],对蚂蚁全局指引作用很 小,不仅仅在二维平面如此,三维空间同样如此,加上三维空间的扩大,使得蚂 蚁更容易盲目搜索,甚至朝着相反的道路探索,极大降低算法的搜索效率。采用 信息素初始化分配不均匀策略,设定在主前进方向中,以起始点和目标点为顶点 连接立体区域为全局有利区域,规定其信息素初始值大于其他区域信息素初始 值,依据全局地图信息可知,最优路径往往是一条从起始点朝着目标点方向出发 并逐渐靠拢的路径,三维环境也不例外,因此不均匀分配信息素,有利于减少蚁 群搜索时间,提高搜索效率。
4.4改进算法步骤
算法执行流程图如图4-4所示。

图4-4三维空间蚁群算法流程图

具体步骤如下:
步骤1:对机器人工作环境建立三维抽象模型,选择起始点和目标点,根据 全局地图信息划定有利区域,对初始信息素值进行不均匀分配。
步骤2:初始化妈蚁数量m、最大迭代次数I、调整系数5等算法所需参 数。选择起始节点,根据公式(4-1)寻找下一个可达路径节点,直到妈蚁搜索结束。 步骤3:设定蚁群在完成一次迭代搜索后,依据优质蚂蚁更新规则,抛弃未
走到目标点的死锁蚂蚁,不对其进行信息素更新,并且对最优蚂蚁和最差蚂蚁按 式(4-9)、(4-10)进行信息素更新处理,同时限定信息素上下限值。
步骤4:设定迭代阈值r,即连续r次求得最优解没有变化时,则自适应调 整p的大小。
步骤5:判断蚁群迭代次数是否达到上限,如果没有达到上限,接着进行下 一次迭代搜索,如果到达上限,结束搜索,保存最优路径信息。
步骤6:输出最优路径长度,算法结束。
4.5实验与结果分析
随机生成31m*31m*31m环境模型,在安全避障的前提下,以最短路径为评 价指标,采用改进蚁群算法和基本蚁群算法进行实验对比。
4.5.1仿真实验一
设定起始点为(1,15,8),目标点为(31,16,9),路径规划结果如图4-5、4-6所示, 实验数据如表4_1所示,可以看出基本蚁群算法在迭代了 14次才找到了全局最 优路径37.8776m,而改进蚁群算法在第8次就找到了全局最优路径33.9494m。 改进蚁群算法相比基本蚁群算法迭代次数减少43°/。,路径长度减少10%,实验 结果表明改进蚁群算法在三维环境下路径规划有效减少了收敛次数并且缩短路 径长度。
表4-1仿真实验一
算法 基本蚁群算法 本文改进蚁群算法
最优路径长度/m 37.8776 33.9494
收敛迭代次数 14 8
算法运行时间/s 1.0234 1.8833

图4-5基本蚁群算法路径规划


图4-6改进蚁群算法路径规划


图4-7两种算法收敛情况

4.5.2仿真实验二
设定起始点为(1,1,5),目标点为(31,8,5),实验数据如表4-2所示。



图4-8基本蚁群算法路径规划

可以看出基本蚁群算法在迭代了 15次才找到了全局最优路径37.1920m,而 改进蚁群算法在第10次就找到了全局最优路径35.5997m。改进蚁群算法相比基 本蚁群算法迭代次数减少了 33%,路径长度减少4%。尽管在算法运行时间上改 进蚁群算法耗时稍微多点,这是因为在算法中增添了一些搜索策略导致算法计算 变得复杂,但是从路径规划结果来看,本文改进蚁群算法有效提高算法搜索能力 和收敛速度。

图4-9改进蚁群算法路径规划


选代次数
图4-10两种算法收敛情况

4.6本章小结
本章首先介绍了三维环境下路径规划的意义引出本章的主要工作,设计一种 改进蚁群算法在三维环境下路径规划方法。首先采用栅格法扩展建立三维环境模 型,更改信息素存储方式,将信息素存储在路径节点上替代原先的路径上,使用 分层前进的搜索模式实现三维环境下的路径规划研究,采用上一章改进算法策
略,进行改进优化,通过实验对比分析,验证了该算法的可行性和有效性。


第5章总结与展望
5.1工作总结
本文研究了基于蚁群算法的移动机器人路径规划问题,这不仅仅要求为移动 机器人在工作空间中规划一条路径,还要使得这条路径符合移动机器人行驶时间 最短、距离最短、能耗最低等标准,最大限度提高工作效率,选择恰当合适的算 法显得十分重要。本论文对此进行了大量实验对比,通过实验数据分析得出本文 改进算法的正确性和优越性,主要工作内容如下:
1、 分析和叙述了国内外移动机器人研究进展情况,结合现今的研究热点引 出本课题的主要研宄内容。
2、 介绍了移动机器人路径规划技术。首先以导航技术的原理和用途出发论 述移动机器人自主移动的基础,接着开始对环境建模方式的分析,描述如何将移 动机器人工作环境电子地图抽象化表达,并且可被其识别感知,最后展开对路径 搜索算法研宄,并给出了一些基本传统算法和智能优化算法的简要介绍。
3、 设计一种改进的蚁群优化算法。该方法依据起始点和目标点在全局地图 中的位置信息不均匀分配其初始信息素浓度,提高前期蚂蚁搜索效率;综合禁忌 表信息以及障碍物不可行的因素,在蚂蚁搜索路径时增加避障策略,避免蚂蚁盲 目搜索产生大量交叉路径;釆用动态参数控制的伪随机转移策略,提出优质蚂蚁 信息素更新原则,自适应调整挥发系数,提高算法全局性,最后对求得的最优路 径进行平滑处理,优化路径并降低移动机器人能耗的损失。实验结果表明该算法 有较高的全局搜索能力,收敛速度明显加快,验证了该算法的有效性和优越性。
4、 在上述研究内容基础上,设计一种应用于三维环境下路径规划的蚁群算 法。分析了如何扩展栅格法对三维环境进行空间建模,更改路径搜索模式、信息 素存储方式等使其能够应用于三维环境下路径规划,并且增加避障策略构造新的 启发函数,改进信息素更新规则,自适应调整挥发系数,实验结果表明有效减少 收敛次数,有着较高的全局搜索性,证实了算法是可行有效的。
5.2论文创新之处
1、结合本课题研究背景和意义,研宄了基于改进蚁群算法的移动机器人路 径规划研宄,该算法在复杂环境下能够快速地寻找到全局最优解,解决了基本蚁
群算法收敛速度慢且易陷入局部最优值的问题,并且有效减少了蚂蚁死锁数量。
2、根据课题研宄方向继续深入,设计一种基于改进蚁群算法的三维环境下 路径规划研究。该算法不仅实现了三维空间下的路径规划,而且对其釆用二维平 面路径规划研宄的改进措施,实验仿真结果表明该算法的可行性,提高了算法的 实用性。
5.3工作展望
本论文研宄了移动机器人路径规划问题,都是建立在全局地图下,缺乏针对 移动障碍物的避障解决方案,后续研究将以动态避障为主,结合动态避障,提高 算法的实用性和有效性,对三维环境下的蚁群算法路径规划的研宄中,算法程序 有待进一步改进和优化,使其达到更好的效果。


参考文献
[1]杨晟.遥自主移动机器人关键技术研宄[〇].哈尔滨工程大学,2012.
[2]柯星.动态环境下多移动机器人路径规划研究[D].电子科技大学,2013.
[3]徐兆辉.移动机器人路径规划技术的现状与发展[J].科技创新与应用,2016 (03):43.
[4]霍凤财,迟金,黄梓健,等.移动机器人路径规划算法综述[J].吉林大学学报(信 息科学版),2018, 36(06):639-647.
[5]倪晓清.基于视觉与激光的移动机器人环境识别研究[D].苏州大学,2013.
[6]井超超.轮式机器人运动系统设计与研究[D].西安电子科技大学,2012.
曹超.基于ARM的移动机器人嵌入式组合导航系统研究[D].西南交通大学, 2013.
[8]邹强,丛明,刘冬,等.基于生物认知的移动机器人路径规划方法[J].机器人, 2018, 40(06):894-902.
[9]崔新忠,常诚,缪新颖.仿生机器人的发展与应用研究[J].机器人技术与应用, 2017(04):33-36.
[10]郑望望.高精度槽口管道检测机器人的设计[D]. 2015.
[11]樊迪.SHR-8S人形机器人步态规划及稳定性研究[D]. 2015.
[12]宋子墨.仿生移动轮腿式遥操作机器人[D].东南大学,2017.
[13]Liu X J, Ni Z H. Application of ant colony optimization algorithm in process planning optimization^]. Journal of Intelligent Manufacturing, 2013, 24(1):1-13.
[14]Shi E, Chen M, Li J, et al. Research on Method of Global Path-planning for Mobile Robot Based on Ant-colony Algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2014, 45(6):53-57.
[15]任孝平,蔡自兴,邰磊等中南移动二号”多移动机器人通信系统[J].中南大学 学报(自然科学版),2010,41(04):1442-1448.
[16]嵇鹏程,沈惠平.服务机器人的现状及其发展趋势[J].常州大学学报(自然科 学版),2010,22(02):73-78.
[17]高超.移动机器人的定位与地图构建研宄[D].内蒙古科技大学,2014.
[18]王春颖,刘平,秦洪政.移动机器人的智能路径规划算法综述[J].传感器与微 系统,2018,37(08):5-8.
[191黎竹娟.人工蜂群算法在移动机器人路径规划中的应用[J].计算机仿真,2012, 29(12):247-250.
[2〇]王东署,王佳.未知环境中移动机器人环境感知技术研宄综述m.机床与液压,
2013,41(15):187-191.
[21]秦菘.移动机器人导航控制系统研究[D].江西理工大学,2014.
[22]Yu J P, Wang C E. Assembly Sequence Planning Based on Max-Min Ant Colony System[J]. Applied Mechanics & Materials, 2012, 284-287(23):2220-2227.
[23]Lin Y, Gao F, Qin T, et al. Autonomous aerial navigation using monocular visual -inertial fusion[J]. Journal of Field Robotics, 2017,35(4).
[24]宋玉珍,刘炼.MEMS-IMU/GPS组合导航系统仿真研究[J].雷达科学与技术, 2010, 8(04):301-305.
[25]陈阳.未知环境下移动机器人路径规划与路径跟踪研宄[D].安徽工业大学,
2018.
[26]方浩然.基于视觉的四旋翼飞行器导航降落系统研宄[D].沈阳理工大学, 2017.
[27]丁林祥,陶卫军.未知环境下室内移动机器人定位导航设计与实现[J].兵工自 动化,2018, 37(03):12-17.
[28]谭民,王硕.机器人技术研宄进展[J]•自动化学报,2013,39(07):963-972•
[29J 王慧,王光宇,潘德文.基于改进粒子群算法的移动机器人路径规划 [J]. 传感 器与微系统,2017,36(05):77-79.
[30]陈至坤,郭宝军,王淑香.移动机器人目标路径规划的仿真研究[J].计算机 仿真,2016,33(5).
[31]张谦.基于激光雷达的机器人路径规划[J]•激光杂志,2018,39(05):88-91.
[32]陈和平,黎小琴,顾进广,等.基于矢量地图数据的路径规划算法研宄[J].计 算机工程与应用,2010,46(19)238-240.
[33]杨卫波,赵燕伟.求解TSP问题的改进模拟退火算法[J].计算机工程与应用, 2010,46(15):34-36.
[34]刘建华,杨建国,刘华平,等.基于势场蚁群算法的移动机器人全局路径规划方 法[J].农业机械学报,2015,46(09):18-27.
[35]Dorigo M , Gambardella L M . Ant Colony System: A Cooperative Learning