皮玉珍,苑全德,舒英利

(1.長春工程學(xué)院； 2.吉林省配電設(shè)備自動化產(chǎn)業(yè)公共技術(shù)研發(fā)中心，長春 130012)

?

一種多機器人的任務(wù)分配和自動協(xié)商的方法

皮玉珍1,2,苑全德1,2,舒英利1

(1.長春工程學(xué)院； 2.吉林省配電設(shè)備自動化產(chǎn)業(yè)公共技術(shù)研發(fā)中心，長春 130012)

摘要：提出了一種多機器人的任務(wù)分配和自動協(xié)商的方法。在進行任務(wù)分配時充分考慮機器人的真正性能；構(gòu)建自動協(xié)商的模型時，改進最小二乘法支持向量回歸算法(LSSVR)，用于估計對手的談判效用，并采用魯棒控制器的輸出反饋變量來限制優(yōu)化實用性能指標，然后提出協(xié)商和再分配的協(xié)議來提高實時性和任務(wù)分配效率。最后，通過仿真實驗來驗證次方法的有效性。

關(guān)鍵詞：多機器人；任務(wù)分配；協(xié)商

在多機器人技術(shù)中，任務(wù)分配和協(xié)商一直是研究的關(guān)鍵問題之一。其研究主要集中在任務(wù)分配的方法、資源能力的推理、自主合作、系統(tǒng)通信流量、學(xué)習(xí)和雙向多問題協(xié)商等方面。例如，在參考文獻[1]中劉淑華等提出的任務(wù)分配方法是基于群體智能的采用分層架構(gòu)的帶有寬松和緊密耦合任務(wù)的大規(guī)模多機器人系統(tǒng)；在參考文獻[2]中提出分布式同質(zhì)的多機器人系統(tǒng)，以實現(xiàn)以負載平衡為目的的任務(wù)分配方案；在參考文獻[3]中Elango開發(fā)了一個仿真模型包括任務(wù)優(yōu)先級和機器人的利用率，把它做為一個平衡的多機器人任務(wù)分配問題的優(yōu)先級；在參考文獻[4]中Jouandeau提出一個以貿(mào)易為基礎(chǔ)的多機器人任務(wù)分配方法，這個方法模擬了買家和賣家通過使用一種機械的主動競價方式完成動態(tài)的任務(wù)分配，等等。

本文提出的任務(wù)分配和協(xié)商方法，考慮機器人的實際能力和性能。并改進了競爭性投標效用函數(shù)，實現(xiàn)了快速學(xué)習(xí)。

1機器人的能力和任務(wù)分配的原則

1.1機器人能力的描述

在多機器人中，設(shè)R={R1…,Ri,…Rm}，每一個機器人與其他機器人之間可以是同型的或是非異構(gòu)的，但是至少保證Ri={PR,SR,BR}，其中，PR是機器人的位置和方向，SR是傳感器的類型，BR是處理任務(wù)的能力。

BR=g(bi,τi) 是Ri里bi的實際能力，與能力狀態(tài)τi有關(guān)，0≤τi≤1。

映射perfi∨timei∨bandwidthi∨poweri→τi的意思是τi受性能、執(zhí)行時間、帶寬、電源等的影響。Ri完成任務(wù)的能力t用式(1)表示：

j(τi,bi,t)=τiω(bi)-u(t)

(1)

式中：ω(bi)是消耗能力；u(t)是完成時的成本t。

ComCost∨ResCost∨RisCost∨ChaCost→ω(t) 表示ω(t)受很多因素的影響，ComCost是通信成本，ResCost是資源成本，RisCost是執(zhí)行任務(wù)風(fēng)險成本t，ChaCost是機會成本，j(τi,bi,t)被用來判斷t是否已經(jīng)完成。如果j(τi,bi,t)≥0說明Ri能夠完成t，否則不能完成。

1.2任務(wù)分配的原則

在理想的狀態(tài)下，τi=1，遍歷n任務(wù)。對于任務(wù)tj，如果(ω(b1)+…+ω(bm))/m-u(tj)≥0，說明tj通過單個機器人能夠完成，所以tj被看是一個單一的任務(wù)。如果(ω(b1)+…+ω(bm))/m-u(tj)≤0，說明tj通過很多機器人能被完成，tj被視為一個團隊任務(wù)。因此進行單一任務(wù)設(shè)IT={it1,…,itx,…itu}，團隊任務(wù)設(shè)CT={ct1,…cty,…ctv}，同時?(itx∧cty)=φ。

參考文獻在[5]中祖麗楠等設(shè)計用競爭性競標效用函數(shù)去實現(xiàn)機器人的任務(wù)分配，但是這個方法沒有考慮當(dāng)機器人加入到實際的合作時機器人實際性能的變化和對機器人的能力補償。在此我們根據(jù)以上的分析對這種方法做了進一步的改進。

(2)式中：p(bil,itxi)是初始化Ril到處理itxi階段的成本，它隨著距離和時間的增加而增加；α和β是映射比例系數(shù)；Δb(τil)是對Ril的性能補償；τ是補償?shù)燃?，τ∈R+。ρxi且隨著p(bil,itxi)和ω(bil)的減少而增加，表明選取Ril有適合的性能去處理itxi的原理。

(3)

2自主協(xié)商

2.1協(xié)商模型

單一的機器人被指派去完成itxi可以實現(xiàn)單一任務(wù)的指派分配，在這里我們考慮多機器人的協(xié)商情況。下面將分析機器人在處理ct時如何建立它們之間的協(xié)商關(guān)系。基本步驟如下：

從自由機器人{R1,…,Rz}中選擇有最小ω(bp)的機器人Rp(1≤p≤z)作為申請人；

Rp輪流選擇自由機器人依據(jù)機器人的能力進行降序排列和向他們發(fā)送協(xié)商方案，在tKk和Rq協(xié)商成功后做出處理Ck，1≤q≤z，q≠p；

Rp選擇tKk+1，重復(fù)步驟2直到全部任務(wù)都被分配了。

在多機器人上定義協(xié)商模型NMM={R,CT,E}，其中R={R1,…,RP,…,RZ}是被許可加入?yún)f(xié)商的機器人。CT是合作任務(wù)，E是合作效用評估。

2.2協(xié)商效用的估計

盡管最小二乘法向量回歸幫助解決了在理想狀態(tài)下小樣本的快速學(xué)習(xí)問題，但是當(dāng)用在實際的協(xié)商狀態(tài)下卻變得不穩(wěn)定，多機器人帶有很多不確定的干擾信息會引起無休止的學(xué)習(xí)。為了維持最小二乘法向量回歸的穩(wěn)定性，在此我們選擇徑向基函數(shù)核函數(shù)，采用魯棒反饋控制器抑制不確定的干擾信息以保持系統(tǒng)的穩(wěn)定性。

vi(t+1)=fvi(t)+c1r1(Pi-xi(t))+c2r2(Pg-xi(t))

xi(t+1)=xi(t)+vi(t+1)

(5)

式中：vi(t+1)、vi(t)分別是在t+1和t時刻第i個粒子的速度；f是慣性權(quán)重；c1、c2是兩個常數(shù)，r1、r2是在[0,1]之間的隨機數(shù)；Pi、Pg分別是第i個粒子和全部粒子的最佳位置；xi(t+1)、xi(t)分別是第i個粒子在t+1和t時刻的位置。

為了優(yōu)化在多機器人協(xié)商系統(tǒng)實際的性能指標，LMI被用來設(shè)計魯棒控制器的H輸出反饋。當(dāng)LSSVMI有誤差或者學(xué)習(xí)過程不完全收斂，魯棒控制器輸出錯誤路徑，產(chǎn)生反饋信號確保協(xié)商過程的連續(xù)性和閉環(huán)系統(tǒng)的穩(wěn)定性。

權(quán)重理解之后，對手的效用估計

EUp→q(·)=κfr+(1-κ)gr

(6)

式中：fr是LSSVMC的輸出；gr是魯棒控制器的輸出，κ是魯棒因素值。

κ=e-φEm，

(7)

式中：φ是魯棒系數(shù)，φ∈(0,1)。

(8)

2.3協(xié)商協(xié)議和再分配

由于高實時性的要求，在協(xié)商中機器人數(shù)量的控制和協(xié)商回合應(yīng)該被升級，避免在頻繁的協(xié)商時通信帶寬的擁擠和信號延遲。設(shè)Rp到提議通過局部廣播只在relative net內(nèi)和僅僅那些屬于這個區(qū)域的空閑機器人可以加入到這個協(xié)商中。L(Rq)∈NRp(rp)是指Rq屬于Rp的relative net ，L(Rq)是Rq的當(dāng)前位置，NRp(rp)是在半徑rp到Rprelative net 覆蓋的區(qū)域。0≤p,q≤z′≤z,q≠p,z′是在relative net 中包括Rp的機器人數(shù)量。Rp通過局部廣播網(wǎng)在tkk上提出協(xié)商協(xié)議。如果L(Rq)∈NRp(rp),Rq返回響應(yīng)d(Rq)，

(9)

在協(xié)商過程中，當(dāng)ξmin≤EU(·)≤ξmax連續(xù)拒絕或停止協(xié)商。協(xié)商申請人升級協(xié)商廣播網(wǎng)區(qū)域以尋求更多的候選人，其中ξmin和ξmax是最小效用和最大效用。協(xié)商的步驟如下：

準備階段i=1 表示開始第一回合協(xié)商。

步驟4?d(Rq)=拒絕，轉(zhuǎn)到步驟1。

步驟5?d(Rq)=等待∧?d(Rq)≠同意。Rp在特定的等待時間δ階段接受提議響應(yīng)，且?d(Rq)=同意，轉(zhuǎn)到步驟2。如果?d(Rq)≠同意在δ時間段轉(zhuǎn)到步驟6。

步驟6如果rp>rmax，協(xié)商失敗，或者Rp擴大半徑到rp=rp+βΔr，β是放大比例系數(shù)，Δr是半徑增加量。Rp通過局部廣播在次發(fā)送廣播。轉(zhuǎn)到步驟1。

步驟7 在tkk上Rp同Rq建立任務(wù)分配關(guān)系Ck(tkk,Rp,Rq)。協(xié)商成功結(jié)束。

3多機器人追逐仿真實驗

實驗在矩形方格區(qū)域進行，在矩形方格區(qū)域內(nèi)隨機創(chuàng)建不同形狀的障礙物。多機器人協(xié)商去追逐目標機器人(獵物)。如圖1所示，是追逐初始化階段圖。目標機器人通過智能策略逃跑。在追逐者和獵物間的視野半徑比例為1∶1。聲波定位儀的范圍比例為1∶2。當(dāng)協(xié)商時廣播是唯一的通信方式，LSSVR常常被用來評估對手的談判效用。

圖1　追逐初始化階段

追逐過程中，算法中分別設(shè)計了沒有協(xié)商的追逐和有協(xié)商的追逐兩種。在沒有協(xié)商的追逐過程中，追逐者追逐獵物是依靠局部的優(yōu)化算法。而有協(xié)商的追逐過程，機器人之間互相協(xié)商去包圍獵物。協(xié)商的條目有向前移動的距離d，向后移動的距離d，向左轉(zhuǎn)的角度θ，向右轉(zhuǎn)過的角度θ。他們的權(quán)重因子是(0.25，0.25，0.25，0.25)。機器人預(yù)測獵物的移動方向，提供計數(shù)提議。協(xié)商的記錄儲存在協(xié)商歷史數(shù)據(jù)庫里作為協(xié)商雙方效用評估樣本。

表1表示的是60個沒有協(xié)商的追逐過程的時間數(shù)據(jù)。表2表示的是60個有協(xié)商的追逐過程時間數(shù)據(jù)。其中，vp和ve分別是追逐者和獵物的速度，它明顯地表明有協(xié)商的追逐過程的成功率要高于沒協(xié)商的追逐過程。表中，SR是成功比率，F(xiàn)表示失敗。

表1 　沒有協(xié)商的追逐過程的時間數(shù)據(jù)

表2　有協(xié)商的追逐過程的時間數(shù)據(jù)

4 結(jié)語

在多機器人任務(wù)分配中，傳統(tǒng)的競爭性招標效用函數(shù)僅考慮機器人的理想性能而不能補償機器人的實際性能，忽略了由外部不確定干擾因素引起的協(xié)商系統(tǒng)穩(wěn)定性問題。本文提出的基于機器人的真實性能的多機器人任務(wù)分配和協(xié)商的方法，改進了競爭性投標效用函數(shù)。改進的LSSVR實現(xiàn)了快速學(xué)習(xí)，魯棒控制器實現(xiàn)了維持系統(tǒng)穩(wěn)定性。本方法的有效性已經(jīng)在實驗中得到證明，實驗表明這個方法改進了任務(wù)分配的效率。

[1] 劉淑華，張崳，吳洪巖，等. 基于群體智能的多機器人任務(wù)分配[J].吉林大學(xué)學(xué)報：工學(xué)版本，2010(1)： 123-129.

[2] 周菁，慕德俊. 多機器人系統(tǒng)任務(wù)分配研究[J].西北大學(xué)學(xué)報：自然科學(xué)版，2014(6): 403-410.

[3] Elango M，Nachiappan S P.Balancing multi-robot prioritized task allocation: A simulation ap-proach[C]//2011 IEEE International Conference on In-dustrial Engineering and Engineering Management. Singapore:IEEE, 2011: 1725-1729.

[4] Jouandeau N, Yan Zhi. Improved trade-based multi-robot coordination[C]//2011 6th IEEE Joint International Information Technology and Artificial Intelligence Conference (ITAIC)，Chongqing, China：ITAIC, 2011：500-503。

[5] 祖麗楠，田彥濤，梅昊.大規(guī)模多移動機器人合作任務(wù)的分布自主協(xié)作系統(tǒng)[J].機器人，2006，28(5)：470-477.

A Method of Task Allocation and Automated Negotiation for Multi-robots

PI Yu-zhen, etc.

(ChangchunInstituteofTechnology,Changchun130012,China)

Abstract：A method of task allocation and automated negotiation for multi-robots has been proposed. In the paper, the principles of task allocation are described based on the real capability of robot. During the construction of automated negotiation model, Least-Squares Support Vector Regression (LSSVR) has been improved to estimate the opponent's negotiation utility, and the robust controller of output feedback has been employed to optimize the utility performance indicators. Then, the protocol of negotiation and reallocation has been proposed to improve the real-time capability and task allocation. Finally, the validity of method is proved through experiments.

Key words：multi-robot; task allocation; consultation

文獻標志碼：A

文章編號：1009-8984(2016)01-0053-04

中圖分類號：TP242.6

作者簡介：皮玉珍(1981-)，女(漢),長春，講師

基金項目：吉林省科技廳項目(20150204008SF,20130206049GX,201301010052JC)吉林省教育廳項目(2013296，2014324,2014339,2014327,2014309)

收稿日期：2015-11-04

doi:10.3969/j.issn.1009-8984.2016.01.012

主要研究多智能體、智能電網(wǎng)。