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

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

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

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

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

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

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

1.改進(jìn)合同網(wǎng)模型動(dòng)態(tài)任務(wù)分配框架

本文運(yùn)輸場(chǎng)景中的動(dòng)態(tài)任務(wù)分配問(wèn)題，主要涉及3種Agent：倉(cāng)庫(kù)Agent、數(shù)據(jù)庫(kù)Agent和AGV Agent。

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

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

2.改進(jìn)合同網(wǎng)模型的協(xié)作策略

（1）招標(biāo)階段

在本文中的運(yùn)輸場(chǎng)景中，當(dāng)倉(cāng)庫(kù)Agent作為招標(biāo)Agent在接收到訂單信息之后，根據(jù)以下標(biāo)書(shū)格式對(duì)訂單信息中的數(shù)據(jù)進(jìn)行收集和整理。

標(biāo)書(shū)的格式為：

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

其中，Task ID：此次運(yùn)輸任務(wù)的唯一編碼；

Category：此次任務(wù)要運(yùn)輸?shù)呢浳锓N類；

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

Li：此任務(wù)中所需搬運(yùn)貨物的裝載位置；

Le：此任務(wù)中所需搬運(yùn)貨物的卸載位置；

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

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

倉(cāng)庫(kù)Agent將標(biāo)書(shū)進(jìn)行公布，所有AGV主動(dòng)去感知標(biāo)書(shū)信息，當(dāng)標(biāo)書(shū)中的任務(wù)優(yōu)先級(jí)比自身任務(wù)緩沖池中的任務(wù)優(yōu)先級(jí)要高時(shí)，AGV開(kāi)始計(jì)算自身反饋系數(shù)并決定是否要對(duì)相應(yīng)任務(wù)進(jìn)行反饋。

（2）投標(biāo)階段

每臺(tái)執(zhí)行任務(wù)的AGV的都配有任務(wù)緩沖池，任務(wù)緩沖池中最多有3個(gè)待執(zhí)行的任務(wù)，當(dāng)新的訂單出現(xiàn)的時(shí)候，倉(cāng)庫(kù)Agent將訂單信息整理成任務(wù)標(biāo)書(shū)，每個(gè)任務(wù)標(biāo)書(shū)只對(duì)應(yīng)著一個(gè)訂單，AGV對(duì)整理好的任務(wù)標(biāo)書(shū)進(jìn)行主動(dòng)感知并計(jì)算自身的反饋系數(shù)，反饋系數(shù)跟AGV的負(fù)載情況和自身能力值有關(guān)。AGV負(fù)載過(guò)大或者自身能力值不能滿足任務(wù)需求都會(huì)導(dǎo)致反饋系數(shù)達(dá)不到任務(wù)要求，則AGV不會(huì)對(duì)公布的標(biāo)書(shū)信息就行投標(biāo)。

①AGV負(fù)載系數(shù)

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

表示此時(shí)系統(tǒng)內(nèi)平均工作負(fù)載最小的AGV的系數(shù)，

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

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

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

    (1)

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

（T總）/任務(wù)總數(shù)：

   (2)

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

  (3)

當(dāng)Load1=0時(shí)，表明AGV1的工作負(fù)載為系統(tǒng)內(nèi)最小，適合對(duì)新任務(wù)進(jìn)行投標(biāo)。

當(dāng)Load1=1時(shí)，表明AGV1的工作負(fù)載為系統(tǒng)內(nèi)最高，不適合對(duì)新任務(wù)進(jìn)行投標(biāo)。

當(dāng)Load1＜Load2時(shí)，說(shuō)明AGV1的工作負(fù)載比AGV2的工作負(fù)載低。

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

②AGV的反饋值

定義變量：Peri表示AGVi對(duì)投標(biāo)任務(wù)的反饋值；Loadi表示AGVi在投標(biāo)任務(wù)時(shí)的工作負(fù)載系數(shù)。當(dāng)AGV最大載重量滿足標(biāo)書(shū)中的能力值時(shí)，A=1，否則，A=0。

AGVi根據(jù)下方公式來(lái)計(jì)算自身的反饋系數(shù)

       (4)

（3）評(píng)標(biāo)階段

AGVi的感應(yīng)系數(shù)、能力值[12]和信任度在文中具有不同的量綱級(jí)別和不同的物理含義，因此本文將對(duì)它們進(jìn)行歸一化處理。

①AGV能力值

在同一項(xiàng)任務(wù)標(biāo)書(shū)中，AGV的能力值（Capi）與分配到該任務(wù)的可能性呈正相關(guān)。本文用AGVi完成標(biāo)書(shū)任務(wù)的時(shí)間比值，來(lái)刻畫其完成任務(wù)的能力大小。

定義變量：TM0 ：AGV完成與標(biāo)書(shū)任務(wù)的時(shí)間；maxTM0 ：系統(tǒng)內(nèi)的AGV預(yù)計(jì)完成標(biāo)書(shū)任務(wù)的最長(zhǎng)用時(shí)；minTM0 ：系統(tǒng)內(nèi)的AGV預(yù)計(jì)完成標(biāo)書(shū)任務(wù)的最短用時(shí)，那么，AGVi針對(duì)此項(xiàng)任務(wù)的能力值Capi為： 

  (5)

當(dāng) Cap1> Cap2時(shí)，說(shuō)明針對(duì)此標(biāo)書(shū)發(fā)布的任務(wù)，AGV1的能力值比AGV2的能力值高。

②AGV的信任度

另一個(gè)影響任務(wù)分配結(jié)果的是倉(cāng)庫(kù)Agent對(duì)AGVi的信任度。同樣的，在同一項(xiàng)任務(wù)中，信任度越高的AGV分配到任務(wù)的可能性越大。

信任度可以從AGVi成功完成任務(wù)的次數(shù)來(lái)表示，隨著AGVi成功完成任務(wù)次數(shù)的增加，其在倉(cāng)庫(kù)Agent的信任度方面會(huì)不斷地積累與提高。

定義變量：Believei：倉(cāng)庫(kù)Agent對(duì)于AGVi完成任務(wù)的信任度；N為AGVi成功完成任務(wù)的總次數(shù)；Faili為AGVi中標(biāo)之后因?yàn)樽陨砟芰Σ蛔愣荒芡瓿扇蝿?wù)的次數(shù)，那么AGVi信任度為：

  (6)

倉(cāng)庫(kù)Agent從AGVi反饋的標(biāo)書(shū)中得知其感知系數(shù)，再綜合AGVi的能力值和信任度，綜合三個(gè)要素來(lái)計(jì)算評(píng)價(jià)AGVi。

 (7)

Valuei表示倉(cāng)庫(kù)Agent對(duì)AGVi投標(biāo)的評(píng)價(jià)值；Loadi表示AGVi對(duì)任務(wù)的感知系數(shù)；Capi表示AGVi自身能力值；Beli表示倉(cāng)庫(kù)Agent對(duì)AGVi的信任度。

AGVi將標(biāo)書(shū)發(fā)送給倉(cāng)庫(kù)Agent，倉(cāng)庫(kù)Agent對(duì)所有投標(biāo)標(biāo)書(shū)進(jìn)行評(píng)價(jià)排序，評(píng)價(jià)值最高者被分配到該任務(wù)。以上完整定義了合同網(wǎng)中任務(wù)分配策略的形式化表示。

1.仿真實(shí)驗(yàn)場(chǎng)景

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

2.仿真實(shí)驗(yàn)的條件

為了評(píng)價(jià)提出的多屬性評(píng)價(jià)中標(biāo)策略的性能，本文做了相應(yīng)的對(duì)比仿真實(shí)驗(yàn)。仿真實(shí)驗(yàn)的條件如下： 

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

（2）機(jī)械臂隨時(shí)可以滿足使用需求，當(dāng)AGV到達(dá)機(jī)械臂工位時(shí)，機(jī)械臂可立刻執(zhí)行貨物搬運(yùn)任務(wù)。

（3）系統(tǒng)中AGV數(shù)量：9臺(tái)。

當(dāng)任務(wù)需求為整托盤貨物時(shí)，倉(cāng)儲(chǔ)系統(tǒng)的作業(yè)流程具體分解為：

STEP1倉(cāng)儲(chǔ)貨架中的穿梭車將整托盤運(yùn)送至AGV裝載處；

STEP2 AGV裝載整托盤，并將整托盤直接運(yùn)送至月臺(tái)裝卸處；

STEP3 AGV將空托盤運(yùn)送至空托盤組工位；

當(dāng)任務(wù)需求為散托盤任務(wù)時(shí)，倉(cāng)儲(chǔ)系統(tǒng)的作業(yè)流程具體分解為：

STEP1倉(cāng)儲(chǔ)貨架查詢中是否有直接滿足任務(wù)需求的散托盤。若有，AGV執(zhí)行上述操作；若無(wú)，穿梭車將整托盤運(yùn)送至AGV裝載處；

STEP2 AGV裝載整托盤，并將整托盤運(yùn)送至機(jī)械臂工位處；

STEP3 機(jī)械臂工位將托盤上的貨物搬運(yùn)至輸送線上；

STEP4 AGV將散托盤運(yùn)回至倉(cāng)儲(chǔ)貨架。

（4）結(jié)合作業(yè)流程分解，分解AGV搬運(yùn)的動(dòng)作周期：接托盤（升降）－轉(zhuǎn)向上道－勻加速直線運(yùn)動(dòng)－勻速直線運(yùn)動(dòng)－勻減速直線運(yùn)動(dòng)－轉(zhuǎn)向下道－放托盤（升降）。

（5）執(zhí)行任務(wù)的總時(shí)間組成為：t通訊+t升降+n*t上下道+t直線。

3.基于多屬性評(píng)價(jià)策略的調(diào)度優(yōu)化結(jié)果分析 

AGV運(yùn)行基礎(chǔ)數(shù)據(jù)，如表1所示?；诟倪M(jìn)合同網(wǎng)仿真實(shí)驗(yàn)，傳統(tǒng)合同網(wǎng)系統(tǒng)運(yùn)行數(shù)據(jù)和改進(jìn)合同網(wǎng)系統(tǒng)運(yùn)行數(shù)據(jù)，如表2所示。

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

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