基于改进合同网协议的多Agent的AGV调度协作机制

(北京物资学院 北京 100010)

在自动化物流系统中，AGV是一种重要而特殊的物料搬运设备，相比于传统的输送设备，AGV的运行线路设定灵活，小车的调度完全由控制系统灵活调配，具有自动化程度高、准确快捷、机动灵活和环保等优点，因此，在物流系统中得到广泛的应用，所以AGV调度的优劣对整个系统有着重要影响。AGV的调度就是AGV在空闲、仓库或工作站发出运送请求时，合理地安排各台AGV的工作流程。多AGV调度主要解决如下两个问题：

1)当一台AGV收到多个货物任务运送请求时，AGV对任务进行评估选择。

2)当多台AGV响应一个任务运送请求时，任务要对AGV进行评估抉择。

智能体(Agent)是一个具有自主性、主动性、持续性、交互性和自适应性的智能实体，可以在没有外界直接操纵的情况下，通过自身的传感器感知外部环境的变化，并通过效应器自主地对环境做出反应。而由多个智能体组成的多智能体系统(Multi-Agent System，MAS)具有敏捷、灵活、实时的优点，采用分布式体系结构，其每个智能体皆有一定的独立功能，且智能体之间的结构关系是动态可调整的，不同功能Agent组成紧耦合的运输调度管理体系结构，具有适应性、自组织和良好的协调性能，可以通过协调方式完成繁杂的整体运作。因此，可采用多智能体技术解决物流配送中的AGV调度问题。

一、合同网协议

(一)合同网的定义

合同网协作模型是Smith和Davis于1980年提出的,它通过引入市场中的招标—投标—中标机制,对系统的任务进行委托分配,从而解决资源、知识的冲突等问题。在合同网协议中，共有两种Agent，分别代表竞标的发起者和参与者。发起者Agent和参与者Agent通过竞标的方式进行任务的分发，并生成调度结果。发起者Agent接到任务后进行招标，各个参与者Agent进行投标，发起者Agent选择合适的参与者Agent执行任务,但是执行任务的参与者Agent可能由于资源的不足等原因导致无法完成任务,这时它转变为发起者Agent的角色，继续对该任务进行再招标。参与者Agent和发起者Agent的协商频繁导致通讯量迅速增加，容易造成信息阻塞。为了减少通讯量，本文对传统合同网协议进行简化，简化合同网协议可以使每次招投标过程的通讯次数减少至3次，这既保留了合同网协议的灵活性，又满足了应用场合的实时性需求。简化合同网协议中共有两类Agent：任务Agent(Task Agent,TA)和机器Agent(Machine Agent,MA)。其中TA发起招标并决策，MA参与竞标并进行投标，TA和MA相互协商协作共同完成任务。虽然简化了的合同网协议，可以减少两者间一定的通讯量，但是随着任务数量的增多，可能一个TA同时向一个或多个MA发起招标，一个MA同时接受一个或多个TA招标，两者之间会就任务情况频繁协商，还是容易造成信息阻塞。

(二)黑板模型

黑板模型是将异构知识源集成在模型中，形成一个专家系统结构模式。多个人类专家或主体专家协同求解一个问题，黑板是一个共享的问题求解工作空间，多个专家都能“看到”黑板。当问题和初始数据记录到黑板上，求解开始。所有专家通过“看”黑板寻求利用其专家经验知识求解问题的机会。当一个专家发现黑板上的信息足以支持他进一步求解问题时，他就将求解结果记录在黑板上。新增加的信息有可能使其他专家继续求解。重复这一过程直到问题彻底解决，获得最终结果。黑板模型主要由“黑板”、知识源(Knowledge Source)和控制结构3大部分组成。黑板模型己经被广泛使用,并且相应的技术己经比较成熟,但仍存在着2个问题：

(1)一个问题是黑板模型中公共数据库的强藕合性，虽然数据的集中存放给数据的一致性带来了许多益处,但是因为在求解的中间过程产生的数据都要传到黑板上,所以与黑板的数据传输成为系统的一个瓶颈。

(2)另一个问题是系统中数据格式的异构性。由于各知识源通过黑板进行交互时必须转换为规定的格式,这给具有不同知识及使用不同工具开发的的通讯与协作造成了一定的困难。

二、改进的合同网模型

针对黑板模型存在问题以及合同网模型运行机制的特点,提出了一种公告板模型，并将其应用于合同网模型中可以有效地提高合同网模型的性能。在公告板方式下,各Agent有自己的知识源,能以不同的格式存放在不同的地点.当想要参加协作时,只需将自己的名字、物理位置、资源、当前状态、如何与他们联系、可以提供的服务或需要得到的服务在公告板上登记,即可由公告板Agent辅助建立Agent之间匿名的互操作和知识共享.公告板Agent匹配任务及Agent,把适当的任务及Agent之间进行联系所需的信息传送给适当的Agent,为Agent之间进行联系提供路由服务。与任务有关的Agent可以通过公告板建立联系,进行点对点的通信。本文根据AGV的调度系统对简化合同网模型中的招标过程进行了修改：当发起者发布任务时,只是将任务信息发送给公告板,由公告板进行任务的匹配,并代替发起者向所有符合要求的参与者招标,然后,参与者再向发起者直接投标。这样既避免了发起者无限制的招标,也省去了发起者搜索参与者的信息。

三、结论

本文利用多智能体系统敏捷、灵活、实时的优点，结合目前合同网协议取得的研究成果，针对多AGV运行和调度的实际问题，分析研究了基于黑板模型改进合同网协议的agv调度协作机制，以实现agv调度过程的智能化、合理化。仿真结果表明，基于改进合同网协议后的agv调度机制具有良好的性能表现。本文中考虑引入了黑板模型来协调合同网协议中双方的信息沟通，减少了信息阻塞，提高了系统效率,但是实际情况中还可能发生中标的agent不履行任务即失信的行为，造成系统资源浪费。所以，在未来进一步研究中，可以考虑引入信用度和惩罚机制来约束和评估中标agent失信的可能性，提高系统运行效率。