基于改進合同網協議的多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失信的可能性，提高系統運行效率。