基于多传感器信息融合的自动化集装箱码头AGV定位问题研究外文翻译资料

摘要

智能仓库成为物流过程自动化的关键组成部分，从根本上提升生产力和降低成本。本文介绍了智能仓库自动引导车（AGV）系统的新型设计方案。提出了一种改进的经典Dijkstra最短路径算法，用于高效的全局路径规划。在多AGV的情况下，时间窗方法用于解决冲突和死锁的问题。此外，本地路径规划和自动定位分别通过使用基于启发式算法和蒙特卡罗定位算法来解决。进行基于Player/Stage模拟器的广泛数值实验，以评估建议的算法，对于一系列场景，结果很好地验证了其有效性。目前，拟议的设计方案被用于开发在实践中部署的AGV的原型。

关键词：AGV；改进的Dijkstra算法;路径规划

一 介绍

自动引导车辆（AGV）目前广泛部署在许多工业领域，例如智能仓库，物料搬运系统，灵活制造系统等。近几十年来，针对从不同方面设计和开发先进AGV的技术，已经做了大量研究工作。在^[1]中，作者概述了AGVS的现有调度和路线算法。^[2]提出了AGV控制和设计中的遗传方法。研究的最新进展旨在提高AGV的可靠性，可用性和鲁棒性，并大大降低生产成本。事实上，AGV的设计和控制涉及许多需要解决的技术问题，关键的是车辆调度和路线（例如路径规划）、本地化、障碍物避免、电池管理。

AGV的调度和路线本质上不同于图论中的常规路径选择问题，需要为多AGV系统中的不同代理人派遣任务并规划最优的无冲突路线，同时避免潜在的拥塞和冲突。在^[3]中，提出了基于时间窗口方法的无冲突最短双向AGV路线算法。在^[4]中提出了基于启发式的方法和动态多项式时间序列，用于任务分配，并且能够保证无死锁和无冲突的路线。在^[5]中研究了使用Petri网络的AGV死锁和冲突的避免。应该注意的是，虽然在文献中有各种各样的方法和建议可用于提高AGV的性能（例如^[6][7]），但仍然值得深入研究开发低计算复杂度和提高效率的先进解决方案。

自动定位对于AGV设计至关重要，目前有几种算法可用。最著名的包括扩展卡尔曼滤波定位（EKFL）算法、马尔科夫定位（ML）算法和蒙特卡罗定位（MCL）算法。基于卡尔曼滤波器的EKFL方法已经在许多机器人设计中被采用（例如^[8]）并支持非线性系统MCL是最近提出的基于概率的方法，已经在实践中应用^[9][10]，MCL方法通过降低蒙特卡罗样本量来提高其效率。

同时，本文提出了一种新型的AGV设计方案，采用集中控制架构优化控制多台AGV。设计考虑三重：（1）利用仓库拓扑图，通过添加搜索规则提出了改进的Dijkstra算法，用于提高路径规划的效率和鲁棒性;（2）采用基于时间窗方法的无冲突双向AGV路线算法，避免潜在的冲突和拥塞;（3）将蒙特卡罗定位算法用于自动定位。

本文的其余部分组织如下：第二部分描述了系统架构，其次是第三部分介绍了建模，路径规划算法和本地化中的提出的解决方案，第四部分介绍了仿真环境，并提出了几个关键的仿真结果，对上述算法解决方案进行了评估，最后在第五节中给出了一些结论性的评论。

二 系统架构概述

从控制实现的角度来看，系统架构可以分为集中控制或分散控制架构。前者可以确保最佳的控制性能，但具有有限的可扩展性，因为计算时间可能变得令人望而却步。相比之下，后一种控制范式可以在大型系统中扩展良好，但由于分布式任务分配而不能保证最佳控制性能，其中各个代理只保留全局系统信息的部分视图^[11]。

本工作采用的集中控制架构如图1所示。系统架构和操作可以描述如下，由于中央控制单元维护全局信息，集中控制范式可以确保代理导航的最佳控制，并防止与全局路径规划算法的冲突和冲突。在这种控制结构中，中央控制单元（例如PC）管理调度和路径规划。在各个AGV中，它们中的每一个与其相关联的多个传感器（即五个超声波传感器、激光传感器和仪表板传感器）和独立操作的子系统，例如，自动定位子系统和电池管理子系统。这些任务可以通过人机界面分配给AGV系统。在接收到任务信息（例如优先级，类型，起始点，目的地和时间），计算时间和资源需求时，中央控制单元可以将任务适当地调度到空闲AGV以执行任务。

图1. 集中的AGV控制架构

可以通过具有拓扑图的信息的路径规划算法来计算一组最优的无冲突路径，并使其可用于各个AGV。中央控制单元将监视所有AGV的运行状态，并且在发生意外或意外事件（例如员工进入仓库）时将重新计算路径，从而避免冲突，拥塞或死锁。一旦AGV接收到任务请求和确定的路径，它将在某些点加载或卸载货物来实施任务。运行的自动定位子系统将定期更新AGV位置信息，电池管理子系统将定期检查AGV的电源容量。在某些情况下，可以通过配置其操作模式手动操作AGV。

三 AGV建模，路径规划和自我定位

A.建模

1）工业环境建模：图2说明了智能仓库的二维模型，显示用于专用目的的不同节点（即站点）：货架和生产站是AGV可以装载或卸载货物的节点;站点用于空闲AGV，充电点可以用于AGV充电的地方。此外，激光片装在墙上，而架子也被用作激光传感器的标志。

图2. 工业智能仓库的环境模型

图3. 工业智能仓库的拓扑图

环境可以被建模为基于空间离散化的有限资源集。为了有效地执行数学分析和控制算法，智能仓库可以通过有向图呈现，其中交点和路径点是图形节点，路径是节点之间的弧。

更具体地说，在该工作中使用了表示为G=（N，A）的有向图，其中包含一组节点N=n₁，n₂，...，n_n以及一组加权弧，A=a₁，a₂，...，a_m。考虑到智能仓库中的道路几乎处于相同状态，我们根据弧长设定每个弧的重量。对于路径规划算法，我们做出以下假设：

a）：每个弧表示双向道路，每个AGV可以向前或向后移动，而转角为-180°

b）：在任何一段时间内，每个电弧只能由一只AGV占用

c）：每个AGV在正常运行条件下以恒定速度移动。在本文的实验评估中使用v=1m/s的速度

使用由271个节点和748个弧组成的智能仓库的拓扑图，如图3所示。在地图中，每个站（例如，货架，充电点）都有一个唯一的全局地址，由一组坐标（x，y，h），其中x和y是平坐标，h是加载或卸载高度。

2）AGV的运动模型：在这个工作中采用单轮驱动和转向，两个驱动轮支撑机械结构。图4示出了AGV的运动学模型。前轮是两个从动轮之间的距离为2b的驱动。两个从动轮之间的中点O是AGV车身的旋转中心，l是前轮之间的距离，车轮和中点O。

假设在智能仓库中车轮和地面之间只有滚动和无滑动。运动模型受到一系列非完整约束^[12]。其配置可以由四个广义坐标的向量q描述，包括固定框架中的地面点的位置坐标（x，y），相对于x轴测量AGV体方向的角度theta;和角度phi;相对于以正交向量K和J固定在AGV身体的移动坐标的K轴测量前轮方向。系统广义向量q需要满足以下约束：

(1)

前轮动力学模型可以表达如下：

(2)

AGV可以被有效地视为刚体，因此其身体的动力学模型可以描述如下：

(3)

上述动态模型将用于控制应用，例如蒙特卡洛定位算法的轨迹跟踪和运动模型。

图4. 全球和移动坐标系的运动模型

B.路径规划

1）全局路径规划：任务可以描述为T=（加载点A，卸载点B，优先级）。在AGV收到任务之后，将转至A点装载货物，然后移至B点卸货。完成任务后，如果有另外一个任务，它继续执行任务，否则返回到站点。为了正确地指示机器人，任务需要与识别的路径一起发送到AGV。

最终的目标以及路线的挑战是同时确定一组适用于多AGV的路径，同时最小化成本函数，提高系统生产力并避免冲突和拥塞。在此工作中，实现了基于Dijkstra最短路径方法的路径算法^[13]，通过添加一组精心设计的搜索规则，提高路径规划性能。时间窗口方法用于解决潜在的拥塞，冲突和死锁。最后所提出的算法可以通过使用一组相邻弧来找到次优解，但是具有增强的路径鲁棒性。

为了改进Dijkstra算法，应用搜索规则的集合，规则如下：

a）：向左转时，将tau;_l（tau;_l是转角的增加函数）加到f_成本（成本函数）。采用这种规则来避免不必要的转动，因为转向动作会导致额外的时间消耗。

b）：当右转时，将tau;_r（tau;_r=1/2tau;_l）加到成本上。规则2使右转更优先于左转，这有两个优点：（1）形成循环路径，这意味着向前和向后移动的道路可能不同;（2）根据规则1和规则2，首先直接先行AGV，然后右转，最后左转。

c）：如果其他AGV使用了弧，则将tau;_u（弧长的增加函数和共享相同弧的AGV的数量）添加到f_成本。根据规则3，AGV的路径将分布在整个空间，有效避免同一条路上的竞争，可以大大减少拥塞的可能性。

通过使用上面提出的改进的Dijkstra算法，可以同时计算多AGV的路径。但是在多AGV路径中可能存在冲突和死锁。为了解决这个问题，时间窗口方法如下。

如在拓扑图中假设的，每个弧只能同时被一个AGV占用。将AGV定义为AGV在电弧上移动的时间，当AGV移出电弧时，将其定义为t_out

(4)

l是弧的长度，v是AGV的恒定速度。此外，t_r表示当两个弧的角度不为零时AGV转动的时间费用，因此t_r随着角度的增加而增加。当确定AGV的路径时，也可以计算每个弧的时间窗口，表示为（arc_i，t_in，t_out）

图5显示了调度和路径规划算法。每个任务具有一定的优先级，即首先处理具有较高优先级的任务。当接收到任务请求时，将根据优先级排队。中央控制单元开始检查并识别空闲的AGV来分配任务。将派遣一个空闲的AGV来实现具有最高优先级的任务。如果没有足够的AGV可用，优先级较低的任务将保持等待，直到AGV可用。

改进的Dijkstra算法将计算路径并检查是否存在任何冲突或死锁。如果两个AGV在其路径上具有相同的弧线，则同一拱顶上的时间窗（t_in，t_out）重叠，这意味着在时间和空间中两个AGV的路径之间存在相同的交点，以及因此不能绝对保证无冲突，并且需要重新计算路径，直到找到一组适当的路径。

基于在环境中存在许多事故的观察，例如由于仓库人员的某些原因，AGV的故障或环境发生变化，导致系统出现新的冲突，监控程序需要运行以监督所有AGV。当发生新的冲突时，该算法能够通过重新计算AGV的一组新路径来应对事件。最后，每个AGV将任务执行的结果发送回中央控制单元。

2）本地路径规划和障碍避免：路径数据是一组弧（由初始点和最终点定义），因此每个AGV必须达到一系列点才能实现该任务。为了找到两点之间的最小路径，使用了A*算法。A*算法是一种基于启发式的搜索算法，可以评估成本函数，并导致计算复杂度低的次优解。所以这是一个适合本地路径规划的算法。

当AGV在智能仓库中移动时，超声波将检测到AGV前面是否有任何障碍物。障碍物避免策略是环境已知下的难题。因此，可以以AGV等待直到障碍物被检测到障碍物移开的方式来实现。如果仪表板传感器检测到物理故障，AGV将停止并寻求指示。

C 蒙特卡罗定位算法

定位误差主要是由于两个原因：一个是制动器错误（例如车轮和地面之间的滑动，电机错误），另一个是测量误差（例如编码器反馈误差，激光角度误差）。因此，定位算法对于提供AGV位置的准确估计是重要的。在这项工作中，采用^[14]中提出的蒙特卡罗定位（MCL）算法来解决全局定位问题。

蒙特卡罗定位（MCL）是一种粒子滤波算法，将运动模型和测量模型代入粒子滤波算法^[15]。它表示作为一组M个粒子的bel（x_t）（bel（x_t）=p（x_t|z₁：t，u₁：t））chi;_t=q_t¹，q_t²，...，q_t^M。它首先从分布贝尔（x_t-1）中采样粒子的加权重采样，然后应用运动模型和测量模型，最后选择代表更好假设的粒子。以下算法给出了蒙特卡罗定位^[16]算法的细节。

命令：时间为0时，一组单元为i:

while(Exploring)do

k=k 1

if(ESS(W)lt;beta;lowast;M)

Inde

剩余内容已隐藏，支付完成后下载完整资料

英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[140255]，资料为PDF文档或Word文档，PDF文档可免费转换为Word