AGV吧-agv小车-基于智能仓储多AGV的地图构建和调度算法研究_邱歌

  • 2
  • 685 views
  • A+
所属分类:AGV设计资料
摘要

针对智能仓储中多AGV运作可能引发的碰撞、死锁、运行低效等问题,从地图构建和调度算法两方面探索设计,前者将系统资源合理分配设置来预防可能导致的死锁,而后者通过优化调度和资源锁控制避免了AGV之间的碰撞.通过系统仿真证明,该策略能实现多个AGV在无碰撞和死锁的情况下运行至各自目标点,从而完成大批量订单.

AGV吧-agv小车-基于智能仓储多AGV的地图构建和调度算法研究_邱歌

AGV吧-agv小车-基于智能仓储多AGV的地图构建和调度算法研究_邱歌

不同于传统的电商仓库的人工分拣模式 , 智能仓储以中心系 统 (Kernel 系 统 )为 控 制 中 心 ,和 企 业 资 源 计 划 系 统 (Enterprise Resource Planning ,简 称 ERP)、仓 库 管 理 系 统 (Warehouse Management System ,简称 WMS)实现对接 。 订单从ERP 下达给 Kernel ,Kernel 从 WMS 中匹配资源信息并进行资源调度和指导自动导航车 (Automated guided vehicle , 简称AGV )进行协调运作 ,利用成本大幅降低的 AGV 系统 ,真正实现了物流仓库从 “人到货 ”向 “货物到人 ”的“机器换人 ”操作模式转变。目前为止 ,市场上已经有一些比较成熟的智能仓储系统和AGV 产 品 应 用 于 实 际 生 产 中 , 例 如 国 外 的 亚 马 逊 Kiva Systems 公司 ,国内的阿里巴巴菜鸟物流 、海康威视等 。
在 现 有 研 究 成 果 中 , 单 机 技 术 已 经 比 较 成 熟 , 但 如 何 多AGV 协调合作 ,至今行业没形成一定的标准 ,以往研究问题时 ,只对单 AGV 进行规划或将多 AGV 的路径规划问题分解成单机问题 [3]。 但在实际仓库中 ,由于 AGV 和货架都在每时每刻移动变化 ,地图环境信息也在动态变化 ,从而带来复杂的路况 ,从而引发 AGV 之间可能形成堵塞甚至碰撞等问题 。本研究旨在实现智能仓库多 AGV 协调运作 [4-6],避免发 生碰撞 、死锁和局部甚至大面积拥堵问题 ,最终实现在复杂多变的环境下系统的稳定 、高效 、可靠 。

1 智能仓储多 AGV 问题形成机理

1.1单 AGV 运作周期

在智能仓储系统中 ,取一次货物 ,为 AGV 指派并执行一个任务 ,AGV 只负责为工人取货架 , 工人负责从货架中挑取货物并装箱 。
一个 AGV 的运行周期大致分为如下 10 步 (初始设定在货架下面 ):①识别确认对应货架 ,②原地旋转抬起货架 ,③运载货架出库 ,④驮行 ,⑤送达货架至分拣台 ,等待人员分拣 ,⑥现场人员确认取出物品 ,⑦驮行货架 ,⑧到达指定入库站点 ,⑨放置货架 ,⑩停靠或充电 。

1.2碰撞冲突分类

以栅格地图形式的仓库为例 ,多 AGV 之间的碰撞产生类型可以分为 :①同向行驶横向碰撞 ;②对向行驶横向碰撞 ;③侧面碰撞 。分别如图 1、图 2、图 3 所示 。其中地图坐标以栅格为单位 ,A 和 B 代表 AGV 小车 ,箭头代表行驶方向 ,灰色栅格是障碍物(不可通行 )。
AGV吧-agv小车-基于智能仓储多AGV的地图构建和调度算法研究_邱歌
在上节中的 ④→⑤和⑦→⑧形式过程中 ,多个 AGV 之间需
要进行避障 ,同向行驶的 AGV 可能导致的前后碰撞可以和 ⑤一样采用超声波检测和排队算法进行等待 ,车与车之间保持车距即可避免 。
AGV 的障碍物超声探测仪一般安置在行驶方向的正前方 ,
当探测到对面行驶过来的 AGV 时,假设小车 A 优先级低于 B,A 正好在 B 需要行驶的路线上 ,此时若 A 暂停避让 ,B 也无法继续向前行驶 。 若 A 重新规划路径 ,因为仓库信息复杂多变 ,可能会有如图 4 所示情况 ,此时会引起连锁反应 ,需要周围 AGV 都重新进行规划 ,这样会带来很大的计算量和暂时的局部拥堵 ,有时候可能多个 AGV 规划时无解导致最终死锁 。
因为现有 AGV 探测距离和范围的限制以及 AGV 在仓库中很高的行驶速度 ,图 3 所示的情况侧面障碍物不容易探测到 ,探测到也不能立即停下 。因此会发生侧面碰撞冲突 。

1.3智能仓储中的死锁成因

智能仓库系统产生死锁的原因主要是 :
1)系统资源不足 :智能仓库中因小车和货架位置不断变更引起路况复杂多变 ,AGV 能行走的路径有限 , 一个站点每次最多只能被一个 AGV 占据 。
2)运行推进的顺序不当 :若智能仓库系统不能有效调度管理 ,会引起管理混乱 。
3)资源分配不当 :缺乏有效的资源调度和任务分配以及约束条件 。

2 智能仓储多 AGV 系统模型设计

2.1死锁预防

经分析 ,在系统设计和调度管理等方面为了不让表 1 中的四个必要条件成立 ,需要对资源进行高效的规划 ,确定资源的合理分配算法 ,避免单 AGV 永久占用系统资源 ,可以最大可能地避免 、预防和解除死锁 。

2.2地图设计规范

确定地图设计规范 ,能够有效避免 AGV 运行过程中发生堵死、碰撞等事故 ,提高运行效率和失误率 。
(1)站点
此研究方案针对栅格地图 ,每个站点占据一个栅格 ,栅格大小均相同 。
站点分为两种 :货位点和通道点 。
货位点可放置货架 ,AGV 可以运行至货架底部 , 也可长时间停留在此点 。
通道点不能放置货架 ,AGV 可以通过该点或在该点短暂停留,不能长时间停留在此点 。如图 7 所示 ,P1 为货位点 ,P2 为通道点 。
(2)路线 (Path )
路线指的是两点之间可行走的路线 , 规定地图拓扑图是有向图 。一个区域通道站点必须组成图 5 所示环路 (逆时针或顺时针方向 ),这样可实现图 6 中每两点之间均可达 。地图中唯一可双向行驶的路线如图 7 所示 。
(3)AGV 小车
AGV 小车在地图中的模型如图所示 ,有唯一编号 ID,此处是 0001 。

2.3调度算法

2.3.1Bundle 区
为避免发生侧面碰撞和对象行驶的横向碰撞问题 , 将以可能发生碰撞的站点为中心的路段绑定到 Bundle 区中 。
2.3.2Bundle 区类型
(1)交叉路口
如图 8 所示 ,以交叉路口站点 P0 为冲突中心 ,Bundle 区包含路线 :P0→P1、P0→P3、P5→P0 、P6→P0。
(2)货位点出口
如图 9 所示 ,以出库入库站点 P1 为冲突中心 ,Bundle 区包含路线 :P3→P1、P0→P1。
2.3.3调度策略
以图 10a 为例 ,可看出该地图有两种类型的 bundle 区域 。现放置两个 AGV :小车 0001 和小车 0002 。初始位置分别在站点 P15 和站点 P16。
假设 :小车任务优先级相同 ,此处实验小车 0001 比小车0002 优先级高 。 小车为同构型 ,各项参数指标均相同 。
(1)构建 Bundle 区域
此 Bundle 区 域 定 义 为 Bundle - 0001, 包 含 成 员 PathP0→P1、Path P0→P3、Path P5→P0、Path P6→P0。控制中心是交叉点 P0,边界点包括 P1、P3、P5、P6 。
(2)假设几乎同时指派下达两个任务 :
小车 0001 的任务是从 P15 行驶至 P9, 小车 0002 的任务是从 P16 行驶至 P13。
(3)为 AGV 规划行驶路径 。
小车 0001 :P15→P5→P0→P1→P2→P9
小车 0002 :P16→P6→P0→P3→P4→P13
(4)行驶路线跟踪
1)当小车 0001 和小车 0002 同时行驶到达 Bundle -0001区边界 (点 P5 和 P6)时 (如图 10b 所示 ),向控制中心发送申请需要 在 下 一 步 (分 别 为 P5→P0→P1 和 P6→P0→P3)进 入 Bundle -0001区行驶 。
2)若二者同时 (精确到 1ms )申请进入 bundle -0001区,则判定小车 0001 (优先级较高 )优先驶入 ;否则谁先向控制中心发出申请 ,谁优先驶入该区 ,其余车辆在区域边界和外侧排队等待wait /pause 。
3)假设小车 0001 获得优先行使权 ,当小车 0001 进入 Bundle -0001区时将该区域上锁 , 小车 0002 自动被拦截至 P6 原地等待 ,随后小车 0001 到达交叉点 P0(如图 10c 所示 )。
4)当小 车 0001 经 过 Bundle 区 边 界 点 P1,反 馈 给 控 制 中心,判断下一步是否驶离 Bundle 区,若驶离则释放锁 (如图 10d所示 )。
5)确定小车 0001 驶离 Bundle 区域 ,此时小 车 0002 进 入Bundle 区域并上锁 ,小车 0002 行驶至交叉点 P0(如图 10e 所示 )。
6)小车 0002 行驶至 Bundle 区边界点 P3,随后驶离 bundle 区 ,控 制 中 心 释 放 锁 ;此 时 小 车 0001 已 经 到 达 目 标 点 P9 ,完成任务 (如图 10f 所示 )。
7)小车 0002 经过 P4,到达 P13,完成任务 (如图 10g 和图10h 所示 )。
(5)结果分析
由实验结果可看出 ,系统能够通过控制中心实现多 AGV 之间的协作运行 ,从而避免冲突 。

3 实验

3.1实验地图数据模型

(1)实验平台
openTCS 是一个能控制 AGV 的交通控制系统平台 ,内部嵌入有路由算法 ,调度资源等初始算法 。本实验借助其仓储视图监控功能和路由算法功能 ,嵌入自己的调度资源算法和地图设计 。
(2)实验环境 (如图 11 所示 )
1)地图为 21(宽度 )* 10(高度 )大小的栅格地图 。
2)站点 210 个 ,货位站点 96 个 ,通道站点 114 个 。
3)多个 AGV (此处设置 8 辆),初始位置随意放置在货位点 。
(3)约束条件
小车初始位置和停留位置均只能在货位点 ,过道站点不可停留 。

3.2实验结果分析

订 单 任 务 一 共 有 4 个 状 态 (如 图 12 所 示 ):DISPAICHABLE (待分配 )、DISABLE (无路 可 走 或 无 小 车 可 以 分 配 )、BEING_PROCESSED(正在执行中 )、FINISHED (完成 )。
本研究共有 20 组测试订单任务 ,每组订单 40 个,共 800 个样例。测试发现所有的订单均完成 ,期间没有发生堵塞碰撞 ,也无死锁。保证所有 AGV 在一般情况下无碰撞和死锁地运动至目标位置 。

文件下载 AGV吧-agv小车-基于智能仓储多AGV的地图构建和调度算法研究
下载地址
weinxin
微信公众号
agvba是一个分享AGV知识和agv案例视频的网站。

评论已关闭!