四足機器人自由步態規劃建模與算法實現

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

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

?

四足機器人自由步態規劃建模與算法實現

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

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

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

四足機器人;自由步態;步態規劃;A*算法;越障步態

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

自由步態規劃的任務是在一定地形條件下規劃機器人的步態運動,包括機體的運動、腿的擺動順序和落足點等[2],使機器人安全穩定地通過給定的地形。McGhee等針對含有不適合支撐區域(稱為“禁區”)的平坦地形,設計了一種自由步態的規劃方法,該方法可能會使機器人陷入“死鎖”狀態,即由于運動學約束、穩定性約束或地形條件的限制等,機器人無法繼續前進的狀態[3]。Pal等針對“死鎖”的問題,引入圖搜索方法[4],規劃了跨越禁區的優化自由步態,但是其簡化的模型不符合實際。斯坦福大學的“運動學習”項目對LittleDog機器人在崎嶇地形上行走的運動規劃與控制進行了研究[5-8],其中Kolter等采用分層規劃的方法[7],首先規劃通過崎嶇地形的全局最小代價路徑,然后在路徑周圍搜索局部代價最小的落足點,這種方法降低了搜索空間的維度,提高了運動控制的實時性,但是其步態為局部最優。Kalakrishnan等采用了類似的分級規劃方法[8]。首先在預處理階段,機器人使用排序函數計算了地形上候選落足點的“獎勵”,得到地形獎勵圖,然后依據地形獎勵圖,采用Dijkstra算法規劃出大概的機體路徑,最后采用貪心搜索算法和ARA*(anytime repairing A*)算法在機體路徑周圍搜索出下幾步的落足點。

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

1 四足機器人步態規劃模型

四足機器人步態可以看作是腿與機體相對位置的變化過程,本文定義一組腿和機體的位置組合為機器人的一個構型,那么四足機器人的步態可以離散為一個構型序列。采用搜索算法進行四足機器人自由步態規劃的核心思想是:用節點描述機器人的構型,依據一定的構型轉換規則,構造以初始構型為根節點的搜索圖,然后采用搜索算法搜索出到達目標節點的路徑,這條路徑即為四足機器人的一個構型轉換序列,即離散的運動序列,最后規劃機體和關節的運動軌跡來實現離散序列的連續運動,在低層實現軌跡的跟蹤控制。采用搜索策略的步態規劃與控制的總體結構如圖1所示。

圖1 基于搜索的四足機器人分層步態規劃與控制結構

1.1 四足機器人及地形模型

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

圖2 四足機器人三維模型

圖3 四足機器人簡化模型

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

1.2 四足機器人構型描述

四足機器人的構型是機器人運動狀態的描述,由于一組重心與足端位置可以完全確定機器人在世界坐標系中的位置,因此本文機器人構型由機體重心位置和4個足端的位置組成,可以用數組S(rc,f1,f2,f3,f4)描述,如圖3所示,其中rc為機體重心在世界坐標系xoy中的位置,f1～f4為足端在機體坐標系xcy中的位置。

1.3 四足機器人構型轉換

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

1.4 構型轉換規則

構型轉換規則是依據實際的四足機器人的步態運動規律設計的簡化模型的構型之間的轉換規則,其物理意義是四足機器人在運動中機體重心和4條腿的相對位置變化的規律。

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

表1 腿的狀態轉換表

1.4.2 可行構型轉換 機器人的構型轉換的實質是腿和機體的相對位置發生變化的過程。對于四足機器人的自由步態,每個時刻至少有3條腿著地,其運動形式有4條腿保持足的位置不變并同時推動機體向前移動,機體及3條腿不動,另一條腿向前擺動,對應的構型轉換如下:①4條腿同時進行動態轉換,即4條腿一起推進機體向前移動,例如S(1,1,1,2,2)→S(2,2,2,3,3);②3條腿進行靜態轉換,另一條腿進行擺動轉換,即3條腿及機體重心保持不動,另一條腿向前擺動,例如S(2,2,2,2,0)→S(2,0,2,2,0)。

2 步態規劃搜索算法實現

2.1 搜索算法

在搜索圖中,用節點代表機器人構型S,用邊代表構型轉換。搜索算法以四足機器人的初始構型S0為根節點,依據構型轉換規則拓展子節點來構建搜索圖。為了保證步態的穩定性以及實現對障礙物的跨越,對每一步拓展的子節點要進行穩定性檢測和障礙碰撞檢測,刪除不滿足穩定裕度的子節點以及與障礙物發生碰撞(落足點占據u=0的柵格點)的子節點,并把剩余節點放入后繼節點表中,然后定義路徑的代價以及評價函數f(n),優先拓展評價值最小的節點進行下一步搜索,如此循環直到到達設定的目標節點,這樣規劃得到的路徑即為滿足運動約束并且跨越障礙的最優運動序列。

2.2 評價函數的構建

圖4 當前構型與目標構型的距離

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

Dlp=Dg+xgj-xci

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

(1)

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

r1=r2=r3=r4

(2)

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

不妨取q=0.5;∑ri=0.5

ri=0.125

(3)

最終構建的評價函數為

f(n)=d+kDe

(4)

3 仿真實驗及結果分析

為了驗證模型和算法的有效性,本文在計算機上進行了仿真,仿真環境為Visual C++,主機CPU頻率為1.8 GHz,運行內存為6.0 GB。

3.1 k值的選取

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

(a)k-t關系

(b)k-步數關系

(c)k-節點數關系圖5 k值與規劃算法參數值的關系

3.2 跨越障礙自由步態仿真及分析

為了驗證所規劃自由步態的越障能力,設置目標點為前進方向9個柵格的距離;在機器人前后腿前進路線上隨機設置了9個障礙,取n=3,仿真結果如圖6a所示。算法拓展節點數目為78,所用步數為20,搜索算法執行時間為0.019 s;為了與無障礙的規劃結果進行對比分析,以相同的起點和目標點進行了仿真,算法拓展節點數目為191,所用步數為20,搜索算法執行時間為0.046 s,仿真結果如圖6b所示。可以看出,規劃算法得到了可行結果,規劃時間很短,這體現了規劃模型的有效性及評價函數的優越性。

由圖6a可見,由于障礙物的存在,其運動序列與圖6b發生了明顯的變化。序列在第3步開始不同,機器人由邁l4改為邁l3。在第5步中,由于穩定性約束不能選擇邁l3,在經過第6步機體重心向前調整后,l3滿足了穩定性約束,然后選擇了障礙物間的候選落足點。同理,在經過第9和10步的動態轉換后,l4在第11步跨越了障礙物。第12步中l1向前邁步使得機器人在第13步實現了動態轉換,從而使得l3和l2分別在第14和15步跨越了障礙。由此可以看出,搜索算法得到的步態序列調整了步序和落足點位置,從而使機器人順利地跨越了障礙而沒有陷入死鎖狀態。

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

(b)無障礙地形自由步態■:障礙物圖6 自由步態規劃仿真結果

3.3 候選落足點數對機器人越障能力的影響分析

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

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

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

(b)候選落足點為0～6(n=6)的仿真結果●:落足點;?:障礙物圖7 不同候選落足點數的步態仿真結果

3.4 三維模型仿真驗證

為了進一步驗證結果的可行性,本文建立了自由步態規劃與控制系統,在ADAMS-Simulink聯合平臺中進行了仿真,仿真截圖如圖8所示,截圖1～20分別與圖6b中的步態序列1～20相對應,從而驗證了規劃步態的可行性。

圖8 越障自由步態ADAMS與Simulink聯合仿真

4 結 論

本文闡述了一種基于圖搜索的四足機器人步態規劃方法,建立了一種改進的離散化四足機器人步態規劃模型,設計了基于A*算法的步態規劃算法,實現了跨越障礙的直線自由步態規劃,通過仿真驗證了規劃模型和算法的有效性及優越性并分析得出通過增加候選落足點個數可以提高機器人對地形的適應能力。需要說明的是,當障礙物的尺寸超過了機器人的最大跨距或障礙物分布過于密集時,會造成算法無解。這是因為障礙物已超過機器人越障能力范圍,本文算法在有解的情況下均能快速規劃出最優越障自由步態。

[1]陳學東, 孫翊, 賈文川.多足步行機器人運動規劃與控制 [M].武漢: 華中科技大學出版社, 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].機器人, 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].機床與液壓, 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].北京: 清華大學出版社, 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。 作者簡介:劉冠初(1989—),男,碩士生;熊靜琪(通信作者),女,教授。 基金項目:國家高技術研究發展計劃資助項目(2011AA040701)。

時間: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