四足機(jī)器人自由步態(tài)規(guī)劃建模與算法實(shí)現(xiàn)

劉冠初,熊靜琪,喬林,杜麗

(電子科技大學(xué)機(jī)械電子工程學(xué)院,611731,成都)

?

四足機(jī)器人自由步態(tài)規(guī)劃建模與算法實(shí)現(xiàn)

劉冠初,熊靜琪,喬林,杜麗

(電子科技大學(xué)機(jī)械電子工程學(xué)院,611731,成都)

針對(duì)四足機(jī)器人的越障自由步態(tài)規(guī)劃問(wèn)題,提出了一種改進(jìn)的離散化四足機(jī)器人步態(tài)規(guī)劃模型,該模型可通過(guò)設(shè)置相關(guān)參數(shù)準(zhǔn)確模擬實(shí)際物理模型,并且可以根據(jù)障礙物的分布密集程度改變候選落足點(diǎn)數(shù)以提高機(jī)器人對(duì)地形的適應(yīng)能力;根據(jù)此模型建立了基于A*算法的步態(tài)規(guī)劃算法,對(duì)步態(tài)序列進(jìn)行穩(wěn)定性檢測(cè)和碰撞檢測(cè),并設(shè)計(jì)了以步數(shù)最少為目標(biāo)的評(píng)價(jià)函數(shù),以使規(guī)劃的步態(tài)穩(wěn)定、與障礙無(wú)碰撞且總步數(shù)最少。實(shí)驗(yàn)結(jié)果表明:該算法計(jì)算量小、規(guī)劃時(shí)間短,規(guī)劃一個(gè)20步的越障步態(tài)僅拓展了78個(gè)節(jié)點(diǎn),用時(shí)0.019 s;機(jī)器人以最少的步數(shù)安全地通過(guò)了給定的含障礙物的地形,從而驗(yàn)證了所提模型的有效性及算法的優(yōu)越性,ADAMS和Simulink聯(lián)合仿真進(jìn)一步驗(yàn)證了所規(guī)劃的自由步態(tài)是可行的。

四足機(jī)器人;自由步態(tài);步態(tài)規(guī)劃;A*算法;越障步態(tài)

四足機(jī)器人的步態(tài)規(guī)劃問(wèn)題在近幾十年已被廣泛研究。這些研究多集中在具有周期運(yùn)動(dòng)規(guī)律的規(guī)則步態(tài)上,例如爬行步態(tài)、對(duì)角小跑步態(tài)等。規(guī)則步態(tài)難以適應(yīng)不規(guī)則的地形[1],例如凹凸不平的地形、有障礙物的地形以及崎嶇地形等,因此研究非周期的自由步態(tài)的規(guī)劃方法對(duì)于提高四足機(jī)器人在各種復(fù)雜地形上的行走能力具有重要意義。

自由步態(tài)規(guī)劃的任務(wù)是在一定地形條件下規(guī)劃?rùn)C(jī)器人的步態(tài)運(yùn)動(dòng),包括機(jī)體的運(yùn)動(dòng)、腿的擺動(dòng)順序和落足點(diǎn)等[2],使機(jī)器人安全穩(wěn)定地通過(guò)給定的地形。McGhee等針對(duì)含有不適合支撐區(qū)域(稱為“禁區(qū)”)的平坦地形,設(shè)計(jì)了一種自由步態(tài)的規(guī)劃方法,該方法可能會(huì)使機(jī)器人陷入“死鎖”狀態(tài),即由于運(yùn)動(dòng)學(xué)約束、穩(wěn)定性約束或地形條件的限制等,機(jī)器人無(wú)法繼續(xù)前進(jìn)的狀態(tài)[3]。Pal等針對(duì)“死鎖”的問(wèn)題,引入圖搜索方法[4],規(guī)劃了跨越禁區(qū)的優(yōu)化自由步態(tài),但是其簡(jiǎn)化的模型不符合實(shí)際。斯坦福大學(xué)的“運(yùn)動(dòng)學(xué)習(xí)”項(xiàng)目對(duì)LittleDog機(jī)器人在崎嶇地形上行走的運(yùn)動(dòng)規(guī)劃與控制進(jìn)行了研究[5-8],其中Kolter等采用分層規(guī)劃的方法[7],首先規(guī)劃通過(guò)崎嶇地形的全局最小代價(jià)路徑,然后在路徑周?chē)阉骶植看鷥r(jià)最小的落足點(diǎn),這種方法降低了搜索空間的維度,提高了運(yùn)動(dòng)控制的實(shí)時(shí)性,但是其步態(tài)為局部最優(yōu)。Kalakrishnan等采用了類(lèi)似的分級(jí)規(guī)劃方法[8]。首先在預(yù)處理階段,機(jī)器人使用排序函數(shù)計(jì)算了地形上候選落足點(diǎn)的“獎(jiǎng)勵(lì)”,得到地形獎(jiǎng)勵(lì)圖,然后依據(jù)地形獎(jiǎng)勵(lì)圖,采用Dijkstra算法規(guī)劃出大概的機(jī)體路徑,最后采用貪心搜索算法和ARA*(anytime repairing A*)算法在機(jī)體路徑周?chē)阉鞒鱿聨撞降穆渥泓c(diǎn)。

雖然在國(guó)內(nèi)已有研究將圖搜索算法應(yīng)用于雙足機(jī)器人的足跡規(guī)劃[9],但是還未見(jiàn)相關(guān)研究將其應(yīng)用于四足機(jī)器人的自由步態(tài)規(guī)劃中,因此本文針對(duì)分布有障礙物的平坦地形,基于Pal等建立的模型[4]提出了一種改進(jìn)的離散化四足機(jī)器人步態(tài)規(guī)劃模型,建立了基于A*算法的自由步態(tài)規(guī)劃算法,規(guī)劃了通過(guò)給定地形環(huán)境的四足機(jī)器人越障自由步態(tài),仿真結(jié)果驗(yàn)證了規(guī)劃步態(tài)的合理性及可行性。此外,本文還通過(guò)仿真實(shí)驗(yàn)分析了候選落足點(diǎn)數(shù)對(duì)機(jī)器人跨越障礙能力的影響。

1 四足機(jī)器人步態(tài)規(guī)劃模型

四足機(jī)器人步態(tài)可以看作是腿與機(jī)體相對(duì)位置的變化過(guò)程,本文定義一組腿和機(jī)體的位置組合為機(jī)器人的一個(gè)構(gòu)型,那么四足機(jī)器人的步態(tài)可以離散為一個(gè)構(gòu)型序列。采用搜索算法進(jìn)行四足機(jī)器人自由步態(tài)規(guī)劃的核心思想是:用節(jié)點(diǎn)描述機(jī)器人的構(gòu)型,依據(jù)一定的構(gòu)型轉(zhuǎn)換規(guī)則,構(gòu)造以初始構(gòu)型為根節(jié)點(diǎn)的搜索圖,然后采用搜索算法搜索出到達(dá)目標(biāo)節(jié)點(diǎn)的路徑,這條路徑即為四足機(jī)器人的一個(gè)構(gòu)型轉(zhuǎn)換序列,即離散的運(yùn)動(dòng)序列,最后規(guī)劃?rùn)C(jī)體和關(guān)節(jié)的運(yùn)動(dòng)軌跡來(lái)實(shí)現(xiàn)離散序列的連續(xù)運(yùn)動(dòng),在低層實(shí)現(xiàn)軌跡的跟蹤控制。采用搜索策略的步態(tài)規(guī)劃與控制的總體結(jié)構(gòu)如圖1所示。

圖1 基于搜索的四足機(jī)器人分層步態(tài)規(guī)劃與控制結(jié)構(gòu)

1.1 四足機(jī)器人及地形模型

四足機(jī)器人三維模型如圖2所示,其平面簡(jiǎn)化模型如圖3所示,其中xoy為世界坐標(biāo)系,xcy為機(jī)器人質(zhì)心坐標(biāo)系,l1～l4分別代表機(jī)器人4條腿,x軸正向?yàn)闄C(jī)器人的行走方向。設(shè)λ為腿在x方向的最大工作空間,點(diǎn)0～n為離散的候選落足點(diǎn),dx為同側(cè)足端候選落足點(diǎn)的最小間距,dy為足端在y方向的間距。與Pal的模型相比,本文模型可以通過(guò)設(shè)置參數(shù)λ、dx、dy與實(shí)際模型保持一致,并且可以通過(guò)設(shè)置n值改變候選落足點(diǎn)數(shù),從而使得機(jī)器人能夠根據(jù)障礙物的分布情況改變候選落足點(diǎn)數(shù),提高算法的適應(yīng)性。

圖2 四足機(jī)器人三維模型

圖3 四足機(jī)器人簡(jiǎn)化模型

針對(duì)含有障礙物的平坦地形,本文用柵格化地圖模型來(lái)表示,每個(gè)柵格點(diǎn)定義為G=(x,y,u)T,其中x和y分別為柵格點(diǎn)在世界坐標(biāo)系xoy中的位置,u=1表示柵格點(diǎn)沒(méi)有障礙物,機(jī)器人可落足;u=0表示有障礙物,機(jī)器人不可落足,假設(shè)所有障礙是可跨越的。地面障礙物的大小和位置信息由機(jī)器人的視覺(jué)系統(tǒng)檢測(cè)和識(shí)別,然后自動(dòng)劃分地圖柵格,獲取柵格中障礙物的分布位置,此內(nèi)容不是本文研究的重點(diǎn),因此假設(shè)地圖和障礙物信息為已知。需要說(shuō)明的是,按照本文的建模方法,需以柵格尺寸為單位對(duì)機(jī)器人的最大越障空間進(jìn)行歸一化處理,即設(shè)定機(jī)器人單腿最大跨距為地圖柵格尺寸的整數(shù)倍,這可以通過(guò)適當(dāng)舍棄機(jī)器人的單腿越障空間來(lái)實(shí)現(xiàn)。

1.2 四足機(jī)器人構(gòu)型描述

四足機(jī)器人的構(gòu)型是機(jī)器人運(yùn)動(dòng)狀態(tài)的描述,由于一組重心與足端位置可以完全確定機(jī)器人在世界坐標(biāo)系中的位置,因此本文機(jī)器人構(gòu)型由機(jī)體重心位置和4個(gè)足端的位置組成,可以用數(shù)組S(rc,f1,f2,f3,f4)描述,如圖3所示,其中rc為機(jī)體重心在世界坐標(biāo)系xoy中的位置,f1～f4為足端在機(jī)體坐標(biāo)系xcy中的位置。

1.3 四足機(jī)器人構(gòu)型轉(zhuǎn)換

根據(jù)四足機(jī)器人步態(tài)運(yùn)動(dòng)特點(diǎn),構(gòu)型之間的轉(zhuǎn)換須滿足步態(tài)穩(wěn)定性約束和運(yùn)動(dòng)學(xué)約束。①穩(wěn)定性約束。四足機(jī)器人步態(tài)穩(wěn)定的必要條件是其機(jī)體重心在支撐平面的投影必須落在由支撐足構(gòu)成的支撐多邊形內(nèi)。本文不考慮機(jī)器人的橫向移動(dòng),故只需考慮機(jī)器人在前進(jìn)方向的穩(wěn)定性約束,因此本文以縱向穩(wěn)定裕度sm[10]作為衡量穩(wěn)定性的標(biāo)準(zhǔn),其定義是機(jī)體重心在支撐平面的投影在其前進(jìn)方向上與支撐多邊形的最短直線距離,在進(jìn)行構(gòu)型時(shí)轉(zhuǎn)換應(yīng)滿足sm≥ξ,其中ξ為期望的最小縱向穩(wěn)定裕度值。②運(yùn)動(dòng)學(xué)約束。各條腿的運(yùn)動(dòng)必須限制在其工作空間內(nèi)。將足端的工作空間λ均勻地離散為n+1個(gè)候選落足點(diǎn),如圖3所示,設(shè)候選落足點(diǎn)集為F,則F={xi}(i=0,1,…,n)。例如l2所處位置x1的前向可選落足點(diǎn)為x0,后向可選落足點(diǎn)為x2～xn。

1.4 構(gòu)型轉(zhuǎn)換規(guī)則

構(gòu)型轉(zhuǎn)換規(guī)則是依據(jù)實(shí)際的四足機(jī)器人的步態(tài)運(yùn)動(dòng)規(guī)律設(shè)計(jì)的簡(jiǎn)化模型的構(gòu)型之間的轉(zhuǎn)換規(guī)則,其物理意義是四足機(jī)器人在運(yùn)動(dòng)中機(jī)體重心和4條腿的相對(duì)位置變化的規(guī)律。

1.4.1 腿的狀態(tài)轉(zhuǎn)換規(guī)則 用i(i=0,1,…,n)代表腿在xi點(diǎn)的狀態(tài),這里不允許腿有相對(duì)地面向后的擺動(dòng),設(shè)計(jì)腿的可行的始狀態(tài)到末狀態(tài)轉(zhuǎn)換如表1所示。①靜態(tài)轉(zhuǎn)換(s):腿的狀態(tài)不變,即腿沒(méi)有相對(duì)于機(jī)體和地面的移動(dòng);②動(dòng)態(tài)轉(zhuǎn)換(d):腿的狀態(tài)值增加(如0→1,1→2),此時(shí)機(jī)器人通過(guò)腿的伸展和收縮來(lái)推動(dòng)機(jī)體重心向前移動(dòng)一個(gè)柵格單元;③擺動(dòng)轉(zhuǎn)換(w):腿的狀態(tài)值減小(如1→0,3→1),此時(shí)腿進(jìn)行擺動(dòng),發(fā)生相對(duì)于地面的前移;④腿向后擺動(dòng)是不允許的,即表中的空位置。

表1 腿的狀態(tài)轉(zhuǎn)換表

1.4.2 可行構(gòu)型轉(zhuǎn)換 機(jī)器人的構(gòu)型轉(zhuǎn)換的實(shí)質(zhì)是腿和機(jī)體的相對(duì)位置發(fā)生變化的過(guò)程。對(duì)于四足機(jī)器人的自由步態(tài),每個(gè)時(shí)刻至少有3條腿著地,其運(yùn)動(dòng)形式有4條腿保持足的位置不變并同時(shí)推動(dòng)機(jī)體向前移動(dòng),機(jī)體及3條腿不動(dòng),另一條腿向前擺動(dòng),對(duì)應(yīng)的構(gòu)型轉(zhuǎn)換如下:①4條腿同時(shí)進(jìn)行動(dòng)態(tài)轉(zhuǎn)換,即4條腿一起推進(jìn)機(jī)體向前移動(dòng),例如S(1,1,1,2,2)→S(2,2,2,3,3);②3條腿進(jìn)行靜態(tài)轉(zhuǎn)換,另一條腿進(jìn)行擺動(dòng)轉(zhuǎn)換,即3條腿及機(jī)體重心保持不動(dòng),另一條腿向前擺動(dòng),例如S(2,2,2,2,0)→S(2,0,2,2,0)。

2 步態(tài)規(guī)劃搜索算法實(shí)現(xiàn)

2.1 搜索算法

在搜索圖中,用節(jié)點(diǎn)代表機(jī)器人構(gòu)型S,用邊代表構(gòu)型轉(zhuǎn)換。搜索算法以四足機(jī)器人的初始構(gòu)型S0為根節(jié)點(diǎn),依據(jù)構(gòu)型轉(zhuǎn)換規(guī)則拓展子節(jié)點(diǎn)來(lái)構(gòu)建搜索圖。為了保證步態(tài)的穩(wěn)定性以及實(shí)現(xiàn)對(duì)障礙物的跨越,對(duì)每一步拓展的子節(jié)點(diǎn)要進(jìn)行穩(wěn)定性檢測(cè)和障礙碰撞檢測(cè),刪除不滿足穩(wěn)定裕度的子節(jié)點(diǎn)以及與障礙物發(fā)生碰撞(落足點(diǎn)占據(jù)u=0的柵格點(diǎn))的子節(jié)點(diǎn),并把剩余節(jié)點(diǎn)放入后繼節(jié)點(diǎn)表中,然后定義路徑的代價(jià)以及評(píng)價(jià)函數(shù)f(n),優(yōu)先拓展評(píng)價(jià)值最小的節(jié)點(diǎn)進(jìn)行下一步搜索,如此循環(huán)直到到達(dá)設(shè)定的目標(biāo)節(jié)點(diǎn),這樣規(guī)劃得到的路徑即為滿足運(yùn)動(dòng)約束并且跨越障礙的最優(yōu)運(yùn)動(dòng)序列。

2.2 評(píng)價(jià)函數(shù)的構(gòu)建

圖4 當(dāng)前構(gòu)型與目標(biāo)構(gòu)型的距離

A*算法是一種啟發(fā)式搜索算法,其核心在于評(píng)價(jià)函數(shù)的設(shè)計(jì)。本文定義路徑的構(gòu)型轉(zhuǎn)換次數(shù)為路徑的代價(jià),路徑的構(gòu)型轉(zhuǎn)換次數(shù)越少,即規(guī)劃的步態(tài)從起點(diǎn)到達(dá)目標(biāo)所用的步數(shù)最少,則機(jī)器人能更快地到達(dá)目標(biāo)點(diǎn)。評(píng)價(jià)函數(shù)的一般形式為f(n)=g(n)+h(n),其中g(shù)(n)為從起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)路徑已消耗的代價(jià),h(n)為從當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最小路徑代價(jià)的估計(jì)值。設(shè)h*(n)為從當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的實(shí)際最小代價(jià),那么當(dāng)h(n)≤h*(n)時(shí),A*算法具有可采納性,即當(dāng)問(wèn)題有解時(shí)一定能夠找到一條從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最小代價(jià)路徑[11]。此處定義當(dāng)前節(jié)點(diǎn)已消耗的代價(jià)為從起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)經(jīng)過(guò)的構(gòu)型轉(zhuǎn)換次數(shù),其值為當(dāng)前節(jié)點(diǎn)在搜索圖中的深度d,即g(n)=d。h(n)是對(duì)機(jī)器人從當(dāng)前構(gòu)型到達(dá)目標(biāo)構(gòu)型需要的構(gòu)型轉(zhuǎn)換次數(shù)的估計(jì),設(shè)h(n)=kDe,其中De為機(jī)器人從當(dāng)前節(jié)點(diǎn)構(gòu)型Sc到目標(biāo)節(jié)點(diǎn)構(gòu)型Sg還需要移動(dòng)的距離的評(píng)價(jià)值,k為移動(dòng)單位距離需要的構(gòu)型轉(zhuǎn)換次數(shù)的估計(jì)值,機(jī)器人到達(dá)目標(biāo)構(gòu)型需要機(jī)體重心以及4條腿同時(shí)到達(dá)目標(biāo)構(gòu)型,因此需要分別計(jì)算重心和腿到達(dá)目標(biāo)構(gòu)型需要移動(dòng)的距離,分別記為Dg和Dlp(p=1,2,3,4),如圖4所示。設(shè)起點(diǎn)到目標(biāo)點(diǎn)的重心的距離為D,從當(dāng)前點(diǎn)到目標(biāo)點(diǎn)重心需要移動(dòng)的距離為Dg,已知當(dāng)前點(diǎn)重心移動(dòng)了距離Dc,則Dg=D-Dc。設(shè)足端在任意構(gòu)型中處于狀態(tài)i時(shí)x方向與重心的距離為xni,則根據(jù)圖4有

Dlp=Dg+xgj-xci

i,j=0,…,n;p=1,2,3,4

(1)

設(shè)De=qDg+r1Dl1+r2Dl2+r3Dl3+r4Dl4,其中q和r1～r4分別為重心及4條腿在與目標(biāo)距離的評(píng)價(jià)中的權(quán)重系數(shù)。由于在四足機(jī)器人的步態(tài)中,移動(dòng)重心相對(duì)于擺動(dòng)腿會(huì)使機(jī)器人更加靠近目標(biāo),從而使步態(tài)的構(gòu)型轉(zhuǎn)換次數(shù)更少,即代價(jià)更小,因此在評(píng)價(jià)函數(shù)中要鼓勵(lì)重心的移動(dòng),即在對(duì)某個(gè)節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的距離評(píng)價(jià)中,須保證在單腿和重心移動(dòng)相同的距離(Dlp與Dg減少相同值)的情況下,移動(dòng)了重心的節(jié)點(diǎn)具有更小的代價(jià),從而保證該節(jié)點(diǎn)在OPEN表中優(yōu)先選取并拓展,那么須有Dg的權(quán)重系數(shù)大于Dlp的權(quán)重系數(shù),即q>ri(i=1,2,3,4)。其物理意義是,在滿足步態(tài)運(yùn)動(dòng)約束的情況下,機(jī)器人優(yōu)先移動(dòng)重心可以更快地到達(dá)目標(biāo)點(diǎn)。由于四足機(jī)器人結(jié)構(gòu)的對(duì)稱性,腿移動(dòng)相同距離的不同節(jié)點(diǎn)可以具有相等的代價(jià),因此有

r1=r2=r3=r4

(2)

又q+∑ri=1i=1,2,3,4

不妨取q=0.5;∑ri=0.5

ri=0.125

(3)

最終構(gòu)建的評(píng)價(jià)函數(shù)為

f(n)=d+kDe

(4)

3 仿真實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證模型和算法的有效性,本文在計(jì)算機(jī)上進(jìn)行了仿真,仿真環(huán)境為Visual C++,主機(jī)CPU頻率為1.8 GHz,運(yùn)行內(nèi)存為6.0 GB。

3.1 k值的選取

本文采用實(shí)驗(yàn)法選取k值。由2.2節(jié)所述,k為移動(dòng)單位距離需要的構(gòu)型轉(zhuǎn)換次數(shù)的估計(jì)值,其值越接近實(shí)際最小值,則算法效率越高[11]。首先給k限定一個(gè)合理的范圍,對(duì)于本文的四足機(jī)器人模型,移動(dòng)1次重心平均至少需要2次構(gòu)型轉(zhuǎn)換,而最多需要5次構(gòu)型轉(zhuǎn)換(重心移動(dòng)1次,4條腿分別移動(dòng)1次),因此取k∈[2,5]。在此范圍內(nèi),對(duì)機(jī)器人在無(wú)障礙的地形上移動(dòng)一定距離的規(guī)劃算法進(jìn)行了仿真,算法搜索時(shí)間、規(guī)劃步態(tài)步數(shù)及總的拓展節(jié)點(diǎn)數(shù)與k的關(guān)系曲線如圖5所示。由圖可以看出,隨著k值的增大,算法拓展的總節(jié)點(diǎn)數(shù)減少,搜索時(shí)間減少,所規(guī)劃的步態(tài)的總步數(shù)增加。這是由于在A*算法中,當(dāng)估計(jì)值h(n)越接近h*(n)時(shí),越能更快地找到最優(yōu)解,而增強(qiáng)評(píng)價(jià)函數(shù)的啟發(fā)性可以增加搜索速度,但不能保證解是最優(yōu)的。由圖5中k值與規(guī)劃算法參數(shù)值的關(guān)系曲線得出,本算法在無(wú)障礙地形上取k=2.5,保證了結(jié)果的優(yōu)化性,同時(shí)搜索時(shí)間較短。由于在有障礙的地形下一般需要更多的構(gòu)型轉(zhuǎn)換次數(shù),h(n)≤h*(n)仍然成立,因此在有障礙的情況下k=2.5仍然滿足可采納性條件。

(a)k-t關(guān)系

(b)k-步數(shù)關(guān)系

(c)k-節(jié)點(diǎn)數(shù)關(guān)系圖5 k值與規(guī)劃算法參數(shù)值的關(guān)系

3.2 跨越障礙自由步態(tài)仿真及分析

為了驗(yàn)證所規(guī)劃自由步態(tài)的越障能力,設(shè)置目標(biāo)點(diǎn)為前進(jìn)方向9個(gè)柵格的距離;在機(jī)器人前后腿前進(jìn)路線上隨機(jī)設(shè)置了9個(gè)障礙,取n=3,仿真結(jié)果如圖6a所示。算法拓展節(jié)點(diǎn)數(shù)目為78,所用步數(shù)為20,搜索算法執(zhí)行時(shí)間為0.019 s;為了與無(wú)障礙的規(guī)劃結(jié)果進(jìn)行對(duì)比分析,以相同的起點(diǎn)和目標(biāo)點(diǎn)進(jìn)行了仿真,算法拓展節(jié)點(diǎn)數(shù)目為191,所用步數(shù)為20,搜索算法執(zhí)行時(shí)間為0.046 s,仿真結(jié)果如圖6b所示。可以看出,規(guī)劃算法得到了可行結(jié)果,規(guī)劃時(shí)間很短,這體現(xiàn)了規(guī)劃模型的有效性及評(píng)價(jià)函數(shù)的優(yōu)越性。

由圖6a可見(jiàn),由于障礙物的存在,其運(yùn)動(dòng)序列與圖6b發(fā)生了明顯的變化。序列在第3步開(kāi)始不同,機(jī)器人由邁l4改為邁l3。在第5步中,由于穩(wěn)定性約束不能選擇邁l3,在經(jīng)過(guò)第6步機(jī)體重心向前調(diào)整后,l3滿足了穩(wěn)定性約束,然后選擇了障礙物間的候選落足點(diǎn)。同理,在經(jīng)過(guò)第9和10步的動(dòng)態(tài)轉(zhuǎn)換后,l4在第11步跨越了障礙物。第12步中l(wèi)1向前邁步使得機(jī)器人在第13步實(shí)現(xiàn)了動(dòng)態(tài)轉(zhuǎn)換,從而使得l3和l2分別在第14和15步跨越了障礙。由此可以看出,搜索算法得到的步態(tài)序列調(diào)整了步序和落足點(diǎn)位置,從而使機(jī)器人順利地跨越了障礙而沒(méi)有陷入死鎖狀態(tài)。

(a)有障礙地形自由步態(tài)

(b)無(wú)障礙地形自由步態(tài)■:障礙物圖6 自由步態(tài)規(guī)劃仿真結(jié)果

3.3 候選落足點(diǎn)數(shù)對(duì)機(jī)器人越障能力的影響分析

候選落足點(diǎn)數(shù)對(duì)規(guī)劃算法有顯著影響,理論上更多的候選落足點(diǎn)數(shù)使機(jī)器人有更多的落足位置選擇,從而更容易通過(guò)復(fù)雜多障礙的地形,但是算法每一步拓展的子節(jié)點(diǎn)數(shù)增加,造成總的拓展節(jié)點(diǎn)數(shù)呈指數(shù)階增長(zhǎng),算法復(fù)雜度增加。圖7a中足端工作空間內(nèi)有候選落足點(diǎn)0～3,但連續(xù)障礙物恰好占據(jù)了足端的3個(gè)候選落足點(diǎn),仿真結(jié)果為未找到路徑;保持障礙物位置不變,在工作空間內(nèi)均勻離散為候選落足點(diǎn)0～6的仿真結(jié)果如圖7b所示;算法拓展節(jié)點(diǎn)總數(shù)為733,搜索時(shí)間為0.186 s,假設(shè)障礙物間距大于足的寬度。

圖7a中,由于候選落足點(diǎn)完全被障礙物占據(jù),且連續(xù)障礙物寬度大于機(jī)器人的最大跨距,機(jī)器人沒(méi)有可選落足位置,因此算法無(wú)解。圖7b中,更多的候選落足點(diǎn)使得機(jī)器人在障礙物間隙處有了落足位置,利用障礙物間的候選落足點(diǎn),機(jī)器人順利通過(guò)了障礙物密集的地形。因此,在腿的最大跨距不變的情況下,通過(guò)離散更多的候選落足點(diǎn)可以提高機(jī)器人通過(guò)障礙地形的能力,但代價(jià)是可能消耗更多的規(guī)劃時(shí)間。在實(shí)際應(yīng)用中,可以設(shè)計(jì)規(guī)劃算法根據(jù)障礙物的分布情況而自主改變候選落足點(diǎn)數(shù),在障礙物較密集的區(qū)域離散較多的候選落足點(diǎn),在障礙物稀疏的區(qū)域離散較少的候選落足點(diǎn),這樣可以在縮短規(guī)劃時(shí)間的同時(shí)提高機(jī)器人通過(guò)含有障礙的地形的能力。

(a)候選落足點(diǎn)為0～3(n=3)的仿真結(jié)果

(b)候選落足點(diǎn)為0～6(n=6)的仿真結(jié)果●:落足點(diǎn);?:障礙物圖7 不同候選落足點(diǎn)數(shù)的步態(tài)仿真結(jié)果

3.4 三維模型仿真驗(yàn)證

為了進(jìn)一步驗(yàn)證結(jié)果的可行性,本文建立了自由步態(tài)規(guī)劃與控制系統(tǒng),在ADAMS-Simulink聯(lián)合平臺(tái)中進(jìn)行了仿真,仿真截圖如圖8所示,截圖1～20分別與圖6b中的步態(tài)序列1～20相對(duì)應(yīng),從而驗(yàn)證了規(guī)劃步態(tài)的可行性。

圖8 越障自由步態(tài)ADAMS與Simulink聯(lián)合仿真

4 結(jié) 論

本文闡述了一種基于圖搜索的四足機(jī)器人步態(tài)規(guī)劃方法,建立了一種改進(jìn)的離散化四足機(jī)器人步態(tài)規(guī)劃模型,設(shè)計(jì)了基于A*算法的步態(tài)規(guī)劃算法,實(shí)現(xiàn)了跨越障礙的直線自由步態(tài)規(guī)劃,通過(guò)仿真驗(yàn)證了規(guī)劃模型和算法的有效性及優(yōu)越性并分析得出通過(guò)增加候選落足點(diǎn)個(gè)數(shù)可以提高機(jī)器人對(duì)地形的適應(yīng)能力。需要說(shuō)明的是,當(dāng)障礙物的尺寸超過(guò)了機(jī)器人的最大跨距或障礙物分布過(guò)于密集時(shí),會(huì)造成算法無(wú)解。這是因?yàn)檎系K物已超過(guò)機(jī)器人越障能力范圍,本文算法在有解的情況下均能快速規(guī)劃出最優(yōu)越障自由步態(tài)。

[1]陳學(xué)東, 孫翊, 賈文川.多足步行機(jī)器人運(yùn)動(dòng)規(guī)劃與控制 [M].武漢: 華中科技大學(xué)出版社, 2006: 114-115.

[2]ESTREMERA J, DE SANTOS P G.Generating continuous free crab gaits for quadruped robots on irregular terrain [J].IEEE Transactions on Robotics, 2005, 21(6): 1067-1076.

[3]MCGHEE R B, ISWANDHI G I.Adaptive locomo-tion of a multilegged robot over rough terrain [J].IEEE Transactions on Systems, Man and Cybernetics, 1979, 9(4): 176-182.

[4]PAL P K, JAYARAJAN K.Generation of free gait: a graph search approach [J].IEEE Transactions on Robotics and Automation, 1991, 7(3): 299-305.

[5]VERNAZA P, LIKHACHEV M, BHATTACHARYA S, et al.Search-based planning for a legged robot over rough terrain [C]∥Proceedings of the 2009 IEEE International Conference on Robotics and Automation.Piscataway, NJ, USA: IEEE, 2009: 2380-2387.

[6]REBULA J R, NEUHAUS P D, BONNL B V, et al.A controller for the littledog quadruped walking on rough terrain [C]∥ Proceedings of the 2007 IEEE International Conference on Robotics and Automation.Piscataway, NJ, USA: IEEE, 2007: 1467-1473.

[7]KOLTER J Z, RODGERS M P, NG A Y.A control architecture for quadruped locomotion over rough ter-rain [C]∥Proceedings of the IEEE International Conference on Robotics and Automation.Piscataway, NJ, USA: IEEE, 2008: 811-818.

[8]KALAKRISHNAN M, BUCHLI J, PASTOR P, et al.Learning, planning, and control for quadruped locomotion over challenging terrain [J].The International Journal of Robotics Research, 2011, 30(2): 236-258.

[9]夏澤洋, 陳懇.仿人機(jī)器人足跡規(guī)劃建模及算法實(shí)現(xiàn) [J].機(jī)器人, 2008, 30(3): 231-237.

XIA Zeyang, CHEN Ken.Modeling and algorithm realization of footstep planning for humanoid robots[J].Robot, 2008, 30(3): 231-237.

[10]夏旭峰, 葛文杰.仿生機(jī)器人運(yùn)動(dòng)穩(wěn)定性的研究進(jìn)展 [J].機(jī)床與液壓, 2007, 35(2): 229-234.

XIA Xufeng, GE Wenjie.Research development on motion stability of bionic robotics [J].Machine Tool and Hydraulics, 2007, 35(2): 229-234.

[11]馬少平, 朱小燕.人工智能 [M].北京: 清華大學(xué)出版社, 204: 32-38.

(編輯 武紅江)

Modelling and Algorithm Realization of Free Gait Regulation for Quadruped Robots

LIU Guanchu, XIONG Jingqi, QIAO Lin, DU Li

(School of Mechatronics Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China)

A modified discrete gait planning model for quadruped robots is proposed to solve the free gait planning problem for quadruped robots walking beyond barriers.The model accurately simulates the actual physical model through setting related parameters; and the number of candidate footholds can be changed to improve the robot’s adaptability according to the distribution density of obstacles.A gait planning algorithm based on the A*method is proposed.In this algorithm, the stability detection and collision detection are executed on every gait sequence, and an evaluation function aiming at minimum steps is designed to achieve collision-free and stable gait with minimum total steps.Experimental results show that the proposed algorithm is computationally efficient, and the planning time is short.When a twenty-step collision-free gait is planned, only 78 nodes are expanded and the planning time is 0.019 s.The robot safely traverses through the obstacles of a given terrain with a minimum steps.These results verify the validity of the proposed model and the superiority of the algorithm.Moreover, a joint simulation with ADAMS and Simulink verifies the feasibility of the planned free gait.

quadruped robot; free gait; gait planning; A*algorithm; collision-free gait

2014-08-09。 作者簡(jiǎn)介:劉冠初(1989—),男,碩士生;熊靜琪(通信作者),女,教授。 基金項(xiàng)目:國(guó)家高技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目(2011AA040701)。

時(shí)間:2015-04-29

http:∥www.cnki.net/kcms/detail/61.1069.T.20150429.1437.003.html

10.7652/xjtuxb201506014

TP24

A

0253-987X(2015)06-0084-06