淺析基于隊(duì)工作的CDPS模型的解決方案

楊建衛(wèi)

摘要：該文針對(duì)Wooldrige和Jennings提出基于隊(duì)工作的合作分布式求解（CDPS）四個(gè)階段模型進(jìn)行了具體的分析，結(jié)合了計(jì)算機(jī)支持的協(xié)同工作（CSCW）方法并提出了系統(tǒng)實(shí)現(xiàn)的解決方法，用白板系統(tǒng)來進(jìn)行教學(xué)的實(shí)例來說明系統(tǒng)管理員、教師、學(xué)生三個(gè)角色的令牌控制方案。

關(guān)鍵詞：計(jì)算機(jī)支持協(xié)同工作；CDPS；Agent；隊(duì)工作

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

在多智能體系統(tǒng)里，每個(gè)智能體有不同的解決問題的能力，Agent系統(tǒng)中各個(gè)Agent必須要通過相互協(xié)作來進(jìn)行問題求解。因此需要相適應(yīng)的協(xié)調(diào)機(jī)制來實(shí)現(xiàn)不同智能體之間的任務(wù)分配及任務(wù)沖突后的消除解決方法。目前協(xié)調(diào)機(jī)制有了很多種不同的方法[1]：

1）通過部分全局規(guī)劃的協(xié)調(diào)；

2）通過聯(lián)合意圖的協(xié)調(diào)；

3）通過相互模仿的協(xié)調(diào)；

4）通過規(guī)范和社會(huì)法律的協(xié)調(diào)。

其中聯(lián)合意圖的協(xié)調(diào)是人類隊(duì)工作模型（Human teamwork models）的應(yīng)用，根據(jù)隊(duì)工作Wooldrige和Jennings提出基于隊(duì)工作的合作分布式求解（CDPS）四個(gè)階段模型。本文將結(jié)合多方面技術(shù)對(duì)基于隊(duì)工作的CDPS的四個(gè)階段的實(shí)現(xiàn)進(jìn)行討論。

2 Wooldrige和Jennings提出基于隊(duì)工作的CDPS模型的四個(gè)階段[2]

1）識(shí)別：

當(dāng)在Agent群體中的某個(gè)Agent有一個(gè)目標(biāo)，并且認(rèn)識(shí)到實(shí)現(xiàn)目標(biāo)可能的合作動(dòng)作，CDPS就開始執(zhí)行。

2）隊(duì)形成：

向識(shí)別出存在可能的合作活動(dòng)的Agent尋求幫助，形成Agent團(tuán)隊(duì)，在這個(gè)隊(duì)中形成集體活動(dòng)名義上的一類承諾。

3）計(jì)劃形成：

集體中的成員對(duì)完成的工作的過程達(dá)成一致。

4）隊(duì)活動(dòng)：

Agent執(zhí)行達(dá)成一致的聯(lián)合活動(dòng)的規(guī)劃，并維持緊密的團(tuán)隊(duì)關(guān)系，該關(guān)系就是每個(gè)Agent要遵守的協(xié)議。

3 對(duì)CDPS模型的四個(gè)階段實(shí)現(xiàn)分析

3.1 識(shí)別

識(shí)別過程是得到任務(wù)的Agent需要完成主要工作，在這個(gè)階段形成了團(tuán)隊(duì)的動(dòng)機(jī)。該Agent分析要解決的問題，根據(jù)自身的喜好，自身的能力，自身的代價(jià)這三個(gè)方面權(quán)衡團(tuán)隊(duì)是否應(yīng)該形成，該Agent是團(tuán)隊(duì)的管理者，核心Agent，它很有可能具有分解問題的能力，當(dāng)然問題的分解也可以由專門的Agent。作者個(gè)人認(rèn)為把問題的分解放到隊(duì)形成中較好，專門由問題分解Agent解決。

3.2 隊(duì)形成

隊(duì)形成大體上分為兩個(gè)階段：1）確定隊(duì)的人員；2）確定隊(duì)的集體活動(dòng)名義承諾即團(tuán)隊(duì)的規(guī)章制度。

1）確定隊(duì)的人員

確定隊(duì)員當(dāng)然用著名的RG.Smith的合同網(wǎng)協(xié)議實(shí)現(xiàn)比較好。該協(xié)議將Agent分為兩種角色：管理Agent和合作Agent。接受任務(wù)的Agent成為管理者，管理者將任務(wù)通過信息緩沖區(qū)共享，其他Agent根據(jù)自身的狀態(tài)和能力，以投標(biāo)的方式進(jìn)行隊(duì)的人員組合。管理者可以利用合同網(wǎng)先進(jìn)行問題分解Agent的招標(biāo)，從而再由問題分解Agent和管理Agent協(xié)同招標(biāo)其他行為Agent[3]。

2）集體承諾的形成

在這里的集體承諾是一個(gè)團(tuán)體的規(guī)章制度。例如，在參加本項(xiàng)目團(tuán)隊(duì)的同時(shí)不能再參與其他團(tuán)隊(duì)的工作，如果要退出如何懲罰（賠償違約金，降低該Agent的誠心度）。對(duì)于集體承諾而言，它可以是離線設(shè)計(jì)的，并且放在相應(yīng)的數(shù)據(jù)庫中等待管理者調(diào)用它。另外承諾是雙方的，對(duì)于行為Agent而言可以不許諾集體承諾，并退出團(tuán)隊(duì)[4]。

對(duì)于CDPS的前兩步都是問題的籌備工作，具體的問題求解還沒有正是開始，另外，合同網(wǎng)協(xié)議和離線設(shè)計(jì)都比較成熟了，故而相對(duì)而言兩步較為容易實(shí)現(xiàn)。

3.3 計(jì)劃形成

集體中的成員對(duì)完成的工作的過程達(dá)成一致，作者把它分為兩個(gè)部分1、角色的分配2、計(jì)劃形成。

1）角色的分配

基于角色的計(jì)算機(jī)支持的協(xié)同工作系統(tǒng)的組成元素有3類：權(quán)限組（角色）、共享對(duì)象和協(xié)同活動(dòng)。在計(jì)算機(jī)支持的協(xié)同工作系統(tǒng)模型里，包含多個(gè)功能權(quán)限的組形成了權(quán)限組（角色），這樣可以很方便管理員對(duì)用戶來授權(quán)。在某個(gè)權(quán)限組的用戶就享有這組的權(quán)限，例如系統(tǒng)管理員擁有后臺(tái)管理的功能，后臺(tái)管理的功能包括相關(guān)菜單的權(quán)限、相關(guān)界面及控件的操作權(quán)限。協(xié)同工作是協(xié)調(diào)兩個(gè)或者兩個(gè)以上的不同資源或者個(gè)體，協(xié)同一致地完成某一目標(biāo)的過程。協(xié)同工作可以從上而下的建立，例如上級(jí)活動(dòng)可由多級(jí)嵌套的下級(jí)活動(dòng)組成。協(xié)同工作中，用戶在不同的權(quán)限組（角色），各個(gè)權(quán)限組分配了不同的權(quán)限，不同的權(quán)限完成不同的工作。對(duì)權(quán)限組的各種操作形成了任務(wù)，它是對(duì)共享對(duì)象方法的調(diào)用、同步動(dòng)作、及對(duì)協(xié)同活動(dòng)的管理[5]。

在這里作者認(rèn)為在CDPS過程中也可以借鑒基于角色的CSCW 系統(tǒng)對(duì)每個(gè)Agent分配相應(yīng)的角色，這樣會(huì)方便協(xié)同活動(dòng)的管理。

2）計(jì)劃形成

每個(gè)Agent分配角色后，它們可以按照自己的等級(jí)或任務(wù)的不同進(jìn)行協(xié)商而形成計(jì)劃。協(xié)商是Agent小組的行為，計(jì)劃形成是Agent小組決策的，使用Agent小組決策支持系統(tǒng)實(shí)現(xiàn)計(jì)劃形成。

群體決策支持系統(tǒng)（GDSS） 是一種基于計(jì)算機(jī)的交互式系統(tǒng)，它通過輔助一群決策者的群決策過程，來解決特定領(lǐng)域的半結(jié)構(gòu)化或非結(jié)構(gòu)化問題。典型的GDSS由硬件資源、軟件資源和決策者三部分組成。其中，硬件資源是指各決策者獨(dú)立使用的工作站（或終端）、共享使用的外部數(shù)據(jù)庫、模型庫及I/O設(shè)備等硬件資源，還包括整個(gè)GDSS基于的通訊網(wǎng)絡(luò)；軟件資源包括在各決策者的工作站（或終端）上運(yùn)行的決策支持軟件、支撐GDSS的底層軟件（如DBMS、MBMS）及網(wǎng)絡(luò)軟件；決策者不僅包括參與決策的人員，還包括決策過程的協(xié)調(diào)人員 [6]。

具體的過程為：

①參與決策的人員由一名協(xié)調(diào)者和若干名決策者組成；

②群決策過程由協(xié)調(diào)者主持，協(xié)調(diào)者結(jié)點(diǎn)給各決策者結(jié)點(diǎn)發(fā)送會(huì)議開始消息，通知決策者本次會(huì)議的目標(biāo)、任務(wù)及有關(guān)情況，在收到全部回答報(bào)文后，宣布會(huì)議開始；

③各決策者獨(dú)立進(jìn)行決策，其間共享系統(tǒng)資源；

④各決策者決策完畢后，將決策方案發(fā)送給協(xié)調(diào)者；

⑤協(xié)調(diào)者依某種一致度對(duì)諸多方案進(jìn)行權(quán)衡，如諸方案一致度不夠，則向某些決策者發(fā)送協(xié)商報(bào)文，轉(zhuǎn)回3，重新決策；否則，繼續(xù)；

⑥得出最終的群決策方案，結(jié)束群決策過程。這種簡化了的模型，假設(shè)群決策過程一定能成功，且完全屏蔽了各決策者相互間的通訊聯(lián)系。

3.4 隊(duì)活動(dòng)

Agent執(zhí)行達(dá)成一致的聯(lián)合活動(dòng)的規(guī)劃，并維持緊密的團(tuán)隊(duì)關(guān)系。在每個(gè)Agent進(jìn)行自己分配的子問題時(shí)，共享資源在不同Agent并發(fā)輪詢的方式下，服務(wù)器怎樣處理共享資源的并發(fā)操作來維持客戶Agent上共享目標(biāo)的一致性，是并發(fā)控制研究的關(guān)鍵問題。因此采用“隊(duì)活動(dòng)”的并發(fā)控制策略來解決并發(fā)訪問，算法采用集中式令牌控制，流程圖如圖1，詳細(xì)的算法過程如下（為了描述簡單，特別定義：共享資源為shared resource，令牌為tokens）：

1）shared resource=tokens //給每個(gè)資源賦值一個(gè)令牌。

2）If（ agent want tokens ） then send post for token//想要使用公共資源，必須向服務(wù)器請(qǐng)求申請(qǐng)令牌。

3）server received application //服務(wù)器接收到申請(qǐng)。

4）If （shared resource in use ） then sent to the reject else turn the fifth step //如果資源在使用就拒絕，否則轉(zhuǎn)第五步。

5）If（ multiple Agent for the same shared resource），// 多個(gè)Agent申請(qǐng)同一個(gè)資源

then sends to agent of the highest priority//發(fā)給優(yōu)先級(jí)最高的Agent

else send to applicant//不存在競(jìng)爭(zhēng)，那么就把共享資源的令牌發(fā)給申請(qǐng)者。

6）If （Agent gets token of shares a resource）//若Agent得到一個(gè)共享資源的令牌。

Then agent= operate on shared resources； //則獲得對(duì)該共享資源的操作權(quán)

if （agent received a denial of command ）// 若收到拒絕信號(hào)

then agent = none //共享資源的操作權(quán)置空。

7）If （Agent= shared resource）at any time//如果某個(gè)agent長時(shí)擁有令牌

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

shared resource= occupied//標(biāo)識(shí)該資源已被占用。

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

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

如上的敘述保證了共享工作空間的一致性，能方便地授予（收回）Agent對(duì)一些共享資源的操作權(quán)和優(yōu)先權(quán)，使用令牌控制來解決操作權(quán)的分配。在算法中使用了請(qǐng)求原語、分配原語、拒絕原語、釋放原語來實(shí)現(xiàn)令牌控制策略。

本文設(shè)定了系統(tǒng)超級(jí)管理員、經(jīng)理、用戶三種不同的角色，采用白板系統(tǒng)進(jìn)行管理的實(shí)例來實(shí)現(xiàn)令牌的控制。系統(tǒng)超級(jí)管理員持有系統(tǒng)的最高權(quán)限，包括系統(tǒng)維護(hù)、功能設(shè)置、各種增加、刪除、修改等操作、查看系統(tǒng)，給角色分配權(quán)限等。經(jīng)理權(quán)限組可以對(duì)白板的消息進(jìn)行查看、編輯及修改。用戶權(quán)限組可以對(duì)所有消息進(jìn)行瀏覽、交流等功能。token的發(fā)放和回收由經(jīng)理權(quán)限組完成，只有用戶獲得token才有操作權(quán)限，沒有獲得token的用戶可以申請(qǐng)并等待經(jīng)理的發(fā)放，并發(fā)送詢問申請(qǐng)令牌。在管理時(shí)候，經(jīng)理擁有令牌，用戶需要使用令牌必須向經(jīng)理提出申請(qǐng)，經(jīng)理同意后用戶方可以使用令牌。

4 結(jié)論

人類隊(duì)工作模型是一個(gè)比較好的一個(gè)實(shí)現(xiàn)合作分布式求解（CDPS）的方法，步驟明確，而且投入其中進(jìn)行研究的專家也非常多，近年來，很多領(lǐng)域都非常關(guān)注的計(jì)算機(jī)支持協(xié)同工作（CSCW）對(duì)合作分布式求解也有很大的推動(dòng)作用。在本文中對(duì)Wooldrige和Jennings提出基于隊(duì)工作的合作分布式求解（CDPS）四個(gè)階段模型進(jìn)行了細(xì)化，并對(duì)每個(gè)階段提出了一些實(shí)現(xiàn)的解決方法。

參考文獻(xiàn)：

[1] Michael Wooldridge. 多Agent系統(tǒng)引論[M]. 北京：電子工業(yè)出版社，2003.

[2] 劉玉照，君祥南.基于群體的競(jìng)爭(zhēng)信息分析系統(tǒng)[J].情報(bào)雜志，2000（4）：32.

[3] 石純一，張偉，徐暉.多Agent系統(tǒng)引論[M].北京：電子工業(yè)出版社，2003.

[4] 華勇.基于CSCW的多AGENT協(xié)同式項(xiàng)目協(xié)調(diào)與管理系統(tǒng)的研究[J].高技術(shù)通信，2001.

[5] 胡曉容，明華.CSCW環(huán)境下基于角色的并發(fā)控制策略[J].計(jì)算機(jī)時(shí)代，2001（04）：25.

[6] 曹敏，金以慧.多Agent系統(tǒng)的研究和應(yīng)用[J]. 清華大學(xué)學(xué)報(bào)，2000，40（52）.

[7] 宋德舜，麥中凡.計(jì)算機(jī)支持協(xié)同工作（CSCW）的研究進(jìn)展[J].全國計(jì)算機(jī)新科技與計(jì)算機(jī)繼續(xù)教育研討會(huì)，1998.

[8] 李英.agent系統(tǒng)（MAS）研究進(jìn)展[C].全球智能控制與自動(dòng)化大會(huì)，2000 .

【通聯(lián)編輯：光文玲】