余榮洋 金桂根 物流技術與應用 2023-09-06 17:32 發(fā)表于北京

隨著物流行業(yè)智能化程度的提高，AGV在物流業(yè)內的使用范圍越來越廣。AGV不僅可以根據相應的指令實現對包裹的自動搬運，而且能提高分揀效率和安全性，從而提升企業(yè)的物流水平，給顧客更好的用戶體驗。針對AGV系統(tǒng)多車的優(yōu)化調度，尤其是當任務訂單過多時，如何對AGV進行合理的分配，以實現在滿足訂單時效的情況下，使AGV的運行效率實現最優(yōu)，一直是國內外學者的研究熱點。

在多種任務分配的優(yōu)化方法中，多Agent方法是一個較優(yōu)的選項。多Agent方法是指多個Agent之間在通信的基礎上與環(huán)境進行交互，并相互協(xié)調以求共同完成系統(tǒng)任務的方法。多Agent系統(tǒng)中大多是使用分布式合同網協(xié)議作為其內部協(xié)作的溝通機制，合同網協(xié)議在分布式多Agent系統(tǒng)中的應用有其非常突出的一些優(yōu)點，比如合同網協(xié)議的可再擴充性很好，處理復雜動態(tài)環(huán)境能力很強，所以在與多種分布式智能體系統(tǒng)的協(xié)作過程中的使用普遍。

合同網是將系統(tǒng)中的成員角色分為任務管理Agent和任務執(zhí)行Agent，通過模仿經濟行為中的“招標－投標－中標”機制實現任務分配。Agent可以利用對任務的投標值來進行各種相互的協(xié)作與競爭，爭取以最優(yōu)的全局效能和最低的時間代價來實現任務。由于傳統(tǒng)的合同網模型是通過廣播的方式來向系統(tǒng)內部的Agent發(fā)出各種任務信息以及其他相關的消息，感受到這些任務消息后的所有Agent成員均可以參與投標，一旦參加投標活動的Agent數量過多，就會直接導致整個系統(tǒng)內部的網絡通信量過大，這增加了任務管理Agent的決策壓力。

對此研究合同網的學者提出了多種多樣的改進方案，比如：文獻[1]在傳統(tǒng)合同網基礎上引入可信度模型，使得能力不足的Agent無法參與部分投標[1]。文獻[2]借鑒了蟻群算法，將信息素加入招投標過程，并提出基于信息素的多Agent動態(tài)調度策略，從而減少通信量，增強決策實時性[2]。

文獻[3]通過建立Agent能力模型和Agent執(zhí)行任務描述，使多Agent系統(tǒng)的任務分配更適應于動態(tài)環(huán)境[3]。文獻[4]提出利用Agent具有主動感知的特點，加入公共消息黑板作為合同網的傳統(tǒng)媒介，讓任務執(zhí)行Agent通過公共消息黑板來感知任務[4]。文獻[5]設計了基于多Agent通信的多任務協(xié)作時間調度算法，實現了額外代價最小化和窗口時間內完成任務最大化[5]。但上述文獻中并沒有將Agent的主動性和Agent的負載[6]、能力和信任度的綜合考量結合起來。

本文從實際出發(fā)，考慮到在實際倉庫搬運中，任務需進行優(yōu)先級的劃分，AGV優(yōu)先對高優(yōu)先級[7]和時間性強的任務進行運輸。故本文在基于上述文獻的基礎上，對傳統(tǒng)合同網算法的招投標階段進行改良，同時為AGV加入任務緩沖池，不僅可以充分發(fā)揮Agent的主動感知的特點，還能使任務緩沖池中的任務根據其優(yōu)先級更好地進行動態(tài)分配[8]，使得應用場景更貼合實際。在招標階段，Agent通過對AGV的感知系數、能力和信任度等幾個方面進行綜合考量，使得Agent的主動性和智能性可以充分結合。

1.改進合同網模型動態(tài)任務分配框架

本文運輸場景中的動態(tài)任務分配問題，主要涉及3種Agent：倉庫Agent、數據庫Agent和AGV Agent。

數據庫Agent負責整個招投標過程中的信息采集和加工處理，并統(tǒng)一協(xié)調任務執(zhí)行Agent的行為；倉庫Agent負責在接收到訂單消息之后制作標書，并將標書進行公布；當倉庫Agent發(fā)布標書時，所有AGV Agent會根據標書信息先計算自身的感知系數，依據感知系數來決策是否進行投標；倉庫Agent依據AGV Agent反饋的標書中的感知系數進行決策，選擇與最合適的Agent進行簽約。

以上對傳統(tǒng)合同網的改進流程圖，如圖1所示[9][10][11]。

2.改進合同網模型的協(xié)作策略

（1）招標階段

在本文中的運輸場景中，當倉庫Agent作為招標Agent在接收到訂單信息之后，根據以下標書格式對訂單信息中的數據進行收集和整理。

標書的格式為：

Contract=<Task ID，Category，Priority，Li，Le，Capability>

其中，Task ID：此次運輸任務的唯一編碼；

Category：此次任務要運輸的貨物種類；

Priority：此任務的優(yōu)先等級，分別為1,2,3；

Li：此任務中所需搬運貨物的裝載位置；

Le：此任務中所需搬運貨物的卸載位置；

Capability：執(zhí)行此任務所需的能力。

在倉儲系統(tǒng)中，可以用上面的方法將運輸任務表述為：<TC00001,01,1,(IX,IY),(EX,EY),200KG>根據上述定義，這表示一項編號為TC0001，需裝載的貨物種類是01，任務優(yōu)先級為1，需裝載貨物的位置為（IX,IY），需卸載貨物的位置為（EX,EY），此任務所需任務Agent的最低裝載量為200kg。

倉庫Agent將標書進行公布，所有AGV主動去感知標書信息，當標書中的任務優(yōu)先級比自身任務緩沖池中的任務優(yōu)先級要高時，AGV開始計算自身反饋系數并決定是否要對相應任務進行反饋。

（2）投標階段

每臺執(zhí)行任務的AGV的都配有任務緩沖池，任務緩沖池中最多有3個待執(zhí)行的任務，當新的訂單出現的時候，倉庫Agent將訂單信息整理成任務標書，每個任務標書只對應著一個訂單，AGV對整理好的任務標書進行主動感知并計算自身的反饋系數，反饋系數跟AGV的負載情況和自身能力值有關。AGV負載過大或者自身能力值不能滿足任務需求都會導致反饋系數達不到任務要求，則AGV不會對公布的標書信息就行投標。

①AGV負載系數

定義變量：Loadi表示為AGVi的負載系數，其根據優(yōu)先級動態(tài)變化的，i為AGV的序號；表示AGVi的平均工作負載，

表示此時系統(tǒng)內平均工作負載最小的AGV的系數，

表示此時系統(tǒng)內平均工作負載最大的AGV的系數。Mik表示AGVi執(zhí)行的任務，k代表AGV執(zhí)行任務的順序，例如M11表示AGV1在目前正在執(zhí)行的搬運任務，M12表示AGV1在M11完成后將要執(zhí)行的任務，以此類推；M0則表示新任務標書中待分配的搬運任務。TMik 代表完成任務Mik所需要的時間，例如TM23表示AGV2完成其第三項任務所需要的時間。

當AGV1進入工作狀態(tài)后，其任務總數最多只有4個，由正在執(zhí)行的任務和任務緩沖區(qū)的三個任務組成，可分別表示為M11，M12，M13，M14。若此時倉庫Agent公布了一個新的任務M0，且優(yōu)先級高于AGV1任務緩沖池的M14，則AGV1的負載量是只以M11、M12和M13數據為基礎進行計算。

執(zhí)行任務的總時間（T總）=執(zhí)行當前任務（M11）仍需要的時間+完成任務緩沖池中的任務（M12 、M13）所需的時間+新的任務標書中任務（M0）所需的時間：

    (1)

AGV1平均負載量（    ）=執(zhí)行任務的總時間

（T總）/任務總數：

   (2)

其他AGV的平均負載量以此類推。當系統(tǒng)內的AGV都計算得出自身的平均負載量后，此時，AGV1根據下方公式得出自身的負載系數（Load1）為：

  (3)

當Load1=0時，表明AGV1的工作負載為系統(tǒng)內最小，適合對新任務進行投標。

當Load1=1時，表明AGV1的工作負載為系統(tǒng)內最高，不適合對新任務進行投標。

當Load1＜Load2時，說明AGV1的工作負載比AGV2的工作負載低。

上述過程體現了負載系統(tǒng)的動態(tài)變化過程，即當M0出現在系統(tǒng)里面時，各執(zhí)行AGV首先會檢視自身緩沖池中的任務容量，若自身的任務緩沖池仍有剩余空間，則直接將執(zhí)行M0預計所用的時間代入T總和 進行計算，得出其負載系數。若自身的任務緩沖池沒有剩余空間時，則會檢視自身任務緩沖池中是否有任務優(yōu)先級低于M0的任務存在，若沒有，則不對M0作出響應；若有低于M0的任務存在，如上述例子中的AGV1任務緩沖池里面的M14，當AGV1感知到M0出現時，AGV1首先檢查了自身緩沖池容量，在確定自身的任務緩沖池沒有剩余空間后，檢視出自身任務緩沖池中有任務優(yōu)先級低于M0的任務M14，所以在之后計算T總和時，剔除了執(zhí)行M14預計所用的時間，加入了執(zhí)行M0預計所用的時間。這一部分體現了負載系數的具有動態(tài)變化的特征。

②AGV的反饋值

定義變量：Peri表示AGVi對投標任務的反饋值；Loadi表示AGVi在投標任務時的工作負載系數。當AGV最大載重量滿足標書中的能力值時，A=1，否則，A=0。

AGVi根據下方公式來計算自身的反饋系數

       (4)

（3）評標階段

AGVi的感應系數、能力值[12]和信任度在文中具有不同的量綱級別和不同的物理含義，因此本文將對它們進行歸一化處理。

①AGV能力值

在同一項任務標書中，AGV的能力值（Capi）與分配到該任務的可能性呈正相關。本文用AGVi完成標書任務的時間比值，來刻畫其完成任務的能力大小。

定義變量：TM0 ：AGV完成與標書任務的時間；maxTM0 ：系統(tǒng)內的AGV預計完成標書任務的最長用時；minTM0 ：系統(tǒng)內的AGV預計完成標書任務的最短用時，那么，AGVi針對此項任務的能力值Capi為： 

  (5)

當 Cap1> Cap2時，說明針對此標書發(fā)布的任務，AGV1的能力值比AGV2的能力值高。

②AGV的信任度

另一個影響任務分配結果的是倉庫Agent對AGVi的信任度。同樣的，在同一項任務中，信任度越高的AGV分配到任務的可能性越大。

信任度可以從AGVi成功完成任務的次數來表示，隨著AGVi成功完成任務次數的增加，其在倉庫Agent的信任度方面會不斷地積累與提高。

定義變量：Believei：倉庫Agent對于AGVi完成任務的信任度；N為AGVi成功完成任務的總次數；Faili為AGVi中標之后因為自身能力不足而不能完成任務的次數，那么AGVi信任度為：

  (6)

倉庫Agent從AGVi反饋的標書中得知其感知系數，再綜合AGVi的能力值和信任度，綜合三個要素來計算評價AGVi。

 (7)

Valuei表示倉庫Agent對AGVi投標的評價值；Loadi表示AGVi對任務的感知系數；Capi表示AGVi自身能力值；Beli表示倉庫Agent對AGVi的信任度。

AGVi將標書發(fā)送給倉庫Agent，倉庫Agent對所有投標標書進行評價排序，評價值最高者被分配到該任務。以上完整定義了合同網中任務分配策略的形式化表示。

1.仿真實驗場景

SH物流中心是一個現代化物流項目，可對客戶訂單進行快速處理，并完成物料準確快速的存儲、復核、集貨、發(fā)運等業(yè)務。智能倉內運輸系統(tǒng)包括AGV、機器人擺臂、貨架和智能調度管理系統(tǒng)等。AGV主要負責立體庫出庫站臺，機械臂工作臺和月臺之間的搬運，俯瞰圖如圖2所示。

2.仿真實驗的條件

為了評價提出的多屬性評價中標策略的性能，本文做了相應的對比仿真實驗。仿真實驗的條件如下： 

（1）任務屬性：隨機生成任務優(yōu)先級為1,2,3的任務，分配比率為1:3:6。

（2）機械臂隨時可以滿足使用需求，當AGV到達機械臂工位時，機械臂可立刻執(zhí)行貨物搬運任務。

（3）系統(tǒng)中AGV數量：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.基于多屬性評價策略的調度優(yōu)化結果分析 

AGV運行基礎數據，如表1所示。基于改進合同網仿真實驗，傳統(tǒng)合同網系統(tǒng)運行數據和改進合同網系統(tǒng)運行數據，如表2所示。

本文針對傳統(tǒng)合同網的協(xié)商機制進行了改進。在投標階段，AGV利用主動感知的特點計算自身的感知系數并做出是否投標的決策。在評標階段，倉庫Agent通過對AGV的感知系數、能力和信任度進行綜合考量，從而選擇最優(yōu)AGV來執(zhí)行任務，對比實驗證明了本文所提多屬性評價中標策略的有效性和可行性。

本文基于一種理想狀態(tài)下將多Agent技術與倉儲物流系統(tǒng)相結合，同時充分運用Agent的主動性和智能性，可以使AGV系統(tǒng)能夠靈活處理各種突發(fā)事件，增強系統(tǒng)的魯棒性。后續(xù)研究會在本文的基礎上，對機械臂Agent、貨架Agent和AGV系統(tǒng)的協(xié)作做出進一步研究，使應用場景更貼合實際。