2023-09-06 17:32
摘要：隨著物流行業(yè)智能化發(fā)展，AGV在物流領域的應用日益增加，隨之而來的優(yōu)化調(diào)度問題也成為研究熱點。多Agent方法是針對AGV系統(tǒng)多車調(diào)度優(yōu)化的一個較優(yōu)方法，合同網(wǎng)協(xié)議是多Agent系統(tǒng)中應用最多的協(xié)商機制，但傳統(tǒng)合同網(wǎng)算法存在著通信量過大、效率較低的問題。因此，本文利用了Agent主動感知的特點，引入主動感知系數(shù)，并結合Agent能力值和信任度三個指標，提出了一種改進的合同網(wǎng)方法。仿真實驗結果表明改進的合同網(wǎng)可減少通信量，提高AGV系統(tǒng)單位時間內(nèi)的工作效率。
關鍵詞：自動搬運機器人（AGV）、多Agent系統(tǒng)、改進合同網(wǎng)模型、效率
作者：余榮洋 金桂根 云南財經(jīng)大學
隨著物流行業(yè)智能化程度的提高，AGV在物流業(yè)內(nèi)的使用范圍越來越廣。AGV不僅可以根據(jù)相應的指令實現(xiàn)對包裹的自動搬運，而且能提高分揀效率和安全性，從而提升企業(yè)的物流水平，給顧客更好的用戶體驗。針對AGV系統(tǒng)多車的優(yōu)化調(diào)度，尤其是當任務訂單過多時，如何對AGV進行合理的分配，以實現(xiàn)在滿足訂單時效的情況下，使AGV的運行效率實現(xiàn)最優(yōu)，一直是國內(nèi)外學者的研究熱點。
在多種任務分配的優(yōu)化方法中，多Agent方法是一個較優(yōu)的選項。多Agent方法是指多個Agent之間在通信的基礎上與環(huán)境進行交互，并相互協(xié)調(diào)以求共同完成系統(tǒng)任務的方法。多Agent系統(tǒng)中大多是使用分布式合同網(wǎng)協(xié)議作為其內(nèi)部協(xié)作的溝通機制，合同網(wǎng)協(xié)議在分布式多Agent系統(tǒng)中的應用有其非常突出的一些優(yōu)點，比如合同網(wǎng)協(xié)議的可再擴充性很好，處理復雜動態(tài)環(huán)境能力很強，所以在與多種分布式智能體系統(tǒng)的協(xié)作過程中的使用普遍。
合同網(wǎng)是將系統(tǒng)中的成員角色分為任務管理Agent和任務執(zhí)行Agent，通過模仿經(jīng)濟行為中的“招標－投標－中標”機制實現(xiàn)任務分配。Agent可以利用對任務的投標值來進行各種相互的協(xié)作與競爭，爭取以最優(yōu)的全局效能和最低的時間代價來實現(xiàn)任務。由于傳統(tǒng)的合同網(wǎng)模型是通過廣播的方式來向系統(tǒng)內(nèi)部的Agent發(fā)出各種任務信息以及其他相關的消息，感受到這些任務消息后的所有Agent成員均可以參與投標，一旦參加投標活動的Agent數(shù)量過多，就會直接導致整個系統(tǒng)內(nèi)部的網(wǎng)絡通信量過大，這增加了任務管理Agent的決策壓力。
對此研究合同網(wǎng)的學者提出了多種多樣的改進方案，比如：文獻[1]在傳統(tǒng)合同網(wǎng)基礎上引入可信度模型，使得能力不足的Agent無法參與部分投標[1]。文獻[2]借鑒了蟻群算法，將信息素加入招投標過程，并提出基于信息素的多Agent動態(tài)調(diào)度策略，從而減少通信量，增強決策實時性[2]。
文獻[3]通過建立Agent能力模型和Agent執(zhí)行任務描述，使多Agent系統(tǒng)的任務分配更適應于動態(tài)環(huán)境[3]。文獻[4]提出利用Agent具有主動感知的特點，加入公共消息黑板作為合同網(wǎng)的傳統(tǒng)媒介，讓任務執(zhí)行Agent通過公共消息黑板來感知任務[4]。文獻[5]設計了基于多Agent通信的多任務協(xié)作時間調(diào)度算法，實現(xiàn)了額外代價最小化和窗口時間內(nèi)完成任務最大化[5]。但上述文獻中并沒有將Agent的主動性和Agent的負載[6]、能力和信任度的綜合考量結合起來。
本文從實際出發(fā)，考慮到在實際倉庫搬運中，任務需進行優(yōu)先級的劃分，AGV優(yōu)先對高優(yōu)先級[7]和時間性強的任務進行運輸。故本文在基于上述文獻的基礎上，對傳統(tǒng)合同網(wǎng)算法的招投標階段進行改良，同時為AGV加入任務緩沖池，不僅可以充分發(fā)揮Agent的主動感知的特點，還能使任務緩沖池中的任務根據(jù)其優(yōu)先級更好地進行動態(tài)分配[8]，使得應用場景更貼合實際。在招標階段，Agent通過對AGV的感知系數(shù)、能力和信任度等幾個方面進行綜合考量，使得Agent的主動性和智能性可以充分結合。
1.改進合同網(wǎng)模型動態(tài)任務分配框架
本文運輸場景中的動態(tài)任務分配問題，主要涉及3種Agent：倉庫Agent、數(shù)據(jù)庫Agent和AGV Agent。
數(shù)據(jù)庫Agent負責整個招投標過程中的信息采集和加工處理，并統(tǒng)一協(xié)調(diào)任務執(zhí)行Agent的行為；倉庫Agent負責在接收到訂單消息之后制作標書，并將標書進行公布；當倉庫Agent發(fā)布標書時，所有AGV Agent會根據(jù)標書信息先計算自身的感知系數(shù)，依據(jù)感知系數(shù)來決策是否進行投標；倉庫Agent依據(jù)AGV Agent反饋的標書中的感知系數(shù)進行決策，選擇與最合適的Agent進行簽約。
以上對傳統(tǒng)合同網(wǎng)的改進流程圖，如圖1所示[9][10][11]。
2.改進合同網(wǎng)模型的協(xié)作策略
（1）招標階段
在本文中的運輸場景中，當倉庫Agent作為招標Agent在接收到訂單信息之后，根據(jù)以下標書格式對訂單信息中的數(shù)據(jù)進行收集和整理。
標書的格式為：
Contract=<Task ID，Category，Priority，Li，Le，Capability>
其中，Task ID：此次運輸任務的唯一編碼；
Category：此次任務要運輸?shù)呢浳锓N類；
Priority：此任務的優(yōu)先等級，分別為1,2,3；
Li：此任務中所需搬運貨物的裝載位置；
Le：此任務中所需搬運貨物的卸載位置；
Capability：執(zhí)行此任務所需的能力。
在倉儲系統(tǒng)中，可以用上面的方法將運輸任務表述為：<TC00001,01,1,(IX,IY),(EX,EY),200KG>根據(jù)上述定義，這表示一項編號為TC0001，需裝載的貨物種類是01，任務優(yōu)先級為1，需裝載貨物的位置為（IX,IY），需卸載貨物的位置為（EX,EY），此任務所需任務Agent的最低裝載量為200kg。
倉庫Agent將標書進行公布，所有AGV主動去感知標書信息，當標書中的任務優(yōu)先級比自身任務緩沖池中的任務優(yōu)先級要高時，AGV開始計算自身反饋系數(shù)并決定是否要對相應任務進行反饋。
（2）投標階段
每臺執(zhí)行任務的AGV的都配有任務緩沖池，任務緩沖池中最多有3個待執(zhí)行的任務，當新的訂單出現(xiàn)的時候，倉庫Agent將訂單信息整理成任務標書，每個任務標書只對應著一個訂單，AGV對整理好的任務標書進行主動感知并計算自身的反饋系數(shù)，反饋系數(shù)跟AGV的負載情況和自身能力值有關。AGV負載過大或者自身能力值不能滿足任務需求都會導致反饋系數(shù)達不到任務要求，則AGV不會對公布的標書信息就行投標。
①AGV負載系數(shù)
定義變量：Loadi表示為AGVi的負載系數(shù)，其根據(jù)優(yōu)先級動態(tài)變化的，i為AGV的序號；表示AGVi的平均工作負載，
表示此時系統(tǒng)內(nèi)平均工作負載最小的AGV的系數(shù)，
表示此時系統(tǒng)內(nèi)平均工作負載最大的AGV的系數(shù)。Mik表示AGVi執(zhí)行的任務，k代表AGV執(zhí)行任務的順序，例如M11表示AGV1在目前正在執(zhí)行的搬運任務，M12表示AGV1在M11完成后將要執(zhí)行的任務，以此類推；M0則表示新任務標書中待分配的搬運任務。TMik 代表完成任務Mik所需要的時間，例如TM23表示AGV2完成其第三項任務所需要的時間。
當AGV1進入工作狀態(tài)后，其任務總數(shù)最多只有4個，由正在執(zhí)行的任務和任務緩沖區(qū)的三個任務組成，可分別表示為M11，M12，M13，M14。若此時倉庫Agent公布了一個新的任務M0，且優(yōu)先級高于AGV1任務緩沖池的M14，則AGV1的負載量是只以M11、M12和M13數(shù)據(jù)為基礎進行計算。
執(zhí)行任務的總時間（T總）=執(zhí)行當前任務（M11）仍需要的時間+完成任務緩沖池中的任務（M12 、M13）所需的時間+新的任務標書中任務（M0）所需的時間：
(1)
AGV1平均負載量（ ）=執(zhí)行任務的總時間
（T總）/任務總數(shù)：
(2)
其他AGV的平均負載量以此類推。當系統(tǒng)內(nèi)的AGV都計算得出自身的平均負載量后，此時，AGV1根據(jù)下方公式得出自身的負載系數(shù)（Load1）為：
(3)
當Load1=0時，表明AGV1的工作負載為系統(tǒng)內(nèi)最小，適合對新任務進行投標。
當Load1=1時，表明AGV1的工作負載為系統(tǒng)內(nèi)最高，不適合對新任務進行投標。
當Load1＜Load2時，說明AGV1的工作負載比AGV2的工作負載低。
上述過程體現(xiàn)了負載系統(tǒng)的動態(tài)變化過程，即當M0出現(xiàn)在系統(tǒng)里面時，各執(zhí)行AGV首先會檢視自身緩沖池中的任務容量，若自身的任務緩沖池仍有剩余空間，則直接將執(zhí)行M0預計所用的時間代入T總和 進行計算，得出其負載系數(shù)。若自身的任務緩沖池沒有剩余空間時，則會檢視自身任務緩沖池中是否有任務優(yōu)先級低于M0的任務存在，若沒有，則不對M0作出響應；若有低于M0的任務存在，如上述例子中的AGV1任務緩沖池里面的M14，當AGV1感知到M0出現(xiàn)時，AGV1首先檢查了自身緩沖池容量，在確定自身的任務緩沖池沒有剩余空間后，檢視出自身任務緩沖池中有任務優(yōu)先級低于M0的任務M14，所以在之后計算T總和
時，剔除了執(zhí)行M14預計所用的時間，加入了執(zhí)行M0預計所用的時間。這一部分體現(xiàn)了負載系數(shù)的具有動態(tài)變化的特征。
②AGV的反饋值
定義變量：Peri表示AGVi對投標任務的反饋值；Loadi表示AGVi在投標任務時的工作負載系數(shù)。當AGV最大載重量滿足標書中的能力值時，A=1，否則，A=0。
AGVi根據(jù)下方公式來計算自身的反饋系數(shù)
(4)
（3）評標階段
AGVi的感應系數(shù)、能力值[12]和信任度在文中具有不同的量綱級別和不同的物理含義，因此本文將對它們進行歸一化處理。
①AGV能力值
在同一項任務標書中，AGV的能力值（Capi）與分配到該任務的可能性呈正相關。本文用AGVi完成標書任務的時間比值，來刻畫其完成任務的能力大小。
定義變量：TM0 ：AGV完成與標書任務的時間；maxTM0 ：系統(tǒng)內(nèi)的AGV預計完成標書任務的最長用時；minTM0 ：系統(tǒng)內(nèi)的AGV預計完成標書任務的最短用時，那么，AGVi針對此項任務的能力值Capi為：
(5)
當 Cap1> Cap2時，說明針對此標書發(fā)布的任務，AGV1的能力值比AGV2的能力值高。
②AGV的信任度
另一個影響任務分配結果的是倉庫Agent對AGVi的信任度。同樣的，在同一項任務中，信任度越高的AGV分配到任務的可能性越大。
信任度可以從AGVi成功完成任務的次數(shù)來表示，隨著AGVi成功完成任務次數(shù)的增加，其在倉庫Agent的信任度方面會不斷地積累與提高。
定義變量：Believei：倉庫Agent對于AGVi完成任務的信任度；N為AGVi成功完成任務的總次數(shù)；Faili為AGVi中標之后因為自身能力不足而不能完成任務的次數(shù)，那么AGVi信任度為：
(6)
倉庫Agent從AGVi反饋的標書中得知其感知系數(shù)，再綜合AGVi的能力值和信任度，綜合三個要素來計算評價AGVi。
(7)
Valuei表示倉庫Agent對AGVi投標的評價值；Loadi表示AGVi對任務的感知系數(shù)；Capi表示AGVi自身能力值；Beli表示倉庫Agent對AGVi的信任度。
AGVi將標書發(fā)送給倉庫Agent，倉庫Agent對所有投標標書進行評價排序，評價值最高者被分配到該任務。以上完整定義了合同網(wǎng)中任務分配策略的形式化表示。
1.仿真實驗場景
SH物流中心是一個現(xiàn)代化物流項目，可對客戶訂單進行快速處理，并完成物料準確快速的存儲、復核、集貨、發(fā)運等業(yè)務。智能倉內(nèi)運輸系統(tǒng)包括AGV、機器人擺臂、貨架和智能調(diào)度管理系統(tǒng)等。AGV主要負責立體庫出庫站臺，機械臂工作臺和月臺之間的搬運，俯瞰圖如圖2所示。
2.仿真實驗的條件
為了評價提出的多屬性評價中標策略的性能，本文做了相應的對比仿真實驗。仿真實驗的條件如下：
（1）任務屬性：隨機生成任務優(yōu)先級為1,2,3的任務，分配比率為1:3:6。
（2）機械臂隨時可以滿足使用需求，當AGV到達機械臂工位時，機械臂可立刻執(zhí)行貨物搬運任務。
（3）系統(tǒng)中AGV數(shù)量：9臺。
當任務需求為整托盤貨物時，倉儲系統(tǒng)的作業(yè)流程具體分解為：
STEP1倉儲貨架中的穿梭車將整托盤運送至AGV裝載處；
STEP2 AGV裝載整托盤，并將整托盤直接運送至月臺裝卸處；
STEP3 AGV將空托盤運送至空托盤組工位；
當任務需求為散托盤任務時，倉儲系統(tǒng)的作業(yè)流程具體分解為：
STEP1倉儲貨架查詢中是否有直接滿足任務需求的散托盤。若有，AGV執(zhí)行上述操作；若無，穿梭車將整托盤運送至AGV裝載處；
STEP2 AGV裝載整托盤，并將整托盤運送至機械臂工位處；
STEP3 機械臂工位將托盤上的貨物搬運至輸送線上；
STEP4 AGV將散托盤運回至倉儲貨架。
（4）結合作業(yè)流程分解，分解AGV搬運的動作周期：接托盤（升降）－轉向上道－勻加速直線運動－勻速直線運動－勻減速直線運動－轉向下道－放托盤（升降）。
（5）執(zhí)行任務的總時間組成為：t通訊+t升降+n*t上下道+t直線。
3.基于多屬性評價策略的調(diào)度優(yōu)化結果分析
AGV運行基礎數(shù)據(jù)，如表1所示。基于改進合同網(wǎng)仿真實驗，傳統(tǒng)合同網(wǎng)系統(tǒng)運行數(shù)據(jù)和改進合同網(wǎng)系統(tǒng)運行數(shù)據(jù)，如表2所示。
本文針對傳統(tǒng)合同網(wǎng)的協(xié)商機制進行了改進。在投標階段，AGV利用主動感知的特點計算自身的感知系數(shù)并做出是否投標的決策。在評標階段，倉庫Agent通過對AGV的感知系數(shù)、能力和信任度進行綜合考量，從而選擇最優(yōu)AGV來執(zhí)行任務，對比實驗證明了本文所提多屬性評價中標策略的有效性和可行性。
本文基于一種理想狀態(tài)下將多Agent技術與倉儲物流系統(tǒng)相結合，同時充分運用Agent的主動性和智能性，可以使AGV系統(tǒng)能夠靈活處理各種突發(fā)事件，增強系統(tǒng)的魯棒性。后續(xù)研究會在本文的基礎上，對機械臂Agent、貨架Agent和AGV系統(tǒng)的協(xié)作做出進一步研究，使應用場景更貼合實際。
參考文獻: [1] 趙新字,林作銓.合同網(wǎng)協(xié)議中的Agent可信度模型[J].計算機科學,2006, 33: 6. [2] 陳鳴,朱海華,張澤群,等. [車間調(diào)度]基于信息素的多Agent車間調(diào)度策略[J].中國機械工程, 2018, 29(22): 2659. [3] 李明,劉瑋,張彥鐸.基于改進合同網(wǎng)協(xié)議的多Agent動態(tài)任務分配[J].山東大學學報(工學版), 2015, 46(2): 51-56. [4] 林琳,劉鋒.基于改進合同網(wǎng)協(xié)議的多Agent協(xié)作模型[J].計算機技術與發(fā)展, 2010, 20(3): 71-75. [5] 胡晶晶,曹元大,焦德朝,等.基于多Agent的多任務協(xié)作時間調(diào)度算法研究[J].計算機集成制造系統(tǒng), 2005, 11(3): 394-398. [6] 裘杭萍,覃垚,胡汭,等.多Agent系統(tǒng)中基于改進合同網(wǎng)模型的任務分配研究[D]. ,2012. [7] 秦久峰,曾凡明,陳于濤.基于改進合同網(wǎng)的多Agent系統(tǒng)協(xié)作機理研究[J].武漢理工大學學報,2014,38(5):1065-1069. [8] 張海俊,史忠植.動態(tài)合同網(wǎng)協(xié)議[J].計算機工程,2004,30(21):44-57. [9] 唐蘇,朱一凡,李群,等.多Agent系統(tǒng)任務分配方法綜述[J].系統(tǒng)工程與電子技術,2010, 32(10):2155-2161. [10] 翟政,何明,徐鵬等.基于市場機制的無人集群任務分配研究綜述[J/OL].計算機應用研究:1-9 [11] Buehler J, Pagnucco M. A framework for task planning in heterogeneous multi robot systems based on robot capabilities[C]//Twenty-eighth AAAI conference on artificial intelligence. 2014. [12] Confessore G, Fabiano M, Liotta G. A network flow based heuristic approach for optimising AGV movements[J]. Journal of Intelligent Manufacturing, 2013, 24(2): 405-419.
