基于資源拍賣的農(nóng)業(yè)多機(jī)器人任務(wù)分配

趙 輝 郝夢(mèng)雅 王紅君 岳有軍

1(天津理工大學(xué)天津市復(fù)雜系統(tǒng)控制理論與應(yīng)用重點(diǎn)實(shí)驗(yàn)室 天津 300384)2(天津農(nóng)學(xué)院工程技術(shù)學(xué)院 天津 300384)

0 引 言

在農(nóng)業(yè)生產(chǎn)中，多機(jī)器人協(xié)作對(duì)于實(shí)現(xiàn)規(guī)模化、多樣化、精準(zhǔn)化起重要作用，并在實(shí)際中得到廣泛運(yùn)用[1]。多機(jī)器系統(tǒng)研究中，任務(wù)分配問題(Multi-robot task allocation，MRTA)是基礎(chǔ)和研究熱點(diǎn)之一[2]。

MRTA的目標(biāo)是建立機(jī)器人和任務(wù)之間的有效關(guān)系。傳統(tǒng)的MRTA問題處理任務(wù)時(shí)，每個(gè)任務(wù)只能通過一個(gè)已符合需求的機(jī)器人來完成[3]，當(dāng)任務(wù)需求超出單個(gè)機(jī)器人能力時(shí)，機(jī)器人則無法完成任務(wù)。因此，針對(duì)單機(jī)器人這一任務(wù)缺陷，Parker等[4]提出了使一組異構(gòu)機(jī)器人形成聯(lián)盟，共享傳感器來完成任務(wù)，但計(jì)算成本較高。為了降低計(jì)算成本，Chen等[5]設(shè)計(jì)了兩個(gè)基于聯(lián)盟的資源約束分配方法，即序列聯(lián)盟和整體聯(lián)盟方法，計(jì)算復(fù)雜度顯著改進(jìn)，但完成任務(wù)機(jī)器人所需的資源數(shù)量須事先指定，難以在實(shí)際中實(shí)現(xiàn)。同時(shí)采用貪婪的解決方案，可能導(dǎo)致資源浪費(fèi)。為降低時(shí)間和通信復(fù)雜度，Cao等[6]提出組級(jí)任務(wù)分配和成員級(jí)任務(wù)分配，采用改進(jìn)的PSO-FSA和分布式拍賣算法求解。

近年來基于分布式的拍賣分配算法在多機(jī)器人任務(wù)分配中受到廣泛關(guān)注，基于拍賣的方法是以市場(chǎng)經(jīng)濟(jì)原則為基礎(chǔ)，使其利潤(rùn)最大化，從而導(dǎo)致收入再分配和產(chǎn)出的有效生產(chǎn)。與集中式方法相比，其可以得到計(jì)算量小、可擴(kuò)展性高的靈活任務(wù)分配結(jié)果，并有效地產(chǎn)生次優(yōu)解[7]。姜來浩等[8]為解決多機(jī)器人在搜索過程中多任務(wù)分配和多機(jī)器人利用率問題，提出了一種帶有即時(shí)拍賣的K-means聚類捆綁式拍賣算法，通過K-means聚類算法解決多機(jī)器人系統(tǒng)中的多任務(wù)捆綁問題，再運(yùn)用捆綁式拍賣機(jī)制把聚類分配給相應(yīng)的機(jī)器人。趙明明等[9]針對(duì)多無人機(jī)實(shí)現(xiàn)同時(shí)攻擊目標(biāo)的任務(wù)，提出了拍賣算法，使無人機(jī)在不確定因素中到達(dá)目標(biāo)的時(shí)間趨于一致。許可等[10]提出了將任務(wù)根據(jù)類型分組，以總收益最大為目標(biāo)函數(shù)，考慮無人機(jī)能力、任務(wù)分組等約束條件建立模型。設(shè)計(jì)了帶共享存儲(chǔ)中心的分布式拍賣算法，通過無人機(jī)個(gè)體目標(biāo)的最大化實(shí)現(xiàn)了整體目標(biāo)最大化，但該方法未考慮再充電問題，機(jī)器人使用初始給定的能量來執(zhí)行任務(wù)。

綜上所述，現(xiàn)有基于拍賣方法的研究雖然較多，但僅考慮在路徑長(zhǎng)度、時(shí)間下的最優(yōu)分配。實(shí)際工作中，機(jī)器人存在資源填充問題，當(dāng)機(jī)器人在長(zhǎng)期執(zhí)行任務(wù)中資源量不足(如電池電量低或機(jī)器人存儲(chǔ)量少)時(shí)，機(jī)器人將無法執(zhí)行或按時(shí)完成其給定的任務(wù)，從而增大了運(yùn)行時(shí)間成本，分配結(jié)果與實(shí)際工作將產(chǎn)生較大偏差，從而失去預(yù)估分配的意義。

因此，本文提出一種基于資源的拍賣算法，與現(xiàn)有的拍賣算法相比，機(jī)器人在進(jìn)行任務(wù)分配時(shí)，認(rèn)為資源是可再填充的或可替換的。在分配中，每個(gè)機(jī)器人都會(huì)考慮其工作期間的資源消耗，即出價(jià)。當(dāng)它們中的任何一個(gè)低于一定的閾值時(shí)，機(jī)器人就會(huì)立即停止執(zhí)行任務(wù)，并訪問各自的站點(diǎn)來補(bǔ)充它們的資源。通過考慮機(jī)器人的執(zhí)行能力，采用分散的競(jìng)價(jià)和分配過程，通過仿真實(shí)驗(yàn)可得，該算法在任務(wù)完成時(shí)間和機(jī)器人之間的通信等方面最大限度地提高了機(jī)器人資源的使用效率，并且任務(wù)分配消耗出價(jià)與實(shí)際工作消耗更接近，增加了機(jī)器人工作的準(zhǔn)確性。

1 問題描述

多機(jī)器人協(xié)同任務(wù)規(guī)劃需要多個(gè)農(nóng)機(jī)和多個(gè)作業(yè)地塊之間建立一種映射關(guān)系，在滿足實(shí)際作業(yè)約束條件的前提下，生成一個(gè)最優(yōu)的任務(wù)調(diào)度方案。現(xiàn)有的大多數(shù)研究是通過任務(wù)中機(jī)器人走過的距離、完成任務(wù)所需的時(shí)間或固有的資源進(jìn)行任務(wù)分配，從而導(dǎo)致分配出現(xiàn)“就近”問題[11]。同時(shí)，機(jī)器人在長(zhǎng)期任務(wù)操作過程中存在能量消耗問題，產(chǎn)生能量限制，影響分配結(jié)果。因此，本文在進(jìn)行任務(wù)分配時(shí)，既考慮了機(jī)器人數(shù)目約束、工作時(shí)間約束、距離約束，又加入了任務(wù)執(zhí)行能力的約束，考慮了機(jī)器人在任務(wù)執(zhí)行期間的電量消耗問題。根據(jù)農(nóng)田機(jī)器人智能自主執(zhí)行任務(wù)場(chǎng)景，以性能指標(biāo)最小為目標(biāo)函數(shù)，構(gòu)建MRTA問題描述，使各個(gè)農(nóng)機(jī)有序地為農(nóng)田地塊服務(wù)，降低整個(gè)系統(tǒng)的執(zhí)行代價(jià)，提高作業(yè)效率，實(shí)現(xiàn)區(qū)域農(nóng)田內(nèi)的多機(jī)協(xié)同作業(yè)調(diào)度管理。

1.1 約束指標(biāo)

1) 機(jī)器人數(shù)目約束。在實(shí)際農(nóng)田環(huán)境中任務(wù)目標(biāo)數(shù)目遠(yuǎn)遠(yuǎn)大于機(jī)器人數(shù)目，因此在進(jìn)行任務(wù)編隊(duì)分配時(shí)，要求每個(gè)機(jī)器人執(zhí)行多個(gè)目標(biāo)任務(wù)；所有的任務(wù)都應(yīng)分配給機(jī)器人；每個(gè)任務(wù)由一個(gè)機(jī)器人執(zhí)行。

(1)

(2)

式中：ζ是機(jī)器人的集合，即ζ={1,2,…,NR}；ψ為任務(wù)集合，即ψ={1,2,…,NT}；Ai表示機(jī)器人i的有序任務(wù)列表；如果任務(wù)j在Ai中，則e(j，Ai)=1，否則等于0。

2) 電量約束。機(jī)器人i從起始點(diǎn)到任務(wù)j的距離可以表示為：

(3)

任務(wù)i與任務(wù)j的距離表示為：

(4)

根據(jù)機(jī)器人和任務(wù)目標(biāo)的位置，計(jì)算機(jī)器人執(zhí)行期間各自的電量消耗，為確保機(jī)器人自身安全，要求完成任何任務(wù)后機(jī)器人所有資源元素都應(yīng)高于閾值。

(5)

式中：ξ為資源集合，即ξ={1,2,…,NL}。

3) 任務(wù)載荷數(shù)目。任務(wù)載荷表示每個(gè)機(jī)器人可以執(zhí)行任務(wù)數(shù)目，約束可以表示為：

(6)

1.2 任務(wù)代價(jià)

為了考慮在任務(wù)分配中機(jī)器人的資源影響，可以用全局目標(biāo)函數(shù)的最小化表示：

(7)

2 算法設(shè)計(jì)

2.1 MTSP模型

當(dāng)任務(wù)數(shù)量多于機(jī)器人數(shù)量時(shí)，會(huì)出現(xiàn)多個(gè)任務(wù)同時(shí)分配給一個(gè)農(nóng)機(jī)的情況，此時(shí)就需要解決任務(wù)序列規(guī)劃問題。任務(wù)序列規(guī)劃問題與旅行商問題(TSP)[12]相似，主要差別為：TSP是單一旅行商從起點(diǎn)出發(fā)，完成系列任務(wù)后回到起始點(diǎn)的路徑；而本文的MTSP是機(jī)器人完成所有任務(wù)后，不需要回到起點(diǎn)。因此，在計(jì)算路徑代價(jià)時(shí)，只需要計(jì)算起點(diǎn)到最后目標(biāo)點(diǎn)之間走過的路徑長(zhǎng)度。

2.2 考慮資源的拍賣算法分配過程

以市場(chǎng)經(jīng)濟(jì)為原則的基礎(chǔ)拍賣方法中，機(jī)器人根據(jù)自身的局部信息計(jì)算報(bào)價(jià)，任務(wù)分配完全由機(jī)器人的報(bào)價(jià)決定。在拍賣算法中，拍賣代理對(duì)從投標(biāo)人代理收到的出價(jià)進(jìn)行評(píng)估，然后拍賣人將任務(wù)分配給出價(jià)最高的投標(biāo)人[13]。

本文提出面向資源的競(jìng)價(jià)生成算法，考慮了機(jī)器人的剩余資源，并根據(jù)預(yù)期成本生成一個(gè)競(jìng)價(jià)值。在工作中資源可以再填充，場(chǎng)地內(nèi)設(shè)置一定量的充電樁，當(dāng)機(jī)器人電量低于某些閾值時(shí)，機(jī)器人將不能執(zhí)行或完成其給定的任務(wù)，轉(zhuǎn)向充電樁進(jìn)行充電，確保足夠能源執(zhí)行當(dāng)前任務(wù)。

圖1所示為機(jī)器人i對(duì)于任務(wù)j的投標(biāo)過程。

圖1 機(jī)器人i對(duì)于任務(wù)j的投標(biāo)生成過程

為了考慮在任務(wù)分配中機(jī)器人的資源影響，將任務(wù)列表中任務(wù)的資源向量存儲(chǔ)在資源列表中，則機(jī)器人i的資源列表定義為：

(8)

2.2.1投標(biāo)生成過程

投標(biāo)時(shí)位于路徑k的再填充站的站向量為:

V(k)=[v1(k)v2(k) …vNL(k)]

k∈{1,2,…,NP} (9)

(1) 機(jī)器人通過路徑1完成任務(wù)j，則其資源向量為：

(10)

(2) 通過除路徑1的其他路徑時(shí)：

(11)

通過式(10)、式(11)可以得出，機(jī)器人在nj中執(zhí)行任務(wù)j時(shí)每個(gè)路徑的資源向量為：

(12)

(13)

式中：I是NL×NL的單位矩陣。

2.2.2路徑選擇概率

機(jī)器人i對(duì)于任務(wù)j選擇路徑k的任務(wù)保證概率為：

(14)

(15)

用歸一化路徑的任務(wù)保證概率的變化率計(jì)算路徑選擇概率，機(jī)器人i執(zhí)行任務(wù)j的路徑k的任務(wù)保證概率的變化率為：

(16)

式中：λm(k)(m(k)∈{1,2，…，NP})代表第m(k)個(gè)最小概率值。

機(jī)器人i對(duì)任務(wù)j選擇路徑k的選擇概率為：

(17)

由式(12)-式(13)、式(17)投標(biāo)代價(jià)及路徑選擇概率可得，機(jī)器人i對(duì)于任務(wù)j的估計(jì)資源向量為:

(18)

估計(jì)成本為：

(19)

機(jī)器人i對(duì)于任務(wù)j的出價(jià)為：

(20)

(21)

2.3 拍賣流程

基于拍賣算法的任務(wù)分配由投標(biāo)生成、勝利者更新、任務(wù)交易和列表更新四個(gè)過程組成。與傳統(tǒng)的競(jìng)價(jià)生成過程不同的是，在假設(shè)機(jī)器人有足夠的資源來執(zhí)行任務(wù)的前提下，任務(wù)的競(jìng)價(jià)計(jì)算是確定的，所提出的投標(biāo)生成過程采用了考慮機(jī)器人資源的概率生成方法。四個(gè)過程間的數(shù)據(jù)流具體步驟如下：

步驟一勝利者更新過程接收交易任務(wù)的投標(biāo)消息，并向投標(biāo)生成過程請(qǐng)求新交易任務(wù)的投標(biāo)。

步驟二投標(biāo)生成過程通過列表更新過程提供任務(wù)列表、投標(biāo)列表、資源列表計(jì)算新任務(wù)的投標(biāo)。

步驟三勝利者更新當(dāng)前交易任務(wù)的信息，確定投標(biāo)的任務(wù)，為該任務(wù)發(fā)送投標(biāo)、交易任務(wù)后更新交易列表。

步驟四接受新的任務(wù)后進(jìn)行列表更新，并把過時(shí)的任務(wù)發(fā)送給勝利者。

3 仿真與分析

為驗(yàn)證算法性能，在Windows 10操作系統(tǒng)上，基于MATLAB 2016a環(huán)境實(shí)現(xiàn)算法的仿真。

實(shí)驗(yàn)一：模擬在識(shí)別病害作物后，噴灑機(jī)器人智能性地進(jìn)行病害區(qū)域藥物治理的工作，設(shè)定有3個(gè)農(nóng)業(yè)機(jī)器人及30個(gè)病害作業(yè)地塊，即R=3，T=30。取每個(gè)地塊邊界上的某一點(diǎn)位置坐標(biāo)作為該地塊的任務(wù)坐標(biāo)進(jìn)行實(shí)驗(yàn)。所有機(jī)器人單位電量消耗均為1，電池容量約束可看作路徑長(zhǎng)度的約束，3個(gè)機(jī)器人從同一位置出發(fā)，得到MRTA優(yōu)化結(jié)果。機(jī)器人的起始位置、電池容量和儲(chǔ)備載荷參數(shù)信息如表1所示。

表1 機(jī)器人性能參數(shù)

當(dāng)任務(wù)點(diǎn)位置如圖2所示時(shí)，通過本文基于資源的模型分配可得，機(jī)器人分別執(zhí)行10個(gè)任務(wù)量，滿足任務(wù)載荷約束，同時(shí)基于資源量最優(yōu)、距離最優(yōu)得到分配結(jié)果，證明本文算法的合理性。

圖2 多機(jī)器人任務(wù)分配結(jié)果

由圖2可得機(jī)器人任務(wù)最優(yōu)分配執(zhí)行結(jié)果如表2所示。

表2 任務(wù)分配優(yōu)化結(jié)果

實(shí)驗(yàn)二：對(duì)重復(fù)連續(xù)單項(xiàng)拍賣(RSSIA)、文獻(xiàn)[8]基于聚類的捆綁式算法(KCA-I)、文獻(xiàn)[10]基于固定載荷量的拍賣算法及本文算法，分別進(jìn)行數(shù)量為3、5、7、9、11的機(jī)器人進(jìn)行對(duì)比，觀察本文算法在相同機(jī)器人數(shù)量下的任務(wù)完成量及資源消耗情況，如圖3所示。

(a) 機(jī)器人任務(wù)完成量

(b) 機(jī)器人資源消耗量圖3 算法對(duì)比圖

(22)

式中：dw*j為機(jī)器人w與任務(wù)j的距離。

(23)

實(shí)驗(yàn)結(jié)果表明，本文方法考慮了機(jī)器人多項(xiàng)任務(wù)中存在的資源不足以補(bǔ)充資源的消耗量情況，得到的仿真結(jié)果能正確估計(jì)任務(wù)完成時(shí)間和資源的消耗，與實(shí)際工作結(jié)果更接近。

4 結(jié) 語

本文考慮了基于資源的影響，建立了多機(jī)作業(yè)任務(wù)分配模型。運(yùn)用拍賣算法進(jìn)行任務(wù)分配，充分考慮了機(jī)器人運(yùn)行所需的資源消耗量，以機(jī)器人執(zhí)行能力、距離、時(shí)間為出價(jià)競(jìng)拍任務(wù)。從仿真結(jié)果可以看出，在相同條件下本文算法相對(duì)其他算法在任務(wù)完成數(shù)量及資源消耗量具有優(yōu)越性，有效地降低路徑代價(jià)，提高了工作效率。滿足多機(jī)協(xié)同作業(yè)的實(shí)時(shí)性需求，實(shí)現(xiàn)了區(qū)域農(nóng)田內(nèi)的多機(jī)協(xié)同作業(yè)調(diào)度管理。同時(shí)考慮機(jī)器人在工作中的資源消耗量，使仿真結(jié)果更加準(zhǔn)確。