屈軍鎖,馬玉環(huán),蔡 星,李鵬飛
(西安郵電大學(xué) 通信與信息工程學(xué)院,陜西 西安 710121)
工業(yè)化進(jìn)程的加快使得機(jī)器人技術(shù)的發(fā)展愈發(fā)被重視。機(jī)器人技術(shù)[1]是對(duì)未來(lái)新興產(chǎn)業(yè)發(fā)展具有重要意義的高技術(shù)之一,現(xiàn)已廣泛應(yīng)用在工業(yè)、醫(yī)療和科學(xué)探索等眾多領(lǐng)域。隨著需求的多樣化和復(fù)雜化,單機(jī)器人在許多場(chǎng)景下已無(wú)法滿足需求,而多機(jī)器人技術(shù)開(kāi)拓了機(jī)器人領(lǐng)域的新方向,彌補(bǔ)了單機(jī)器人的缺陷。多機(jī)器人系統(tǒng)可以通過(guò)機(jī)器人之間相互合作共同完成復(fù)雜的任務(wù),比單機(jī)器人系統(tǒng)更靈活、穩(wěn)定性表現(xiàn)更好[2]。目前,多機(jī)器人的編隊(duì)控制問(wèn)題已成為機(jī)器人領(lǐng)域的重要研究方向。多機(jī)器人編隊(duì)控制問(wèn)題源于自然界生物的群體行為,如鳥(niǎo)群的集體遷徙行為、魚(yú)群編隊(duì)防御行為和蟻群集體協(xié)作覓食行為等。在機(jī)器人領(lǐng)域,多機(jī)器人編隊(duì)是指多個(gè)移動(dòng)式機(jī)器人在運(yùn)動(dòng)過(guò)程中,按照一定的距離和運(yùn)動(dòng)狀態(tài)的約束,使得多機(jī)器人形成期望的幾何形狀[3],如工業(yè)中利用倉(cāng)儲(chǔ)機(jī)器人協(xié)同搬運(yùn)貨物、軍事中利用多無(wú)人機(jī)協(xié)同作業(yè)等[4]。
多機(jī)器人系統(tǒng)的控制結(jié)構(gòu)主要包含集中式、分散式和分布式等3類,其中分布式結(jié)構(gòu)包含了集中式與分散式結(jié)構(gòu)的優(yōu)點(diǎn),應(yīng)用較為廣泛。多機(jī)器人編隊(duì)的控制方法主要有領(lǐng)航者-跟隨者編隊(duì)控制策略[5]、基于行為的編隊(duì)控制策略[6],以及基于虛擬結(jié)構(gòu)的編隊(duì)控制策略[7]。領(lǐng)航者-跟隨者編隊(duì)控制策略具有結(jié)構(gòu)簡(jiǎn)潔易于實(shí)現(xiàn)的優(yōu)點(diǎn),但編隊(duì)穩(wěn)定性受到領(lǐng)航者狀態(tài)的影響較大[8]。文獻(xiàn)[9]在領(lǐng)航者-跟隨者策略的基礎(chǔ)上提出了基于拍賣算法的編隊(duì)控制策略,提高了編隊(duì)的效率,但是該策略對(duì)于系統(tǒng)資源消耗較大。文獻(xiàn)[10]引入了虛擬領(lǐng)航者,使得編隊(duì)中跟隨者相對(duì)于領(lǐng)航者的跟蹤誤差更小?;谛袨榈木庩?duì)控制策略適用于機(jī)器人數(shù)量較多的系統(tǒng),但編隊(duì)隊(duì)形的穩(wěn)定性和實(shí)時(shí)性方面存在缺陷?;谔摂M結(jié)構(gòu)的編隊(duì)控制策略[11]編隊(duì)精度較高,但在實(shí)際中的通信與計(jì)算成本較大,編隊(duì)實(shí)時(shí)性較差。文獻(xiàn)[12]針對(duì)多機(jī)器人的編隊(duì)運(yùn)動(dòng)問(wèn)題,提出一種鏈?zhǔn)骄庩?duì)控制方法,該方法通過(guò)主從協(xié)同的方式實(shí)現(xiàn)了多機(jī)器人的編隊(duì)行進(jìn),但編隊(duì)穩(wěn)定性較差。文獻(xiàn)[13]針對(duì)未知環(huán)境下的多機(jī)器人編隊(duì)隊(duì)形控制問(wèn)題,基于類鳥(niǎo)群模擬放射方法設(shè)計(jì)了不同規(guī)則的控制器,能夠?qū)崿F(xiàn)機(jī)器人編隊(duì)任意隊(duì)形的變換和保持,但是該方法計(jì)算復(fù)雜度較高。
近年來(lái),一致性理論在編隊(duì)控制領(lǐng)域的應(yīng)用逐漸受到重視。Ren等[14]將一致性控制律應(yīng)用于多智能體系統(tǒng)的編隊(duì)控制問(wèn)題中,并驗(yàn)證了基于領(lǐng)航-跟隨者策略等幾種傳統(tǒng)編隊(duì)策略均可利用一致性理論實(shí)現(xiàn)?;诜?hào)拉普拉斯矩陣的多機(jī)器人仿射編隊(duì)控制方法[15]分析了多機(jī)器人系統(tǒng)能夠?qū)崿F(xiàn)仿射變換的條件,為多機(jī)器人的編隊(duì)控制提供了一種新的方法。文獻(xiàn)[16]研究了對(duì)應(yīng)于無(wú)向圖應(yīng)力矩陣的仿射編隊(duì)控制方法,給出了機(jī)器人編隊(duì)能夠?qū)崿F(xiàn)仿射定位的充要條件,基于仿射變換設(shè)計(jì)了不同情況下的編隊(duì)控制器,并證明了所提出的控制律的穩(wěn)定性和全局收斂性。然而,各種策略均存在著各自的局限性和不足,限制了其在復(fù)雜場(chǎng)景下的廣泛應(yīng)用。因此,擬對(duì)多機(jī)器人路徑規(guī)劃以及編隊(duì)運(yùn)動(dòng)控制問(wèn)題進(jìn)行研究,給出一種多機(jī)器人路徑規(guī)劃及編隊(duì)控制策略。首先,基于IPOPT(Interior Point Optimizer)路徑優(yōu)化方法,改善A*算法規(guī)劃的路徑不平滑問(wèn)題,得到軌跡平滑的路徑。然后,根據(jù)有向圖結(jié)構(gòu)給出領(lǐng)航-跟隨者型仿射編隊(duì)控制方法,并基于一致性理論設(shè)計(jì)一階和二階多機(jī)器人系統(tǒng)的編隊(duì)運(yùn)動(dòng)控制協(xié)議,實(shí)現(xiàn)機(jī)器人編隊(duì)隊(duì)形的控制。
將多機(jī)器人編隊(duì)視為一個(gè)尺度可伸縮的整體,參照單機(jī)器人的路徑規(guī)劃方法,由編隊(duì)中的領(lǐng)航者負(fù)責(zé)規(guī)劃編隊(duì)整體的參考路徑,根據(jù)編隊(duì)中機(jī)器人之間的位置關(guān)系對(duì)獲得的路徑偏移,得到全部機(jī)器人的路徑。選擇A*算法[17]作為多機(jī)器人編隊(duì)的路徑規(guī)劃算法,基于IPOPT對(duì)A*算法規(guī)劃的全局路徑進(jìn)行優(yōu)化,得到軌跡平滑的路徑?;谟邢驁D結(jié)構(gòu),給出領(lǐng)航-跟隨者型仿射編隊(duì)控制方法,實(shí)現(xiàn)編隊(duì)的放縮、旋轉(zhuǎn)等變換。系統(tǒng)流程如圖1所示。
圖1 系統(tǒng)流程
1.1.1 A*算法
A*算法[17]是一種靜態(tài)路網(wǎng)中求解最短路徑搜索算法,通過(guò)增加啟發(fā)式函數(shù)確定最優(yōu)路徑,是目前應(yīng)用較為廣泛的路徑查找算法。A*算法的公式描述為
F(n)=g(n)+h(n)
(1)
其中,
式中:F(n)為節(jié)點(diǎn)n的估價(jià)函數(shù);g(n)為結(jié)點(diǎn)t的實(shí)際代價(jià);h(n)為從結(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)p的最佳路徑的估計(jì)代價(jià);(xn,yn)為節(jié)點(diǎn)n的坐標(biāo);(xt,yt)為節(jié)點(diǎn)t的坐標(biāo);(xp,yp)為節(jié)點(diǎn)p的坐標(biāo)。
通過(guò)仿真軟件對(duì)A*算法進(jìn)行路徑規(guī)劃仿真,A*算法路徑規(guī)劃過(guò)程如圖2所示,規(guī)劃結(jié)果如圖3所示。
圖2 A*算法路徑規(guī)劃
圖3 A*算法路徑規(guī)劃結(jié)果
觀察圖2和圖3仿真結(jié)果發(fā)現(xiàn),A*算法能夠從起點(diǎn)位置搜索出到達(dá)目標(biāo)位置的無(wú)碰撞路徑,但是路徑的轉(zhuǎn)折角度過(guò)大,路徑不夠平滑。
1.1.2 基于IPOPT的A*算法軌跡優(yōu)化
為了使得A*算法規(guī)劃的路徑更加平滑,基于IPOPT對(duì)A*算法規(guī)劃的全局路徑進(jìn)行優(yōu)化,將線性搜索過(guò)濾原始對(duì)偶內(nèi)點(diǎn)算法用于求解非線性方程組。內(nèi)點(diǎn)算法是將非線性規(guī)劃的不等式約束轉(zhuǎn)化為障礙并將其添加到目標(biāo)函數(shù)中,將原始的非線性規(guī)劃轉(zhuǎn)化為僅等式約束或無(wú)約束問(wèn)題。簡(jiǎn)化后,非線性優(yōu)化問(wèn)題便轉(zhuǎn)換為障礙因素類型的子問(wèn)題。
非線性優(yōu)化的問(wèn)題模型表示為
(2)
s.t.gL≤g(x)≤gU
xL≤x≤xU
式中:x∈Rn為優(yōu)化變量,下限xL∈(R∪{-∞})n,上限xU∈(R∪{+∞})n;函數(shù)f:Rn→R為目標(biāo)函數(shù);函數(shù)g:Rn→Rm為一般非線性約束,其上限gL∈(R∪{-∞})m,下限gU∈(R∪{+∞})m。將式(2)中的約束g(x)和變量x提取為如下形式
(3)
將式(3)中所有的變量下限為0,那么原非線性規(guī)劃式(2)可以轉(zhuǎn)換為一個(gè)新的非線性規(guī)劃問(wèn)題
s.t.c(x)=0
x≥0
(4)
式中:函數(shù)f(x)為目標(biāo)函數(shù);函數(shù)c(x)為約束函數(shù),其約束條件為ci(x)=gi(x)-si=0,(i=1,2,3,…n);x≥0為添加新的約束,使得所有變量的下限等于0。在這個(gè)新的非線性規(guī)劃問(wèn)題中,使用內(nèi)點(diǎn)法并引入對(duì)數(shù)障礙項(xiàng),構(gòu)建得到新的目標(biāo)函數(shù)
s.t.c(x)=0
(5)
式(5)中,對(duì)數(shù)障礙函數(shù)φμ(x)替代了式(4)中c(x),μ為障礙項(xiàng)參數(shù)且μ>0。φμ(x)將x的分量xi添加到目標(biāo)函數(shù)中,從而保證了xi≥0,在優(yōu)化過(guò)程中,任意xi保持非負(fù)??紤]到xi趨于0時(shí),φμ(x)的值將區(qū)域無(wú)窮大,因此式(5)的最優(yōu)解將出現(xiàn)在x的定義域內(nèi),且滿足xi≥0。
原非線性優(yōu)化問(wèn)題的求解可以轉(zhuǎn)換為φμ(x)的最小值求解問(wèn)題,求解步驟如下。
步驟1確定合適的障礙參數(shù)μ,為變量x賦初始值。
步驟2把μ的值減少,求解下一個(gè)障礙問(wèn)題,起始點(diǎn)為前一個(gè)障礙問(wèn)題的解。
步驟3不斷重復(fù)步驟2,直到得到式(4)的解,或者滿足一階最優(yōu)條件的解。
求得式(5)的一階的最優(yōu)條件為
(6)
式中:x,z≥0;e為全1向量;y∈Rn為拉格朗日乘子;z∈Rn為邊界約束的拉格朗日乘子;X=Diag(x),Z=Diag(z)。
(7)
式中:I為單位矩陣;Wi為式(3)中g(shù)i(x)的拉格朗日函數(shù)的海森矩陣;Ai為等式約束的雅克比矩陣的轉(zhuǎn)置;gi為目標(biāo)函數(shù)的梯度。
在zi方向上更新時(shí)滿足
其中,τ=min{0.99,μ}。
(8)
設(shè)約束條件為g、狀態(tài)變量為x,那么使用IPOPT求解非線性優(yōu)化問(wèn)題的主要步驟描述如下。
步驟1設(shè)置狀態(tài)變量x和約束條件g的數(shù)量。
步驟2設(shè)置狀態(tài)變量x的初始值。
步驟3設(shè)置狀態(tài)變量x和約束條件g的上下界。
步驟4構(gòu)建約束條件g。
步驟5構(gòu)建問(wèn)題的目標(biāo)函數(shù)。
步驟6設(shè)置IPOPT求解參數(shù)。
步驟7迭代求解,得到優(yōu)化結(jié)果。
優(yōu)化后的路徑貼近原始路徑,且路徑彎折區(qū)域軌跡平滑連續(xù),使得機(jī)器人在該路徑上的運(yùn)動(dòng)連續(xù),降低了機(jī)器人的運(yùn)動(dòng)代價(jià)?;贗POPT的A*軌跡優(yōu)化過(guò)程如圖4所示。
圖4 基于IPOPT的A*軌跡優(yōu)化過(guò)程
仿射變換是指一個(gè)向量空間通過(guò)線形變換與平移變換組合,轉(zhuǎn)換為另一個(gè)向量空間的變換過(guò)程。圖形的仿射變換如圖5所示。
圖5 圖形仿射變換
二維平面中的一個(gè)多機(jī)器人編隊(duì),如果編隊(duì)變換前后的隊(duì)形仿射等價(jià),那么編隊(duì)隊(duì)形變換過(guò)程可以被仿射變換描述,編隊(duì)可以基于仿射變換生成任意與之仿射等價(jià)的隊(duì)形。
設(shè)d維空間d中由N個(gè)機(jī)器人組成多機(jī)器人系統(tǒng),前Nl個(gè)機(jī)器人為領(lǐng)航者,跟隨者數(shù)量為Nf=N-Nl,則系統(tǒng)中機(jī)器人的位置集合可表示為
(9)
式中:pl(l=1,2…Nl)為系統(tǒng)中領(lǐng)航者的位置集合;pf(f=Nl+1,Nl+2,…N)為跟隨者的位置集合。
系統(tǒng)中機(jī)器人之間通信拓?fù)溆糜邢驁DG=(V,E)表示,其中:V=(Vl,Vf)為節(jié)點(diǎn)集;Vl表示領(lǐng)航者集合;Vf表示跟隨者集合;E?V×V為邊集,若圖中存在有向邊(i,j)∈E,那么節(jié)點(diǎn)j定義為節(jié)點(diǎn)i的入鄰居,節(jié)點(diǎn)i為j的出鄰居。系統(tǒng)編隊(duì)表示為(G,p),有向圖G的節(jié)點(diǎn)與系統(tǒng)中的機(jī)器人依次對(duì)應(yīng)。
標(biāo)稱編隊(duì)描述了編隊(duì)的期望隊(duì)形,定義系統(tǒng)的標(biāo)稱編隊(duì)表示為(G,r),r為標(biāo)稱編隊(duì)的隊(duì)形矩陣,表示為
(10)
式中:rl為領(lǐng)航者的標(biāo)稱隊(duì)形;rf為跟隨者標(biāo)稱編隊(duì)。
定義標(biāo)稱隊(duì)形r的仿射映射為
(11)
式中:(A,b)記作仿射變換;IN與1N分別為N維單位矩陣和全1向量;?為克羅內(nèi)克積。
定義位置集合p的配置矩陣P(p)∈d×N,定義P(p)的增廣矩陣為
(12)
定義時(shí)變目標(biāo)編隊(duì)為
p*(t)=[Id?A(t)]r+1N?b(t)
(13)
式中:Id為d維單位矩陣;A(t)表示仿射變換中的線性變換,而b(t)則仿射變換中的平移變換;t為時(shí)間參數(shù)。
文獻(xiàn)[16]給出了無(wú)向圖結(jié)構(gòu)下的標(biāo)稱編隊(duì)能夠?qū)崿F(xiàn)仿射定位的條件,那么根據(jù)無(wú)向圖結(jié)構(gòu)下的標(biāo)稱編隊(duì)仿射定位的條件可以推導(dǎo)出有向圖結(jié)構(gòu)下標(biāo)稱編隊(duì)(G,r)能夠?qū)崿F(xiàn)仿射定位的條件如下。
1) 系統(tǒng)中跟隨者的位置集合pf總是能夠被領(lǐng)航者的位置pl確定。
2) 對(duì)于有向圖G的符號(hào)拉普拉斯矩陣LΩ及機(jī)器人位置集合p,滿足
(LΩ?Id)p=0
(14)
其中,
式中,kij表示連接節(jié)點(diǎn)i與節(jié)點(diǎn)j的邊的權(quán)重。
(15)
標(biāo)稱編隊(duì)隊(duì)形及其拓?fù)浣Y(jié)構(gòu)如圖6所示,圖6中標(biāo)號(hào)1,2,3的圓形表示領(lǐng)航者機(jī)器人,標(biāo)號(hào)4,5,6,7的圓形表示跟隨機(jī)器人。
圖6 標(biāo)稱編隊(duì)隊(duì)形
基于以上多機(jī)器人能夠?qū)崿F(xiàn)仿射定位的條件,設(shè)計(jì)一階多機(jī)器人系統(tǒng)的運(yùn)動(dòng)控制協(xié)議,一階多機(jī)器人系統(tǒng)中第i個(gè)機(jī)器人的動(dòng)力學(xué)方程為
(16)
式中,ui(t)表示第i個(gè)機(jī)器人的控制輸入。
設(shè)編隊(duì)中領(lǐng)航者的速度為有界的時(shí)變值,設(shè)計(jì)編隊(duì)中跟隨機(jī)器人i的運(yùn)動(dòng)控制協(xié)議為
(17)
(18)
由此,根據(jù)文獻(xiàn)[18]給出的一致性判定條件,式(17)所示的控制協(xié)議能使得系統(tǒng)中跟隨機(jī)器人的位置跟隨誤差全局收斂于領(lǐng)航者。
設(shè)計(jì)二階系統(tǒng)的運(yùn)動(dòng)控制協(xié)議,系統(tǒng)中機(jī)器人的二階動(dòng)力學(xué)方程為
(19)
式中,vi與ui分別表示系統(tǒng)中機(jī)器人的速度與控制輸入,i=1,2,…N。對(duì)于二階系統(tǒng),控制輸入為加速度。受文獻(xiàn)[18]中關(guān)于二階多機(jī)器人系統(tǒng)運(yùn)動(dòng)控制協(xié)議設(shè)計(jì)思路的啟發(fā),設(shè)編隊(duì)中領(lǐng)航者的加速度為有界的時(shí)變值,則設(shè)計(jì)編隊(duì)中第i個(gè)跟隨機(jī)器人的運(yùn)動(dòng)控制協(xié)議為
(20)
根據(jù)文獻(xiàn)[18]給出的一致性判定條件,式(20)所示的控制協(xié)議能使得系統(tǒng)中跟隨機(jī)器人相對(duì)于領(lǐng)航者的跟隨誤差全局收斂。
首先利用A*算法規(guī)劃出全局路徑,基于IPOPT對(duì)獲得的路徑進(jìn)行優(yōu)化。由大小為22×22的柵格單元組成的封閉地圖,地圖中的障礙物隨機(jī)生成。第一次仿真的起始點(diǎn)坐標(biāo)設(shè)置為(3,18),目標(biāo)點(diǎn)坐標(biāo)(18,2),結(jié)果如圖7所示。第二次仿真的起始點(diǎn)坐標(biāo)設(shè)置為(3,18),目標(biāo)點(diǎn)坐標(biāo)設(shè)為(19,7),結(jié)果如圖8所示。圖中黑色柵格代表障礙物,連續(xù)曲線代表規(guī)劃的路徑。圖7(a)與圖8(a)分別表示第一次和第二次仿真的原始路徑,圖7(b)與圖8(b)分別表示第一次和第二次仿真改進(jìn)后的路徑。
圖7 路徑優(yōu)化第一次仿真結(jié)果
圖8 路徑優(yōu)化第二次仿真結(jié)果
相比于圖7(a)和圖8(a)原始算法的路徑,圖7(b)和圖8(b)中改進(jìn)后的路徑在靠近障礙物的區(qū)域沒(méi)有出現(xiàn)角轉(zhuǎn)彎,軌跡連續(xù)性比較好,且貼近原始路徑??梢钥闯?基于IPOPT的軌跡平滑方案能夠有效平滑A*算法規(guī)劃路徑中的轉(zhuǎn)折區(qū)域。
創(chuàng)建二維平面中大小為55 m×55 m的封閉有障礙地圖,確定圖6編隊(duì)中前3個(gè)機(jī)器人作為領(lǐng)航者,領(lǐng)航者的初始位置為
跟隨者的初始位置為
領(lǐng)航者的目標(biāo)位置為
編隊(duì)整體的路徑規(guī)劃步驟如下。
步驟1獲取當(dāng)前環(huán)境地圖信息。
步驟2確定編隊(duì)期望隊(duì)形,根據(jù)期望隊(duì)形確定3個(gè)領(lǐng)航者之間的相對(duì)位置關(guān)系。
步驟3由編隊(duì)中第一個(gè)領(lǐng)航者利用 A*算法在當(dāng)前環(huán)境中規(guī)劃出平滑的全局路徑,并基于IPOPT優(yōu)化當(dāng)前路徑,將該路徑發(fā)布給其余領(lǐng)航者。
步驟4編隊(duì)中其余領(lǐng)航者根據(jù)與第一個(gè)領(lǐng)航者的相對(duì)位置關(guān)系以及環(huán)境中的障礙物分布信息,對(duì)步驟3中得到的路徑進(jìn)行坐標(biāo)偏移,分別得到其他領(lǐng)航者的路徑。
步驟5判斷偏移后的路徑軌跡是否與障礙物發(fā)生碰撞,規(guī)劃編隊(duì)的避障策略。
當(dāng)編隊(duì)中的領(lǐng)航者獲得全局路徑后,根據(jù)編隊(duì)隊(duì)形幾何結(jié)構(gòu),規(guī)劃領(lǐng)航者在當(dāng)前路徑下的速度與加速度等控制變量,進(jìn)而進(jìn)行運(yùn)動(dòng)規(guī)劃。編隊(duì)在當(dāng)前環(huán)境下的運(yùn)動(dòng)軌跡如圖9所示,圖中紅色圓形為編隊(duì)的領(lǐng)航者,藍(lán)色圓形為編隊(duì)中的跟隨者,綠色虛線為第一個(gè)領(lǐng)航者的路徑,黑色區(qū)域?yàn)檎系K物分布。
圖9 編隊(duì)運(yùn)動(dòng)軌跡
編隊(duì)中各機(jī)器人在X軸與Y軸上位移、速度和加速度曲線分別如圖10與圖11所示,可以看出,系統(tǒng)中的領(lǐng)航者和跟隨者機(jī)器人在X軸與Y軸上位移、速度和加速度等均平緩變化,未出現(xiàn)突變現(xiàn)象。
圖10 X軸上位移、速度及加速度與時(shí)間的關(guān)系
圖11 Y軸上位移、速度及加速度與時(shí)間的關(guān)系
研究了多機(jī)器人編隊(duì)的路徑規(guī)劃以及運(yùn)動(dòng)控制問(wèn)題?;贗POPT的路徑優(yōu)化方法改善了A*算法規(guī)劃的路徑轉(zhuǎn)彎不平滑的問(wèn)題。對(duì)于多機(jī)器人的編隊(duì)控制問(wèn)題,給出了基于有向圖結(jié)構(gòu)的領(lǐng)航-跟隨型仿射編隊(duì)控制方法,并設(shè)計(jì)了一階和二階系統(tǒng)的運(yùn)動(dòng)控制協(xié)議。實(shí)驗(yàn)結(jié)果表明,基于IPOPT的路徑優(yōu)化方法能夠有效平滑A*算法規(guī)劃的路徑,且編隊(duì)在沿著規(guī)劃的路徑運(yùn)動(dòng)時(shí)能夠保持編隊(duì)隊(duì)形。