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 时，假设小车 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 在一般情况下无碰撞和死锁地运动至目标位置。

1. 本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长 QQ2766242327进行删除处理。
2. 本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END