張紅強(qiáng) ,吳亮紅 ,周 游 ,章 兢 ,周少武 ,劉朝華

(1.湖南科技大學(xué)信息與電氣工程學(xué)院,湖南湘潭 411201;2.湖南科技大學(xué)機(jī)電工程學(xué)院,湖南湘潭 411201;3.湖南大學(xué)電氣與信息工程學(xué)院,湖南長(zhǎng)沙 410082)

1 引言

群機(jī)器人系統(tǒng)是一種移動(dòng)的分布式系統(tǒng),具有高密度特點(diǎn)并具有魯棒性、可擴(kuò)展性和靈活性.這些重要特征使得群機(jī)器人系統(tǒng)相較于單個(gè)機(jī)器人或多機(jī)器人系統(tǒng)更有希望完成大規(guī)模任務(wù)[1].

要同時(shí)執(zhí)行大量任務(wù),任務(wù)分配作為關(guān)鍵問題直接影響著各種各樣的分布式系統(tǒng)的性能[2].通過任務(wù)分配這種集體行為,機(jī)器人能夠處理不同任務(wù).任務(wù)分配的目標(biāo)是通過使機(jī)器人動(dòng)態(tài)選擇需要完成的任務(wù)從而最大化系統(tǒng)的性能[3].在群機(jī)器人任務(wù)分配研究方面幾乎大部分集中在機(jī)器人覓食上,而其任務(wù)分配方法就是基于不同場(chǎng)景和條件下概率的有限狀態(tài)機(jī)[4–9]或者基于固定閾值或自適應(yīng)閾值進(jìn)行任務(wù)分配[10].另外,還有基于拍賣[11]、基于啟發(fā)式方法[12]以及基于市場(chǎng)的任務(wù)分配方法[13].

盡我們所知,目前僅有少數(shù)工作關(guān)注了具有時(shí)間約束的群機(jī)器人任務(wù)分配.具有弱期限的任務(wù)非常適合群機(jī)器人系統(tǒng)[2].拍賣策略是應(yīng)用最頻繁的之一,參見文獻(xiàn)[14].除了已經(jīng)建立的很好的拍賣策略,啟發(fā)式方法用于機(jī)器人帶時(shí)間約束的任務(wù)分配也得到了介紹,如文獻(xiàn)[15].在文獻(xiàn)[13]中,基于市場(chǎng)的任務(wù)分配策略也進(jìn)行了介紹,在這里時(shí)間是主要的關(guān)鍵約束.基于概率的方法參見文獻(xiàn)[2,16],這里同樣一起考慮到了成功完成任務(wù)時(shí)的獎(jiǎng)勵(lì)機(jī)制.

本文研究的群機(jī)器人多目標(biāo)圍捕任務(wù)屬于需要多個(gè)單一任務(wù)機(jī)器人的即時(shí)分配的多機(jī)器人任務(wù)[17],這是一個(gè)弱時(shí)限問題[2].與前述時(shí)間約束下的群機(jī)器人任務(wù)分配文獻(xiàn)不同的是,對(duì)于多動(dòng)態(tài)目標(biāo)圍捕,任務(wù)完成的時(shí)間固然重要,但最關(guān)鍵的是任務(wù)分配所花費(fèi)的時(shí)間長(zhǎng)短,因?yàn)槿绻麜r(shí)間太長(zhǎng),有可能會(huì)導(dǎo)致目標(biāo)已經(jīng)逃離圍捕機(jī)器人的感知范圍,造成個(gè)別目標(biāo)圍捕失敗.而上述基于市場(chǎng)、基于拍賣的方法,往往需要一個(gè)Leader或仲裁者來統(tǒng)領(lǐng)或裁決,需要團(tuán)體內(nèi)的機(jī)器人均與其通信,會(huì)產(chǎn)生通信瓶頸,只適合小規(guī)模機(jī)器人任務(wù)分配.而且任務(wù)分配過程復(fù)雜、時(shí)間長(zhǎng).基于酒吧系統(tǒng)的啟發(fā)式任務(wù)分配方法,需要知道全部機(jī)器人的數(shù)量和速度,通信和計(jì)算量大,而且解決的是只需要單個(gè)機(jī)器人就可以完成的任務(wù)分配問題,并不適合需要多個(gè)機(jī)器人協(xié)作完成的多目標(biāo)圍捕問題.基于概率的方法需要知道機(jī)器人數(shù)量并離線計(jì)算決策矩陣,其分配任務(wù)的過程復(fù)雜.

關(guān)于群機(jī)器人多目標(biāo)圍捕的研究成果不多.熊舉峰等[18]提出基于虛擬力的群機(jī)器人圍捕算法.然而受力分析復(fù)雜、可擴(kuò)展性差.Kubo等[19]提出一種群機(jī)器人多目標(biāo)圍捕算法.然而,這里的多目標(biāo)是靜止的,而且環(huán)境中無障礙物.Dutta[20]介紹了Kamimura和Ohira以及Angelani的多目標(biāo)離散化圍捕模型,但初始化時(shí)是隨機(jī)分布、無障礙物、無對(duì)抗、路徑特殊、不需要形成一定的圍捕隊(duì)形.Yasuda等[21]基于進(jìn)化人工神經(jīng)網(wǎng)絡(luò)(evolving artificial neural networks,EANNs)研究了群機(jī)器人在連續(xù)二維環(huán)境下多目標(biāo)單層圍捕及搬運(yùn)問題,但環(huán)境中無障礙物.

實(shí)現(xiàn)大規(guī)模群機(jī)器人動(dòng)態(tài)多目標(biāo)圍捕的挑戰(zhàn)在于如何使得當(dāng)動(dòng)態(tài)多目標(biāo)四散逃跑時(shí)每個(gè)機(jī)器人自組織地實(shí)現(xiàn)任務(wù)分配,不但要保證每個(gè)動(dòng)態(tài)目標(biāo)都有足夠多的機(jī)器人參與圍捕,還要保證最遠(yuǎn)目標(biāo)有最多的機(jī)器人參與圍捕,從而保證圍捕成功率;而且任務(wù)分配時(shí)需要的信息是盡可能少的局部信息,并且分配任務(wù)的時(shí)間要非常短,任務(wù)分配算法盡量簡(jiǎn)單,否則任務(wù)尚未分配完畢,目標(biāo)可能已經(jīng)逃離;分配了不同圍捕目標(biāo)的機(jī)器人之間如何避碰,如何減少運(yùn)動(dòng)距離;如何在未知?jiǎng)討B(tài)障礙物環(huán)境中做到既保持多目標(biāo)圍捕隊(duì)形又成功避障,而且由極少的局部信息控制個(gè)體的運(yùn)動(dòng).

為了實(shí)現(xiàn)動(dòng)態(tài)多目標(biāo)圍捕,本文完善了文獻(xiàn)[22]中的單目標(biāo)簡(jiǎn)化虛擬受力模型(simplified virtual-force model,SVF–model),圍捕個(gè)體基于兩最近鄰和目標(biāo)的施力就可以實(shí)現(xiàn)自主運(yùn)動(dòng)(計(jì)算簡(jiǎn)單,高可擴(kuò)展性),設(shè)計(jì)了基于個(gè)體面向多目標(biāo)中心方向兩最近鄰任務(wù)信息的動(dòng)態(tài)多目標(biāo)任務(wù)自組織分配方法,結(jié)合受力模型和任務(wù)分配方法提出了自組織協(xié)同動(dòng)態(tài)多目標(biāo)圍捕方法.在圍捕過程中機(jī)器人個(gè)體還可以根據(jù)距離目標(biāo)的遠(yuǎn)近與近鄰交換圍捕目標(biāo),達(dá)到避障的同時(shí)節(jié)省能量.

2 模型設(shè)計(jì)

2.1 圍捕個(gè)體模型及相關(guān)函數(shù)

圍捕個(gè)體hj(j=1,…,m)的模型請(qǐng)參看文獻(xiàn)[22]中圖1所示,hj的運(yùn)動(dòng)學(xué)方程及其相關(guān)參數(shù)范圍參看文獻(xiàn)[22]中式(1)–(2).

圍捕目標(biāo)和近鄰對(duì)象(包括不是被hj圍捕的目標(biāo)、動(dòng)態(tài)或靜態(tài)障礙物以及機(jī)器人)的施力函數(shù)分別為

其中d與文獻(xiàn)[22]中式(5)–(6)里面的z是一致的.不同之處是i=4表示對(duì)象是非自己圍捕的目標(biāo)時(shí)所用的具體參數(shù),dsp是開始向有效圍捕圓周上運(yùn)動(dòng)時(shí)機(jī)器人與目標(biāo)的距離,其他參數(shù)與文獻(xiàn)[22]中式(5)–(6)是一致的.而且這里用兩個(gè)條件來判斷何時(shí)向有效圍捕圓周上運(yùn)動(dòng)(文獻(xiàn)[22]中只用了ncdsp用來保護(hù)圍捕機(jī)器人不要太靠近目標(biāo),防止受損;當(dāng)d>dsp失效即機(jī)器人有時(shí)很難在一定距離范圍內(nèi)接近目標(biāo)時(shí),nc

對(duì)于凸障礙物,利用文獻(xiàn)[22]中仿生智能避障映射函數(shù)(4)進(jìn)行有效避障.為了確定兩有向線之間的角度,利用文獻(xiàn)[23]中式(1)進(jìn)行計(jì)算.

2.2 圍捕任務(wù)模型

通過研究狼群多目標(biāo)圍捕發(fā)現(xiàn)[24–25],其捕食過程首先是多任務(wù)分配,然后針對(duì)各個(gè)目標(biāo)的行為與文獻(xiàn)[22]相似.多目標(biāo)中單個(gè)目標(biāo)的運(yùn)動(dòng)方程與文獻(xiàn)[22]中相似.不同之處是整個(gè)圍捕環(huán)境及相關(guān)參數(shù)的說明是在文獻(xiàn)[22]中第2.2節(jié)定義1的基礎(chǔ)上擴(kuò)展了多目標(biāo)的定義,這里T={tp:p=0,1,…,e}是指各個(gè)具體的目標(biāo),而t0是指多目標(biāo)的中心.勢(shì)和勢(shì)角的定義同樣是在文獻(xiàn)[22]中第2.2節(jié)定義2的基礎(chǔ)上擴(kuò)展了多目標(biāo)勢(shì)和勢(shì)角的定義,PT={ρtp},p=1,…,e是目標(biāo)勢(shì),而文獻(xiàn)[22]定義1和定義2表達(dá)式中凡是針對(duì)單目標(biāo)的擴(kuò)展為多目標(biāo)即可.由上述描述給定復(fù)雜環(huán)境下多目標(biāo)的運(yùn)動(dòng)方程是將文獻(xiàn)[22]中式(7)里面的單目標(biāo)符號(hào)t1變成tp(p=1,…,e)并對(duì)相關(guān)參數(shù)給定初值即可.障礙物環(huán)境下動(dòng)態(tài)障礙物ui的運(yùn)動(dòng)方程與文獻(xiàn)[22]中式(8)一致.由圍捕環(huán)境、動(dòng)態(tài)多目標(biāo)以及動(dòng)態(tài)障礙物模型的構(gòu)建形成了整體的多目標(biāo)圍捕任務(wù)模型.

與文獻(xiàn)[22,25–26]所描述的圍捕過程不完全一樣,本文用dsp和l兩個(gè)參數(shù)來控制捕食者到獵物之間的距離,這比只用一個(gè)參數(shù)l來控制更科學(xué)一些,具體控制特點(diǎn)參看式(1)中的說明.當(dāng)只用一個(gè)參數(shù)l時(shí)方便控制追捕的時(shí)間,而不方便控制與獵物之間的距離.

3 圍捕算法

本文在文獻(xiàn)[22]的基礎(chǔ)上提出了多目標(biāo)簡(jiǎn)化虛擬受力模型(multi-target simplified virtual-force model,MSVF–model),給出多目標(biāo)自組織任務(wù)分配算法和復(fù)雜環(huán)境中群機(jī)器人協(xié)同圍捕動(dòng)態(tài)多目標(biāo)的算法,使得整個(gè)群體實(shí)現(xiàn)復(fù)雜環(huán)境下的動(dòng)態(tài)多目標(biāo)自組織圍捕.

3.1 多目標(biāo)簡(jiǎn)化虛擬受力模型

本文研究的動(dòng)態(tài)多目標(biāo)圍捕模型是在文獻(xiàn)[22]中提出的單目標(biāo)簡(jiǎn)化虛擬受力模型的基礎(chǔ)上完善的.圖1是多目標(biāo)簡(jiǎn)化虛擬受力模型,與單目標(biāo)的簡(jiǎn)化虛擬受力模型不同之處是圍捕環(huán)境中包含有多個(gè)目標(biāo),hj受到自己圍捕目標(biāo)的引力或斥力作用,其他目標(biāo)則作為近鄰對(duì)象處理.而其他符號(hào)的說明與文獻(xiàn)[22]中定義3一致.由于多目標(biāo)簡(jiǎn)化虛擬受力模型繼承了單目標(biāo)簡(jiǎn)化虛擬受力模型的受力分析方法,使得圍捕個(gè)體不存在局部極小值問題.由上述相關(guān)說明可得到當(dāng)目標(biāo)靜止時(shí)hj的需求速度為

其中:ftpj()是目標(biāo)tp(p=0,1,…,e)的施力函數(shù),按式(1)計(jì)算.其他符號(hào)意義及計(jì)算同文獻(xiàn)[22]中式(9)的相關(guān)說明.

圖1 多目標(biāo)簡(jiǎn)化虛擬受力模型Fig.1 MSVF–model

3.2 基于MSVF–model的個(gè)體控制輸入設(shè)計(jì)

未知復(fù)雜環(huán)境中圍捕時(shí)各機(jī)器人hj運(yùn)動(dòng)學(xué)方程的控制輸入與文獻(xiàn)[22]中基本一致,不同之處是vje,θje按式(4)來確定:

其中:j=1,2,…,mp,p=0,1,…,e,…,e)是個(gè)體感知目標(biāo)tp的速度矢量,是個(gè)體感知多目標(biāo)中心的速度矢量.這樣每個(gè)個(gè)體可以針對(duì)自己的圍捕目標(biāo)進(jìn)行圍捕,從而實(shí)現(xiàn)多目標(biāo)圍捕.

3.3 圍捕算法步驟

針對(duì)第2.2節(jié)中的圍捕任務(wù)模型,結(jié)合了MSVF–model和多任務(wù)分配策略的未知凸動(dòng)態(tài)障礙物環(huán)境下的群機(jī)器人協(xié)同動(dòng)態(tài)多目標(biāo)圍捕算法流程圖如圖2所示,這里需要進(jìn)行任務(wù)分配和交換圍捕目標(biāo),而基于SVF–model的單目標(biāo)圍捕算法沒有這些內(nèi)容[22,26].值得指出的是,該流程圖不但適用于動(dòng)態(tài)多目標(biāo)也適用于動(dòng)態(tài)單目標(biāo)以及靜態(tài)單、多目標(biāo)的圍捕.而圖2中“基于hj面對(duì)多目標(biāo)中心方向180o范圍內(nèi)的兩最近鄰進(jìn)行任務(wù)分配”的算法流程圖如圖3所示,這里的“hj面對(duì)多目標(biāo)中心方向180o范圍內(nèi)”是指以hj指向多目標(biāo)中心方向線為中心的左右90?之間的范圍.而圖2中“交換圍捕目標(biāo)”是每個(gè)機(jī)器人根據(jù)面向多目標(biāo)中心180?范圍內(nèi)的最近鄰機(jī)器人的圍捕目標(biāo)和自己的圍捕目標(biāo)交換前后是否會(huì)減少整體的運(yùn)動(dòng)距離而進(jìn)行決策的.

圖2 多目標(biāo)圍捕算法流程圖Fig.2 The flow chart of multi-target hunting algorithm

由圖3可知,動(dòng)態(tài)多目標(biāo)圍捕的任務(wù)分配只需要根據(jù)hj面對(duì)多目標(biāo)中心方向180?范圍內(nèi)最多兩個(gè)近鄰機(jī)器人的任務(wù)分配信息就可以完成,任務(wù)分配是自組織、分布式地進(jìn)行,沒有統(tǒng)一的領(lǐng)導(dǎo)者或裁判,算法簡(jiǎn)單而且高效,使得大規(guī)模群機(jī)器人的任務(wù)分配可以在短時(shí)間內(nèi)完成.這里需要注意分配任務(wù)時(shí),要將目標(biāo)進(jìn)行排序,任務(wù)0是指多目標(biāo)中心,任務(wù)1到e則是指具體的圍捕目標(biāo),任務(wù)1到e分別是指最遠(yuǎn)的目標(biāo)、次遠(yuǎn)的目標(biāo)、次次遠(yuǎn)的目標(biāo)、…、次次近的目標(biāo)、次近的目標(biāo)、最近的目標(biāo);這樣排序可以使得最遠(yuǎn)的目標(biāo)(也就是最難圍捕的目標(biāo),因?yàn)槠渥钊菀滋与x群機(jī)器人的感知范圍)分配到最多的圍捕機(jī)器人,保證整個(gè)圍捕的成功率.

圖3 hj任務(wù)分配流程圖Fig.3 The flow chart of hj task allocation

由任務(wù)分配算法和多目標(biāo)圍捕算法可知,每個(gè)機(jī)器人hj僅需兩個(gè)近鄰的任務(wù)信息來決定圍捕哪一個(gè)目標(biāo).任務(wù)分配之后,每個(gè)機(jī)器人hj將可能與前面最近鄰機(jī)器人交換圍捕目標(biāo),減少運(yùn)動(dòng)距離和能量消耗,提高了圍捕效率,同時(shí)也減少了機(jī)器人之間相碰的可能性.接著,每個(gè)機(jī)器人每一步的運(yùn)動(dòng)方向和速度大小將根據(jù)目標(biāo)和兩最近鄰來確定.因此,整個(gè)圍捕算法是分布式的和自組織的.

4 穩(wěn)定性分析

系統(tǒng)的穩(wěn)定性分析需要分3部分進(jìn)行:第1部分首先說明群機(jī)器人的自組織動(dòng)態(tài)多目標(biāo)任務(wù)分配算法是穩(wěn)定并合理的,這是文獻(xiàn)[22]所沒有的;第2部分在無障礙物環(huán)境下,對(duì)群機(jī)器人分成各個(gè)子群圍捕每個(gè)動(dòng)態(tài)目標(biāo)的子系統(tǒng)進(jìn)行穩(wěn)定性分析;第3部分在未知?jiǎng)討B(tài)凸障礙物環(huán)境下,分析群機(jī)器人對(duì)每個(gè)動(dòng)態(tài)目標(biāo)進(jìn)行圍捕的子系統(tǒng)的穩(wěn)定性.第2部分和第3部分是將文獻(xiàn)[22]所提出單目標(biāo)圍捕穩(wěn)定性理論推廣到了多目標(biāo)圍捕的子系統(tǒng)穩(wěn)定性分析中去,所以它們之間較相似.

4.1 任務(wù)分配算法的穩(wěn)定性分析

本節(jié)主要說明任務(wù)分配算法的穩(wěn)定性,其流程圖如圖3所示.動(dòng)態(tài)多目標(biāo)圍捕任務(wù)分配的基本要求是:第1,確保每一個(gè)目標(biāo)都有足夠多的機(jī)器人參與圍捕,假設(shè)每個(gè)目標(biāo)至少需要3個(gè)機(jī)器人圍捕,最多不限;第2,在統(tǒng)計(jì)數(shù)據(jù)平均值的意義下,最遠(yuǎn)目標(biāo)有最多機(jī)器人參與圍捕;第3,分配任務(wù)的時(shí)間要盡量短,而且當(dāng)機(jī)器人數(shù)量增加時(shí),分配任務(wù)的時(shí)長(zhǎng)按線性增長(zhǎng)而不是按指數(shù)級(jí)增長(zhǎng);第4,任務(wù)分配算法需要的信息量盡量少,算法本身是分布式的,而且盡量簡(jiǎn)單.

仿真環(huán)境是用MATLAB 2013a的隨機(jī)函數(shù)rand(·)隨機(jī)生成在10 m×10 m范圍內(nèi)分布的群機(jī)器人初始位置,動(dòng)態(tài)多目標(biāo)的位置則人為給定.下面針對(duì)任務(wù)分配的基本要求給出相應(yīng)說明.為了達(dá)到任務(wù)分配的第一個(gè)要求,需要滿足的條件是圍捕機(jī)器人群體中個(gè)體的數(shù)量與目標(biāo)個(gè)數(shù)之間有一個(gè)基本比例的要求,如表1所示,這是由大量仿真統(tǒng)計(jì)得到的.為了滿足第2個(gè)要求,需要滿足兩個(gè)條件,第1個(gè),同樣要滿足表1;第2個(gè)條件是,需要在任務(wù)與動(dòng)態(tài)目標(biāo)之間確定一種對(duì)應(yīng)關(guān)系,參看第3.3節(jié)相關(guān)說明.

分配任務(wù)隨著機(jī)器人數(shù)量增加而消耗的時(shí)間分布圖如圖4所示.圖4是當(dāng)目標(biāo)為50個(gè)時(shí),50次任務(wù)分配仿真中消耗的最長(zhǎng)時(shí)間隨著機(jī)器人的數(shù)量增加時(shí)的變化圖.在圖4中,機(jī)器人數(shù)量由2000增加到了5000,數(shù)量增加了1.5倍,而消耗時(shí)長(zhǎng)由22步增加到27步,只增加了0.23倍.由圖4可以看出,當(dāng)機(jī)器人數(shù)量成倍增加時(shí),其任務(wù)分配消耗的時(shí)間則是以線性增加的,而且當(dāng)機(jī)器人數(shù)量繼續(xù)增加時(shí),任務(wù)分配消耗的時(shí)長(zhǎng)增長(zhǎng)變慢(當(dāng)機(jī)器人數(shù)量增多時(shí),任務(wù)分配時(shí)由于更多的分配路徑使得消耗的時(shí)間增長(zhǎng)越來越慢),即使機(jī)器人規(guī)模達(dá)到5000個(gè)時(shí),任務(wù)分配時(shí)消耗的最大時(shí)長(zhǎng)也才27步,如果不考慮通信的時(shí)間花費(fèi)(獲取兩個(gè)最近鄰的任務(wù)分配信息可以簡(jiǎn)單地通過隱式通信得到,例如可以把不同任務(wù)用不同顏色的信號(hào)燈來表示,這樣可以迅速獲取信息并迅速?zèng)Q策自己的任務(wù)),按每步1 s的運(yùn)動(dòng)時(shí)長(zhǎng)計(jì)算,其任務(wù)分配時(shí)長(zhǎng)也只有幾十秒而已,因此消耗時(shí)間較短.由此說明了所提任務(wù)分配算法可以滿足第3個(gè)要求.

表1 給定目標(biāo)個(gè)數(shù)時(shí)圍捕機(jī)器人群體中個(gè)體的最少數(shù)量表Table 1 The least quantity table in a swarm of hunting robots when giving the number of targets

圖4 任務(wù)分配消耗時(shí)間隨機(jī)器人數(shù)量變化趨勢(shì)圖Fig.4 The tendency chart of the time consumption of task allocation distribution with robots quantity increasing

由任務(wù)分配算法流程圖(圖3所示)可以看出,機(jī)器人個(gè)體任務(wù)分配過程只是根據(jù)其面對(duì)多目標(biāo)中心方向180?范圍內(nèi)的兩最近鄰的任務(wù)分配信息來進(jìn)行,這說明算法本身需要的信息量少,而且是分布式的.整個(gè)任務(wù)分配算法流程簡(jiǎn)單,任務(wù)分配時(shí)計(jì)算只用了加法,可見其足夠簡(jiǎn)單,滿足第4個(gè)要求.

4.2 無障礙物環(huán)境下穩(wěn)定性分析

針對(duì)多目標(biāo)圍捕系統(tǒng)無障礙物環(huán)境下的穩(wěn)定性分析采用了文獻(xiàn)[22]的方法.不同之處是需要推導(dǎo)每個(gè)目標(biāo)都被圍捕機(jī)器人成功圍捕時(shí)所需要的條件,圍捕每一個(gè)目標(biāo)看作是一個(gè)子圍捕系統(tǒng),需要推導(dǎo)每個(gè)子圍捕系統(tǒng)都穩(wěn)定的條件,即把文獻(xiàn)[22]中定理的證明看作是一個(gè)圍捕子系統(tǒng)穩(wěn)定條件的推導(dǎo)過程.系統(tǒng)偏差分解為個(gè)體到目標(biāo)距離偏差δjy′=r,j=1,…,mp,p=1,…,e(這里mp是指圍捕目標(biāo)tp的機(jī)器人個(gè)數(shù),δjy′定義與文獻(xiàn)[22]中不一致,這里的目標(biāo)包含了所有目標(biāo))和個(gè)體到兩最近鄰機(jī)器人距離偏差的一半δjabx′[22](δjabx′的定義與文獻(xiàn)[22]中形式一致,但下標(biāo)含義不一致,這里j=1,…,mp,p=1,…,e,把圍捕時(shí)的機(jī)器人分成了多個(gè)子系統(tǒng)來分析,第4.2節(jié)和第4.3節(jié)式中j的含義均同這里).

個(gè)體的自主運(yùn)動(dòng)偏差方程[22]:

另一個(gè)不同之處是vy′j(k)是vy′j的離散化形式,可以按式(7)來計(jì)算

vx′j(k)可以參看文獻(xiàn)[22]中式(20).

定理1在無障礙物的環(huán)境中,如果每個(gè)目標(biāo)的圍捕機(jī)器人滿足式(5)、(k)dsp或ncl以及0

為大范圍漸近穩(wěn)定,其中p=1,…,e.

證由于證明過程與文獻(xiàn)[22]中定理1的證明過程相似,這里省略.

根據(jù)定理1,選擇了不同目標(biāo)的個(gè)體將會(huì)到達(dá)不同目標(biāo)為中心的有效圍捕圓周上(這是與文獻(xiàn)[22]中定理1結(jié)論不同之處,文獻(xiàn)[22]中只會(huì)到達(dá)唯一目標(biāo)為中心的有效圍捕圓周上),如果要實(shí)現(xiàn)均勻分布,還需要考慮當(dāng)(k)r|<ε1,j=1,2,…,mp,p=1,…,e時(shí)δjabx′(k)即式(6)的收斂性[22].

定理2在無障礙物環(huán)境下,如果每個(gè)目標(biāo)的圍捕機(jī)器人滿足式(6)和0<則系統(tǒng)原點(diǎn)平衡狀態(tài),即

為大范圍漸近穩(wěn)定,其中

證由于證明過程與文獻(xiàn)[22]中定理2的證明過程相似,這里省略.

因此,同時(shí)滿足定理1和定理2,在有限時(shí)間內(nèi)可使圍捕四散分布的靜態(tài)多目標(biāo)的個(gè)體均勻分布在每個(gè)目標(biāo)為中心的有效圍捕圓周上或圍捕聚集在一起的靜態(tài)多目標(biāo)的個(gè)體均勻分布在不同目標(biāo)的有效圍捕圓周的連續(xù)弧段上.這是與文獻(xiàn)[22]中滿足定理1和定理2時(shí)所得結(jié)論不同之處,文獻(xiàn)[22]中的有效圍捕圓周只有一個(gè).說明本文圍捕算法具有較強(qiáng)的靈活性.定理1和定理2還說明了如何通過調(diào)節(jié)時(shí)間步長(zhǎng)或相關(guān)參數(shù)以達(dá)到穩(wěn)定條件,有關(guān)如何調(diào)節(jié)參數(shù)與文獻(xiàn)[22]相似.

動(dòng)態(tài)多目標(biāo)以漫步速度逃逸被成功圍捕的一個(gè)充分條件為

這個(gè)充分條件的推導(dǎo)過程和相關(guān)說明與文獻(xiàn)[22]中式(26)相似,不同之處是這里圍捕的目標(biāo)是指多目標(biāo).

4.3 凸障礙物環(huán)境下穩(wěn)定性分析

這里根據(jù)目標(biāo)方向距離偏差δjy′和兩最近鄰對(duì)象距離偏差對(duì)系統(tǒng)進(jìn)行分析[22].采用

上式包含了多目標(biāo),與文獻(xiàn)[22]不同,障礙物環(huán)境下的分析同定理1,原因請(qǐng)參考文獻(xiàn)[22].δ′jabx′的定義與文獻(xiàn)[22]中的定義形式一致,但下標(biāo)含義不一致,這里j=1,…,mp,p=1,…,e,個(gè)體的自主運(yùn)動(dòng)偏差方程如式(9)[22]:

其中:j=1,2,…,mp,p=1,…,e,vx′j(k)可參看文獻(xiàn)[22]中式(20).

定理3在凸障礙物環(huán)境下,如果每個(gè)機(jī)器人滿足式(9)和0<Γd1μ′<2,則系統(tǒng)原點(diǎn)平衡狀態(tài),即

為大范圍漸近穩(wěn)定,其中:

證由于證明過程與文獻(xiàn)[22]中定理3的證明過程相似,這里省略.

因此,在障礙物環(huán)境中對(duì)于四散分布的或聚集在一起的靜態(tài)多目標(biāo),同時(shí)滿足定理1和定理3,即可使圍捕個(gè)體受力平衡地分布在多個(gè)目標(biāo)的有效圍捕圓周上或其連續(xù)弧段上.這是與文獻(xiàn)[22]的不同之處.這里同樣給出了系統(tǒng)不穩(wěn)定時(shí)參數(shù)調(diào)節(jié)方法,即調(diào)節(jié)c1,d1或Γ等[22].

動(dòng)態(tài)多目標(biāo)以漫步速度逃逸被成功圍捕的一個(gè)充分條件為

這個(gè)充分條件的推導(dǎo)過程和相關(guān)說明與文獻(xiàn)[22]中式(30)相似,不同之處是這里圍捕的目標(biāo)是指多目標(biāo).最終的圍捕隊(duì)形同樣會(huì)由于存在四散分開的動(dòng)態(tài)多目標(biāo)和聚集在一起的動(dòng)態(tài)多目標(biāo)而會(huì)呈現(xiàn)不同的圍捕隊(duì)形,但整體上都會(huì)是受力均衡的圍捕隊(duì)形.這也是與文獻(xiàn)[22]的不同之處.

5 仿真與分析

為了與文獻(xiàn)[22,25–26]作對(duì)比分析,本節(jié)針對(duì)第2.2節(jié)構(gòu)建的動(dòng)態(tài)多目標(biāo),通過未知?jiǎng)討B(tài)凸障礙物復(fù)雜環(huán)境下的仿真討論多目標(biāo)圍捕算法的靈活性、可擴(kuò)展性、避障性能以及魯棒性.表2是系統(tǒng)的參數(shù)設(shè)置,表3是機(jī)器人避碰/避障參數(shù)值,表4是多目標(biāo)和動(dòng)態(tài)障礙物避障參數(shù)值.

表2 圍捕系統(tǒng)參數(shù)值Table 2 The hunting systems parameters

表3 機(jī)器人避碰/避障參數(shù)值Table 3 Avoiding collisions parameters of the robots

表4 目標(biāo)和動(dòng)態(tài)障礙物避障參數(shù)值Table 4 Avoiding collisions parameters of the targets and dynamic obstacles

本節(jié)仿真使用30個(gè)機(jī)器人在含有13個(gè)凸障礙物的環(huán)境中圍捕3個(gè)目標(biāo),表5是它們的初始坐標(biāo),時(shí)間步長(zhǎng)Γ=0.6 s.由于本文研究的是多目標(biāo)圍捕,群機(jī)器人的圍捕過程與文獻(xiàn)[22,25–26]中的單目標(biāo)圍捕不完全一致.圖5是仿真軌跡.每個(gè)圍捕機(jī)器人用圓點(diǎn)表示,其右上角符號(hào)代表圍捕的目標(biāo),右下角符號(hào)代表圍捕機(jī)器人的序號(hào).圖5(a)中,經(jīng)過3步時(shí)間,群機(jī)器人個(gè)體運(yùn)用自組織分布式任務(wù)分配算法,根據(jù)面向多目標(biāo)中心180?范圍內(nèi)最多兩最近鄰的任務(wù)分配信息自動(dòng)地選擇了自己的圍捕目標(biāo),選擇結(jié)果是最近目標(biāo)t1、次近目標(biāo)t2、最遠(yuǎn)目標(biāo)t3分別有8個(gè)、10個(gè)、12個(gè)機(jī)器人圍捕,最遠(yuǎn)目標(biāo)t3具有最多的圍捕機(jī)器人.由此圖還可以看出圍捕3個(gè)目標(biāo)的機(jī)器人混雜在一起.

表5 仿真中目標(biāo)和群機(jī)器人初始位置坐標(biāo)Table 5 Initial coordinate values of targets and swarm robots in simulation

圖5(b)中,通過交換圍捕目標(biāo),到第8步后,整體上圍捕左上方目標(biāo)t1的機(jī)器人位于左上方,而圍捕右下方目標(biāo)t3的機(jī)器人位于右下方,這樣由于圍捕同一目標(biāo)的機(jī)器人在一起,運(yùn)動(dòng)整體上協(xié)調(diào)一致,避免了不必要的避碰,而且還減少了運(yùn)動(dòng)距離和能量損耗,同時(shí)也提高了圍捕效率.

圖5 30個(gè)機(jī)器人圍捕3個(gè)目標(biāo)Fig.5 30 robots hunting 3 targets

余下的圍捕過程與文獻(xiàn)[22,26]一致.復(fù)雜環(huán)境使得群機(jī)器人在圍捕多目標(biāo)時(shí),不僅要對(duì)目標(biāo)進(jìn)行包圍,還要避開障礙物,增加了機(jī)器人之間進(jìn)行協(xié)作的難度.而多目標(biāo)簡(jiǎn)化虛擬受力模型使得群機(jī)器人不僅能避開障礙物,還可以與障礙物形成協(xié)同圍捕的隊(duì)形,如圖5(e)–5(g)所示.整個(gè)群體在機(jī)器人數(shù)目是文獻(xiàn)[22,26]機(jī)器人數(shù)目5倍、目標(biāo)增加了兩個(gè)的復(fù)雜環(huán)境下實(shí)現(xiàn)了多目標(biāo)圍捕,說明本算法的靈活性、可擴(kuò)展性、避碰/避障性能和魯棒性較強(qiáng).

6 本文基于MSVF–model的圍捕算法與其它算法的比較分析

本文基于MSVF–model的方法與基于松散偏好規(guī)則(loose-preference rule,LP–rule)的方法[25]相比優(yōu)勢(shì)如下:1)文獻(xiàn)[22,26]中基于SVF–model的方法與基于LP-rule的方法相比的優(yōu)勢(shì),本文算法同樣具有;2)本文算法還可以圍捕靜態(tài)或動(dòng)態(tài)的單個(gè)或多個(gè)目標(biāo),而基于LP–rule的圍捕算法沒有考慮圍捕多目標(biāo);3)本文算法比基于LP–rule的圍捕算法具有更好的靈活性.

本文基于MSVF–model的圍捕算法與其它基于SVF–model的圍捕算法[22,26]相比優(yōu)勢(shì)如下:1)本文考慮了如何圍捕動(dòng)態(tài)多目標(biāo),而其它圍捕算法沒有考慮;2)本文算法在多目標(biāo)圍捕方面的靈活性優(yōu)于其它算法.

本文基于MSVF–model的圍捕算法與其它多目標(biāo)圍捕算法相比優(yōu)勢(shì)如下:1)文獻(xiàn)[27]研究了多目標(biāo)導(dǎo)航問題,該問題涉及一組智能體協(xié)調(diào)地對(duì)多個(gè)運(yùn)動(dòng)目標(biāo)進(jìn)行導(dǎo)航,采用分布式算法,并分析了穩(wěn)定性.然而,環(huán)境中沒有考慮障礙物,多目標(biāo)整體上在一起運(yùn)動(dòng),而不是四散運(yùn)動(dòng).而本文所提算法不但可以適應(yīng)運(yùn)動(dòng)目標(biāo)四散運(yùn)動(dòng),也適應(yīng)多個(gè)目標(biāo)一塊運(yùn)動(dòng),同時(shí)考慮了避障問題;2)文獻(xiàn)[28]針對(duì)地面存在障礙物和約束的環(huán)境中群機(jī)器人捕獲多目標(biāo)提出了一種自適應(yīng)模式形成的方法.但個(gè)體需要全局信息,可擴(kuò)展性差,因此對(duì)于多目標(biāo)、大規(guī)模群機(jī)器人圍捕的適應(yīng)性較低,而且環(huán)境中沒有動(dòng)態(tài)障礙物,也沒有對(duì)系統(tǒng)進(jìn)行穩(wěn)定性分析.而本文所提算法基于局部?jī)勺罱徯畔⒕涂梢詫?shí)現(xiàn)自組織任務(wù)分配和圍捕隊(duì)形的形成,在避障時(shí)不需要根據(jù)障礙物的形狀來進(jìn)行,只需要感應(yīng)到障礙物上的至多最近兩點(diǎn)的距離就可以實(shí)現(xiàn)避障,算法簡(jiǎn)單易于實(shí)現(xiàn),同時(shí)考慮了環(huán)境中動(dòng)態(tài)障礙物的避障問題.

7 總結(jié)

本文研究未知?jiǎng)討B(tài)凸障礙物環(huán)境下群機(jī)器人自組織協(xié)同動(dòng)態(tài)多目標(biāo)圍捕問題,在完善文獻(xiàn)[22]中單目標(biāo)簡(jiǎn)化虛擬受力模型的基礎(chǔ)上構(gòu)建了MSVF–model,設(shè)計(jì)了動(dòng)態(tài)多目標(biāo)自組織任務(wù)分配算法和動(dòng)態(tài)多目標(biāo)協(xié)同圍捕算法.在理論上分析了整個(gè)圍捕系統(tǒng)的穩(wěn)定性,給出了穩(wěn)定性條件,對(duì)系統(tǒng)參數(shù)設(shè)置有較好的指導(dǎo)作用.由仿真驗(yàn)證了基于MSVF–model的多目標(biāo)圍捕算法具有更好的靈活性、可擴(kuò)展性、魯棒性和避障/避碰性能.最后,與其它圍捕方法進(jìn)行了對(duì)比分析.