合同网协议

合同网协议(contact net protocol,CNP)由Davis和Smith在1980年提出,建立在一个非集中式的市场结构基础上,为了解决任务分配的一个协同过程。它提供一种协议,规定任务指派和有关的角色。整个协议中有两类角色——管理者(manager)和合同者(contractor)。管理者负责监督任务的执行情况并对任务结果进行处理。合同者负责具体任务的执行。每个结点可以代表一个Agent,结点根据需要可以动态地承担不同角色。

合同网协议基本思想就是通过招标-投标-中标过程进行任务分配。首先是公布标书;然后是投标:合同者根据自身的能力来评估这个任务并向管理者投标;接着是授予:管理器评估收到的投标并选择合适的承包商,授予合同;最后是合同签订:管理者等待合同的最终结果。

合同网协议是一个完全分布式的求解模式,已经成功地应用于多个系统并做了相应改进。其不足在于,忽略了Agent之间可能存在的矛盾,没有考虑冲突的识别和消解;而且,由于所有承包商都可以参加投标,管理器必须评价大量的投标书,合同网通信开销和资源占用都较大。针对经典合同网协议中的一些缺陷,许多研究人员对它进行了改进。

针对在公布标书阶段,所有节点都可以参加投标,管理器必须评估大量的投标书,可能会造成管理器瓶颈和信息拥塞等问题,目前为止试图解决的方法有:集中选择(focused addressing)、接收者限制(audience restrictions)、忽略过期消息(ignoring outdated message)和基于案例的推理(CBR)等。集中选择是指在高度约束的情形下,有空闲资源(能力)的Agent宣布其资源(能力);而在低约束的情形下,有任务的主体宣布其任务。这种以公布任务为重点的协商,会减少信息量,避免了在高度约束情形下宣布过多任务而完成很少;在低度约束情况下资源相对于任务来说,相对充足。接收者限制是指管理器只对那些最有潜力完成任务的主体宣布任务。当管理器具有各个节点能力的具体知识,就能粗略估计处理子问题的可能的候选节点,这将大大减少公布标书和投标的通信量。基于案例的推理协议,可以充分利用过去有用的知识,还能适应主体能力及环境的动态变化,大大减少通信量,在一定程度上缓解了管理器瓶颈和信息拥塞问题。

上述几种方法虽然对经典合同网进行了改进,但都存在着一定的问题,以至于在实际应用中很难实现。例如,接收者限制方法需要管理器具有各个节点能力的具体知识,这在很多条件(比如非协作环境)下是不太可能实现的;集中选择方法中存在约束程度判断的问题,另外还要求全局知识,在很多情况下也是不切实际的;基于案例的推理协议方法在主体能力不变的静态环境中能取得满意的效果,但是在主体能力动态变动的环境中,该方法将完全失效,因为过去的案例由于主体能力的变动已经不再适用。

从上述文献分析来看,传统的合同网以及一些改进的合同网协议多数着重考虑和试图解决效率和信息堵塞问题;合同网协议只是提供了一个粗范的合同者的选择步骤和框架,具体的如何操作尤其是对于管理者和合同者如何进行选择评判,并没有一个详细的标准和指导策略。每一个使用者在实际应用过程中都必须对其进行改进和进一步的定义。其次,招标方的授标决策很大程度上取决于合同者的承诺,如果合同者不诚实,没有考虑如何对其进行约束。选中的合同方接到授予信息后,发生反悔,或者是恶意投标,这样管理者必须重新进行合同者的选择,会造成时间的浪费和任务的延误。最后,多Agent系统本身是个社会系统,不完全是多个Agent之间简单的协商,协商是遵循一定的规范,目标和任务也是在一定的背景中完成的,而合同网协议忽略了利用领域背景中的知识和规范来指导Agent之间的协商。