基于帕累托改進的多機器人動態(tài)任務分配算法

姜 棟，徐 欣

(杭州電子科技大學 通信工程學院，杭州 310018)

基于帕累托改進的多機器人動態(tài)任務分配算法

姜 棟，徐 欣*

(杭州電子科技大學 通信工程學院，杭州 310018)

針對多機器人系統(tǒng)動態(tài)任務分配中存在的優(yōu)化問題，在使用合同網(wǎng)初始任務分配的基礎上提出了一種使用帕累托改進的任務二次分配算法。多機器人系統(tǒng)并行執(zhí)行救火任務時，首先通過初始化任務分配將多機器人劃分為若干子群；然后,每個子群承包某一救火任務，子群在執(zhí)行任務的同時與就近子群進行帕累托改進確定需要遷移的機器人，實現(xiàn)兩子群之間帕累托最優(yōu)；最后,使用后序二叉樹遍歷對所有子群進行帕累托改進實現(xiàn)全局帕累托最優(yōu)。理論分析和仿真結果表明，相較于強化學習算法和蟻群算法，所提算法的救火任務時間分別減少26.18%和37.04%；相較于傳統(tǒng)合同網(wǎng)方法,所提算法在時間方面能夠高效完成救火任務，在系統(tǒng)收益方面也具有明顯優(yōu)勢。

多機器人；救火任務；任務分配；合同網(wǎng)；帕累托改進；帕累托最優(yōu)

0 引言

多機器人系統(tǒng)越來越多地應用到軍事、未知環(huán)境和災區(qū)等領域，包括無人飛行器(Unmanned Aerial Vehicle, UAV)、自動地面車輛(Automatic Ground Vehicle, AGV)、無人水下航行器(Unmanned Underwater Vehicle, UUV)。多機器人通過協(xié)作來交流和分享信息改進了單個機器人的性能，如任務執(zhí)行效率、健壯性、靈活性和容錯性[1-5]。因此，多機器人系統(tǒng)的研究成為機器人研究熱點，近年來，多機器人系統(tǒng)涵蓋了分布式?jīng)Q策，編隊控制、區(qū)域覆蓋及其相關應用[6]。Gerkey等[7]對多機器人系統(tǒng)在不同領域的任務分配問題進行特定分類，包括運籌學、經(jīng)濟學、調度問題、網(wǎng)絡流量問題和組合優(yōu)化問題。當分派多個機器人執(zhí)行任務時，第一步就是任務分配，任務分配決定各個機器人在何時執(zhí)行何種任務, 任務分配的目的是使整體性能最大化盡快完成任務、提高整個系統(tǒng)的運行效率。多機器人的任務分配問題在不同情況下可分別看作最優(yōu)分配問題(Optimal Allocation Problem, OAP)、整數(shù)線性規(guī)劃問題、調度問題、網(wǎng)絡流問題和組合優(yōu)化問題[8]。

根據(jù)任務情況一般將任務分配分為靜態(tài)任務分配和動態(tài)任務分配。當任務執(zhí)行之前，機器人是已知的任務執(zhí)行，它們可以被稱為靜態(tài)任務分配。對于動態(tài)任務分配來說，機器人任務分配是一個動態(tài)的過程，需要根據(jù)任務環(huán)境的變化和子群對利益的需求處于不斷調整變化的狀態(tài)。

市場經(jīng)濟的原則非常適用于資源分配，在多機器人系統(tǒng)任務分配中應用取得了很多的成果。Sandholm[9]通過使用基于邊際成本的個體理性機制，將傳統(tǒng)合同應用到多機器人競爭系統(tǒng)，引入基于邊際成本的個體理性機制，將傳統(tǒng)的擴展合同網(wǎng)協(xié)議應用于競爭性系統(tǒng)，通過采用多種類型的任務合同消除傳統(tǒng)合同網(wǎng)協(xié)議僅協(xié)商單個任務分配的限制，在理論上可以實現(xiàn)最優(yōu)任務分配，但是實現(xiàn)最優(yōu)任務分配的計算代價和通信代價將隨問題的規(guī)模指數(shù)級增加。Kartal等[10]提出了一種基于蒙特卡羅樹搜索的算法，利用分支和綁定范例來解決空間、時間和其他邊界約束條件的多機器人系統(tǒng)任務分配問題，但是該方法不能夠完全并行處理任務分配。李明等[11]提出一種改進的合同網(wǎng)協(xié)議，首先建立Agent能力模型和Agent執(zhí)行的任務描述，在此基礎上改進合同網(wǎng)中的招標階段，Agent通過對正在執(zhí)行的任務進行招標來動態(tài)改變自身能力以進行任務的再分配。但是，本研究所考慮的任務由單個Agent完成，并沒有考慮到任務由多個Agent共同完成的情況。在多機器人任務分配問題中為了得到帕累托(Pareto)最優(yōu)或者是納什均衡[12]，談判機制可以應用于機器人對之間，但是該方法只實現(xiàn)機器人對之間帕累托最優(yōu)沒有得到全局帕累托最優(yōu)。Cui等[13]在傳統(tǒng)合同網(wǎng)的基礎上提出一種選擇談判機器人和構造談判組的新方法，并提出適用于分布式任務分配的協(xié)商機制，但是該系統(tǒng)的協(xié)商機制是基于機器人對的協(xié)商，沒有在子群中進行協(xié)商，導致該方法適用性較弱。沈莉等[14]通過交換樹競拍和改進Dijkstra的方法解決機器人任務負荷不平衡的問題，來提高多機器人工作效率，但是沒有從多機器人收益的角度來進行考量。

多機器人系統(tǒng)現(xiàn)有研究在對分配結果進行優(yōu)化時沒有從收益的角度出發(fā)，同時多機器人全局最優(yōu)是任務分配中的難點，針對以上問題本文提出一種基于帕累托改進的協(xié)商策略實現(xiàn)子群之間帕累托最優(yōu)，保證多機器人系統(tǒng)在執(zhí)行任務時子群之間更加均衡，在減少完成任務時間的同時增加整體收益。多機器人任務分配可以將任務作為資源在機器人之間進行分配，也可以將機器人作為資源在子群之間進行分配?？紤]到多機器人的設計簡單、分布性好的特點，將機器人作為資源進行分配具有更好的實用性。

1 問題描述

救火任務具有高度動態(tài)性，起火的位置、時間和大小都會實時隨機發(fā)生變化，因此救火任務是研究多機器人動態(tài)任務分配的理想模型。

使用四元組[15]來描述多機器人系統(tǒng)救火任務：

1)機器人信息集合：Datas={Ld,Fd,E,Loc,Fire,Hi,SetB}；

2)多任務Tasks={t1,t2,…,ta},a≥1；

3)多機器人Robs={r1,r2,…,rb},b?a；

4)封閉二維環(huán)境。

所有機器人為同構機器人即各機器人功能、屬性均相同，機器人具備通信能力、移動能力、感知能力和滅火能力。其中：通信能力可以用于機器人之間信息集的交互，信息集包括招標信息Ld、投標信息Fd、自身能量E、自身位置Loc、火勢狀況Fire、歷史滅火信息Hi和機器人投標信息集SetB；移動能力作為機器人自身屬性包括移動速度和轉向能力；機器人通過火勢探測器和射頻(Radio Frequency, RF)傳感器來監(jiān)測周邊火勢情況和周邊機器人情況；此處對火勢進行量化，機器人的滅火能力代表單位時間內消滅的單位火勢。

2 初始化任務分配

救火任務具備動態(tài)性、緊急性等特點，需要多機器人系統(tǒng)盡快完成任務分配參與到任務中控制火勢蔓延。市場方法有良好的分布性和魯棒性，因此非常適用于救火任務，其基本思想[16]為：領導機器人(Leader Robot, LR)有任務需要跟從機器人(Follower Robot, FR)共同完成時，LR對FR進行廣播信息進行招標，然后接收到招標信息的FR根據(jù)自身任務情況進行選擇性投標，LR對接收到的投標信息進行權衡選擇FR參與到任務當中。

2.1 確定領導機器人

多機器人系統(tǒng)使用自身帶有的火勢探測器對二維平面進行全覆蓋并實時監(jiān)控。當二維平面內有火勢發(fā)生時，首先監(jiān)測到任務的機器人對此任務進行承包，如果起火位置處在多個機器人共同覆蓋區(qū)域則根據(jù)機器人信息集中的歷史滅火信息Hi進行競爭性協(xié)商。

Hi=φL+ωF

(1)

其中：L為該機器人作為LR的歷史次數(shù)；F為該機器人作為FR的次數(shù)；φ、ω則對應著不同的加權系數(shù)。

2.2 建立子群

確定LR之后需要在LR的基礎上建立子群，這定義單個子群對應單個任務，并在任務完成后解散子群,子群內機器人數(shù)量根據(jù)系統(tǒng)內任務數(shù)量進行設定。市場方法作為協(xié)商式的任務分配方法，這就需要LR和FR確定統(tǒng)一的出價公式，出價公式采用以下計算式進行描述：

(2)

其中：Pj表示FR出價公式中所涉及到的各項屬性；μj是對應屬性的加權系數(shù);FR根據(jù)LR的招標信息計算出相應的出價公式，LR則對出價公式進行篩選并確定參與到該子群的FR。確定救火任務具有緊急性的特點，因此需要盡可能快地進行任務分配以控制火勢蔓延，使用就近原則進行招標和投標。領導機器人根據(jù)任務情況進行招標，招標算法步驟如算法1所示。

算法1 領導機器人招標算法。

步驟1 LR在初始化通信半徑rint覆蓋范圍內廣播招標信息(Bidding Information, BI)。

步驟2 接收到招標消息的機器人進行選擇性投標發(fā)出投標信息(Sending Information, SI)。

步驟3 LR對接收到的投標消息進行篩選并傳播確定性招標消息。

步驟4 接收到確定性招標消息的機器人成為該LR所領導的FR并參與到LR所承包的任務中。

步驟5 LR根據(jù)當前承包任務情況及子群內FR數(shù)量判斷是否需要繼續(xù)招標。

步驟6 若需要則擴大通信半徑ri=ri-1+λ進行招標，執(zhí)行步驟4，若ri達到該機器人最大通信半徑則停止招標，子群建立完成；若不需要則停止招標，子群建立完成。

跟從機器人根據(jù)招標信息進行投標并最終確定參與到哪個任務中。跟從機器人投標算法步驟如下:

步驟1 機器人處于無參與任務狀態(tài)，將接收到的任務信息存入投標信息集SetB中。

步驟2 若SetB=?，則繼續(xù)監(jiān)測所覆蓋區(qū)域內火勢，否則進行計算篩選，選擇最有利的任務進行投標。

步驟3 若接收到LR的確定性招標消息則直接參與到任務中；若接收到LR的拒絕消息則將該招標信息從SetB中刪除。

建立子群算法流程如圖1所示。

3 任務再分配

3.1 函數(shù)定義

3.1.1 代價函數(shù)

系統(tǒng)中單個子群g完成單個任務t，在完成任務的過程中會損耗移動能力，耗費通信量，同時在參與滅火任務過程中損耗滅火能力，定義代價函數(shù)即機器人執(zhí)行任務過程中所要付出的代價。

Cost(g)=λ1Ecost+λ2Ccost+λ3Fcost

(3)

其中：Cost(g)表示子群內所有機器人完成任務所需要付出的總代價；Ecost為子群內所有機器人所損耗的移動能力；Ccost為子群內所有機器人損耗的通信量；Fcost為子群內所有機器人損耗的滅火能力;λ1、λ2、λ3代表的是權重。這里的Cost(g)是機器人子群代價，那么整個多機器人系統(tǒng)的代價為：

SCost(g)=Cost(g1)+Cost(g2)+…+Cost(gm)

(4)

圖1 建立子群算法流程Fig.1 Flow chart of building subgroup algorithm

一般通過子群代價函數(shù)來求得局部優(yōu)化，通過整體代價則追求更好的全局優(yōu)化效果。代價函數(shù)隨著時間推進任務的完成度增長會呈現(xiàn)一個單調遞增的趨勢，同時子群中的任務個數(shù)增加時也會增加子群付出的代價。

3.1.2 獎勵函數(shù)

多機器人系統(tǒng)在完成任務后，會根據(jù)任務情況得到獎勵，這里的獎勵函數(shù)描述為Rew(g,t)，獎勵函數(shù)包括任務完成獎勵和時間獎勵，使用火勢情況量化描述任務獎勵，同時任務完成時間越短時間獎勵就越高。多機器人系統(tǒng)Rew整體獎懲函數(shù)則可以表示為：

(5)

其中a代表任務數(shù)量。

3.1.3 收益函數(shù)

假定多機器人系統(tǒng)中每一個多機器人追求利益最大化，完成任務的子群內所有機器人平分收益，因此子群LR同樣追求子群利益最大化，每個子群根據(jù)代價函數(shù)和獎勵函數(shù)可以得到最終的子群收益。

Pro=Rew(g,t)-Scost(g)

(6)

子群收益根據(jù)子群內機器人數(shù)量進行平均分配這樣就得到子群內單個機器人的收益。

3.2 協(xié)商策略

3.2.1 兩子群協(xié)商

合同網(wǎng)任務分配方法在一定程度上可以保證局部最優(yōu)解，然而在整個系統(tǒng)層面上存在效率不高的情況，這里對多機器人系統(tǒng)進行任務再分配，實現(xiàn)多機器人系統(tǒng)整體上的帕累托最優(yōu)(Pareto Optimality)。帕累托最優(yōu)是一種資源分配的理想狀態(tài)，它從全部機器人收益的角度來衡量多機器人資源配置的結果。假定固有的多機器人和可進行任務分配的火勢情況，初始任務分配之后進行帕累托改進，在沒有使任何子群收益變壞的前提下，使得至少一個子群收益變得更高，最終實現(xiàn)子群之間的帕累托最優(yōu)狀態(tài)。

定義子群g的當前執(zhí)行救火任務的機器人集合為g={R1,R2,…,Rm}，如果有新的機器人Rn加入到子群中，將子群g的收益函數(shù)定義為：

(7)

相反，如果子群內機器人Rn脫離子群g，則將子群g的收益函數(shù)定義為：

(8)

初始化任務分配結束之后，選擇距離最近子群進行兩兩協(xié)商，實現(xiàn)兩個子群之間的帕累托改進。定義一個效用函數(shù)F以保證帕累托改進過程的合理性和優(yōu)化性，子群g={R1,R2,…,Rm}，該集合為子群g所包含的所有機器人，θ為協(xié)商結果，即可與其他子群交換的FR，因此可以將對應于任務i的效用函數(shù)描述為:

Fi(θ)=Prog-Proi(θ)

(9)

1)協(xié)商的目的是為了優(yōu)化子群收益，因此效用函數(shù)需要保證以下兩個約束條件。

所有的子群LR都是追求子群利益最大化即保證該協(xié)商是合理的，因此在進行協(xié)商解決時必須要滿足?FI(θ)≥0，即：

(F1(θ),F2(θ),…,Fa(θ))≥(0,0,…,0)

該約束條件是保證協(xié)商結果的合理性。

2)子群之間協(xié)商的目的是實現(xiàn)帕累托最優(yōu)解，協(xié)商結果θ屬于帕累托改進，最終實現(xiàn)帕累托最優(yōu)屬于所謂的帕累托最優(yōu)解，因此對于?θ≠θ′滿足：

(F1(θ),F2(θ),…,Fa(θ))≥(F1(θ′),F2(θ′),…,

Fa(θ′))

該約束條件是保證協(xié)商結果滿足帕累托改進。

通過上述兩個約束條件進行約束，協(xié)商子群之間提供各自的當前子群內機器人數(shù)量及收益函數(shù)，然后進行談判，談判雙方交換信息同時儲存對方信息，子群領導者LR兩兩進行信息交互同時可以將談判信息進行分享。兩個子群之間具體信息交互算法如下：

輸入 初始化子群gi、gj；

輸出 子群gi、gj之間轉移機器人{Rij}。

1)

Rij=?

2)

?Rn∈gido

3)

4)

5)

Fj(Rn)>Fi(Rn)

6)

Then {Rij}←{Rij}∪Rn

3.2.2 全局子群協(xié)商

機器人子群兩兩協(xié)商完成帕累托改進之后的信息保存在相互雙方的信息集中，為了實現(xiàn)多次帕累托改進實現(xiàn)全局帕累托最優(yōu)，使用后序二叉樹遍歷算法如圖2所示。首先將協(xié)商之后的兩個子群的當前信息集由一個子群LR保管并與其他協(xié)商后的子群進行協(xié)商改進，兩者的信息由獲得機器人的子群來保管并與其他子群進行協(xié)商，若無機器人添加或減少則隨機選擇其中一個機器人，最終實現(xiàn)全局帕累托最優(yōu)。

算法2 全局子群協(xié)商算法。

步驟1 初始化任務分配子群gi、gj，協(xié)商后得到兩者之間帕累托最優(yōu)。

步驟2 根據(jù)交換信息選擇一個子群LR作為兩子群與其他子群LR進行信息交流。

步驟3 兩個LR進行帕累托改進。

步驟4 重復執(zhí)行步驟2和步驟3直到所有子群均進行帕累托改進。

步驟5 得到子群之間全局帕累托最優(yōu)。

圖2 后序二叉樹遍歷算法示意圖Fig. 2 Schematic diagram of posterior binary tree traversal algorithm

4 實驗結果與分析

本文在Netlogo仿真平臺[17]中建立了多機器人救火仿真模型，該模型中可以設定機器人感知火勢情況、機器人滅火速度、移動速度、通信能力、以及機器人及起火數(shù)量，同時可以通過能量展示模塊跟蹤觀察救火任務完成情況。在仿真過程中，當機器人檢測到有火勢發(fā)生時，多機器人進行任務分配，在滅火過程中子群之間進行任務再分配。多機器人對二維環(huán)境的覆蓋狀態(tài)如圖3所示，其中，人形狀代表救火機器人，星狀代表火勢情況，根據(jù)形狀大小來表示火勢情況緊急程度和火勢大小。

圖3 二維環(huán)境覆蓋狀態(tài)Fig. 3 Two-dimensional environment coverage state

這里對使用帕累托改進的二次分配和傳統(tǒng)合同網(wǎng)方法進行分析對比，考慮到算法的隨機性和火勢的隨機性，針對兩種方法分別進行50次重復實驗。對仿真實驗中的各項參數(shù)進行設置如表1所示。

4.1 使用帕累托改進算法效率結果

為了對比帕累托改進算法的任務執(zhí)行效果，進行了5組對比實驗分析，每次實驗重復50次。時間統(tǒng)計使用Netlogo中自帶時鐘計數(shù)器ticks和秒表計算來作為實驗完成時間上的評價指標，使用帕累托改進和傳統(tǒng)合同網(wǎng)的時鐘計數(shù)器的對比如表2所示，相應的時間對比如圖4所示。結合表2和圖4可以看出，實用帕累托改進后的多機器人系統(tǒng)完成任務的速度優(yōu)于無帕累托改進算法，隨著任務數(shù)量的上升效果更加明顯。實驗結果表明，使用帕累托改進算法能夠將時間復雜度將低20個百分點，驗證了帕累托改進算法能夠有效地提高任務執(zhí)行效率。

表1 主要仿真參數(shù)Tab. 1 Main simulation parameters

表2 不同算法時鐘計數(shù)器結果Tab. 2 Clock counter results of different algorithms

圖4 不同算法時間對比Fig. 4 Time comparison of different algorithms

4.2 使用帕累托改進收益結果

同樣使用上述實驗方式進行多次對比實驗，對救火任務進行量化，將單個火勢的收益根據(jù)火勢大小設置為500～2 000，多機器人每移動一個單位所損耗的能量設置為0.1，參與救火任務時每消滅一個單位的火勢損耗的能量設置為0.4，能量統(tǒng)計及收益情況由Netlogo中設計的海龜觀測圖進行展示，使用帕累托改進的多機器人執(zhí)行任務的收益結果如圖5所示。

圖5 不同算法收益對比Fig. 5 Revenue comparison of different algorithms

由圖5可以看出，在所有起火數(shù)量相同的對比實驗中，帕累托改進后算法收益結果優(yōu)于無帕累托改進的算法；隨著起火數(shù)量的增加，兩種算法的收益結果差距明顯增大。實驗結果表明，多機器人系統(tǒng)使用帕累托改進算法進行二次分配后收益效果要明顯好于基于合同網(wǎng)的任務分配算法，這種優(yōu)勢隨著任務數(shù)量的增加更加明顯。

4.3 對比蟻群算法和強化學習算法

為對比帕累托改進算法與其他任務分配算法的任務執(zhí)行效率，三種算法使用相同的表1中參數(shù)進行對比實驗，按照起火數(shù)量進行5組對比實驗分析，每次實驗重復50次。將任務分配分為初始化任務分配階段和任務完成階段，系統(tǒng)中所有機器人均參與到任務中定義為初始化任務分配完成，初始化任務分配完成到所有火勢消滅定義為任務完成階段。分析對比三種算法所用的兩階段時間如表3所示，帕累托改進算法相較于蟻群算法和強化學習算法在初始化任務分配階段和任務執(zhí)行階段的效率都有明顯提升，尤其是初始化任務分配階段有很大的提高，這對于具有緊急性特點的救火任務來說能夠第一時間有效控制火勢的蔓延非常重要。實驗結果表明，帕累托改進算法在救火任務時間上相較于強化學習算法下降26.18%，相較于蟻群算法下降37.04%。帕累托改進算法在整個救火任務效率明顯好于強化學習算法和蟻群算法。

表3 不同算法兩階段時間對比 sTab. 3 Time comparison of two stages of different algorithms s

5 結語

為研究多機器人領域內的動態(tài)任務分配問題，本文在Netlogo仿真平臺上建立多機器人救火任務模型，提出在合同網(wǎng)初始任務分配基礎上進行基于帕累托改進的二次任務分配的算法，針對任務模型的特點構造收益函數(shù)，并設計相關協(xié)商策略。仿真實驗結果表明，使用帕累托改進對任務分配進行再次分配可以有效提高多機器人系統(tǒng)工作效率，同時可以增加系統(tǒng)總收益。本文的策略都是基于協(xié)商的，因此在通信量控制方面有所不足，對通信要求高，下一步工作在保證高效、高收益的情況下控制通信量，保證多機器人系統(tǒng)各項屬性更加平衡。

References)

[1] YANG C, LI J, LI Z. Optimized adaptive control design and NN based trajectory planning for a class of wheeled inverted pendulum vehicle models [J]. IEEE Transactions on Cybernetics, 2013, 43(1): 24-35.

[2] YANG C G, GANESH G, HADDADIN S, et al. Human-like adaptation of force and impedance in stable and unstable interactions [J]. IEEE Transactions on Robotics, 2011, 27(5): 918-930.

[3] CUI R X, GE S S, HOW B V E, et al. Leader-follower formation control of underactuated autonomous underwater vehicles [J]. Ocean Engineering, 2010, 37(17/18): 1491-1502.

[4] LI Z J, LI J X, KANG Y. Adaptive robust coordinated control of multiple mobile manipulators interacting with rigid environments [J]. Automatica, 2010, 46(12): 2028-2034.

[5] LI Z J, CAO X Q, DING N. Adaptive fuzzy control for synchronization of nonlinear teleoperators with stochastic time-varying communication delays [J]. IEEE Transactions on Fuzzy Systems, 2011, 19(4): 745-757.

[6] ELANGO M, NACHIAPPAN S, TIWARI M K. Balancing task allocation in multi-robot systems usingK-means clustering and auction based mechanisms [J]. Expert Systems with Applications, 2011, 38(6): 6486-6491.

[7] GERKEY B P, MATARIC M J. A formal framework for the study of task allocation in multi-robot systems [J]. International Journal of Robotics Research, 2003, 23(9): 1-17.

[8] 吳軍,徐昕,連傳強,等.協(xié)作多機器人系統(tǒng)研究進展綜述[J].智能系統(tǒng)學報,2011,6(1):13-27.(WU J, XU X, LIAN C Q, et al. A survey of recent advances in cooperative multi-robot systems [J] . CAAI Transactions on Intelligent Systems, 2011, 6(1): 13-27.)

[9] SANDHOLM T. An implementation of the contract net protocol based on marginal cost calculations [C]// Proceedings of the 1993 Eleventh National Conference on Artificial Intelligence. Menlo Park: AAAI, 1993: 256-262.

[10] KARTAL B, NUNES E, GODOY J, et al. Monte Carlo tree search for multi-robot task allocation [C]// Proceedings of the 2016 Thirtieth AAAI Conference on Artificial Intelligence. Menlo Park: AAAI, 2016: 4222-4223.

[11] 李明,劉瑋,張彥鐸.基于改進合同網(wǎng)協(xié)議的多Agent動態(tài)任務分配[J].山東大學學報(工學版),2016,46(2):51-56.(LI M, LIU W, ZHANG Y D. Mulit-agent dynamic task allocation based on improved contract net protocol [J]. Journal of Shandong University (Engineering Science), 2016, 46 (2): 51-56.)

[12] BARILE F, ROSSI A, STAFFA M, et al. A market mechanism for qos-aware multi-robot task allocation [EB/OL]. [2017- 04- 06]. http://ceur-ws.org/Vol-1382/paper20.pdf.

[13] CUI R, GAO J G B. Game theory-based negotiation for multiple robots task allocation [J]. Robotica, 2013, 31(6): 923-934.

[14] 沈莉,李杰,朱華勇.基于交換樹的多機器人任務協(xié)調與負荷平衡方法[J].計算機應用,2016,36(11):3127-3130,3135.(SHEN L, LI J, ZHU H Y. Task coordination and workload balance method for multi-robot based on trading tree [J]. Journal of Computer Applications, 2016, 36 (11): 3127-3130, 3135.)

[15] 張云正,薛頌東,曾建潮.群機器人多目標搜索中的合作協(xié)同和競爭協(xié)同[J].機器人,2015,37(2):142-151.(ZHANG Y Z, XUE S D, ZENG J C. Cooperative and competitive coordination in swarm robotic search for multiple targets [J]. Robot, 2015, 37(2): 142-151.)

[16] SANDHOLM T. Algorithm for optimal winner determination in combinatorial auctions [J]. Artificial Intelligence, 2002, 135(1/2): 1-54.

[17] TISUE S, WILENSKY U. Netlogo: a simple environment for modeling complexity [EB/OL]. [2017- 04- 06]. http://www.ccl.sesp.northwestern.edu/papers/netlogo-iccs2004.pdf.

This work is partially supported by the National Defense Pre-Research Foundation of China (GFZ17040406004).

JIANGDong, born in 1990, M. S. candidate. His research interests include information security, collaborative multi-robot, distributed instant messaging, block chain.

XUXin, born in 1975, Ph. D., professor. His research interests include information security, solid state storage, distributed instant messaging.

Multi-robotdynamictaskallocationalgorithmbasedonParetoimprovment

JIANG Dong, XU Xin*

(CollegeofCommunicationEngineering,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

In order to solve the optimization problem of dynamic task allocation in multi-robot system, a new quadratic task allocation algorithm based on Pareto improvement was proposed based on the initial task allocation of contract net. When the fire fighting task was performed by the multi-robot system in parallel, firstly, the multiple robots were divided into several sub-group through the initialization of task allocation. Then, a fire fighting task was undertook by a subgroup, and the robots needed to be migrated were determined by the Pareto improvement of the subgroup and its nearest subgroup while the subgroup performing the task to achieve the Pareto optimality between the two subgroups. Finally, the global Pareto optimality was achieved by the Pareto improvement of all subgroups with posterior binary tree traversal. The theoretical analysis and simulation results show that, compared with reinforcement learning algorithm and ant colony algorithm, the fire fighting time of the proposed algorithm is reduced by 26.18% and 37.04% respectively. And compared with the traditional contract net method, the proposed algorithm can perform the fire fighting task efficiently in time, and also has the obvious advantage in system revenue.

multi-robot; fire fighting task; task allocation; contract net; Pareto improvement; Pareto optimality

2017- 06- 29;

2017- 09- 05。

國防預研基金資助項目(GFZ17040406004)。

姜棟(1990—)，男，山東泰安人，碩士研究生，主要研究方向：信息安全、協(xié)作多機器人、分布式即時通信、區(qū)塊鏈； 徐欣(1975—)，男，浙江縉云人，教授，博士，主要研究方向：信息安全、固態(tài)存儲、分布式即時通信。

1001- 9081(2017)12- 3620- 05

10.11772/j.issn.1001- 9081.2017.12.3620

(*通信作者電子郵箱jaedong1126@foxmail.com)

TP242.6

A