基于Dijkstra-蚁群算法的泊车系统路径规划研究

  • 基于Dijkstra-蚁群算法的泊车系统路径规划研究已关闭评论
  • 155 views
  • A+
所属分类:AGV设计资料
摘要

针对智能停车库中自动导引运输车(automated guided vehicle,AGV)存取车路径规划问题,提出了一种基于Dijkstra-蚁群算法(Dijkstra-ACO)的泊车系统路径规划方法.首先利用链接可视图法建立环境模型,并在此环境模型下,采用Dijkstra算法规划出AGV的初始路径;其次,通过引入节点随机选择机制、调整信息素更新方式和限定信息素阈值策略等对基本蚁群算法进行优化改进;最后,选用改进的蚁群算法对初始路径进行优化.结果显示:Dijkstra算法和混合算法均能使AGV有效避开障碍物,然后搜索到一条从起点到终点的无碰优化路径;与Dijkstra算法相比,混合算法能有效提高路径搜索效率,缩短搜索路径长度,改善搜索路径质量,表明该算法正确、可行及有效,且具有较强的全局搜索能力和较好的收敛性能,能够满足AGV存取车路径规划的要求.

汽车保有量的急剧增加,致使城市交通拥挤、停 车困难等社会问题不断涌现,严重影响了市民的居 住环境,因此,停车难已成为社会亟待解决的难题. 而基于自动导引小车(AGV)的平面移动式智能停 车库凭借占地面积少、有效停车数量多以及智能化 程度高等优点而备受社会各界广泛关注.研究平面 移动式智能停车库的核心,就是要解决 AGV 存取 车路径规划问题.车库路径规划的主要目的是让 AGV运行在有障碍物的未知环境中,根据某些评 价标准(如最短时间、最短距离或最少转弯次数),寻 找一条从预存停车位到目标停车位的最优无碰路 径,确保车辆在最短时间内完成存取,提高停车位利 用率,减少存取车等待时间,实现停车设备自动化管 理.针对路径规划问题,国内外学者已对其进行了深 入研究,并相继提出了多种算法,主要有可视图法、 图搜索法以及人工势场法等.随着智能算法的不断 发展, Dijkstra算法、 A*算法、遗传算法、粒子群算法 以及蚁群算法等也被广泛用于解决各领域路径规划 问题 [1 -2].

Dijkstra算法是一种典型的单源最短路径算 法,因其采用遍历搜索方式求解最短路径,故得到的 最短路径往往具有可靠性高、鲁棒性好的特点,但也 存在时间复杂度高、搜索效率低、占用内存大等缺 陷 [3].蚁群算法是一种新型的仿生算法,该算法凭借 并行性、强鲁棒性、全局最优以及易与其他启发式算 法相结合等优点,被广泛用于解决TSP问题、路由 问题、二次分配问题以及车间调度问题等,并取得了 不错的效果 [4 -9].Johnson等 [2]研究了蚁群算法中信 息素对车辆路径选择的影响,仿真结果显示在允许 时间范围内,蚁群算法可有效解决逆向物流车辆路 径规划问题;康冰等 [4]将折返蚂蚁策略应用到蚁群 算法中,极大地提高了算法的收敛速度;黄震等 [8]将 蚁群算法和遗传算法进行了有效融合,通过将时间 窗因素引入蚁群算法来产生初始种群,然后由遗传 算法对其进行交叉和变异操作,得到了更优路径; Chaari等 [9]针对机器人在静态环境中的路径规划问 题,提出将蚁群算法与遗传算法进行有效结合,并通 过仿真实验验证了算法的可行性和有效性;王美珍 等 [10]将粒子群算法和蚁群算法进行了有效融合,极 大地提高了算法的搜索效率,缩短了路径长度;何少 佳等 [11]利用 Dijkstra算法的优点对蚁群算法进行 了改进,解决了逃生路径规划问题.

针对 AGV 存取车路径规划问题,将 Dijkstra 算法和蚁群算法的优点结合起来,提出一种基于Dijkstra -蚁群(ACO)的混合算法.利用链接可视图 法建立环境模型,采用 Dijkstra算法规划出 AGV 的初始路径,通过节点随机选择机制及信息素局部 更新和全局更新相结合的方式对基本蚁群算法进行 优化改进,然后选用改进的蚁群算法对初始路径进 行优化,并通过仿真测试验证混合算法的可行性和 有效性.

1 问题描述及环境建模

1.1 问题描述

为实现算法在 AGV 路径规划中的应用,须对 运行环境作如下假设 [12]: 1)假设 AGV运行环境为 二维有限空间; 2)假设图中障碍物已知,位置确定, 以不规则多边形表示,且忽略其高度方向; 3)假设 AGV在运行环境中匀速行驶,忽略 AGV 的启动、 转向、制动以及液压系统举升操作等因素; 4)以 AGV实际尺寸为基准,适当扩大障碍范围,为便于 仿真,将 AGV视为质点.

1.2 环境建模

利用 AGV自带的摄像头、雷达传感器及红外 传感器等采集AGV运行环境信息,其包括AGV的 起始车位、目标车位、障碍物以及 AGV待充电位置 等,根据上述信息通过链接可视图法创建 AGV 运行环境模型.图1 所示为采用链接可视图法在 MATLAB环境下创建的环境模型,模型规格为250m×250m,模型用6个黑色凸多边形表示障碍物区 域.图中各障碍物区域以及边界区域顶点之间的虚 线为自由链接线,黑色实线为 AGV的可行路径,以V开头的序列数代表各链接线的中点, S和T为AGV的起点和终点位置.

基于Dijkstra-蚁群算法的泊车系统路径规划研究

图1 agv二维工作环境模型


抱歉,此资源仅限赞助会员下载,请先
注意:本站资源多为网络收集,如涉及版权问题请及时与站长联系QQ:2766242327,我们会在第一时间内与您协商解决。如非特殊说明,本站所有资源解压密码均为:agvba.com。
weinxin
微信公众号
agvba是一个分享AGV知识和agv案例视频的网站。