基于改進(jìn)合同網(wǎng)協(xié)議的多Agent的AGV調(diào)度協(xié)作機(jī)制

(北京物資學(xué)院 北京 100010)

在自動(dòng)化物流系統(tǒng)中，AGV是一種重要而特殊的物料搬運(yùn)設(shè)備，相比于傳統(tǒng)的輸送設(shè)備，AGV的運(yùn)行線路設(shè)定靈活，小車的調(diào)度完全由控制系統(tǒng)靈活調(diào)配，具有自動(dòng)化程度高、準(zhǔn)確快捷、機(jī)動(dòng)靈活和環(huán)保等優(yōu)點(diǎn)，因此，在物流系統(tǒng)中得到廣泛的應(yīng)用，所以AGV調(diào)度的優(yōu)劣對(duì)整個(gè)系統(tǒng)有著重要影響。AGV的調(diào)度就是AGV在空閑、倉(cāng)庫(kù)或工作站發(fā)出運(yùn)送請(qǐng)求時(shí)，合理地安排各臺(tái)AGV的工作流程。多AGV調(diào)度主要解決如下兩個(gè)問(wèn)題：

1)當(dāng)一臺(tái)AGV收到多個(gè)貨物任務(wù)運(yùn)送請(qǐng)求時(shí)，AGV對(duì)任務(wù)進(jìn)行評(píng)估選擇。

2)當(dāng)多臺(tái)AGV響應(yīng)一個(gè)任務(wù)運(yùn)送請(qǐng)求時(shí)，任務(wù)要對(duì)AGV進(jìn)行評(píng)估抉擇。

智能體(Agent)是一個(gè)具有自主性、主動(dòng)性、持續(xù)性、交互性和自適應(yīng)性的智能實(shí)體，可以在沒(méi)有外界直接操縱的情況下，通過(guò)自身的傳感器感知外部環(huán)境的變化，并通過(guò)效應(yīng)器自主地對(duì)環(huán)境做出反應(yīng)。而由多個(gè)智能體組成的多智能體系統(tǒng)(Multi-Agent System，MAS)具有敏捷、靈活、實(shí)時(shí)的優(yōu)點(diǎn)，采用分布式體系結(jié)構(gòu)，其每個(gè)智能體皆有一定的獨(dú)立功能，且智能體之間的結(jié)構(gòu)關(guān)系是動(dòng)態(tài)可調(diào)整的，不同功能Agent組成緊耦合的運(yùn)輸調(diào)度管理體系結(jié)構(gòu)，具有適應(yīng)性、自組織和良好的協(xié)調(diào)性能，可以通過(guò)協(xié)調(diào)方式完成繁雜的整體運(yùn)作。因此，可采用多智能體技術(shù)解決物流配送中的AGV調(diào)度問(wèn)題。

一、合同網(wǎng)協(xié)議

(一)合同網(wǎng)的定義

合同網(wǎng)協(xié)作模型是Smith和Davis于1980年提出的,它通過(guò)引入市場(chǎng)中的招標(biāo)—投標(biāo)—中標(biāo)機(jī)制,對(duì)系統(tǒng)的任務(wù)進(jìn)行委托分配,從而解決資源、知識(shí)的沖突等問(wèn)題。在合同網(wǎng)協(xié)議中，共有兩種Agent，分別代表競(jìng)標(biāo)的發(fā)起者和參與者。發(fā)起者Agent和參與者Agent通過(guò)競(jìng)標(biāo)的方式進(jìn)行任務(wù)的分發(fā)，并生成調(diào)度結(jié)果。發(fā)起者Agent接到任務(wù)后進(jìn)行招標(biāo)，各個(gè)參與者Agent進(jìn)行投標(biāo)，發(fā)起者Agent選擇合適的參與者Agent執(zhí)行任務(wù),但是執(zhí)行任務(wù)的參與者Agent可能由于資源的不足等原因?qū)е聼o(wú)法完成任務(wù),這時(shí)它轉(zhuǎn)變?yōu)榘l(fā)起者Agent的角色，繼續(xù)對(duì)該任務(wù)進(jìn)行再招標(biāo)。參與者Agent和發(fā)起者Agent的協(xié)商頻繁導(dǎo)致通訊量迅速增加，容易造成信息阻塞。為了減少通訊量，本文對(duì)傳統(tǒng)合同網(wǎng)協(xié)議進(jìn)行簡(jiǎn)化，簡(jiǎn)化合同網(wǎng)協(xié)議可以使每次招投標(biāo)過(guò)程的通訊次數(shù)減少至3次，這既保留了合同網(wǎng)協(xié)議的靈活性，又滿足了應(yīng)用場(chǎng)合的實(shí)時(shí)性需求。簡(jiǎn)化合同網(wǎng)協(xié)議中共有兩類Agent：任務(wù)Agent(Task Agent,TA)和機(jī)器Agent(Machine Agent,MA)。其中TA發(fā)起招標(biāo)并決策，MA參與競(jìng)標(biāo)并進(jìn)行投標(biāo)，TA和MA相互協(xié)商協(xié)作共同完成任務(wù)。雖然簡(jiǎn)化了的合同網(wǎng)協(xié)議，可以減少兩者間一定的通訊量，但是隨著任務(wù)數(shù)量的增多，可能一個(gè)TA同時(shí)向一個(gè)或多個(gè)MA發(fā)起招標(biāo)，一個(gè)MA同時(shí)接受一個(gè)或多個(gè)TA招標(biāo)，兩者之間會(huì)就任務(wù)情況頻繁協(xié)商，還是容易造成信息阻塞。

(二)黑板模型

黑板模型是將異構(gòu)知識(shí)源集成在模型中，形成一個(gè)專家系統(tǒng)結(jié)構(gòu)模式。多個(gè)人類專家或主體專家協(xié)同求解一個(gè)問(wèn)題，黑板是一個(gè)共享的問(wèn)題求解工作空間，多個(gè)專家都能“看到”黑板。當(dāng)問(wèn)題和初始數(shù)據(jù)記錄到黑板上，求解開始。所有專家通過(guò)“看”黑板尋求利用其專家經(jīng)驗(yàn)知識(shí)求解問(wèn)題的機(jī)會(huì)。當(dāng)一個(gè)專家發(fā)現(xiàn)黑板上的信息足以支持他進(jìn)一步求解問(wèn)題時(shí)，他就將求解結(jié)果記錄在黑板上。新增加的信息有可能使其他專家繼續(xù)求解。重復(fù)這一過(guò)程直到問(wèn)題徹底解決，獲得最終結(jié)果。黑板模型主要由“黑板”、知識(shí)源(Knowledge Source)和控制結(jié)構(gòu)3大部分組成。黑板模型己經(jīng)被廣泛使用,并且相應(yīng)的技術(shù)己經(jīng)比較成熟,但仍存在著2個(gè)問(wèn)題：

(1)一個(gè)問(wèn)題是黑板模型中公共數(shù)據(jù)庫(kù)的強(qiáng)藕合性，雖然數(shù)據(jù)的集中存放給數(shù)據(jù)的一致性帶來(lái)了許多益處,但是因?yàn)樵谇蠼獾闹虚g過(guò)程產(chǎn)生的數(shù)據(jù)都要傳到黑板上,所以與黑板的數(shù)據(jù)傳輸成為系統(tǒng)的一個(gè)瓶頸。

(2)另一個(gè)問(wèn)題是系統(tǒng)中數(shù)據(jù)格式的異構(gòu)性。由于各知識(shí)源通過(guò)黑板進(jìn)行交互時(shí)必須轉(zhuǎn)換為規(guī)定的格式,這給具有不同知識(shí)及使用不同工具開發(fā)的的通訊與協(xié)作造成了一定的困難。

二、改進(jìn)的合同網(wǎng)模型

針對(duì)黑板模型存在問(wèn)題以及合同網(wǎng)模型運(yùn)行機(jī)制的特點(diǎn),提出了一種公告板模型，并將其應(yīng)用于合同網(wǎng)模型中可以有效地提高合同網(wǎng)模型的性能。在公告板方式下,各Agent有自己的知識(shí)源,能以不同的格式存放在不同的地點(diǎn).當(dāng)想要參加協(xié)作時(shí),只需將自己的名字、物理位置、資源、當(dāng)前狀態(tài)、如何與他們聯(lián)系、可以提供的服務(wù)或需要得到的服務(wù)在公告板上登記,即可由公告板Agent輔助建立Agent之間匿名的互操作和知識(shí)共享.公告板Agent匹配任務(wù)及Agent,把適當(dāng)?shù)娜蝿?wù)及Agent之間進(jìn)行聯(lián)系所需的信息傳送給適當(dāng)?shù)腁gent,為Agent之間進(jìn)行聯(lián)系提供路由服務(wù)。與任務(wù)有關(guān)的Agent可以通過(guò)公告板建立聯(lián)系,進(jìn)行點(diǎn)對(duì)點(diǎn)的通信。本文根據(jù)AGV的調(diào)度系統(tǒng)對(duì)簡(jiǎn)化合同網(wǎng)模型中的招標(biāo)過(guò)程進(jìn)行了修改：當(dāng)發(fā)起者發(fā)布任務(wù)時(shí),只是將任務(wù)信息發(fā)送給公告板,由公告板進(jìn)行任務(wù)的匹配,并代替發(fā)起者向所有符合要求的參與者招標(biāo),然后,參與者再向發(fā)起者直接投標(biāo)。這樣既避免了發(fā)起者無(wú)限制的招標(biāo),也省去了發(fā)起者搜索參與者的信息。

三、結(jié)論

本文利用多智能體系統(tǒng)敏捷、靈活、實(shí)時(shí)的優(yōu)點(diǎn)，結(jié)合目前合同網(wǎng)協(xié)議取得的研究成果，針對(duì)多AGV運(yùn)行和調(diào)度的實(shí)際問(wèn)題，分析研究了基于黑板模型改進(jìn)合同網(wǎng)協(xié)議的agv調(diào)度協(xié)作機(jī)制，以實(shí)現(xiàn)agv調(diào)度過(guò)程的智能化、合理化。仿真結(jié)果表明，基于改進(jìn)合同網(wǎng)協(xié)議后的agv調(diào)度機(jī)制具有良好的性能表現(xiàn)。本文中考慮引入了黑板模型來(lái)協(xié)調(diào)合同網(wǎng)協(xié)議中雙方的信息溝通，減少了信息阻塞，提高了系統(tǒng)效率,但是實(shí)際情況中還可能發(fā)生中標(biāo)的agent不履行任務(wù)即失信的行為，造成系統(tǒng)資源浪費(fèi)。所以，在未來(lái)進(jìn)一步研究中，可以考慮引入信用度和懲罰機(jī)制來(lái)約束和評(píng)估中標(biāo)agent失信的可能性，提高系統(tǒng)運(yùn)行效率。