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

皮玉珍,苑全德,舒英利

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

?

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

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

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

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

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

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

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

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

1.1機(jī)器人能力的描述

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

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

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

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

(1)

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

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

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

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

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

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

(3)

2自主協(xié)商

2.1協(xié)商模型

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

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

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

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

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

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

盡管最小二乘法向量回歸幫助解決了在理想狀態(tài)下小樣本的快速學(xué)習(xí)問(wèn)題，但是當(dāng)用在實(shí)際的協(xié)商狀態(tài)下卻變得不穩(wěn)定，多機(jī)器人帶有很多不確定的干擾信息會(huì)引起無(wú)休止的學(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時(shí)刻第i個(gè)粒子的速度；f是慣性權(quán)重；c1、c2是兩個(gè)常數(shù)，r1、r2是在[0,1]之間的隨機(jī)數(shù)；Pi、Pg分別是第i個(gè)粒子和全部粒子的最佳位置；xi(t+1)、xi(t)分別是第i個(gè)粒子在t+1和t時(shí)刻的位置。

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

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

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

(6)

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

κ=e-φEm，

(7)

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

(8)

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

由于高實(shí)時(shí)性的要求，在協(xié)商中機(jī)器人數(shù)量的控制和協(xié)商回合應(yīng)該被升級(jí)，避免在頻繁的協(xié)商時(shí)通信帶寬的擁擠和信號(hào)延遲。設(shè)Rp到提議通過(guò)局部廣播只在relative net內(nèi)和僅僅那些屬于這個(gè)區(qū)域的空閑機(jī)器人可以加入到這個(gè)協(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的機(jī)器人數(shù)量。Rp通過(guò)局部廣播網(wǎng)在tkk上提出協(xié)商協(xié)議。如果L(Rq)∈NRp(rp),Rq返回響應(yīng)d(Rq)，

(9)

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

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

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

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

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

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

3多機(jī)器人追逐仿真實(shí)驗(yàn)

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

圖1　追逐初始化階段

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

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

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

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

4 結(jié)語(yǔ)

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

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

[2] 周菁，慕德俊. 多機(jī)器人系統(tǒng)任務(wù)分配研究[J].西北大學(xué)學(xué)報(bào)：自然科學(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ī)模多移動(dòng)機(jī)器人合作任務(wù)的分布自主協(xié)作系統(tǒng)[J].機(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

文獻(xiàn)標(biāo)志碼：A

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

中圖分類(lèi)號(hào)：TP242.6

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

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

收稿日期：2015-11-04

doi:10.3969/j.issn.1009-8984.2016.01.012

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