浅析基于队工作的CDPS模型的解决方案

杨建卫

摘要：该文针对Wooldrige和Jennings提出基于队工作的合作分布式求解（CDPS）四个阶段模型进行了具体的分析，结合了计算机支持的协同工作（CSCW）方法并提出了系统实现的解决方法，用白板系统来进行教学的实例来说明系统管理员、教师、学生三个角色的令牌控制方案。

关键词：计算机支持协同工作；CDPS；Agent；队工作

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2018）23-0123-03

Abstract： This article analyze four stage models which base on CDPS of Human Teamwork Model， which is provided by Woodrige and Jennings. This article even provided how to solve the system which combined with the CSCW method. This article used a lot of recently successful model， For example GDSS.

Key words： CSCW； CDPS； Agent； Human Teamwork Models

1 引言

在多智能体系统里，每个智能体有不同的解决问题的能力，Agent系统中各个Agent必须要通过相互协作来进行问题求解。因此需要相适应的协调机制来实现不同智能体之间的任务分配及任务冲突后的消除解决方法。目前协调机制有了很多种不同的方法[1]：

1）通过部分全局规划的协调；

2）通过联合意图的协调；

3）通过相互模仿的协调；

4）通过规范和社会法律的协调。

其中联合意图的协调是人类队工作模型（Human teamwork models）的应用，根据队工作Wooldrige和Jennings提出基于队工作的合作分布式求解（CDPS）四个阶段模型。本文将结合多方面技术对基于队工作的CDPS的四个阶段的实现进行讨论。

2 Wooldrige和Jennings提出基于队工作的CDPS模型的四个阶段[2]

1）识别：

当在Agent群体中的某个Agent有一个目标，并且认识到实现目标可能的合作动作，CDPS就开始执行。

2）队形成：

向识别出存在可能的合作活动的Agent寻求帮助，形成Agent团队，在这个队中形成集体活动名义上的一类承诺。

3）计划形成：

集体中的成员对完成的工作的过程达成一致。

4）队活动：

Agent执行达成一致的联合活动的规划，并维持紧密的团队关系，该关系就是每个Agent要遵守的协议。

3 对CDPS模型的四个阶段实现分析

3.1 识别

识别过程是得到任务的Agent需要完成主要工作，在这个阶段形成了团队的动机。该Agent分析要解决的问题，根据自身的喜好，自身的能力，自身的代价这三个方面权衡团队是否应该形成，该Agent是团队的管理者，核心Agent，它很有可能具有分解问题的能力，当然问题的分解也可以由专门的Agent。作者個人认为把问题的分解放到队形成中较好，专门由问题分解Agent解决。

3.2 队形成

队形成大体上分为两个阶段：1）确定队的人员；2）确定队的集体活动名义承诺即团队的规章制度。

1）确定队的人员

确定队员当然用著名的RG.Smith的合同网协议实现比较好。该协议将Agent分为两种角色：管理Agent和合作Agent。接受任务的Agent成为管理者，管理者将任务通过信息缓冲区共享，其他Agent根据自身的状态和能力，以投标的方式进行队的人员组合。管理者可以利用合同网先进行问题分解Agent的招标，从而再由问题分解Agent和管理Agent协同招标其他行为Agent[3]。

2）集体承诺的形成

在这里的集体承诺是一个团体的规章制度。例如，在参加本项目团队的同时不能再参与其他团队的工作，如果要退出如何惩罚（赔偿违约金，降低该Agent的诚心度）。对于集体承诺而言，它可以是离线设计的，并且放在相应的数据库中等待管理者调用它。另外承诺是双方的，对于行为Agent而言可以不许诺集体承诺，并退出团队[4]。

对于CDPS的前两步都是问题的筹备工作，具体的问题求解还没有正是开始，另外，合同网协议和离线设计都比较成熟了，故而相对而言两步较为容易实现。

3.3 计划形成

集体中的成员对完成的工作的过程达成一致，作者把它分为两个部分1、角色的分配2、计划形成。

1）角色的分配

基于角色的计算机支持的协同工作系统的组成元素有3类：权限组（角色）、共享对象和协同活动。在计算机支持的协同工作系统模型里，包含多个功能权限的组形成了权限组（角色），这样可以很方便管理员对用户来授权。在某个权限组的用户就享有这组的权限，例如系统管理员拥有后台管理的功能，后台管理的功能包括相关菜单的权限、相关界面及控件的操作权限。协同工作是协调两个或者两个以上的不同资源或者个体，协同一致地完成某一目标的过程。协同工作可以从上而下的建立，例如上级活动可由多级嵌套的下级活动组成。协同工作中，用户在不同的权限组（角色），各个权限组分配了不同的权限，不同的权限完成不同的工作。对权限组的各种操作形成了任务，它是对共享对象方法的调用、同步动作、及对协同活动的管理[5]。

在这里作者认为在CDPS过程中也可以借鉴基于角色的CSCW 系统对每个Agent分配相应的角色，这样会方便协同活动的管理。

2）计划形成

每个Agent分配角色后，它们可以按照自己的等级或任务的不同进行协商而形成计划。协商是Agent小组的行为，计划形成是Agent小组决策的，使用Agent小组决策支持系统实现计划形成。

群体决策支持系统（GDSS） 是一种基于计算机的交互式系统，它通过辅助一群决策者的群决策过程，来解决特定领域的半结构化或非结构化问题。典型的GDSS由硬件资源、软件资源和决策者三部分组成。其中，硬件资源是指各决策者独立使用的工作站（或终端）、共享使用的外部数据库、模型库及I/O设备等硬件资源，还包括整个GDSS基于的通讯网络；软件资源包括在各决策者的工作站（或终端）上运行的决策支持软件、支撑GDSS的底层软件（如DBMS、MBMS）及网络软件；决策者不仅包括参与决策的人员，还包括决策过程的协调人员 [6]。

具体的过程为：

①参与决策的人员由一名协调者和若干名决策者组成；

②群决策过程由协调者主持，协调者结点给各决策者结点发送会议开始消息，通知决策者本次会议的目标、任务及有关情况，在收到全部回答报文后，宣布会议开始；

③各决策者独立进行决策，其间共享系统资源；

④各决策者决策完毕后，将决策方案发送给协调者；

⑤协调者依某种一致度对诸多方案进行权衡，如诸方案一致度不够，则向某些决策者发送协商报文，转回3，重新决策；否则，继续；

⑥得出最终的群决策方案，结束群决策过程。这种简化了的模型，假设群决策过程一定能成功，且完全屏蔽了各决策者相互间的通讯联系。

3.4 队活动

Agent执行达成一致的联合活动的规划，并维持紧密的团队关系。在每个Agent进行自己分配的子问题时，共享资源在不同Agent并发轮询的方式下，服务器怎样处理共享资源的并发操作来维持客户Agent上共享目标的一致性，是并发控制研究的关键问题。因此采用“队活动”的并发控制策略来解决并发访问，算法采用集中式令牌控制，流程图如图1，详细的算法过程如下（为了描述简单，特别定义：共享资源为shared resource，令牌为tokens）：

1）shared resource=tokens //给每个资源赋值一个令牌。

2）If（ agent want tokens ） then send post for token//想要使用公共资源，必须向服务器请求申请令牌。

3）server received application //服务器接收到申请。

4）If （shared resource in use ） then sent to the reject else turn the fifth step //如果资源在使用就拒绝，否则转第五步。

5）If（ multiple Agent for the same shared resource），// 多个Agent申请同一个资源

then sends to agent of the highest priority//发给优先级最高的Agent

else send to applicant//不存在竞争，那么就把共享资源的令牌发给申请者。

6）If （Agent gets token of shares a resource）//若Agent得到一个共享资源的令牌。

Then agent= operate on shared resources； //则获得对该共享资源的操作权

if （agent received a denial of command ）// 若收到拒绝信号

then agent = none //共享资源的操作权置空。

7）If （Agent= shared resource）at any time//如果某个agent长时拥有令牌

Then broadcast to oother Agent//那么广播其他agent

shared resource= occupied//标识该资源已被占用。

8） local agent=operation or other Agent= operation//本地或者其他agent操作改变共享空间。

9）if（Agenthas finished sharing resources） then released to the shared resource.//如果Agent用完共享资源就释放共享资源的令牌。

如上的叙述保证了共享工作空间的一致性，能方便地授予（收回）Agent对一些共享资源的操作权和优先权，使用令牌控制来解决操作权的分配。在算法中使用了请求原语、分配原语、拒绝原语、释放原语来实现令牌控制策略。

本文设定了系统超级管理员、经理、用户三种不同的角色，采用白板系统进行管理的实例来实现令牌的控制。系统超级管理员持有系统的最高权限，包括系统维护、功能设置、各种增加、删除、修改等操作、查看系统，给角色分配权限等。经理权限组可以对白板的消息进行查看、编辑及修改。用户权限组可以对所有消息进行浏览、交流等功能。token的发放和回收由经理权限组完成，只有用户获得token才有操作权限，没有获得token的用户可以申请并等待经理的发放，并发送询问申请令牌。在管理时候，经理拥有令牌，用户需要使用令牌必须向经理提出申请，经理同意后用户方可以使用令牌。

4 结论

人类队工作模型是一个比较好的一个实现合作分布式求解（CDPS）的方法，步骤明确，而且投入其中进行研究的专家也非常多，近年来，很多领域都非常关注的计算机支持协同工作（CSCW）对合作分布式求解也有很大的推动作用。在本文中对Wooldrige和Jennings提出基于队工作的合作分布式求解（CDPS）四个阶段模型进行了细化，并对每个阶段提出了一些实现的解决方法。

参考文献：

[1] Michael Wooldridge. 多Agent系统引论[M]. 北京：电子工业出版社，2003.

[2] 刘玉照，君祥南.基于群体的竞争信息分析系统[J].情报杂志，2000（4）：32.

[3] 石纯一，张伟，徐晖.多Agent系统引论[M].北京：电子工业出版社，2003.

[4] 华勇.基于CSCW的多AGENT协同式项目协调与管理系统的研究[J].高技术通信，2001.

[5] 胡晓容，明华.CSCW环境下基于角色的并发控制策略[J].计算机时代，2001（04）：25.

[6] 曹敏，金以慧.多Agent系统的研究和应用[J]. 清华大学学报，2000，40（52）.

[7] 宋德舜，麥中凡.计算机支持协同工作（CSCW）的研究进展[J].全国计算机新科技与计算机继续教育研讨会，1998.

[8] 李英.agent系统（MAS）研究进展[C].全球智能控制与自动化大会，2000 .

【通联编辑：光文玲】