基于改进合同网模型的AGV系统多车调度优化研究

余荣洋 金桂根 物流技术与应用 2023-09-06 17:32 发表于北京

随着物流行业智能化程度的提高，AGV在物流业内的使用范围越来越广。AGV不仅可以根据相应的指令实现对包裹的自动搬运，而且能提高分拣效率和安全性，从而提升企业的物流水平，给顾客更好的用户体验。针对AGV系统多车的优化调度，尤其是当任务订单过多时，如何对AGV进行合理的分配，以实现在满足订单时效的情况下，使AGV的运行效率实现最优，一直是国内外学者的研究热点。

在多种任务分配的优化方法中，多Agent方法是一个较优的选项。多Agent方法是指多个Agent之间在通信的基础上与环境进行交互，并相互协调以求共同完成系统任务的方法。多Agent系统中大多是使用分布式合同网协议作为其内部协作的沟通机制，合同网协议在分布式多Agent系统中的应用有其非常突出的一些优点，比如合同网协议的可再扩充性很好，处理复杂动态环境能力很强，所以在与多种分布式智能体系统的协作过程中的使用普遍。

合同网是将系统中的成员角色分为任务管理Agent和任务执行Agent，通过模仿经济行为中的“招标－投标－中标”机制实现任务分配。Agent可以利用对任务的投标值来进行各种相互的协作与竞争，争取以最优的全局效能和最低的时间代价来实现任务。由于传统的合同网模型是通过广播的方式来向系统内部的Agent发出各种任务信息以及其他相关的消息，感受到这些任务消息后的所有Agent成员均可以参与投标，一旦参加投标活动的Agent数量过多，就会直接导致整个系统内部的网络通信量过大，这增加了任务管理Agent的决策压力。

对此研究合同网的学者提出了多种多样的改进方案，比如：文献[1]在传统合同网基础上引入可信度模型，使得能力不足的Agent无法参与部分投标[1]。文献[2]借鉴了蚁群算法，将信息素加入招投标过程，并提出基于信息素的多Agent动态调度策略，从而减少通信量，增强决策实时性[2]。

文献[3]通过建立Agent能力模型和Agent执行任务描述，使多Agent系统的任务分配更适应于动态环境[3]。文献[4]提出利用Agent具有主动感知的特点，加入公共消息黑板作为合同网的传统媒介，让任务执行Agent通过公共消息黑板来感知任务[4]。文献[5]设计了基于多Agent通信的多任务协作时间调度算法，实现了额外代价最小化和窗口时间内完成任务最大化[5]。但上述文献中并没有将Agent的主动性和Agent的负载[6]、能力和信任度的综合考量结合起来。

本文从实际出发，考虑到在实际仓库搬运中，任务需进行优先级的划分，AGV优先对高优先级[7]和时间性强的任务进行运输。故本文在基于上述文献的基础上，对传统合同网算法的招投标阶段进行改良，同时为AGV加入任务缓冲池，不仅可以充分发挥Agent的主动感知的特点，还能使任务缓冲池中的任务根据其优先级更好地进行动态分配[8]，使得应用场景更贴合实际。在招标阶段，Agent通过对AGV的感知系数、能力和信任度等几个方面进行综合考量，使得Agent的主动性和智能性可以充分结合。

1.改进合同网模型动态任务分配框架

本文运输场景中的动态任务分配问题，主要涉及3种Agent：仓库Agent、数据库Agent和AGV Agent。

数据库Agent负责整个招投标过程中的信息采集和加工处理，并统一协调任务执行Agent的行为；仓库Agent负责在接收到订单消息之后制作标书，并将标书进行公布；当仓库Agent发布标书时，所有AGV Agent会根据标书信息先计算自身的感知系数，依据感知系数来决策是否进行投标；仓库Agent依据AGV Agent反馈的标书中的感知系数进行决策，选择与最合适的Agent进行签约。

以上对传统合同网的改进流程图，如图1所示[9][10][11]。

2.改进合同网模型的协作策略

（1）招标阶段

在本文中的运输场景中，当仓库Agent作为招标Agent在接收到订单信息之后，根据以下标书格式对订单信息中的数据进行收集和整理。

标书的格式为：

Contract=<Task ID，Category，Priority，Li，Le，Capability>

其中，Task ID：此次运输任务的唯一编码；

Category：此次任务要运输的货物种类；

Priority：此任务的优先等级，分别为1,2,3；

Li：此任务中所需搬运货物的装载位置；

Le：此任务中所需搬运货物的卸载位置；

Capability：执行此任务所需的能力。

在仓储系统中，可以用上面的方法将运输任务表述为：<TC00001,01,1,(IX,IY),(EX,EY),200KG>根据上述定义，这表示一项编号为TC0001，需装载的货物种类是01，任务优先级为1，需装载货物的位置为（IX,IY），需卸载货物的位置为（EX,EY），此任务所需任务Agent的最低装载量为200kg。

仓库Agent将标书进行公布，所有AGV主动去感知标书信息，当标书中的任务优先级比自身任务缓冲池中的任务优先级要高时，AGV开始计算自身反馈系数并决定是否要对相应任务进行反馈。

（2）投标阶段

每台执行任务的AGV的都配有任务缓冲池，任务缓冲池中最多有3个待执行的任务，当新的订单出现的时候，仓库Agent将订单信息整理成任务标书，每个任务标书只对应着一个订单，AGV对整理好的任务标书进行主动感知并计算自身的反馈系数，反馈系数跟AGV的负载情况和自身能力值有关。AGV负载过大或者自身能力值不能满足任务需求都会导致反馈系数达不到任务要求，则AGV不会对公布的标书信息就行投标。

①AGV负载系数

定义变量：Loadi表示为AGVi的负载系数，其根据优先级动态变化的，i为AGV的序号；表示AGVi的平均工作负载，

表示此时系统内平均工作负载最小的AGV的系数，

表示此时系统内平均工作负载最大的AGV的系数。Mik表示AGVi执行的任务，k代表AGV执行任务的顺序，例如M11表示AGV1在目前正在执行的搬运任务，M12表示AGV1在M11完成后将要执行的任务，以此类推；M0则表示新任务标书中待分配的搬运任务。TMik 代表完成任务Mik所需要的时间，例如TM23表示AGV2完成其第三项任务所需要的时间。

当AGV1进入工作状态后，其任务总数最多只有4个，由正在执行的任务和任务缓冲区的三个任务组成，可分别表示为M11，M12，M13，M14。若此时仓库Agent公布了一个新的任务M0，且优先级高于AGV1任务缓冲池的M14，则AGV1的负载量是只以M11、M12和M13数据为基础进行计算。

执行任务的总时间（T总）=执行当前任务（M11）仍需要的时间+完成任务缓冲池中的任务（M12 、M13）所需的时间+新的任务标书中任务（M0）所需的时间：

    (1)

AGV1平均负载量（    ）=执行任务的总时间

（T总）/任务总数：

   (2)

其他AGV的平均负载量以此类推。当系统内的AGV都计算得出自身的平均负载量后，此时，AGV1根据下方公式得出自身的负载系数（Load1）为：

  (3)

当Load1=0时，表明AGV1的工作负载为系统内最小，适合对新任务进行投标。

当Load1=1时，表明AGV1的工作负载为系统内最高，不适合对新任务进行投标。

当Load1＜Load2时，说明AGV1的工作负载比AGV2的工作负载低。

上述过程体现了负载系统的动态变化过程，即当M0出现在系统里面时，各执行AGV首先会检视自身缓冲池中的任务容量，若自身的任务缓冲池仍有剩余空间，则直接将执行M0预计所用的时间代入T总和 进行计算，得出其负载系数。若自身的任务缓冲池没有剩余空间时，则会检视自身任务缓冲池中是否有任务优先级低于M0的任务存在，若没有，则不对M0作出响应；若有低于M0的任务存在，如上述例子中的AGV1任务缓冲池里面的M14，当AGV1感知到M0出现时，AGV1首先检查了自身缓冲池容量，在确定自身的任务缓冲池没有剩余空间后，检视出自身任务缓冲池中有任务优先级低于M0的任务M14，所以在之后计算T总和时，剔除了执行M14预计所用的时间，加入了执行M0预计所用的时间。这一部分体现了负载系数的具有动态变化的特征。

②AGV的反馈值

定义变量：Peri表示AGVi对投标任务的反馈值；Loadi表示AGVi在投标任务时的工作负载系数。当AGV最大载重量满足标书中的能力值时，A=1，否则，A=0。

AGVi根据下方公式来计算自身的反馈系数

       (4)

（3）评标阶段

AGVi的感应系数、能力值[12]和信任度在文中具有不同的量纲级别和不同的物理含义，因此本文将对它们进行归一化处理。

①AGV能力值

在同一项任务标书中，AGV的能力值（Capi）与分配到该任务的可能性呈正相关。本文用AGVi完成标书任务的时间比值，来刻画其完成任务的能力大小。

定义变量：TM0 ：AGV完成与标书任务的时间；maxTM0 ：系统内的AGV预计完成标书任务的最长用时；minTM0 ：系统内的AGV预计完成标书任务的最短用时，那么，AGVi针对此项任务的能力值Capi为： 

  (5)

当 Cap1> Cap2时，说明针对此标书发布的任务，AGV1的能力值比AGV2的能力值高。

②AGV的信任度

另一个影响任务分配结果的是仓库Agent对AGVi的信任度。同样的，在同一项任务中，信任度越高的AGV分配到任务的可能性越大。

信任度可以从AGVi成功完成任务的次数来表示，随着AGVi成功完成任务次数的增加，其在仓库Agent的信任度方面会不断地积累与提高。

定义变量：Believei：仓库Agent对于AGVi完成任务的信任度；N为AGVi成功完成任务的总次数；Faili为AGVi中标之后因为自身能力不足而不能完成任务的次数，那么AGVi信任度为：

  (6)

仓库Agent从AGVi反馈的标书中得知其感知系数，再综合AGVi的能力值和信任度，综合三个要素来计算评价AGVi。

 (7)

Valuei表示仓库Agent对AGVi投标的评价值；Loadi表示AGVi对任务的感知系数；Capi表示AGVi自身能力值；Beli表示仓库Agent对AGVi的信任度。

AGVi将标书发送给仓库Agent，仓库Agent对所有投标标书进行评价排序，评价值最高者被分配到该任务。以上完整定义了合同网中任务分配策略的形式化表示。

1.仿真实验场景

SH物流中心是一个现代化物流项目，可对客户订单进行快速处理，并完成物料准确快速的存储、复核、集货、发运等业务。智能仓内运输系统包括AGV、机器人摆臂、货架和智能调度管理系统等。AGV主要负责立体库出库站台，机械臂工作台和月台之间的搬运，俯瞰图如图2所示。

2.仿真实验的条件

为了评价提出的多属性评价中标策略的性能，本文做了相应的对比仿真实验。仿真实验的条件如下： 

（1）任务属性：随机生成任务优先级为1,2,3的任务，分配比率为1:3:6。

（2）机械臂随时可以满足使用需求，当AGV到达机械臂工位时，机械臂可立刻执行货物搬运任务。

（3）系统中AGV数量：9台。

当任务需求为整托盘货物时，仓储系统的作业流程具体分解为：

STEP1仓储货架中的穿梭车将整托盘运送至AGV装载处；

STEP2 AGV装载整托盘，并将整托盘直接运送至月台装卸处；

STEP3 AGV将空托盘运送至空托盘组工位；

当任务需求为散托盘任务时，仓储系统的作业流程具体分解为：

STEP1仓储货架查询中是否有直接满足任务需求的散托盘。若有，AGV执行上述操作；若无，穿梭车将整托盘运送至AGV装载处；

STEP2 AGV装载整托盘，并将整托盘运送至机械臂工位处；

STEP3 机械臂工位将托盘上的货物搬运至输送线上；

STEP4 AGV将散托盘运回至仓储货架。

（4）结合作业流程分解，分解AGV搬运的动作周期：接托盘（升降）－转向上道－匀加速直线运动－匀速直线运动－匀减速直线运动－转向下道－放托盘（升降）。

（5）执行任务的总时间组成为：t通讯+t升降+n*t上下道+t直线。

3.基于多属性评价策略的调度优化结果分析 

AGV运行基础数据，如表1所示。基于改进合同网仿真实验，传统合同网系统运行数据和改进合同网系统运行数据，如表2所示。

本文针对传统合同网的协商机制进行了改进。在投标阶段，AGV利用主动感知的特点计算自身的感知系数并做出是否投标的决策。在评标阶段，仓库Agent通过对AGV的感知系数、能力和信任度进行综合考量，从而选择最优AGV来执行任务，对比实验证明了本文所提多属性评价中标策略的有效性和可行性。

本文基于一种理想状态下将多Agent技术与仓储物流系统相结合，同时充分运用Agent的主动性和智能性，可以使AGV系统能够灵活处理各种突发事件，增强系统的鲁棒性。后续研究会在本文的基础上，对机械臂Agent、货架Agent和AGV系统的协作做出进一步研究，使应用场景更贴合实际。