一种MAKLINK图多节点链路建模的路径规划研究

1

作者 孙培刚 张全禹 许春和 《电子设计工程》 2024年第4期140-143,148,共5页

针对传统MAKLINK图规划路径线路改变时,其最优化路径易与环境约束条件冲突的问题,提出了在MAKLINK图中各链路上增加节点数目的方法,以提高系统建模的适应性和鲁棒性。设计的多节点链路通过dijkstra算法得到更为理想的次优化路径,由蚁群... 针对传统MAKLINK图规划路径线路改变时,其最优化路径易与环境约束条件冲突的问题,提出了在MAKLINK图中各链路上增加节点数目的方法,以提高系统建模的适应性和鲁棒性。设计的多节点链路通过dijkstra算法得到更为理想的次优化路径,由蚁群算法进行迭代计算获得最优化路径,实现了在保证路径适应度的前提下,提高优化路径对环境约束条件的适应性。实验结果表明,与基本MAKLINK图路径规划算法相比,多节点链路的建模路径规划算法可有效提高次优路径的建模精度,最优路径的适应度值较单节点链路减小了1.43%,具有一定的建模优势。 展开更多

关键词 maklink图 多节点链路 DIJKSTRA算法 蚁群算法

下载PDF 职称材料

基于Maklink图和遗传算法的改航路径规划方法研究 被引量：29

2

作者 王飞 王红勇 《交通运输系统工程与信息》 EI CSCD 北大核心 2014年第5期154-160,共7页

为了保障恶劣天气下的飞行安全,航班需要采取改航策略避开危险区.采用已有的以改航路径最短为目标,以航段最小距离、避开危险区、转弯角度等为约束条件的规划模型,设计了3阶段方法研究改航路径规划.首先应用Maklink图和Dijkstra算法规... 为了保障恶劣天气下的飞行安全,航班需要采取改航策略避开危险区.采用已有的以改航路径最短为目标,以航段最小距离、避开危险区、转弯角度等为约束条件的规划模型,设计了3阶段方法研究改航路径规划.首先应用Maklink图和Dijkstra算法规划一条能够避开危险区的路径,接着应用遗传算法优化路径,最后进行路径调整以满足约束条件.算例仿真结果显示,应用本文方法得到的改航路径长度较短,转弯次数少、转弯角度小,计算效率高.仿真结果说明,应用本文提出的方法获得的改航路径满足目标和约束要求,验证了该方法的可行性和有效性. 展开更多

关键词 航空运输 maklink图 遗传算法 DIJKSTRA算法 改航路径规划 民航

下载PDF 职称材料

基于变参数萤火虫算法和Maklink图的路径规划研究 被引量：9

3

作者 李明富 张玉彦 +1 位作者 马建华 周友行 《机械科学与技术》 CSCD 北大核心 2015年第11期1728-1732,共5页

针对静态二维环境下的全局路径规划问题,提出了一种基于变参数萤火虫算法和Maklink图的全局路径规划方法。将定参数的连续型萤火虫算法改进为变参数的离散型萤火虫算法;根据全局路径规划问题的特点,定义了变参数萤火虫算法的编码规则及... 针对静态二维环境下的全局路径规划问题,提出了一种基于变参数萤火虫算法和Maklink图的全局路径规划方法。将定参数的连续型萤火虫算法改进为变参数的离散型萤火虫算法;根据全局路径规划问题的特点,定义了变参数萤火虫算法的编码规则及萤火虫之间的距离表征方法;以含有多个任意形状障碍物的环境为例,在Maklink图的基础上采用变参数萤火虫算法对路径进行优化,改进后的萤火虫算法能够较好的解决离散路径规划问题。实验表明:变参数萤火虫算法的性能不仅优于标准萤火虫算法,而且在收敛速度、算法稳定性等方面优于粒子群算法。 展开更多

关键词 全局路径规划 萤火虫算法 maklink图

下载PDF 职称材料

基于Maklink图和蚁群算法的航线规划 被引量：23

4

作者 陈晓 戴冉 陈昌源 《中国航海》 CSCD 北大核心 2017年第3期9-13,共5页

为实现航线自动规划设计,提出一种可行的计算方法,并对船舶实际运营中进行航线规划时需注意的问题进行分析。以路径最短为目标,建立以避开障碍物区域和危险区域、控制转弯角度及减少转向点数目等为约束条件的规划模型。在建立模型过程中... 为实现航线自动规划设计,提出一种可行的计算方法,并对船舶实际运营中进行航线规划时需注意的问题进行分析。以路径最短为目标,建立以避开障碍物区域和危险区域、控制转弯角度及减少转向点数目等为约束条件的规划模型。在建立模型过程中,采用Maklink图和Dijkstra算法生成初始规划路径,采用蚁群算法对路径作进一步的优化和调整,以满足约束条件。试验结果表明:与传统的在纸质海图上绘制航线及在电子海图上手动输入转向点生成航线相比,通过智能算法生成航线具有耗时短、经济可靠等优点。 展开更多

关键词 船舶工程 航线自动规划 maklink图 DIJKSTRA算法 蚁群算法

下载PDF 职称材料

基于Maklink图和布谷鸟搜索算法的施工水域路径规划 被引量：1

5

作者 张波菲 谢新连 何傲 《上海海事大学学报》 北大核心 2020年第3期6-11,30,共7页

为提高船舶在复杂施工水域通行的安全性,提出一种基于Maklink图和布谷鸟搜索(cuckoo search,CS)算法的船舶路径规划方法。利用改进的Maklink图构建施工水域环境模型;设置变量参数并用改进的CS算法对模型进行求解,其中采用基于Dijkstra... 为提高船舶在复杂施工水域通行的安全性,提出一种基于Maklink图和布谷鸟搜索(cuckoo search,CS)算法的船舶路径规划方法。利用改进的Maklink图构建施工水域环境模型;设置变量参数并用改进的CS算法对模型进行求解,其中采用基于Dijkstra算法得到的最短路径长度作为种群个体的适应度值;采用3个衡量算法性能的指标——优化性能指标、时间性能指标和动态性能指标,对多种算法进行分析比较。结果表明,采用指数型自适应步长和线性自适应发现概率对CS算法进行改进,能提高其在路径规划中的搜索效率和迭代速度,并可以保证求出一定精度内的近似最优解,显示出该算法的优越性。 展开更多

关键词 船舶避障 智能交通 布谷鸟搜索(CS)算法 性能指标 施工水域 maklink图

下载PDF 职称材料

基于Maklink路径规划混合定位算法研究 被引量：2

6

作者 杨俊磊 段倩倩 《传感器与微系统》 CSCD 北大核心 2022年第2期62-65,共4页

为了提高含有障碍物下的路径规划的质量和效率,保证遍历节点少且路径短,提出了一种混合定位算法。算法融合了粒子群算法选择最佳位置的优越性,以提高蚁群算法蚂蚁所在节点与盲节点间距离估计的精度和搜寻速度;根据蚁群算法通过信息素浓... 为了提高含有障碍物下的路径规划的质量和效率,保证遍历节点少且路径短,提出了一种混合定位算法。算法融合了粒子群算法选择最佳位置的优越性,以提高蚁群算法蚂蚁所在节点与盲节点间距离估计的精度和搜寻速度;根据蚁群算法通过信息素浓度选择遍历节点的特点,规划节点与盲节点之间的最短距离,以增强蚁群信息素的浓度值,提高收敛速度,规划最短路径。实验表明:在不同规模障碍物区域路径搜寻过程中,采用混合定位算法规划路径优于文中其他两种算法,规划路径最短,效率最高。 展开更多

关键词 路径规划 混合定位 maklink图 信息素

下载PDF 职称材料

基于粒子群算法的移动机器人路径规划 被引量：42

7

作者 秦元庆 孙德宝 +1 位作者 李宁 马强 《机器人》 EI CSCD 北大核心 2004年第3期222-225,共4页

提出一种分步路径规划方法 ,首先采用链接图建立机器人工作空间模型 ,用Dijkstra算法求得链接图最短路径 ;然后用粒子群算法对此路径进行优化 ,得到全局最优路径 .仿真结果表明 :所提方法简便可行 ,能够满足移动机器人导航的高实时性要... 提出一种分步路径规划方法 ,首先采用链接图建立机器人工作空间模型 ,用Dijkstra算法求得链接图最短路径 ;然后用粒子群算法对此路径进行优化 ,得到全局最优路径 .仿真结果表明 :所提方法简便可行 ,能够满足移动机器人导航的高实时性要求 。 展开更多

关键词 移动机器人 路径规划 DIJKSTRA算法 仿真 粒子群算法

下载PDF 职称材料

基于改进蚁群算法的自动导引运输车全局路径规划方法研究 被引量：14

8

作者 梁建刚 刘晓平 +1 位作者 王刚 韩松 《机电工程》 CAS 北大核心 2018年第4期431-436,共6页

针对自动导引运输车(AGV)全局路径规划采用传统蚁群算法存在收敛速度慢、易陷入局部最优的问题,提出了基于改进蚁群算法的AGV全局路径规划方法。首先,运用MAKLINK图论法构建了具有障碍物的环境模型,作为路径规划的基础;其次,改进的蚁群... 针对自动导引运输车(AGV)全局路径规划采用传统蚁群算法存在收敛速度慢、易陷入局部最优的问题,提出了基于改进蚁群算法的AGV全局路径规划方法。首先,运用MAKLINK图论法构建了具有障碍物的环境模型,作为路径规划的基础;其次,改进的蚁群算法中融合了动态权重目标导向原理,设计了一种新的启发式函数,提高了其选择距离目标点更近的可选节点的概率,减小了AGV对非最短路径的选择概率;然后,采用动态调整信息素挥发系数策略进行了信息素更新,提高了算法的搜索效率;最后,将改进蚁群算法与传统蚁群算法进行了仿真实验对比。研究结果表明:与传统蚁群算法相比较,改进措施可使收敛速度提升近一倍,路径规划效率显著提高。 展开更多

关键词 蚁群算法 路径规划 自动导引运输车 maklink图论法

下载PDF 职称材料

基于蚂蚁算法的移动机器人路径规划 被引量：22

9

作者 董玉成 陈义华 《重庆大学学报（自然科学版）》 EI CAS CSCD 北大核心 2003年第3期49-51,共3页

蚂蚁算法是近几年问世并逐步引起重视的一种新的全局优化仿生算法 ,它模仿昆虫王国中蚂蚁搜索食物的行为特征 ,是一种通用型随机优化方法。移动机器人在进行工作时 ,往往要求根据某一准则 ,在工作空间沿一条最优 (或近似最优 )的路线行... 蚂蚁算法是近几年问世并逐步引起重视的一种新的全局优化仿生算法 ,它模仿昆虫王国中蚂蚁搜索食物的行为特征 ,是一种通用型随机优化方法。移动机器人在进行工作时 ,往往要求根据某一准则 ,在工作空间沿一条最优 (或近似最优 )的路线行走。因此首先对移动机器人的规划空间进行链接图表示 ,然后采用Ford算法求出移动机器人的初始路径 ,最后运用蚂蚁算法对初始路径进行优化 。 展开更多

关键词 移动机器人 路径规划 链接图 Ford算法 蚂蚁算法

下载PDF 职称材料

基于链接图法和遗传算法的航路规划 被引量：5

10

作者 程春华 吴进华 +1 位作者 周大旺 齐玉华 《舰船电子工程》 2010年第1期85-87,共3页

航迹规划对军用飞行器完成任务具有重要的意义。链接图的特点是简单明了,文章针对链接图法进行航路规划的不足,使用遗传算法进行再次优化,使该航路满足了性能要求。最后给出了仿真,反正结果表明该方法的可行性。

关键词 航路规划 链接图 遗传算法

下载PDF 职称材料

矿井中多机器人搜救系统路径规划 被引量：4

11

作者 金纯 王升刚 尹远阳 《机床与液压》 北大核心 2014年第15期10-14,共5页

矿难发生后,井下通信设施可能已有一定的损害、无法正常使用,因而无法知道被困人员的确切位置并且井下环境复杂危险,可能对营救人员造成伤害发生二次事故。为了快速地搜索到被困人员,结合井下无线传播环境的特点,提出井下多机器人组网... 矿难发生后,井下通信设施可能已有一定的损害、无法正常使用,因而无法知道被困人员的确切位置并且井下环境复杂危险,可能对营救人员造成伤害发生二次事故。为了快速地搜索到被困人员,结合井下无线传播环境的特点,提出井下多机器人组网搜救系统,其中包括机器人自由空间环境模型的创建、机器人搜索的局部和全局路径的规划。利用MAKLINK图论理论对井下环境进行建模,并且采用Dijkstra算法规划出避障初始路径,最后依据距离改进蚁群算法节点选择得出优化的最终路径,完成搜索路径的规划。MATLAB仿真结果表明,优化的路径总长度明显优于初始路径并且改进的蚁群算法有着较好的收敛速度,可以满足多机器人搜救系统的要求。 展开更多

关键词 路径规划 搜救系统 机器人 蚁群算法 链接图

下载PDF 职称材料

改进型蚁群算法的全局路径规划仿真研究 被引量：4

12

作者 张鹏 徐晓旭 《航空计算技术》 2013年第6期1-4,8,共5页

针对传统蚁群算法收敛较慢的问题,提出了一种在复杂环境下全局路径规划的改进型蚁群算法。利用链接图法建立了路径规划的空间模型;借鉴狼群分配原则对信息素进行更新;在缩小搜索区域,提高搜索效率的过程中,引入了启发式概率公式和启发函... 针对传统蚁群算法收敛较慢的问题,提出了一种在复杂环境下全局路径规划的改进型蚁群算法。利用链接图法建立了路径规划的空间模型;借鉴狼群分配原则对信息素进行更新;在缩小搜索区域,提高搜索效率的过程中,引入了启发式概率公式和启发函数;通过参数自适应调整策略,进一步对最优解进行了优化。将基于Dijkstra算法的初始路径规划和改进后蚁群算法的规划结果进行了仿真对比,结果表明,改进后蚁群算法的全局优化性能较好,具有一定的有效性和可行性。 展开更多

关键词 全局路径规划 改进型蚁群算法 链接图 启发函数 DIJKSTRA算法

下载PDF 职称材料

基于竞选算法的移动机器人路径规划 被引量：1

13

作者 李劲 吕文阁 侯梦华 《机床与液压》 北大核心 2009年第1期30-31,68,共3页

提出了一种路径规划的新方法,利用链接图法(MAKLINK Graph)建立规划环境模型,将规划分为两个层次:用E.W.Dijkstra算法求链接图的最短路径,得到初始路径点;用竞选算法来调整各个初始路径点,得到最优的或近似最优的移动路径点。分析结果... 提出了一种路径规划的新方法,利用链接图法(MAKLINK Graph)建立规划环境模型,将规划分为两个层次:用E.W.Dijkstra算法求链接图的最短路径,得到初始路径点;用竞选算法来调整各个初始路径点,得到最优的或近似最优的移动路径点。分析结果表明该方法是有效的。 展开更多

关键词 移动机器人 路径规划 链接图 E.W.Dijkstra算法 竞选算法

下载PDF 职称材料

基于谱聚类的空域扇区分割 被引量：8

14

作者 王超 王晓英 王飞 《计算机应用研究》 CSCD 北大核心 2014年第6期1889-1893,共5页

为解决当前空域扇区结构对交通流适应性差的问题,进行了空域扇区分割与边界优化算法的研究。根据管制空域的基本航线网络结构和空中交通流量,提出了顶点间联系程度的计算模型;结合顶点融合与边航线离散化方法,建立了空域运行图模型;应... 为解决当前空域扇区结构对交通流适应性差的问题,进行了空域扇区分割与边界优化算法的研究。根据管制空域的基本航线网络结构和空中交通流量,提出了顶点间联系程度的计算模型;结合顶点融合与边航线离散化方法,建立了空域运行图模型;应用谱聚类算法实现了空域图顶点的有效分割,解决了近距平行航路分割误差问题,实现了扇区凸壳的构造与划分;提出了基于MAKLINK图的扇区间边界优化路径选择算法。实例分析表明,该算法能根据空中交通流量需求进行扇区优化设计,运行时间较短,约为10 s。 展开更多

关键词 空域规划 扇区划分 图论 谱聚类 maklink图

下载PDF 职称材料

滴水湖无人船测试场应急保障航道规划

15

作者 白响恩 周俊杰 +6 位作者 肖英杰 徐笑锋 戚玉玲 沈建华 徐元 任鸿翔 曾建峰 《上海海事大学学报》 北大核心 2021年第1期13-18,25,共7页

针对滴水湖新建无人船测试场的应急保障问题,建立基于Maklink图论和Dijkstra算法的多终点航道规划模型。通过环境建模确定障碍物大小和位置;受PNPoly算法启发,引入剔除函数进行模型改进;利用Dijkstra算法在无向网络图中搜索从起点至终... 针对滴水湖新建无人船测试场的应急保障问题,建立基于Maklink图论和Dijkstra算法的多终点航道规划模型。通过环境建模确定障碍物大小和位置;受PNPoly算法启发,引入剔除函数进行模型改进;利用Dijkstra算法在无向网络图中搜索从起点至终点的最短应急航道,并利用蚁群算法对最短应急航道集合进行优化。结果分析显示,最终规划的航道高效、安全,规划结果可以为滴水湖管理工作和无人船测试场应急保障提供参考。 展开更多

关键词 滴水湖 无人船测试场 应急保障 航道规划 maklink图论 DIJKSTRA算法

下载PDF 职称材料

基于环境模型的移动机器人路径规划 被引量：4

16

作者 宋彩云 王明磊 刘肖琳 《电光与控制》 北大核心 2006年第3期102-104,共3页

介绍了一种新的移动机器人路径规划方法。采用链接图法,对工作空间建模。用Di-jkstra算法决策出全局最短路径,然后用遗传算法对此路径进行优化,得到全局最优路径。最后提出了一种对路径几何改进的方法。仿真结果表明,该方法方便简单,对... 介绍了一种新的移动机器人路径规划方法。采用链接图法,对工作空间建模。用Di-jkstra算法决策出全局最短路径,然后用遗传算法对此路径进行优化,得到全局最优路径。最后提出了一种对路径几何改进的方法。仿真结果表明,该方法方便简单,对所规划的路径质量有所提高。 展开更多

关键词 链接图法 DIJKSTRA算法 遗传算法 路径规划 移动机器人

下载PDF 职称材料

利用三次样条改进蚁群算法的无人机航路规划 被引量：9

17

作者 程琪 荆涛 于志游 《计算机测量与控制》 2016年第8期272-274,293,共4页

针对无人机在二维平面自动飞行中转弯角度过大、路径规划困难的问题,研究了蚁群算法在复杂环境下航路规划中的应用,利用链接图简洁的特点建立空间模型,对无人机的飞行环境和航迹代价进行了描述,并结合三次样条插值函数与蚁群算法,提出... 针对无人机在二维平面自动飞行中转弯角度过大、路径规划困难的问题,研究了蚁群算法在复杂环境下航路规划中的应用,利用链接图简洁的特点建立空间模型,对无人机的飞行环境和航迹代价进行了描述,并结合三次样条插值函数与蚁群算法,提出了改进蚁群算法,对无人机飞行路径进行优化,并给出算法软件流程;利用MATLAB进行了仿真实验,得出了最优的航路,算法具有较好的稳定性和鲁棒性,对轨迹中不可飞的尖角进行了平滑处理,使得航路为曲线轨迹,满足无人机工作的性能要求,减少无人机在飞行中的代价损耗,验证了该优化算法在无人机航路规划中的可行性。 展开更多

关键词 蚁群算法 三次样条插值函数 航路规划 链接图 DIJKSTRA算法

下载PDF 职称材料

恶劣天气下多条改航路径的生成 被引量：1

18

作者 仝佳璐 胡明华 张颖 《航空计算技术》 2018年第6期55-58,63,共5页

为了解决复杂空域中航班流的运行问题,以最优改航航路为目标函数,采用改进的双向Dijkstra优先队列算法生成多条改航航路。对于一些实时的恶劣天气冲突,利用MAKLINK图对改航路径进行局部修改,并在此基础上利用路径代价函数与多条路径规... 为了解决复杂空域中航班流的运行问题,以最优改航航路为目标函数,采用改进的双向Dijkstra优先队列算法生成多条改航航路。对于一些实时的恶劣天气冲突,利用MAKLINK图对改航路径进行局部修改,并在此基础上利用路径代价函数与多条路径规划模型对所生成的改航路径进行评价,求得多条最优改航航路。实例验证结果证明,应用的改进算法和设计的系统能高效规划出k条最优路径,且满足实际要求,适用于航班流的整体运行。 展开更多

关键词 双向Dijkstra优先队列算法 maklink图 路径代价函数 多条路径规划模型

下载PDF 职称材料

Ant Colony System Algorithm for Real-Time Globally Optimal Path Planning of Mobile Robots 被引量：26

19

作者 TAN Guan-Zheng HE Huan SLOMAN Aaron 《自动化学报》 EI CSCD 北大核心 2007年第3期279-285,共7页

为活动机器人计划的即时全球性最佳的路径的一个新奇方法基于蚂蚁殖民地系统(交流) 被建议算法。这个方法包括三步：第一步正在利用 MAKLINK 图理论建立活动机器人的空间模型，第二步正在利用 Dijkstra 算法发现一条非最优的没有碰撞的... 为活动机器人计划的即时全球性最佳的路径的一个新奇方法基于蚂蚁殖民地系统(交流) 被建议算法。这个方法包括三步：第一步正在利用 MAKLINK 图理论建立活动机器人的空间模型，第二步正在利用 Dijkstra 算法发现一条非最优的没有碰撞的路径，并且第三步正在利用 ACS 算法优化非最优的路径的地点以便产生全球性最佳的路径。建议方法是有效的并且能在即时路径被使用活动机器人计划的计算机模拟实验表演的结果。建议方法比与优秀人材模型一起基于基因算法计划方法的路径处于集中速度，答案变化，动态集中行为，和计算效率有更好的性能，这被验证了。 展开更多

关键词 蚁群系统 运算法则 自动化系统 计算机技术

下载PDF 职称材料

海上施工水域船舶航线规划数学建模及求解 被引量：9

20

作者 谢新连 刘毅 何傲 《重庆交通大学学报（自然科学版）》 CAS CSCD 北大核心 2019年第9期7-12,共6页

海上施工水域是船舶在航行中风险较大的区域,为了解决船舶在施工水域中的船舶航线规划问题,建立了以航线总长度最短为目标函数,以不可航行区域和船舶转向角等为约束方程的航线规划数学模型。在建立航线规划的数学模型的基础上,重点研究... 海上施工水域是船舶在航行中风险较大的区域,为了解决船舶在施工水域中的船舶航线规划问题,建立了以航线总长度最短为目标函数,以不可航行区域和船舶转向角等为约束方程的航线规划数学模型。在建立航线规划的数学模型的基础上,重点研究了模型求解的具体方法。在求解施工水域航线规划的数学模型时,首先利用图论的方法将可自由航行区域通过链接线将其拆分为若干个凸多边形。其次将链接线的中点两两相连,形成海上施工水域中的Maklink航线网络。然后再采用两阶段优化方法求解,第1阶段利用Dijkstra算法求解出能够避开所有危险区域的初始航线;第2阶段利用蚁群算法,对初始航线进行优化。最后通过蚁群算法的优化,求得了航线总长度更短而且转向角更小的最优航线。 展开更多

关键词 交通运输工程 施工水域 航线设计 maklink图 DIJKSTRA算法 蚁群算法

下载PDF 职称材料