合同網(wǎng)協(xié)議改進研究現(xiàn)狀與展望

郭 超， 熊 偉， 劉呈祥

(1. 裝備學(xué)院 研究生管理大隊, 北京 101416； 2. 裝備學(xué)院 復(fù)雜電子系統(tǒng)仿真實驗室, 北京 101416)

?

合同網(wǎng)協(xié)議改進研究現(xiàn)狀與展望

郭 超1， 熊 偉2， 劉呈祥1

(1. 裝備學(xué)院 研究生管理大隊, 北京 101416； 2. 裝備學(xué)院 復(fù)雜電子系統(tǒng)仿真實驗室, 北京 101416)

合同網(wǎng)協(xié)議是解決復(fù)雜系統(tǒng)任務(wù)分配問題的重要方法之一。鑒于基本合同網(wǎng)協(xié)議的缺陷，研究者們廣泛開展了改進研究，提出了大量的改進措施，但缺乏系統(tǒng)地梳理。分析了基本合同網(wǎng)協(xié)議的主要缺陷；從3個重點改進方向——降低協(xié)商通信量、提升多方協(xié)調(diào)能力和完善任務(wù)資格評價策略，對國內(nèi)外研究者改進合同網(wǎng)協(xié)議的主要措施進行了梳理，總結(jié)了各改進方向的基本思路和局限性；最后提出合同網(wǎng)協(xié)議改進研究可以在歷史與規(guī)范相結(jié)合、動態(tài)投標(biāo)閾值與動態(tài)緩沖池、多因素融合的任務(wù)資格評價和多改進措施組合應(yīng)用等方面開展探索。

合同網(wǎng)改進；多Agent系統(tǒng)；任務(wù)分配

合同網(wǎng)協(xié)議(Contract Net Protocol，CNP)是由Smith等[1-2]于20世紀(jì)80年代提出的分布式協(xié)商機制，旨在借鑒市場行為中合同生成思路解決分布式人工智能(Distributed Artificial Intelligence，DAI)中的任務(wù)分配問題。20世紀(jì)90年代后，分布式人工智能關(guān)注重點轉(zhuǎn)向多Agent系統(tǒng)(MAS)，合同網(wǎng)協(xié)議由于具有對分布式系統(tǒng)的適用性，成為一種有效的多Agent協(xié)調(diào)機制[3-4]。近年來，合同網(wǎng)協(xié)議被廣泛應(yīng)用到生產(chǎn)調(diào)度[5-6]、無人機[7-9]、多機器人系統(tǒng)[10-11]等具體領(lǐng)域，展現(xiàn)出良好的動態(tài)性、擴展性、魯棒性，逐步取代了傳統(tǒng)的集中式任務(wù)分配方法，成為這些領(lǐng)域解決任務(wù)分配問題的重要手段。

隨著應(yīng)用的深入與擴展，基本的合同網(wǎng)協(xié)議暴露出了明顯的缺陷，為此研究者們開展了大量工作，以期改善并提高適用性。目前，各種合同網(wǎng)協(xié)議改進措施層出不窮，但相關(guān)研究面向不同實際問題，缺乏系統(tǒng)的梳理和總結(jié)，不利于實際應(yīng)用，也增加了后續(xù)探索的難度。本文從基本合同網(wǎng)協(xié)議的主要缺陷出發(fā)，將改進研究歸納為3個重點方向：降低協(xié)商通信量、提升多方協(xié)調(diào)能力、完善任務(wù)資格評價策略，對典型改進研究進行總結(jié)，并對下一步研究方向進行探討。

1 基本合同網(wǎng)

在基本合同網(wǎng)協(xié)議中，系統(tǒng)內(nèi)存在2種Agent：產(chǎn)生任務(wù)分配需求的管理者(Manager)與執(zhí)行任務(wù)的合同者(Contractor)。通過對招投標(biāo)過程的抽象與簡化，Smith等[1-2]提出了基本合同網(wǎng)協(xié)議的主要環(huán)節(jié)，包括招標(biāo)、投標(biāo)、資格評價、授權(quán)、簽訂合同等，如圖1所示。它與集中式任務(wù)分配方法的不同之處在于多Agent共同參與決策，經(jīng)協(xié)商產(chǎn)生分配方案。

圖1 基本合同網(wǎng)協(xié)議流程

研究者們在使用基本合同網(wǎng)協(xié)議解決實際問題時，發(fā)現(xiàn)了其存在的缺陷[12-16]，突出表現(xiàn)在：

1) 協(xié)商通信量大。基本合同網(wǎng)協(xié)議面向規(guī)模不大的系統(tǒng)，管理者將招標(biāo)信息無差別地廣播給所有合同者，并未考慮其是否具有潛在招標(biāo)價值。對于大規(guī)模系統(tǒng)，合同者數(shù)量眾多且分布分散，廣播招標(biāo)將產(chǎn)生極大的通信量；若任務(wù)需多次協(xié)商，則通信量還將成倍增長。同時，管理者需接收和處理大量投標(biāo)消息，協(xié)商效率不高。

2) 缺乏有效的多方協(xié)調(diào)機制。基本合同網(wǎng)協(xié)議面向單任務(wù)、單回合，將合同者嚴(yán)格限制在與唯一管理者的協(xié)商之中。多個合同者與某一管理者協(xié)商時，必須拒絕其他管理者的招標(biāo)，故在協(xié)商持續(xù)期間，各合同者的資源都將被臨時占用，而最終卻只有唯一合同者獲得任務(wù)資格，造成系統(tǒng)擁有空閑資源而任務(wù)卻無法分配的局面。

3) 任務(wù)資格評價策略不完善。在基本合同網(wǎng)協(xié)議中，管理者通過評價合同者投標(biāo)值來確定其對任務(wù)的勝任情況，投標(biāo)值最高的合同者將獲得任務(wù)授權(quán)，這存在明顯的片面性：由于未考慮合同者實際負載，可能得出錯誤的分配方案。此外，合同者為得到任務(wù)授權(quán)，可能提交與其實際能力不符的虛假投標(biāo)，管理者僅憑投標(biāo)值可能做出錯誤決策。

2 合同網(wǎng)協(xié)議改進研究現(xiàn)狀

對應(yīng)3個主要缺陷，合同網(wǎng)協(xié)議改進研究集中在3個重要方向：降低協(xié)商通信量的改進、提升多方協(xié)調(diào)能力的改進、完善任務(wù)資格評價策略的改進。

2.1 降低協(xié)商通信量的改進研究

廣播招標(biāo)是產(chǎn)生大通信量的根本原因。為此，Sandholm等[17]提出了接收者限制(Audience Restrictions)的思想來減少通信量，在此基礎(chǔ)上出現(xiàn)了一些改進招標(biāo)策略。

2.1.1 基于信任評價的招標(biāo)

信任評價就是管理者對合同者能力的預(yù)期評價[18]，評價結(jié)果由信任度來反映。基于信任評價的招標(biāo)思路為：以信任度為依據(jù)，基于預(yù)定閾值將合同者劃分為若干信用等級，并優(yōu)先向信用等級高者招標(biāo)，從而縮小招標(biāo)范圍。在多Agent系統(tǒng)中，合同者的信任度首先來自于管理者對其能力的直接評價，取決于合同者的歷史表現(xiàn)，成功執(zhí)行任務(wù)時評價值升高，反之評價值下降[15,19]。此外，由于管理者知識有限，為全面評價合同者能力，還應(yīng)參考其他Agent的間接評價，管理者由此獲得的合同者的評價值稱為信譽[20-21]或推薦信任度[22]98-99，綜合直接與間接兩方面評價可得到合同者的信任度。信任度能夠直觀地反映Agent能力的變化，故改進招標(biāo)策略可應(yīng)用于動態(tài)環(huán)境，但其也有明顯缺陷：僅憑信任度來限定招標(biāo)范圍，容易遺漏某些歷史表現(xiàn)不佳但可勝任當(dāng)前任務(wù)的Agent；最壞的情況下，全部有能力的Agent可能都被過濾在招標(biāo)范圍之外，將得不到可行的分配方案。

2.1.2 基于范例推理的招標(biāo)

范例推理(Case-Based Reasoning，CBR)[23]是一種使用舊經(jīng)驗來解決新問題的手段，基本思想為：將舊問題及其解決方法記錄為范例，形成系統(tǒng)范例庫；新問題到來時，在范例庫中檢索相似的舊問題，在此基礎(chǔ)上生成新問題解決方案?；诜独评淼母倪M招標(biāo)，就是通過保存歷史任務(wù)信息建立范例庫，協(xié)商時充分利用相似任務(wù)的招投標(biāo)信息，選取合適的合同者優(yōu)先招標(biāo)[24]。這種改進具有較強的實用性，Ohko等[25-27]據(jù)此開發(fā)了多機器人任務(wù)分配系統(tǒng)——LEMMING，經(jīng)驗證能夠顯著降低通信量。

基于范例推理的招標(biāo)，能夠利用歷史信息，指導(dǎo)當(dāng)前任務(wù)招標(biāo)范圍的選擇，但也存在局限性：(1) 缺乏完善的任務(wù)相似度判斷方法，范例匹配以最近鄰域法[28]為主，需要將任務(wù)表示為屬性向量，對任務(wù)特征具有明顯要求；(2) 范例維護難度大，范例庫保存全部歷史任務(wù)的協(xié)商方案，隨著時間推移范例庫規(guī)模將不斷擴大，使檢索效率下降；(3) 動態(tài)環(huán)境適用性差，范例對應(yīng)已處理過的任務(wù)，為確定的靜態(tài)信息，故范例推理僅適用于任務(wù)具有重復(fù)性和相似性的環(huán)境，同時要求Agent的能力穩(wěn)定。若新任務(wù)與所有歷史任務(wù)均存在顯著差異，或當(dāng)前Agent能力已較過去發(fā)生變化，范例將很難起到有效的指導(dǎo)作用。

2.1.3 基于熟人集的招標(biāo)

熟人集定義為與某Agent曾成功合作且達到一定頻度的Agent集合[29]。根據(jù)社會心理學(xué)的觀點，熟人之間具有更高的合作概率，若招標(biāo)時管理者以其熟人集為依據(jù)，會減少協(xié)商的盲目性[30]?；谑烊思恼袠?biāo)也是對系統(tǒng)歷史信息的利用，但相比范例庫，熟人集記錄的是系統(tǒng)中各Agent在歷次任務(wù)執(zhí)行過程中所積累的合作關(guān)系，而非局限于特定歷史任務(wù)，動態(tài)環(huán)境適用性更好。鑒于動態(tài)環(huán)境中多樣化任務(wù)需求，萬武南等[31]認為熟人集應(yīng)以抽象的任務(wù)類為核心，根據(jù)Agent在每類任務(wù)執(zhí)行過程中的合作情況，基于熟悉程度建立針對該類任務(wù)的熟人集。馬巧云[22]97-98認為Agent熟悉程度只增不降具有不合理性，為適應(yīng)Agent發(fā)生能力下降的情況，應(yīng)根據(jù)Agent任務(wù)完成績效來調(diào)整熟悉程度。基于熟人集的招標(biāo)能夠適應(yīng)任務(wù)類型與Agent能力變化的動態(tài)環(huán)境，是一種合理的改進招標(biāo)策略，但要求Agent間有足夠頻繁的交互，而且僅根據(jù)熟悉程度劃分熟人集具有片面性，需要在熟悉程度的基礎(chǔ)上尋找更為全面的劃分依據(jù)。

2.1.4 基于Agent心智系數(shù)的招標(biāo)

信任度、范例推理和熟人集分別從不同角度體現(xiàn)了“接收者限制”的思想，但都是管理者對合同者的單向評價，實際上合同者的意愿、個性、風(fēng)險承受能力等因素同樣影響其對任務(wù)的態(tài)度。為此，研究者們引入Agent心智模型，為Agent定義多種可動態(tài)更新的心智系數(shù)，管理者以心智系數(shù)為依據(jù)，從合同者集合中選擇招標(biāo)對象。

基于Agent心智系數(shù)的招標(biāo)核心問題在于定義心智系數(shù)并制定其更新規(guī)則。從相關(guān)文獻[32-35]來看，研究者們定義的Agent心智系數(shù)大致可分為3類：(1) 反映Agent固有屬性和當(dāng)前狀態(tài)，如自信度、穩(wěn)健度、風(fēng)險承受度；(2) 反映Agent在歷史任務(wù)中的表現(xiàn)，如積極度、貢獻度；(3) 反映Agent之間交互關(guān)系，如親密度、合作頻度、忠誠度等。同時，每類心智系數(shù)都必須在每次協(xié)商完畢后進行更新，故這種招標(biāo)對Agent智能性具有較高要求。通過為各心智系數(shù)制定一定的門限值，可將合同者分為若干集合(或等級)，有選擇地從各集合中尋找招標(biāo)對象，可有效實現(xiàn)“接受者限制”，相比基于熟悉程度劃分的熟人集更為全面。蘭少華[32]按照心智系數(shù)將Agent劃分為3個互不相交的子集，提出了一種多級top-n隨機選擇算法，以不同概率向3個子集招標(biāo)。類似的還有陳明等[34]的研究，基于對Agent心智的綜合評價，將Agent分為熟人、一般熟人和陌生人3種類型，以從大到小的概率選擇3種Agent招標(biāo)。

2.2 提升多方協(xié)調(diào)能力的改進研究

基本合同網(wǎng)協(xié)議對多管理者、多任務(wù)的情況缺乏有效的協(xié)調(diào)機制。為此，研究者們提出了相應(yīng)的改進措施，希望通過放松對合同者的限制，促使其充分發(fā)揮能力，以提升多方協(xié)調(diào)能力。

2.2.1 合同網(wǎng)確認協(xié)議

Schillo等[36]在基本合同網(wǎng)協(xié)議的基礎(chǔ)上提出了合同網(wǎng)確認協(xié)議(Contract Net Confirmation Protocol，CNCP)，基本思路為：在授權(quán)環(huán)節(jié)中加入資格確認，允許合同者對任務(wù)進行選擇，如圖2所示。管理者可在任意時刻向任意合同者招標(biāo)，某合同者只要尚未獲得任務(wù)授權(quán)，就能隨時響應(yīng)其他招標(biāo)，甚至可以接受其他任務(wù)授權(quán)而拒絕當(dāng)前合同。CNCP使合同者不再被嚴(yán)格限制在當(dāng)前協(xié)商周期中，提高了多任務(wù)處理能力，緩解了等待投標(biāo)結(jié)果造成的資源浪費。

圖2 合同網(wǎng)確認協(xié)議流程示意

CNCP提高了系統(tǒng)資源利用率，但帶來了新問題：允許合同者在獲得授權(quán)前盲目投標(biāo)而未加節(jié)制，將使投標(biāo)消息劇增，系統(tǒng)通信量增大。對此，研究者們提出了節(jié)制措施——閾值限定，即設(shè)定特定的閾值來限制合同者盲目投標(biāo)[16]47-49。只有在已投出標(biāo)書數(shù)目小于閾值的情況下合同者才可繼續(xù)投標(biāo)，否則忽略任何新招標(biāo)消息。假設(shè)合同者c投標(biāo)閾值為Tb(Tb≥1)，已投標(biāo)書數(shù)為nb(nb≥1)，則閾值限定的投標(biāo)規(guī)則為[37]1017-1018：

閾值限定能夠有效節(jié)制合同者盲目投標(biāo)，但閾值的確定又是一個新問題，若閾值過低則CNCP的優(yōu)勢無法體現(xiàn)，反之則無法有效制止盲目投標(biāo)。Schillo等[38]提出了一種基于風(fēng)險分析的投標(biāo)策略，給出了一種基于統(tǒng)計學(xué)理論的方法，用來評估合同者投出的nb個標(biāo)書中有t(t≤nb)個被接受的概率。在其基礎(chǔ)上，楊件等[37]1018-1019提出了一種投標(biāo)閾值確定方法，在各合同者投標(biāo)策略相同的假設(shè)下，將t個標(biāo)書被接受的最大概率所對應(yīng)的投標(biāo)數(shù)量作為合同者的投標(biāo)閾值，相比普通CNCP通信量大大降低。

2.2.2 緩沖池

CNCP中，雖然合同者可以有選擇地對多任務(wù)投標(biāo)，但最終只能接受一項任務(wù)授權(quán)，若某合同者是多項任務(wù)的最佳執(zhí)行者，則除已授權(quán)任務(wù)外，其他任務(wù)無法得到最優(yōu)執(zhí)行。為此，研究者為合同者建立了緩沖池[39-40]，旨在允許其接受多項任務(wù)授權(quán)。緩沖池即任務(wù)隊列，當(dāng)收到一項任務(wù)授權(quán)后，合同者可繼續(xù)接受其他任務(wù)并按優(yōu)先級(重要性或時效性)存入緩沖池。待當(dāng)前任務(wù)執(zhí)行完畢，緩沖池中任務(wù)按順序依次執(zhí)行[41]，這在一定程度上提高了將任務(wù)分配給最佳執(zhí)行者的可能性。此外，當(dāng)接到新任務(wù)授權(quán)時，合同者將其與緩沖池中的任務(wù)進行比較，并將其插入合適位置，使優(yōu)先級高者優(yōu)先執(zhí)行。

緩沖池使合同者獲得多項任務(wù)授權(quán)成為可能，但合同者之間可能存在能力差距，能力強者勢必得到更多的授權(quán)，使其緩沖池中任務(wù)堆積，造成負載不平衡(見2.3節(jié))。限制各合同者的緩沖池大小，在一定程度上可以防止負載差距過大，但無法從根本上解決負載不平衡問題。

2.2.3 可解約合同網(wǎng)

CNCP允許合同者向多個管理者投標(biāo)，緩沖池允許合同者同時獲得多項任務(wù)授權(quán)，但在任務(wù)開始執(zhí)行后它們?nèi)耘c基本合同網(wǎng)協(xié)議一致，要求合同者必須將任務(wù)執(zhí)行完畢，即任務(wù)具有嚴(yán)格的貪婪性。這將帶來2個問題：(1)突發(fā)重要任務(wù)的執(zhí)行需要等待；(2)當(dāng)合同者能力不再滿足任務(wù)要求時，繼續(xù)執(zhí)行將導(dǎo)致任務(wù)失敗。為了解決這些問題，研究者們引入了可解約機制。可解約就是允許Agent中止或放棄當(dāng)前已開始任務(wù)(或已授權(quán)任務(wù))，轉(zhuǎn)而執(zhí)行新任務(wù)。當(dāng)突發(fā)重要任務(wù)或合同者能力不足以繼續(xù)當(dāng)前任務(wù)時，合同者可提出解除合同，中止當(dāng)前任務(wù)(稱為“解約任務(wù)”)，所有“解約任務(wù)”將重新由管理者向其他合同者招標(biāo)[42-43]。最早使用可解約機制的是Sandholm與Lesser提出的分級承諾(leveled commitment)合同網(wǎng)[44]：當(dāng)Agent發(fā)現(xiàn)執(zhí)行新任務(wù)對自己更有利時，可以支付一定的罰金并違約，但其所考慮的仍是唯一管理者的情況，若合同者在與多個管理者的協(xié)商中違約，需要承受高昂的罰金，嚴(yán)重影響合同者后續(xù)行為。為減少懲罰的影響，陳浩等[42]提出了“免責(zé)機制”，規(guī)定只要Agent的解約行為能夠使系統(tǒng)整體收益增加，就能免于懲罰。

可解約機制的引入大大提升了合同網(wǎng)協(xié)議的靈活性，能夠有效改善多方協(xié)調(diào)能力，但也使合同者故意違約成為可能，仍需要一定的限制措施。誠信機制[13,45]是對該問題的有效解決方法，它限制了合同者個性，規(guī)定其必須如實發(fā)送真實信息，當(dāng)確有重要任務(wù)需要調(diào)度或資源失效時才能進行解約，從根本上杜絕了故意違約的可能性。

2.3 完善任務(wù)資格評價策略的改進研究

基本合同網(wǎng)協(xié)議中，常見的任務(wù)資格評價策略包括成本最低策略、時間最短策略、質(zhì)量優(yōu)先策略等，都是從管理者的角度判斷合同者能力。實際上僅按照此類策略并不一定能保證任務(wù)成功執(zhí)行，必須考慮合同者狀態(tài)的影響。

2.3.1 負載均衡

除需具備潛在能力外，合同者是否勝任任務(wù)，還取決于其當(dāng)前已承擔(dān)任務(wù)，即負載。若合同者間存在能力差距，能力較強者可能被多個管理者選中故而承擔(dān)較高的負載，而能力弱者幾乎得不到執(zhí)行任務(wù)的機會，造成資源利用不平衡，也使部分任務(wù)拖延執(zhí)行。負載均衡就是在可接受范圍內(nèi)，將任務(wù)執(zhí)行資格更多地授予相對空閑的合同者，使任務(wù)的分布更加均勻。

合同者負載可由其已承擔(dān)任務(wù)數(shù)目衡量，Sugawara等[46]214以合同者緩沖池中已有任務(wù)數(shù)目表示其負載水平，緩沖池滿的合同者無法獲得任務(wù)授權(quán)，但未考慮系統(tǒng)整體負載狀況，具有一定的片面性。李新亮[47]以所有合同者的平均負載表示系統(tǒng)整體負載，并將各合同者負載與平均負載之間的差距定義為負載率，以此作為任務(wù)資格評價因素，任務(wù)分配結(jié)果能夠促進負載均衡。錢艷平等[8]首先以常規(guī)評價策略將任務(wù)分配給合同者，而后以負載系數(shù)(定義同負載率)為依據(jù)，通過合同者之間的協(xié)商，達到負載均衡。Sugawara等[46]211-213還提出一種改進的任務(wù)資格評價策略，將概率選擇與隨機選擇結(jié)合。實驗發(fā)現(xiàn)，當(dāng)以最短完成時間為主要目標(biāo)時，該策略可有效改善負載不均衡的狀況，但其研究對象為大規(guī)模多Agent系統(tǒng)(Large-Scale Multi-Agent System，LSMAS)，對一般系統(tǒng)是否適用未得到驗證。

2.3.2 協(xié)作成本

基本合同網(wǎng)協(xié)議面向簡單任務(wù)，可交由一個合同者執(zhí)行，不涉及多合同者協(xié)作；而復(fù)雜任務(wù)可能需要多個分散的合同者共同承擔(dān)，任務(wù)成本既包括合同者自身成本，也包括合同者間的協(xié)作成本。在任務(wù)資格評價階段，若忽略協(xié)作成本，所得結(jié)果很可能并非最佳方案，故對多合同者協(xié)作的情況，協(xié)作成本必須作為任務(wù)資格評價的考慮因素。但對于管理者而言協(xié)作成本為外部信息，其計算不僅要獲得合同者狀態(tài)還需要考慮多合同者在任務(wù)中的交互關(guān)系。

胡曉輝等[48]將協(xié)作成本作為任務(wù)資格評價的依據(jù)，但計算協(xié)作成本時僅考慮了合同者的地理分布，而忽略了系統(tǒng)拓撲結(jié)構(gòu)的影響。張立等[33]2890則主要關(guān)注拓撲結(jié)構(gòu)，將系統(tǒng)中各級實體按照隸屬關(guān)系映射成組織結(jié)構(gòu)樹，使用兩節(jié)點間邊的條數(shù)之和，來衡量任意兩點協(xié)作成本。實際上，協(xié)作成本同時受到系統(tǒng)拓撲結(jié)構(gòu)與Agent的地理分布的影響，此外他們未考慮動態(tài)結(jié)構(gòu)的系統(tǒng)。動態(tài)環(huán)境中管理者要準(zhǔn)確、實時掌握協(xié)作成本并非易事，如何獲取合同者協(xié)作成本是任務(wù)資格評價中尚需進一步研究的問題。3種可能的思路為：(1)在招標(biāo)消息中指明計算協(xié)作成本需要的信息，但管理者只能在合同者投標(biāo)后才能獲得所需信息；(2)引入反向招標(biāo)，即合同者在自身狀態(tài)或位置變化時主動通知管理者[49]，但增加了通信量；(3)建立黑板模型，保存全部Agent的狀態(tài)，Agent定期更新黑板中的信息[50-51]，但集中式的控制方式一定程度上犧牲了靈活性。

2.3.3 可用度估計

除了成本、時間、質(zhì)量、負載等因素，還有研究者提出了將可用度(Degree of Availability，DoA)作為任務(wù)資格評價的依據(jù)。當(dāng)管理者數(shù)目較多時，多項招標(biāo)活動頻繁進行，每個合同者將向多個管理者投標(biāo)并接受其中一部分任務(wù)，則每個管理者的任務(wù)只能以一定的概率得到執(zhí)行。若管理者未加考慮就賦予某合同者執(zhí)行資格，則該合同者可能最終并不執(zhí)行該任務(wù)，故在進行資格評價時需要考慮合同者接受任務(wù)授權(quán)的可能性，可用度就是對這一可能性的估計。

假設(shè)某合同者同時參與多個管理者的招標(biāo)，則其中任意管理者都無法預(yù)測該合同者最終接受誰的授權(quán)，唯一可確定的是合同者投標(biāo)數(shù)越多，它接受其中任何一個管理者授權(quán)的概率越低。為了直觀反映合同者可用度，Chen等[16]48-49將其表示為合同者已投標(biāo)數(shù)的倒數(shù)，柴慧敏等[52]定義可用度為已投標(biāo)數(shù)與投標(biāo)費用乘積的倒數(shù)，但他們都忽略了合同者可接受多項任務(wù)的情況(如具有緩沖池)。楊件等[37]1019-1020考慮到當(dāng)合同者能力較強時，即使已多次投標(biāo)，仍具有較高的可用度，故將可用度定義為合同者能力與已投標(biāo)數(shù)之比，對提高任務(wù)執(zhí)行質(zhì)量起到了積極作用。

3 總結(jié)與展望

3.1 研究總結(jié)

通過梳理相關(guān)研究可見，國內(nèi)外研究者提出了大量的改進措施，在很大程度上提高了合同網(wǎng)協(xié)議的適用性，但也存在一定的局限性，總結(jié)如下。

1) 降低協(xié)商通信量方面。主要思路為基于“接收者限制”思想改進招標(biāo)策略，核心問題在于選擇何種準(zhǔn)則或指標(biāo)在招標(biāo)前對合同者進行預(yù)評價。信任度的引入提供了一種通過歷史表現(xiàn)預(yù)先評價合同者的基本思路；范例推理根據(jù)靜態(tài)歷史任務(wù)指導(dǎo)招標(biāo)，適用于任務(wù)特征和Agent能力穩(wěn)定的情況；熟人集反映Agent間的動態(tài)合作關(guān)系，但需要交互達到較高的頻繁程度；Agent心智系數(shù)全面反映合同者的當(dāng)前狀態(tài)、歷史表現(xiàn)和交互關(guān)系，在其基礎(chǔ)上能夠更合理地限制招標(biāo)范圍，但心智系數(shù)的維護與更新復(fù)雜，對Agent智能水平提出較高要求?？梢园l(fā)現(xiàn)，此類改進研究的共同思路為：根據(jù)系統(tǒng)歷史信息獲得對合同者當(dāng)前能力的預(yù)估，需要足夠的歷史信息以供借鑒。該思路在協(xié)商初始階段將表現(xiàn)出局限性，因為大多數(shù)Agent在初始時期尚未參與任務(wù)執(zhí)行，系統(tǒng)缺乏歷史信息指導(dǎo)，難以準(zhǔn)確地建立信任度、范例庫、熟人集及心智系數(shù)模型，此時這些改進招標(biāo)實質(zhì)上仍為廣播方式，無法有效實現(xiàn)“接收者限制”。

2) 提升多方協(xié)調(diào)能力方面。主要思路為減少對合同者的約束，促進其能力發(fā)揮，從而有效利用系統(tǒng)資源，提升多方協(xié)調(diào)能力。CNCP允許合同者有選擇地參與多任務(wù)投標(biāo)，緩沖池允許合同者獲得多項授權(quán)，可解約機制甚至允許合同者解除已承擔(dān)任務(wù)。隨著約束的減少，合同者投標(biāo)靈活度越來越高，多方協(xié)調(diào)能力越來越強；但與此同時，靈活性的提升將伴隨著系統(tǒng)內(nèi)無序性的增加，一味放松合同者約束可能反而令協(xié)商效率下降，如CNCP中的盲目投標(biāo)、緩沖池中的負載不平衡、可解約機制中的故意違約等。這是因為合同網(wǎng)協(xié)議是一種分布式協(xié)調(diào)機制，系統(tǒng)內(nèi)無協(xié)調(diào)全局的控制中心，Agent作為一種自主性個體，在缺少全局控制時，難免會將自身利益作為驅(qū)動目標(biāo)。為此，改進研究采取了一定的節(jié)制措施，如設(shè)定投標(biāo)閾值、限制緩沖池大小、誠信機制等，通過犧牲一部分靈活性制約無序性，但這些措施仍存在局限性：在合同者能力變化時，固定的投標(biāo)閾值與緩沖池不能適應(yīng)這種變化，如當(dāng)某合同者能力大幅下降時，其投標(biāo)閾值與緩沖池都應(yīng)相應(yīng)減小，否則將失去節(jié)制作用。

3) 完善任務(wù)資格評價策略方面。主要思路為從管理者角度轉(zhuǎn)向合同者的角度，挖掘影響任務(wù)執(zhí)行的因素。負載狀況、協(xié)作成本、可用度等是改進研究中任務(wù)資格評價考慮的因素：對于Agent存在明顯能力差距的情況，需考慮使任務(wù)分配結(jié)果有利于負載均衡；對于Agent分布較為分散、任務(wù)需多合同者協(xié)作的情況，任務(wù)資格評價不能忽略合同者的協(xié)作成本；對于管理者數(shù)量較多、招標(biāo)活動頻繁的情況，則通過估計可用度提高任務(wù)分配成功的概率?？梢?，針對特定特征的系統(tǒng)，任務(wù)資格評價需要考慮相應(yīng)的因素。然而實際系統(tǒng)往往更為復(fù)雜，同時具有多方面特征，例如一個系統(tǒng)很可能包含眾多個體，而個體分散分布且相互間能力差距明顯，同時任務(wù)又需要多個體協(xié)作執(zhí)行，這種情況下僅考慮前文任何單一因素都將難以保證評價結(jié)果的合理性。

3.2 研究展望

結(jié)合以上總結(jié)，本文認為下一步合同網(wǎng)協(xié)議改進研究還可以針對以下幾點開展進一步探索：

1) 歷史與規(guī)范的結(jié)合。降低協(xié)商通信量的改進依賴于系統(tǒng)歷史信息，故在初始階段作用不大，可引入規(guī)范作為補充措施。規(guī)范是不同于協(xié)商的多Agent協(xié)調(diào)機制，即基于所掌握的領(lǐng)域背景先驗知識，針對不同角色制定全局行為限制規(guī)則，減少搜索空間中的分支因素和不必要的交互，在一定程度上犧牲了Agent的自治能力和靈活性，但換取了通信和協(xié)同開銷的降低[53]。下一步研究可以采用規(guī)范與歷史相結(jié)合的改進策略，由于規(guī)范為全局規(guī)則，在缺乏歷史信息時仍可過濾一部分無意義的招投標(biāo)，當(dāng)歷史信息有所積累時，再據(jù)此對招標(biāo)做進一步限制。

2) 動態(tài)投標(biāo)閾值與動態(tài)緩沖池。投標(biāo)閾值能夠改善CNCP中的盲目投標(biāo)，緩沖池令合同者可以接受多項任務(wù)授權(quán)。下一步可開展動態(tài)投標(biāo)閾值與動態(tài)緩沖池機制研究，即根據(jù)任務(wù)需求與合同者實際能力靈活地改變投標(biāo)閾值和緩沖池的大小，可有效節(jié)制系統(tǒng)無序性，同時減少資源的浪費。其中待解決的問題是任務(wù)需求預(yù)測，即預(yù)估未來任務(wù)對合同者能力的需求量，可以借鑒降低協(xié)商通信量的改進思路，以合同者已執(zhí)行歷史任務(wù)的平均能力需求作為未來任務(wù)需求的估計。

3) 多因素融合的任務(wù)資格評價。無論從管理者或是合同者角度看，能夠影響任務(wù)分配方案合理性的因素多樣。在復(fù)雜情況下，僅依據(jù)單一因素進行任務(wù)資格評價難以避免結(jié)果的片面性。多因素融合的任務(wù)資格評價就是融合多因素的影響做出全面的任務(wù)資格評價。目前尚缺少合理的信息融合方法，能夠有效綜合多方面因素的作用，這將是下一步改進研究需要解決的問題；此外，如何根據(jù)實際系統(tǒng)特征及任務(wù)分配需求，全面、準(zhǔn)確地挖掘資格評價的影響因素也是值得探索的問題。

4) 多種改進措施的組合應(yīng)用。不同改進措施側(cè)重解決基本合同網(wǎng)協(xié)議不同環(huán)節(jié)的問題，為達到更好的改進效果，可在協(xié)商中組合應(yīng)用多種改進措施，如：在招標(biāo)中使用基于Agent心智系數(shù)的招標(biāo)，在投標(biāo)中允許合同者解約任務(wù)，而在任務(wù)資格評價中考慮合同者協(xié)作成本。需要注意的是，改進措施的選擇必須符合實際系統(tǒng)特征及任務(wù)分配需求，而多種措施組合應(yīng)用時還必須注意不同措施間的邏輯關(guān)系，如：緩沖池允許合同者接受多項任務(wù)授權(quán)，則任務(wù)資格評價環(huán)節(jié)就必須解決負載均衡問題；可解約機制允許合同者放棄執(zhí)行已授權(quán)的任務(wù)，則為提高任務(wù)成功概率，在任務(wù)資格評價時需要評價合同者的可用度。

4 結(jié) 束 語

本文從降低協(xié)商通信量、提升多方協(xié)調(diào)能力、完善任務(wù)資格評價策略3個方向，對典型合同網(wǎng)協(xié)議改進研究的基本思想與不足進行了總結(jié)，指出了下一步研究值得關(guān)注的方面。除了本文歸納的3個方向外，還有誠信合同網(wǎng)、多級合同網(wǎng)、迭代合同網(wǎng)等改進研究，由于篇幅所限未全面介紹(可參考文獻[54-56])。隨著合同網(wǎng)協(xié)議應(yīng)用范圍不斷拓展，尋找普適改進方法越來越困難。理論來自實踐，未來研究將更加側(cè)重具體領(lǐng)域，解決現(xiàn)實問題，如作戰(zhàn)協(xié)同、分布式衛(wèi)星調(diào)度、動態(tài)武器目標(biāo)分配等，必須在現(xiàn)有改進研究的基礎(chǔ)上，結(jié)合具體領(lǐng)域中任務(wù)分配問題的特點，在特定應(yīng)用需求下探索更為合理可行的改進方法。

References)

[1]SMITH R G.The contract net protocol:high-level communication and control in a distributed problem solver [J].IEEE Transactions on Computers,1980(12):1104-1113.

[2]SMITH R G,DAVIS R.Frameworks for co-operation in distributed problem solving [J].IEEE Transactions on System Man & Cybernetics,1981,11(1):61-70.

[3]唐蘇妍,朱一凡,李群,等.多Agent系統(tǒng)任務(wù)分配方法綜述[J].系統(tǒng)工程與電子技術(shù),2010,32(10):2155-2161.

[4]秦久峰,曾凡明,陳于濤.基于改進合同網(wǎng)的多Agent系統(tǒng)協(xié)作機理研究[J].武漢理工大學(xué)學(xué)報,2014,38(5):1065-1069.

[5]QIN L,KAN S.Production dynamic scheduling method based on improved contract net of multi-agent [C]// Proceedings of 2012 International Conference of Intelligence Computation and Evolutionary Computation.New York:Springer Berlin Heidelberg,2013:929-936.

[6]趙良輝.無拍賣的動態(tài)Agent調(diào)度模型[J].計算機集成制造系統(tǒng),2013,19(11):2893-2899.

[7]鄧啟波.多無人機協(xié)同任務(wù)規(guī)劃技術(shù)研究[D].北京：北京理工大學(xué),2014：56-92.

[8]錢艷平,夏潔,劉天宇.基于合同網(wǎng)的無人機協(xié)同目標(biāo)分配方法[J] 系統(tǒng)仿真學(xué)報,2011,23(8):1672-1676.

[9]YOU G X,PANG Y J,JIANG D P.Market based framework for multiple AUVs cooperation [J].Journal of Marine Science and Application,2005,4(2):7-12.

[10]高志軍,顏國正,丁國清.多Agent協(xié)作環(huán)境下的任務(wù)分配[J].系統(tǒng)工程與電子技術(shù),2005,27(1):134-136.

[11]DIAS B M,ZLOT R,KALRA N,et al.Market-based multirobot coordination:a survey and analysis [J].Proceedings of the IEEE,2006,94(7):1257-1270.

[12]吳浩,劉建勛,李欽富.基于MAS的分布式作戰(zhàn)任務(wù)分配研究[J].中國電子科學(xué)研究院學(xué)報,2005(4):435-440.

[13]楊萍,劉穎,裴瑩.改進合同網(wǎng)協(xié)議的Agent動態(tài)任務(wù)分配[J].火力與指揮控制,2011,36(10):77-80.

[14]陳愷，陳浩，李軍.基于改進合同網(wǎng)協(xié)議的分布式衛(wèi)星任務(wù)規(guī)劃算法實現(xiàn)[J].中國電子商情：通信市場,2011(3):93-98.

[15]李新亮,翟江濤,戴躍偉.動態(tài)環(huán)境下基于改進合同網(wǎng)的多Agent任務(wù)分配算法[J].科學(xué)技術(shù)與工程,2013,13(27):8014-8019.

[16]CHEN X G,SONG H G.Further extensions of FIPA contract net protocol:threshold plus DoA [C]// Proceedings of the 2004 ACM Symposium on Applied Computing.New York:ACM,2004:45-51.

[17]SANDHOLM T,LESSER V.Issues in automated negotiation and electronic commerce:extending the contract net framework [M]//Readings in agents.San Francisco:Morgan Kaufmann Publishers Inc.,1997:66-73.

[18]POVEY D.Developing electronic trust policies using a risk management model [J] Lecture Notes in Computer Science,1999,1740:1-16.

[19]陳堅,廖守億,鄧方林.一種基于多Agent的計算機生成兵力協(xié)作方法[J].計算機仿真,2010,27(2):113-117.

[20]黃利堅.多Agent系統(tǒng)中信任和信譽模型的研究[D] 北京：北京交通大學(xué),2011：18-19.

[21]HUYNH T,JENNINGS N,SHADBOLT N.An integrated trust and reputation model for open multi-agent systems [J].Autonomous Agents and Multi-Agent Systems,2006,13(2):119-154.

[22]馬巧云.基于多Agent系統(tǒng)的動態(tài)任務(wù)分配研究[D].武漢：華中科技大學(xué),2006.

[23]KOLODNER J L.An introduction to case-based reasoning [J].Artificial Intelligence Review,1992,6(1):3-34.

[24]UMESH D,AROBINDA G,ANUPAM B.Performance improvement of the contract net protocol using instance based learning [J].Lecture Note for Computer Science,2003,2918:290-299.

[25]OHKO T,HIRAKI K,ANZAI Y.LEMMING:a learning system for multi-robot environments [C]// Proceedings of the 1993 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’ 93).New York:IEEE,1993:1141-1146.

[26]OHKO T,HIRAKI K,ANZAI Y.Learning to reduce communication cost on task negotiation among multiple robots [C]// Proceedings of the workshop on Adaption and Learning in Multi-Agent Systems (IJCAI’ 95).London:Springer-Verlag,1995:177-190.

[27]OHKO T,HIRAKI K,ANZAI Y A.Reducing communication load on contract net by case-based reasoning- extension with directed contract and forgetting [C]//Proceedings of IEEE/RSJ International Conference on Intelligent Robots & Systems (IROS’ 97).New York:IEEE,1997:244-251.

[28]萬武南,王曉京,宋春雨,等.基于范例推理的合同網(wǎng)模型[J].小型微型計算機系統(tǒng),2005,26(9):1578-1581.

[29]陶海軍,王亞東,郭茂祖,等.基于熟人聯(lián)盟及擴充合同網(wǎng)協(xié)議的多智能體協(xié)商模型[J].計算機研究與發(fā)展,2006,43(7):1155-1160.

[30]葉東海,藍少華,王玉善,等.基于熟人的Agent聯(lián)盟策略[J].小型微型計算機系統(tǒng)，2000,21(10):1053-1055.

[31]萬武南,張蕾.基于任務(wù)熟人集的合同網(wǎng)模型的改進[J].計算機應(yīng)用,2003,23(3):3-5.

[32]蘭少華.多Agent技術(shù)及其應(yīng)用研究[D].南京：南京理工大學(xué),2002：41-46.

[33]張立,王茜竹,趙春江,等.基于心智與擴展合同網(wǎng)的半自治多智能體任務(wù)分配[J].計算機集成制造系統(tǒng),2015,21(11):2885-2891.

[34]陳明,簡玉梅.基于心智系數(shù)的多Agent合同網(wǎng)協(xié)作模型研究[J].計算機應(yīng)用與軟件，2013,30(6):46-56.

[35]徐燕妮.基于合同網(wǎng)協(xié)議的多Agent協(xié)作技術(shù)研究[D].青島：山東科技大學(xué),2006：15-17.

[36]SCHILLO M,FISHER K,KRAY C.The contract net with confirmation protocol:an improved mechanism for task assignment [R].[S.l.]:German Research Center for Artificial Intelligence,2001：1-4.

[37]楊件,李文立,洪春宇.基于閾值和可用度的合同網(wǎng)協(xié)議改進方案研究[J].計算機集成制造系統(tǒng),2009,15(5):1017-1022.

[38]SCHILLO M,KRAY C,FISHER K.The eager bidder problem:a fundamental problem of DAI and selected solutions[C]// Proceedings of the 1st International Joint Conference on Autonomous Agents and Multi-Agent Systems.New York:ACM,2002:599-606.

[39]韋兆文,區(qū)云鵬,閆俊燕.一種改進的動態(tài)合同網(wǎng)協(xié)議[J].計算機工程與應(yīng)用,2007,43(36):208-210；216.

[40]SUAGAWARA T,FUKUDA K,HIROTSU T,et al.Effect of alternative distributed task allocation strategy based on local observations in contract net protocol [J].Lecture Notes in Computer Science,2012,7057(3):90-104.

[41]SUAGAWARA T,KURIHARA S,HIROTSU T,et al.Total performance by local agent selection strategies in multi-agent systems [C]// Proceedings of 5th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2006).New York:ACM,2006:601-608.

[42]陳浩,景寧,李軍,等.基于外包合同網(wǎng)的自治電磁探測衛(wèi)星群任務(wù)規(guī)劃[J].宇航學(xué)報,2009,30(6):2285-2291.

[43]郝會成.敏捷衛(wèi)星任務(wù)規(guī)劃問題建模及求解方法研究[D].哈爾濱：哈爾濱工業(yè)大學(xué),2013：89-95.

[44]SANDHOLM T,LESSER V.Advantages of a leveled commitment contracting protocol [C]// Proceedings of 13th National Conference on Artificial Intelligence (AAAI-96).Portland:AAAI Press,1996:126-133.

[45]于在亮.多中心協(xié)同衛(wèi)星任務(wù)規(guī)劃平臺關(guān)鍵技術(shù)研究[D].長沙：國防科學(xué)技術(shù)大學(xué),2010：45-54.

[46]SUGAWARA T,HIROTSU T,KURIHARA S,et al.Controlling contract net protocol by local observation for large-scale multi-agent systems [J].Lecture Notes in Computer Science,2008,5180:206-220.

[47]李新亮.面向信息探測的多智能體組網(wǎng)技術(shù)研究[D].鎮(zhèn)江：江蘇科技大學(xué),2014：34-35.

[48]胡曉輝,李蘭風(fēng),方政,等.改進的任務(wù)分配策略在WSN中的應(yīng)用研究 [J/OL].計算機工程與應(yīng)用， http:// www.cnki.net/ kcms/ detail/ 11.2127.TP.20150929.1135.060.html

[49]江建清,朱曉敏,伍國華,等.面向應(yīng)急對地觀測任務(wù)的多飛艇協(xié)同分配方法[J].系統(tǒng)工程與電子技術(shù),2013,35(2):317-325.

[50]陳華東,劉忠,李云凡,等.黃頁服務(wù)的合同網(wǎng)在編隊武器目標(biāo)分配中的應(yīng)用[J].火力與指揮控制,2013,38(7):103-106.

[51]肖玉杰,李杰,劉方.基于合同網(wǎng)的分布式動態(tài)任務(wù)分配算法[J].艦船科學(xué)技術(shù),2015,37(3):113-118.

[52]柴慧敏,侯健,周坤,等.基于多Agent的資源聚合方法:201510394107.3[P].2015-11-18.

[53]吳菊花,吳麗花,甘仞初.基于規(guī)范的多Agent協(xié)同機制研究[J].計算機應(yīng)用研究,2009,26(5):1778-1781

[54]郝會成,姜維,李一軍,等.基于Multi-Agent敏捷衛(wèi)星動態(tài)任務(wù)規(guī)劃問題[J].國防科技大學(xué)學(xué)報,2013,35(1):53-59.

[55]CONRY S E,MEYER R A,LESSER V R.Multistage negotiation in distributed planning [M]//BOND A H,GASSER L.Reading in Distributed Artificial Intelligence.[S.l.]:Elsevier,1988:367-384.

[56]Foundation for Intelligent Physical Agents.FIPA iterated contract net interaction protocol specification[EB/OL].(2002-12-06)[2015-04-07].http://www.fipa.org/specs/fipa0030/SC0030H.html.

(編輯：李江濤)

Prospects and Current Researches on Improvement of Contract Net Protocol

GUO Chao1， XIONG Wei2， LIU Chengxiang1

(1. Department of Graduate Management, Equipment Academy, Beijing 101416, China；2. Science and Technology on Complex Electronic System Simulation Laboratory, Equipment Academy, Beijing 101416, China)

Contract network protocol is one of the important methods to tackle complex system task assignment issues. In view of the defects of the basic contract network protocol, researchers have carried out extensive research and put forward a large number of improvement measures, but all these lack a systematic analysis. This paper analyzes the main defects of the basic contract network protocol. From three key improving directions-reducing collaborative communication, improving multi-coordination ability and perfecting task qualification evaluation strategy, the paper sores the main contract network protocol improvement measures proposed home and abroad. The paper concludes the basic ideas and limitations of each improving direction. Finally, it proposes that, in the field of contract network protocol improvement study, the methods like combined applications of history and norms, dynamic bidding threshold and dynamic buffer pool, multi-factor task and qualification evaluation and multiple improvement measures should be tried.

improvement of contract net protocol; multi-agent system(MAS); task allocation

2016-05-15

郭 超(1987-)，男，博士研究生，主要研究方向為體系任務(wù)優(yōu)化。gch_87_10_26@126.com 熊 偉，男，研究員，博士生導(dǎo)師。

TP18

2095-3828(2016)06-0082-08

A DOI 10.3783/j.issn.2095-3828.2016.06.016