陳光榮 王軍政 郭盛 侯博文

1.北京交通大學(xué)機器人研究中心北京100044 2.北京理工大學(xué)復(fù)雜系統(tǒng)智能控制與決策國家重點實驗室北京100081 3.北京市軌道交通線路安全與防災(zāi)工程技術(shù)研究中心北京100044

艾薩克·阿西莫夫在《我,機器人》[1]中訂立了“機器人三定律”,要求機器人具有決策、學(xué)習(xí)和優(yōu)化能力.顯然,人工智能對機器人尤為重要.機器學(xué)習(xí)作為人工智能的核心問題之一,被廣泛地應(yīng)用到生活中的各行各業(yè)[2?3].如,在RoboCup 比賽中,為了提高AIBO 機器人的運動速度和穩(wěn)定性,一些研究學(xué)者利用策略梯度法和遺傳算法等機器學(xué)習(xí)方法來優(yōu)化機器人的步長、步頻等步態(tài)參數(shù)[4?6].眾多研究學(xué)者基于Little Dog 提出了不同的機器學(xué)習(xí)算法進行機器人行走控制,實現(xiàn)了在復(fù)雜地形下的行走跳躍[7?8].為實現(xiàn)Little Dog 攀爬臺階任務(wù),Kolter J等利用微分符號策略梯度法來優(yōu)化機體后移的位移,以便完成攀爬動作[9].Kolter J、Kalakrishnan M 以及Zucker M 等都將分層強化學(xué)習(xí)作為機器人運動規(guī)劃算法的主要框架[10?12].Belter D 在六足機器人Messor 的運動規(guī)劃中對機器學(xué)習(xí)算法進行了大幅度優(yōu)化,實現(xiàn)了在線地形圖生成和路徑規(guī)劃[13?14].谷歌DeepMind 團隊曾開發(fā)出一款人工智能圍棋程序AlphaGo[15?16],打敗了圍棋世界冠軍.近年來,該團隊又用AI 教雙足和四足模型如何走路、模仿、跳躍、格斗,適應(yīng)各種地形環(huán)境等[17?19],逐漸開辟了一個足式機器人步態(tài)規(guī)劃與控制的新方向.

足式機器人運動控制研究[20?23]日趨成熟,人工智能機器學(xué)習(xí)在足式機器人方面的應(yīng)用還需要更深入的探索和研究[24].隨著機器人學(xué)的迅速發(fā)展,人工智能的作用越來越突出.人們對足式機器人的要求已經(jīng)不只是一些簡單的、重復(fù)性的機械動作,或者單純的行走跳躍,機器人應(yīng)當(dāng)能作出更好的、更優(yōu)化的動作,能夠自我學(xué)習(xí)以適應(yīng)地面環(huán)境和外界干擾,并根據(jù)所處環(huán)境找到最優(yōu)路徑作出動作決策等[25?26].

傳統(tǒng)的足式機器人步態(tài)規(guī)劃算法通常是規(guī)劃給定目標約束下,從起點到終點的路徑,對于機器人通過此路徑采用什么樣的步態(tài),并沒有給出明確的說明,且目標約束大多是最短時間或最短路徑,相對較為片面.

本文研究的問題就是在給定了4 個主要因素(即新增的目標約束):四足機器人所在地形的地形復(fù)雜度,所需的行進速度、所要求的行走能耗和應(yīng)當(dāng)保證的穩(wěn)定性水平下,機器人的自主步態(tài)選擇問題—是選擇靜步態(tài)好還是動步態(tài)好.針對此問題,采用C4.5 決策樹理論進行了研究,并得到了此條件下的靜動步態(tài)自主步態(tài)選擇決策規(guī)則.為了驗證算法有效性,結(jié)合A*路徑規(guī)劃算法,改進A*算法的總代價函數(shù),將行走路程、行走時間、行走地形起伏量(即地形復(fù)雜度)、行走穩(wěn)定性、行走速度、行走能耗等6 個目標加權(quán)融入其中,同時在后4 個目標中加入C4.5 算法決策靜動步態(tài)的影響,使路徑規(guī)劃相對更為合理,綜合因素更全面.

因此,為解決機器人在一定復(fù)雜度的地形下[27?28],根據(jù)設(shè)定的能耗[29?30]、速度[31]和穩(wěn)定性能自主的決策進行靜步態(tài)或動步態(tài)行走問題[32?33],提出一種基于C4.5 決策樹[34?35]的步態(tài)自主選擇算法.

1 四足機器人

1.1 四足機器人模型

利用Webots 搭建的仿真模型和對應(yīng)的坐標系統(tǒng)分別如圖1和圖2所示.機器人單腿3 個自由度:髖關(guān)節(jié)2 個自由度,膝關(guān)節(jié)1 個自由度,前后腿均為肘式配置,機器人的機械結(jié)構(gòu)參數(shù)如表1所示.

圖1 四足機器人仿真模型Fig.1 Simulation model of quadruped robot

表1 機器人系統(tǒng)參數(shù)Table 1 System parameters of quadruped robot

圖2 四足機器人坐標系統(tǒng)Fig.2 Coordinate system of quadruped robot

1.2 四足機器人步態(tài)類型

從仿生學(xué)角度看,四足動物的步態(tài)可分為靜步態(tài)和動步態(tài).靜步態(tài)指具有靜態(tài)穩(wěn)定性的步態(tài),即身體靜止時或行走的時時刻刻都滿足平衡條件,不會傾倒,其速度較慢,通常有3 條及以上支撐腿,如爬行(walk)步態(tài);反過來,機器人需要不斷地切換支撐腿才能保證身體不傾倒的步態(tài)就是動步態(tài),其速度較快,通常有兩條甚至一條支撐腿,如對角步(trot)、飛跑(gallop)、跳躍(bounding)等.四足動物會根據(jù)自身的行走速度需求自動調(diào)整步態(tài)參數(shù)(步長、步頻、占空比等)和類別(靜、動步態(tài)).本文主要研究四足動物行走中最常見的兩種步態(tài):walk 靜步態(tài)和trot動步態(tài)的規(guī)劃方法和平衡控制策略.

1.3 四足機器人步態(tài)選擇依據(jù)

顯然,地形復(fù)雜度是步態(tài)選擇的一個重要依據(jù).在不同地形下,四足機器人采取的靜動步態(tài)不同以便更好地通過.四足機器人的靜步態(tài)雖然速度慢,行走能耗較高,但穩(wěn)定性好,具有很強的地形適應(yīng)能力,可適應(yīng)高復(fù)雜度地形;動步態(tài)則正好相反,動步態(tài)雖然速度快,行走能耗較低,但穩(wěn)定性差,地形適應(yīng)能力較弱,更適應(yīng)低復(fù)雜度地形.因此,當(dāng)?shù)匦螐?fù)雜度低時,靜動步態(tài)都可以選擇,但需要綜合考慮速度、行走能耗和穩(wěn)定性要求;當(dāng)?shù)匦螐?fù)雜度高時,更適宜選擇靜步態(tài)以首要保證機器人的運動穩(wěn)定性.因此,本文以地形復(fù)雜度、速度、行走能耗和穩(wěn)定性為4 個主要選擇依據(jù)展開自主步態(tài)選擇算法研究.

地形復(fù)雜度的量化指標為STCI.地形越復(fù)雜,STCI越大,兩者正相關(guān).參考標準差的概率統(tǒng)計意義,其表示一個數(shù)據(jù)集個體間的離散程度,可用來衡量地形復(fù)雜度(地形僅針對足式機器人可穿越地形,非不可穿越障礙).從數(shù)學(xué)角度上看,當(dāng)標準差為零時,數(shù)據(jù)集個體間的差異為零,即個體完全相同;當(dāng)標準差越來越大時,數(shù)據(jù)集個體間的差異也越來越大.從物理角度上看,在地面上均勻地選取數(shù)據(jù)采集點,僅取其高度值或相對高度值,當(dāng)這些地面點高度值的標準差為零時,這些地面點高度值間的差異為零,即地面是完全平坦的;當(dāng)這些地面點高度值的標準差越來越大時,這些地面點高度值間的差異也越來越大,即地面越來越復(fù)雜崎嶇,地面復(fù)雜度也越來越高.

在此給出具體的地面選取方法和地形復(fù)雜度簡易計算方法如圖3,因為地形的復(fù)雜程度或機器人的越障能力與其自身的尺寸大小和步長有關(guān),所以本文選取機器人機體中心往外約兩倍面積的地面區(qū)域Aterrain≈2Arobot,取當(dāng)前行走1/2 步長S/2 作為最小網(wǎng)格將該區(qū)域網(wǎng)格化,計算所有網(wǎng)格交點的高度值hi(i=1,...,N)的標準差作為地形復(fù)雜度:

圖3 地形復(fù)雜度計算方法Fig.3 Calculation method of terrain complexity index

行走能耗的量化指標為η,指單位步行距離執(zhí)行器所做的功的總和,即

其中,s為步行距離,θi和Ti分別為機器人的12 個關(guān)節(jié)的關(guān)節(jié)角度和力矩.

靜步態(tài)穩(wěn)定性的量化指標為穩(wěn)定裕度Ss,具體是指機器人的壓力中心點與多邊形每條邊的最短距離,即

其中,d1,d2,d3為質(zhì)心點投影到支撐多變形各邊的距離,如圖4所示.

圖4 穩(wěn)定裕度Fig.4 Stability margin

動步態(tài)的量化指標為Sd.簡單以一個步態(tài)周期內(nèi)姿態(tài)角αi,βi,γi(i=1,...,N)的標準差的平方根的倒數(shù)作為動態(tài)穩(wěn)定性參考,即

為了獲取影響機器人步態(tài)選擇4 個因素的內(nèi)在聯(lián)系,進一步分析靜步態(tài)的速度、行走能耗、穩(wěn)定性三者之間的關(guān)系,通過改變步態(tài)和步態(tài)周期來對比4種不同速度下,靜步態(tài)的速度、行走能耗、穩(wěn)定性三者之間的關(guān)系,如圖5所示.可以看出靜步態(tài)速度的提升直接導(dǎo)致了穩(wěn)定裕度的下降,但是行走能耗也得到了降低.

同時,進一步分析靜步態(tài)的速度、行走能耗、穩(wěn)定性三者之間的關(guān)系,根據(jù)仿真比較在平地動步態(tài)穩(wěn)定行走時不同速度與能耗和穩(wěn)定性的關(guān)系,如圖6所示.可以看出與靜步態(tài)行走相類似的結(jié)果,速度的增加會導(dǎo)致穩(wěn)定性下降,使行走能耗變大.

圖5 靜步態(tài)的速度、行走能耗、穩(wěn)定性三者之間的關(guān)系(?,?,★分別為上下限和均值)Fig.5 The relationship among the speed,cost of transport and stability of static gait(?,?,★are the upper limits,lower limits and mean value,respectively)

圖6 動步態(tài)的速度、行走能耗、穩(wěn)定性三者之間的關(guān)系(?,?,★分別為上下限和均值)Fig.6 The relationship among the speed,cost of transport and stability of dynamic gait(?,?,★are the upper limits,lower limits and mean value,respectively)

2 自主步態(tài)選擇算法

2.1 C4.5 決策樹算法

決策樹(Decision Tree,DT)算法是一種基于數(shù)據(jù)的歸納推理分類方法,它不需要過多領(lǐng)域背景知識和固定的診斷模型,即可通過對決策表形式的無序樣本數(shù)據(jù)進行推理學(xué)習(xí),建立用于分類判斷的決策樹,從中提取清晰直觀的分類規(guī)則[36].常見的決策樹算法有:ID3、C4.5 和CART.相比于ID3 和C4.5,CART 不但可以分類還可以作回歸分析,但是CART 只能產(chǎn)生二叉樹,而ID3 和C4.5 可以多叉,而且CART 更適合于大樣本,ID3 和C4.5 適合于小樣本.C4.5 本身是ID3 的繼承和改進,解決了ID3 不能處理連續(xù)變量(只能處理分類變量)和對缺失值敏感的問題,故本文采用C4.5 決策樹方法.

如圖7所示,決策樹的建立需要經(jīng)過初始決策樹的生成和決策樹剪枝兩步.C4.5 決策樹算法流程如算法1.在用C4.5 算法生成初始決策樹后,為避免訓(xùn)練樣本數(shù)太少導(dǎo)致的過擬合現(xiàn)象和初始決策樹較為復(fù)雜難理解的問題,需要對初始決策樹進行剪枝(pruning),剪枝方法有兩種:預(yù)剪枝(prepruning)和后剪枝(postpruning)[36].預(yù)剪枝是指在決策樹生成的過程中,在屬性劃分前對每個節(jié)點先進行估計,如果當(dāng)前節(jié)點的劃分不能帶來決策樹泛化能力或分類精確性的提升,則停止劃分并將當(dāng)前節(jié)點標記為葉節(jié)點;后剪枝是指先從訓(xùn)練集生成一棵初始決策樹,然后自下而上地對非葉節(jié)點進行考察,如果該點對應(yīng)的子樹替換為葉節(jié)點,可以帶來決策樹泛化能力或分類精確性的提升,則將該子樹替換為葉節(jié)點.

圖7 決策樹算法規(guī)則提取流程Fig.7 Rule extraction process of decision tree algorithm

算法1.C4.5決策樹算法輸入:訓(xùn)練集決策表:訓(xùn)練集D={(x1,y1),(x2,y2),...,(xn,yn)}與屬性集A={a1,a2,...,am}輸出:以node 為根節(jié)點的決策樹1:function Build DT(D,A)建樹函數(shù)2:生成節(jié)點node;3:if D 中樣本全屬于同一類別C then 4:將node 標記為C 類葉節(jié)點;return 5:end if 6:if A=?,D 中樣本在A 上取值相同then 7:將node 標記為D 中樣本數(shù)最多的類的葉節(jié)點;return 8:end if 9:從A 中選擇最優(yōu)屬性,即a?=arg max GR(D,a)增益率最高的屬性;10:for a?的每一個屬性值av?do 11:為node 生成一個分支;令Dv 為D 中在a?上取值為av?的樣本子集;12:if Dv 為空then 13:將分支節(jié)點標記為D 中樣本數(shù)最多的類的葉節(jié)點;return 14:else 15:以Build a∈A DT(Dv,A{a?})為分支節(jié)點;16:end if 17:end for 18:end function

2.2 建立初始決策表

通過1.3 節(jié)分析可知,機器人靜動步態(tài)的影響因素主要有穩(wěn)定性、速度、行走能耗、地形復(fù)雜度4 個,將它們?nèi)闂l件屬性,且均可以取高、中、低3 個等級,如表2和表3所示(注:只取行進速度分析).

表3 動步態(tài)條件屬性表Table 3 Condition attribute table of dynamic gait

決策樹形即靜步態(tài)和動步態(tài)兩種.利用條件屬性和決策屬性,結(jié)合仿真效果建立初始決策表,并在仿真同時收集樣本數(shù)據(jù),從樣本數(shù)據(jù)中隨機抽取30組作為訓(xùn)練集,30 組作為驗證集,分別如表4和表5所示.

表4 訓(xùn)練集樣本示例Table 4 Training set samples

2.3 建立決策樹

對表4中的數(shù)據(jù)利用C4.5 算法1 生成初始決策樹,如圖8所示.

為提高決策樹分類準確性,利用表5中的驗證集數(shù)據(jù),對其進行后剪枝,發(fā)現(xiàn)初始決策樹中非葉節(jié)點對應(yīng)的子樹替換為葉節(jié)點并不能提要高其原來的驗證集精度96.67%.

從圖8決策樹可以看出,影響步態(tài)4 個因素的主次關(guān)系為:地形復(fù)雜度>穩(wěn)定性>速度>行走能耗.通過1.3 節(jié)分析可知,地形復(fù)雜度會影響其他3 個因素.決策樹偏向于選擇靜步態(tài),因為穩(wěn)定是機器人執(zhí)行任務(wù)的基礎(chǔ).在滿足穩(wěn)定性前提下,動步態(tài)可以很容易提高速度.行走能耗的分析也并不是多余的,因為給予更多的能量,靜步態(tài)可以更好地控制住速度,尤其是橫向速度.

表5 驗證集樣本示例Table 5 Verificatio set samples

圖8 C4.5 算法生成的決策樹Fig.8 Decision tree generated by C4.5 algorithm

2.4 提取決策規(guī)則

根據(jù)剪枝后的決策樹,可以提取決策規(guī)則“IF 條件THEN 決策”模式如下:

1)IF 條件:地形復(fù)雜度低

THEN 決策:動步態(tài)

2)IF 條件:地形復(fù)雜度中,穩(wěn)定性低,速度低,行走能耗低

THEN 決策:動步態(tài)

3)IF 條件:地形復(fù)雜度中,穩(wěn)定性低,速度低,行走能耗中

THEN 決策:動步態(tài)

4)IF 條件:地形復(fù)雜度中,穩(wěn)定性低,速度低,行走能耗高

THEN 決策:靜步態(tài)

5)IF 條件:地形復(fù)雜度中,穩(wěn)定性低,速度中

THEN 決策:動步態(tài)

6)IF 條件:地形復(fù)雜度中,穩(wěn)定性低,速度高

THEN 決策:動步態(tài)

7)IF 條件:地形復(fù)雜度中,穩(wěn)定性中

THEN 決策:靜步態(tài)

8)IF 條件:地形復(fù)雜度中,穩(wěn)定性高

THEN 決策:靜步態(tài)

9)IF 條件:地形復(fù)雜度高

THEN 決策:靜步態(tài)

3 仿真驗證

給定地形如圖9,設(shè)定機器人要從當(dāng)前初始位置走到黑框目標位置.首先,利用生成的決策樹圖8,對整個地形進行靜動步態(tài)選擇決策,如圖10所示,其中綠色區(qū)域為適宜動步態(tài)行走區(qū)域,紅色區(qū)域為適宜靜步態(tài)行走區(qū)域,黃色區(qū)域為靜步態(tài)和動步態(tài)皆宜行走區(qū)域.

然后,設(shè)定完成該行走任務(wù)可以具有以下6 個目標約束:

1)Js最小:機器人行走路程最小,即路徑長度s最短;

2)JT最小:機器人行走時間最小,即總用時T最短;

3)JTCI最小:機器人行走地形起伏最小,即STCI最小;

4)JS最大:機器人行走穩(wěn)定性最大,即Ss或Sd最小;

5)Jv最大:機器人行走速度最快,即最大;

6)JCoT最小:機器人行走能耗最小,即η 最大.

注意此種設(shè)定相對更為合理,因為人從一個位置到另一個位置正常行走時,也會選擇更平坦、更省力、更不容易摔倒、速度更快、時間更短、長度更短的路徑.而傳統(tǒng)的A*算法[37]和文獻[38]提出的改進A*算法都只考慮目標約束1 的路徑最短方式,相對較為片面.

為了避免出現(xiàn)多目標優(yōu)化的Pareto 前沿面,可將6 個多目標加權(quán)為一個單目標,設(shè)計任務(wù)總代價函數(shù)為

其中,k?>0 為相應(yīng)優(yōu)化目標J?的加權(quán)系數(shù),要突出某一個目標則加大其系數(shù)即可.k?<0 為獎勵動作,暫不考慮.

將式(5)融合到文獻[38]中提出的改進A*算法的估價函數(shù)

其中,f(n)是從初始節(jié)點經(jīng)由任意節(jié)點n移動到目標節(jié)點的估價函數(shù),g(n)是從初始節(jié)點移動到節(jié)點n的實際代價,h(n)是從節(jié)點n到目標節(jié)點的估計移動代價.采用式(5)代替歐幾里得距離作為兩點之間的移動代價.當(dāng)ks>0,kT=kTCI=kS=kv=kCoT=0 時,則該算法與文獻[38]的改進A*算法相同.

最后,利用C4.5 決策樹分析得到的圖8,結(jié)合式(5)修正的改進A*路徑規(guī)劃算法[38]進行仿真,可得出如圖10所示的3 種典型規(guī)劃路徑,其仿真目標約束和相應(yīng)參數(shù)如表6所示.根據(jù)當(dāng)前行走任務(wù)執(zhí)行的目標約束要求選擇最佳路徑,如果只要求路徑最短,則選擇路徑1;如果既要求路徑短又要保證穩(wěn)定性,則選擇路徑2;如果只要求時間短,則選擇路徑3.相比與文獻[38]的改進A*算法,該方法可根據(jù)行走任務(wù)執(zhí)行需求生成不同的路徑,更具有一般性和適應(yīng)性.

圖9 機器人行走地形環(huán)境Fig.9 Terrain environment for robot walking

圖10 靜動步態(tài)選擇決策與路徑選擇Fig.10 Static and dynamic gait selection decision and path selection

表6 仿真參數(shù)Table 6 Simulation parameters

4 結(jié)論

以地形復(fù)雜度、速度、行走能耗和穩(wěn)定性作為4個主要選擇依據(jù),研究一種基于C4.5 決策樹的自主步態(tài)選擇算法.主要貢獻如下:

1)研究影響四足機器人靜動步態(tài)行走的4 個主要因素:地形復(fù)雜度、速度、行走能耗和穩(wěn)定性,并分析這4 個因素之間的內(nèi)在聯(lián)系;

2)將以上4 個因素作為靜動步態(tài)選擇依據(jù),研究一種基于C4.5 決策樹的自主步態(tài)選擇算法,通過訓(xùn)練得到靜動步態(tài)自主決策規(guī)則;

3)結(jié)合式(5)修正的改進A*路徑規(guī)劃算法,通過仿真驗證所提出算法的有效性和可行性.

該算法也存在一定的局限性,算法中提出了一種地形復(fù)雜度的定量計算方法式(1),即算法局限所在.在仿真環(huán)境中,地面網(wǎng)格各點的高度值容易得到,但在實際應(yīng)用中,需要通過激光雷達等傳感器進行采集(可為相對高度值),存在采集誤差、采集盲區(qū)等問題,容易影響到地形復(fù)雜度計算結(jié)果的準確性;同時,地形復(fù)雜度計算結(jié)果的準確性也受到選取有效地面網(wǎng)格區(qū)域的差異,網(wǎng)格大小等因素影響.在實際應(yīng)用中,以上局限也可以通過工程的方式加以彌補和修正,如增加激光雷達等傳感器數(shù)量和精度等.此外,在計算誤差允許范圍內(nèi),地形復(fù)雜度的計算結(jié)果也是可以作為步態(tài)選擇的參考依據(jù).

該方法可以運用到其他類型足式機器人.同時,帶有獎勵性質(zhì)(k?<0)的路徑規(guī)劃也是未來需要做的工作.