AGV导航策略

AGV导航策略

本文整理于:https://blog.csdn.net/weixin_41987706/category_8532239.html 相关文章

AGV控制系统策略

利用集中式系统的优势,由上层控制系统(CCS) 同一分配资源并将任务分解,使多个机器人并发执行的策略。采用导航路径算法和多 AGV 调度控制策略,利用电子地图的通道约束条件尽可能减 少机器人之间的碰撞冲突,提升系统的运行效率。主要分为以下四个层次,如图所示:

2019052113535814.png

  • 地图层:地图层确定了仓库的基本大小和分区布局。主要包括停靠区、充电区、分拣台、货架为以及二维码铺设规则和选型等。
  • AGV 层:二维码为主的导航方式可以实时上传位置坐标。
  • 路径规划算法、调度控制策略保证多 AGV 的动态运行,拥塞控制策略确保不会发生大面积堵塞。
  • 导航分配层:CCS 控制中心是智能物流导航控制系统的核心,通过 Modus 通讯接口接收来自 ERP 处理的订单任务。采用多级子任务分配 算法动态选择 AGV,由 CCS 控制中心调用路径规划算法进行最优路径规划。同时,对 AGV 的运行状态进行监控和协同调度,确保在运行过程中多 AGV 协同作业。
  • 交互通讯层:数据通信连接导航分配层与 AGV 层,采用 Modbus RS485 通讯协议,实现 AGV 与二维码之间、中心控制服务器与 AGV 之间的数据交互。通讯是信息交互的介质,保证了 AGV 坐标实时上传 与 CCS 控制中心全局的动态任务分配。

外部接口:

  • 一是数据库,用于保存或更改坐标数据,并储存部分导航规划路径;

  • 二是企业资源计划(简称 ERP),主要实现物流订单录入和分拣管理。

AGV路径规划算法:

20190522092058849.png
20190522092118701.png

​ 多 AGV 路径规划是指,同一工作空间的多 AGV 按照某一性能指标各自搜索一条从起点到终点的优或近似优的无碰路径,各 AGV 要避开环境中的动静态障碍和其它运动着的 AGV。

​ 由于其它运动 AGV 的存在,使得多 AGV 路径 规划变得十分复杂,它是一个新的、独立的问题,而不是单 AGV 运动方法的叠加。多 AGV 之间的避碰策略是解决 AGV 之间发生碰撞的有效方法,也是多 AGV 与 单 AGV 路径规划根本的不同之处。

​ 从某种意义上来说,多 AGV 协作路径规划的能力决定了协作系统实现的可能性与协作的效率,从而对 AGV 之间路径的规划和协调提出了更高的要求。

  • 基于分区路径搜索的思想,采用栅格法,解决了 AGV 环境地图预处理问题,得到初始环境栅格地图;然后采用分区阈值改进基于 Canopy 的 K-means 聚类算法,实现初始栅格地图的分区,得到货架区和可行区这两种分区结构的栅格地图。
  • 为了解决 AGV 与货架的碰撞问题,根据环境地图中不同分区的特点, 在无货架的可行区,采用直线短路径;在货架区,通过对比不同的路径规划方法,采用基于 A *算法和蚁群算法的融合算法。为避免 AGV 与货架的碰撞,设计蚁群算法的距离矩阵,通过对比实验调试优算法参数,对多个分区的路径进 行整合修正,得到单 AGV 优路径。
  • 为了解决 AGV 与 AGV 的碰撞问题,在环境复杂的货架区,采用蚁群系统算法实现多个 AGV 的路径规划。
  • 为解决 AGV 之间竞争栅格碰撞问题, 设计了基于优先级的避碰策略,改进蚁群系统数学模型,使得多 AGV 之间通过蚁群信息素进行不直接通信,实现多 AGV 路径规划。
  • 为进一步提高方法的协调 性,设计了协作策略,预先判断每辆 AGV 是否需要重新规划路径,保证 AGV 行驶时都是无碰撞状态。

避碰策略

目前提出的避碰策略主要有速率调整法交通规则法优先级法几何修正法以及基于行为的避碰方法等。

  • 速率调整法:不会同时改变多个 AGV 速度。相反,它使用一定的规则来选择 AGV 并改变其速度,其他 AGV 速度保持不变。速度调整法中常用的策略是暂停策略。即当多个 AGV 发生碰撞的时候,某些 AGV 选择暂停一段时间,待其他 AGV 行驶过后,碰撞解除,再继续行驶。
  • 交通规则法:交通规则法是 AGV 在十字路口发生碰撞时的避碰规则。碰撞是由多个物体同时占据一条路线发生的。因此,可以通过对相关环境中的所有交叉点采取适当的措施来避免每次碰撞。通过枚举重叠的路线:沿相反方向、相同方向的路线和交叉路口,构建适应所有这些重叠路线的交通规则来避免碰撞。
  • 优先级法:优先级法解决了当发生碰撞时,谁该让路的问题。也就是按照一定的条件, 为每个 AGV 制定优先级。规划过程中,当优先级低的 AGV 遇到优先级高的 AGV 时,前者该给后者让路,也就是前者会被视为静态物体,从而可以把问题转化为单 AGV 路径规划问题。该方法的难点在于优先级的设定并且需要紧密结合实际需求。
  • 几何修正法:通常用于局部路径调整,指通过传感器信息预测到 AGV 之间 发生碰撞的危险区域,然后在 AGV 未到达该区域之前,调整 AGV 的几何路径实现避碰,比如在危险范围增加路径边,绕开该区域。该方法的优点是无需全局 调整路径,节省调整时间;但若几何路径的调整规则设置不当,则会增加路径长度。
  • 基于行为:主要有两种行为,躲避其它 AGV 和躲避货架。躲避货架是根据 AGV 当前探测到的环境信息,规划 AGV 如何在工作空间运动才能避开货架。躲避其它 AGV 是基于 AGV 之间的通 信,协调 AGV 之间的运动,以避免 AGV 之间发生碰撞。

基于栅格地图的环境建模

高效的环境建模方式是环境地图建模,使用栅格地图模型, 结合AGV运动模型给定栅格地图的栅格单元大小,创建初始的环境地图模型。

基于分区路径搜索思想,在初始的栅格地图模型上,使用聚类算法进一步划分地图,划分出不同大小的分区,后续在不同的分区使用合适高效的路径规划方法。

过程如下:

  • 根据 AGV 的实际尺寸设计栅格大小,并将 AGV 简化为二维栅格平面内可移动的质点。

    以 AGV 运动模型为例,如图 (a)所示,其运动方向为八个 方向,旋转半径为 1m,按照 1:1 的比例设置栅格的粒度 B=1m 。

  • 这样 AGV 就可在单个栅格内旋转,如图 (b)所示,角度为 β ,运行速度为v,运动方向的偏角为 α ,$$OX_t Y_t $$为t时刻 AGV 坐标系。

    20190522093437894.png

  • 使用栅格法对 AGV 工作空间进行初始环境建模。按照设定的栅格大小,将 AGV 工作空间划分成连通的二维栅格地图。所有栅格分为两种类型:货架栅格自由栅格,再将这些栅格信息保存到数组中。

    20190522093958843.png

    可以将栅格数组的序号转换 成 AGV 所在工作空间的物理坐标,这样 AGV 便得到了一条从起始点到达目标点的物理路径。

    栅格地图对应关系:

    假设栅格地图有X 行Y 列,则栅格数量 $$U =X * Y$$ ,栅格采用二维行列坐标$$P (i , j )$$表示,$$i ∈{ 1,2…, X}$$ ,$$j ∈ { 1,2…, Y}$$ 。$$D = {1,2…, U }$$ 表示所有栅格序号集,栅格$$P ( i , j)$$ 的坐标,$$i = mod(D , X) $$,$$j =Y−(D/Y)$$ 。其中,0 代表栅格$$P ( i , j)$$为自由栅格,1 代表栅格$$ P ( i , j)$$为货架栅格。

    图中,栅格地图有 35 行 35 列,栅格数量为 1225。如序号为 70 的栅格,其行列坐标为(2,35),值为 0,为自由栅格。

K-means 聚类的栅格地图分区

Canopy聚类不需要事先指定聚类中心的个数,且寻找聚类中心点的速度快。除此之外,在聚类算法实现中,引入了分区货架比例 α分区状态标记λ 和**分区阈值β **三个系数。

  • 分区货架比例 α 为是否需要继续细分提供依据:

    20190522100640319.png

  • 分区状态标记:如果分区内的货架较多,分区状态标记λ 取值 0 或 1。λ 取值 0,在该分区中使用较复杂的路径搜索算法;如果λ 取值 1 表示当前分区没有货架,可使用直线路径。

  • 分区阈值:分区阈值 β 为是否需要对分区继续进行划分的边界值, β 值越大,那么分区 的划分就越细,耗费时间越长; β 值越小,分区划分越粗糙,耗费时间越短。

    根据三个参数的定义,地图分区划分分为如下四种情况:

  1. α = 0 ,分区没有货架,不再进行细分,设置λ = 1 。
  2. 0< α<β ,分区内货架较少,则需要继续细分。
  3. β ≤α <1 ,分区内货架较多,可停止划分。设置 λ =0 。
  4. α = 1 ,分区内只有货架栅格,可停止划分。设置 λ =2 。
基于 Canopy 的 K-means 聚类的地图分区的步骤如下:
  1. 使用Canopy聚类,对所有的栅格数据进行分组处理,得到K个Canopy 集合和各个Canopy集合的中心。

  2. 将Canopy集合的数量K初始化K-means聚类算法的要构建的划分的数目;将各个Canopy集合的中心作为划分的K个簇中心;基于上述确定的簇数K 和簇中心对所有原始数据采用K-means聚类算法进行聚类优化处理,输出聚类优化结果。

  3. 根据聚类分区结果,计算每个分区的 α 值,若某个分区P i , 0 <αi < βi , 重复步骤1和步骤2;若 αi = 0 ,则该分区可停止划分,设置 λi =1 ,表示货架区; 若 αi =1 ,则该分区可停止划分,设置 λi =2 ,表示货架区;若 β i ≤αi <1,则该 分区停止划分,设置 λ i =0 ,表示可行区,其中i= 1,2,…,N 。 聚类分区地图的预处理流程图设计如图所示:

    20190522101202607.png

分区终的结果是分成两类分区:一类是没有货架的可行区,一类是货架数量达到该分区总数量一定比例的货架区,表示货架数量较密集。

算法对比

对于聚类算法,每个划分的聚类密度越大,则聚类效果越好:

对同一 副地图的162个栅格数据,采用3个聚类算法,分别进行了聚类划分,得到如图所示的结果对比,每个聚类划分使用不相连的颜色进行标记:

20190522101237847.png

20190522101252107.png

其数据分析结果如下:

201905221013314.png

从每个聚类算法的分区大 α 值和分区小 α 值的差值可看出,K-means 算法的聚类效果优于Canopy聚类算法,但是需要手动设定K值,采用阈值限制的基于Canopy的K-means算法聚类效果优于K-means算法,且灵活性更高。

基于分区和融合算法的单 AGV 路径规划

A*算法的核心思想是通过设置代价函数对未遍历点进行筛选,使搜索方向更偏向目标点,缩小搜索范围,进而提升搜索速度。路径成本表达式为:

​ $$f(n)=g(n)+h(n)$$

其中:

f(n):起点P—遍历中间点n—目标点g的路径总成本;

g(n):起点P—遍历中间点n之间的实际路径成本;

h(n):遍历中间点—目标点0的预估路径成本。

寻找到最优解的条件是f(n)尽可能接近起点P到目标点Q的真实路径成本,此时搜寻到的点都是最短路径的过程点。由于遍历中间点n的值g(n)己知,因此只能提升h(n)的估计准确性。根据AGV在作业环境中只有“上下左右”四个行走方向,所以选取$$h(n)=|X_n-X_Q|+|Y_n-Y_Q|$$,算法流程描述如下:

  • 新建两个列表用作路径数据点存储:openlist和closelist,openlist初始默认包含路径起点;
  • 计算与起点相邻的节点的f(n),按数值大小进行排序,f(n)最小节点m转移到closelist作为当前最优路径的过程点,其余节点留在openlist中做备用节点;
  • 若m为目标点,则停止搜索,并输出最优路径结果,否则继续;
  • 计算遍历中间栅格点m的所有相邻栅格点的f(n),若相邻节点n未加入openlist,及时添加,并令$g(n)=g(m)+d(m,n)$,此时n的父节点为m;若相邻点n在openlist中,当$g(n)>g(m)+d(m,n)$,更新$g(n)=g(m)+d(m,n)$,设置n的父节点为m;
  • 遍历完所有备选点后重复步骤(2)-(4),直到目标点Q出现在openlist中,搜索结束,按进入closelist的先后顺序输出中的节点栅格序列,该序列即为最优路径。

模拟 A 星算法的路径规划过程,如图所示,其中起始点为 A,目标点为 B,黑色为货架。假设 AGV 朝垂直方向移动的g( n) 为 10,朝水平方向移动的g( n ) 为 10,朝对角线方向移动的g(n ) 为 14,图中栅格的左下角为g( n ) 的计算结果:

20190522133238157.png

从起始点 A 开始检查其相邻栅格的f(n) ,图中栅格的左上角为f(n) 的计算结果, 然后持续向相邻方向的栅格扩展,选择f(n) 值小的栅格,直到搜索目标点 B 为止。图中用蓝色点标识后得到的 A 到 B 的路径,栅格右下角为h(n) 的值, 可以看出选择的栅格h(n) 数值都为小的。

A *算法具有较高的路径搜索效率,其特点是简单,降低了问题 的复杂性。但是在存在货架的实际环境中,使用 A *算法规划出的路径会与货 架顶点相交,不符合 AGV 实际工作中无碰撞行驶的需求。

赞赏
Nemo版权所有丨如未注明,均为原创丨本网站采用BY-NC-SA协议进行授权,转载请注明转自:https://nemo.cool/648.html

Nemo

文章作者

推荐文章

发表回复

textsms
account_circle
email

AGV导航策略
本文整理于:https://blog.csdn.net/weixin_41987706/category_8532239.html 相关文章 AGV控制系统策略 利用集中式系统的优势,由上层控制系统(CCS) 同一分配资源并将任务分解,使多个…
扫描二维码继续阅读
2020-08-11