姜 棟，徐 欣

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

基于帕累托改進(jìn)的多機(jī)器人動(dòng)態(tài)任務(wù)分配算法

姜 棟，徐 欣*

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

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

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

0 引言

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

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

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

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

1 問題描述

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

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

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

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

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

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

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

2 初始化任務(wù)分配

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

2.1 確定領(lǐng)導(dǎo)機(jī)器人

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

Hi=φL+ωF

(1)

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

2.2 建立子群

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

(2)

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

算法1 領(lǐng)導(dǎo)機(jī)器人招標(biāo)算法。

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

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

步驟3 LR對(duì)接收到的投標(biāo)消息進(jìn)行篩選并傳播確定性招標(biāo)消息。

步驟4 接收到確定性招標(biāo)消息的機(jī)器人成為該LR所領(lǐng)導(dǎo)的FR并參與到LR所承包的任務(wù)中。

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

步驟6 若需要?jiǎng)t擴(kuò)大通信半徑ri=ri-1+λ進(jìn)行招標(biāo)，執(zhí)行步驟4，若ri達(dá)到該機(jī)器人最大通信半徑則停止招標(biāo)，子群建立完成；若不需要?jiǎng)t停止招標(biāo)，子群建立完成。

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

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

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

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

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

3 任務(wù)再分配

3.1 函數(shù)定義

3.1.1 代價(jià)函數(shù)

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

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

(3)

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

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

(4)

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

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

3.1.2 獎(jiǎng)勵(lì)函數(shù)

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

(5)

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

3.1.3 收益函數(shù)

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

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

(6)

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

3.2 協(xié)商策略

3.2.1 兩子群協(xié)商

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

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

(7)

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

(8)

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

Fi(θ)=Prog-Proi(θ)

(9)

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

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

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

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

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

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

Fa(θ′))

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

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

輸入 初始化子群gi、gj；

輸出 子群gi、gj之間轉(zhuǎn)移機(jī)器人{(lán)Rij}。

1)

Rij=?

2)

?Rn∈gido

3)

4)

5)

Fj(Rn)>Fi(Rn)

6)

Then {Rij}←{Rij}∪Rn

3.2.2 全局子群協(xié)商

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

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

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

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

步驟3 兩個(gè)LR進(jìn)行帕累托改進(jìn)。

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

4.1 使用帕累托改進(jìn)算法效率結(jié)果

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

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

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

圖4 不同算法時(shí)間對(duì)比Fig. 4 Time comparison of different algorithms

4.2 使用帕累托改進(jìn)收益結(jié)果

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

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

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

4.3 對(duì)比蟻群算法和強(qiáng)化學(xué)習(xí)算法

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

表3 不同算法兩階段時(shí)間對(duì)比 sTab. 3 Time comparison of two stages of different algorithms s

5 結(jié)語

為研究多機(jī)器人領(lǐng)域內(nèi)的動(dòng)態(tài)任務(wù)分配問題，本文在Netlogo仿真平臺(tái)上建立多機(jī)器人救火任務(wù)模型，提出在合同網(wǎng)初始任務(wù)分配基礎(chǔ)上進(jìn)行基于帕累托改進(jìn)的二次任務(wù)分配的算法，針對(duì)任務(wù)模型的特點(diǎn)構(gòu)造收益函數(shù)，并設(shè)計(jì)相關(guān)協(xié)商策略。仿真實(shí)驗(yàn)結(jié)果表明，使用帕累托改進(jìn)對(duì)任務(wù)分配進(jìn)行再次分配可以有效提高多機(jī)器人系統(tǒng)工作效率，同時(shí)可以增加系統(tǒng)總收益。本文的策略都是基于協(xié)商的，因此在通信量控制方面有所不足，對(duì)通信要求高，下一步工作在保證高效、高收益的情況下控制通信量，保證多機(jī)器人系統(tǒng)各項(xià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] 吳軍,徐昕,連傳強(qiáng),等.協(xié)作多機(jī)器人系統(tǒng)研究進(jìn)展綜述[J].智能系統(tǒng)學(xué)報(bào),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] 李明,劉瑋,張彥鐸.基于改進(jìn)合同網(wǎng)協(xié)議的多Agent動(dòng)態(tài)任務(wù)分配[J].山東大學(xué)學(xué)報(bào)(工學(xué)版),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] 沈莉,李杰,朱華勇.基于交換樹的多機(jī)器人任務(wù)協(xié)調(diào)與負(fù)荷平衡方法[J].計(jì)算機(jī)應(yīng)用,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] 張?jiān)普?薛頌東,曾建潮.群機(jī)器人多目標(biāo)搜索中的合作協(xié)同和競爭協(xié)同[J].機(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。

國防預(yù)研基金資助項(xiàng)目(GFZ17040406004)。

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

1001- 9081(2017)12- 3620- 05

10.11772/j.issn.1001- 9081.2017.12.3620

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

TP242.6

A