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

趙 輝 郝夢雅 王紅君 岳有軍

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

0 引 言

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

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

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

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

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

1 問題描述

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

1.1 約束指標

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

(1)

(2)

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

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

(3)

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

(4)

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

(5)

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

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

(6)

1.2 任務(wù)代價

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

(7)

2 算法設(shè)計

2.1 MTSP模型

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

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

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

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

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

圖1 機器人i對于任務(wù)j的投標生成過程

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

(8)

2.2.1投標生成過程

投標時位于路徑k的再填充站的站向量為:

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

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

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

(10)

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

(11)

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

(12)

(13)

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

2.2.2路徑選擇概率

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

(14)

(15)

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

(16)

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

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

(17)

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

(18)

估計成本為：

(19)

機器人i對于任務(wù)j的出價為：

(20)

(21)

2.3 拍賣流程

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

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

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

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

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

3 仿真與分析

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

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

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

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

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

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

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

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

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

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

(22)

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

(23)

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

4 結(jié) 語

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