張泮虹 倪 濤 趙亞輝 翟海陽 趙澤仁
(燕山大學(xué)車輛與能源學(xué)院, 秦皇島 066000)
自主移動機(jī)器人主要包括前端感知、中間規(guī)劃、終端控制3部分[1-3]。規(guī)劃層主要是為移動機(jī)器人計(jì)算出一條由起點(diǎn)到終點(diǎn)的無障礙的可行路徑[4],是影響移動機(jī)器人移動行為質(zhì)量的最直接因素。
目前,路徑規(guī)劃方法主要包括圖搜索、勢場、隨機(jī)采樣、曲線插值、機(jī)器學(xué)習(xí)以及優(yōu)化方法[5-6]。
圖搜索的方法是對環(huán)境進(jìn)行網(wǎng)格化建模,然后在圖中搜索符合任務(wù)要求的路徑。在對建模要求精度不高的條件下,基于A*的圖搜索[7-8]能夠快速生成質(zhì)量較高的移動路徑,對于建模精度要求較高的運(yùn)動規(guī)劃任務(wù)需要對圖搜索獲得的粗糙路徑進(jìn)行精細(xì)化處理之后才能用于底層的控制環(huán)節(jié)[9]。
勢場方法[10]是對環(huán)境中的障礙物和非障礙物建模為斥力場和引力場,通過對勢場函數(shù)進(jìn)行改進(jìn)[11-12]可適應(yīng)不同的應(yīng)用環(huán)境。基于勢場的算法是[13-15]通過修改傳統(tǒng)人工勢場法斥力場函數(shù)獲得平順且安全的無碰撞路徑,但是易陷入局部最優(yōu)[16]。
隨機(jī)采樣的方法是在環(huán)境中隨機(jī)生成一系列采樣點(diǎn),然后篩選出滿足任務(wù)要求的序列作為路徑。相比于圖搜索,隨機(jī)采樣可以處理較高維度的運(yùn)動規(guī)劃問題,具有概率完備性。主要包括概率路標(biāo)算法(PRM)[17]和快速搜索隨機(jī)樹算法(RRT)[18],其中RRT由于其規(guī)劃出的路徑可行性強(qiáng)而應(yīng)用廣泛。盡管隨機(jī)采樣的方法具有概率完備性,但是無法處理復(fù)雜的約束條件,其生成運(yùn)動狀態(tài)具有盲目性,導(dǎo)致最終解的不穩(wěn)定,且解通常不是最優(yōu)的[19]。
曲線插值[20]的方法是通過預(yù)設(shè)的路徑點(diǎn)擬合生成連續(xù)性、平滑性較好的路徑。常見的曲線插值方法包括杜賓曲線法、Reeds-Sheep曲線法、多項(xiàng)式樣條曲線擬合法,等等。該方法生成的路徑一般具有可跟蹤的性質(zhì),因此通常是配合其他規(guī)劃方法對軌跡進(jìn)行平滑處理或生成初始路徑,比如王明強(qiáng)等[21]用三次樣條曲線獲取道路基準(zhǔn)線。
機(jī)器學(xué)習(xí)的方法是以作業(yè)需求、機(jī)器人的始末狀態(tài)、環(huán)境設(shè)置等信息作為輸入量,通過增強(qiáng)學(xué)習(xí)模型[22]、卷積神經(jīng)網(wǎng)絡(luò)模型[23]、隱式馬爾可夫模型[24]、高斯混合模型[25]等進(jìn)行學(xué)習(xí),輸出移動機(jī)器人的行駛路徑/軌跡,然而機(jī)器學(xué)習(xí)需要大量的訓(xùn)練樣本,并需要提前進(jìn)行離線學(xué)習(xí),不適合解決未知環(huán)境下實(shí)時性的路徑規(guī)劃問題[26]。
基于優(yōu)化的方法是在動態(tài)系統(tǒng)模型的基礎(chǔ)上加入約束條件以及任務(wù)需求,構(gòu)成了最優(yōu)控制問題,以最優(yōu)控制問題的形式描述移動機(jī)器人的規(guī)劃任務(wù),具有直觀、準(zhǔn)確、客觀的特點(diǎn),這是前述幾種方法所不具備的。目前計(jì)算最優(yōu)控制方法已應(yīng)用于車輛泊車[27]、避障[28]等結(jié)構(gòu)化環(huán)境的駕駛情景中,基于最優(yōu)控制形式建立的模型中一般包含復(fù)雜約束條件,一些研究將這些復(fù)雜的約束條件進(jìn)行簡化并利用現(xiàn)代智能優(yōu)化算法(如粒子群[29]、隨機(jī)分形搜索[30]等)進(jìn)行求解。從目前的研究來看,基于最優(yōu)控制思想去解決軌跡生成問題主要有以下難點(diǎn):用于描述車輛運(yùn)動學(xué)特性的方程是非凸的;用于限制車輛和障礙物碰撞的幾何約束是高度非凸且不可微;避碰約束的維度和障礙物的密度是密切相關(guān)的,障礙物較多環(huán)境下會導(dǎo)致規(guī)劃時間急劇增加;規(guī)劃過程會產(chǎn)生大量的局部最優(yōu)。因此,在復(fù)雜環(huán)境下的軌跡規(guī)劃仍是一個需要研究的問題。
本文在上述研究的基礎(chǔ)上,提出一種基于最優(yōu)控制的復(fù)雜環(huán)境下移動機(jī)器人的軌跡規(guī)劃方法,首先針對優(yōu)化求解問題建立運(yùn)動學(xué)模型、幾何模型、變量極值點(diǎn)約束以及避障模型等約束,通過對控制變量進(jìn)行拉格朗日離散化,針對離散化階段的約束失效進(jìn)行等距時間離散并引入懲罰函數(shù),最后通過隨機(jī)分形搜索算法對所構(gòu)建的優(yōu)化問題進(jìn)行求解。
由于機(jī)器人在復(fù)雜路面上的行駛速度較小,輪胎的側(cè)滑影響較小,因此移動機(jī)器人的運(yùn)動學(xué)模型是基于自行車模型構(gòu)建的。如圖1所示,其數(shù)學(xué)表達(dá)式為

圖1 移動機(jī)器人運(yùn)動學(xué)模型Fig.1 Kinematic model of mobile robot

(1)
式中t——時間
tf——移動機(jī)器人整個運(yùn)動過程總耗時
(x(t),y(t))——移動機(jī)器人后輪軸線中點(diǎn)坐標(biāo),表示機(jī)器人實(shí)時位置
v(t)——機(jī)器人后輪(點(diǎn)P)實(shí)時線速度
θ(t)——機(jī)器人實(shí)時方向角
φ(t)——機(jī)器人前輪實(shí)時轉(zhuǎn)向角
L——機(jī)器人前后輪之間的縱向距離
此外,為了保證后續(xù)規(guī)劃路徑在規(guī)避障礙物時更加有效,本文在運(yùn)動學(xué)建模時加入了M、N兩個量,分別表示移動機(jī)器人后懸長度和前懸長度,更加符合實(shí)際情況。
從模型的數(shù)學(xué)表達(dá)式可以看出,如果機(jī)器人的實(shí)時速度v(t)和方向角θ(t)已知,那么其位置P(x(t),y(t))和前輪的實(shí)時轉(zhuǎn)向角φ(t)均可以通過數(shù)學(xué)積分來推導(dǎo)得出。因此將u=(v(t),θ(t))作為控制向量,χ=(x(t),y(t),φ(t))作為狀態(tài)向量。
此外,由圖1所示的幾何關(guān)系,可以得出移動機(jī)器人的幾何模型,即4個邊角點(diǎn)的坐標(biāo),以便于后續(xù)避障模型的搭建。
(2)
式中B——前后輪之間的橫向距離的一半
在移動機(jī)器人的路徑規(guī)劃中,最重要的原則是保證機(jī)器人避開環(huán)境中的所有障礙物;其次,也將移動機(jī)器人本身硬件所具有的最大速度和轉(zhuǎn)向角加入優(yōu)化條件中;此外,對移動機(jī)器人終點(diǎn)狀態(tài)也做了相應(yīng)的約束。
在移動機(jī)器人的整個運(yùn)動過程中,其線性速度不宜過高,轉(zhuǎn)向角也存在極大值,即
(3)
環(huán)境約束主要包括移動機(jī)器人的始末狀態(tài)約束以及保證機(jī)器人在移動過程中不與環(huán)境中的障礙物發(fā)生碰撞。本文將障礙物建模為矩形,通過不規(guī)律的放置來使環(huán)境的復(fù)雜程度加大。
假設(shè)Q(X,Y)表示移動機(jī)器人的某一邊角點(diǎn),如圖2所示。A、B、C、D分別表示矩形障礙物的4個邊角點(diǎn),設(shè)矩形的幾何尺寸為m×n,其中,lAQ=(X-m,Y-n),lAD=(-m,0),lAB=(0,-n)。

圖2 避障模型構(gòu)建Fig.2 Obstacle avoidance model construction
若點(diǎn)Q在障礙物矩形區(qū)域內(nèi),即說明0 (4) 本文所述算法對移動機(jī)器人的終點(diǎn)狀態(tài)做了相應(yīng)的約束,在實(shí)際應(yīng)用中,根據(jù)移動機(jī)器人不同的任務(wù)需求其終點(diǎn)狀態(tài)也可以做相應(yīng)的改變。本文定義機(jī)器人的終點(diǎn)是以v(tf)=0的狀態(tài)進(jìn)入到預(yù)先定義好的矩形框區(qū)域內(nèi)。由于凸集特性,本文所定義的終端條件等效于移動機(jī)器人的4個角點(diǎn)位于終端矩形框內(nèi)部的約束。移動機(jī)器人終端約束類似于矩形障礙物約束,此處不再贅述。 本文將路徑規(guī)劃問題歸結(jié)為一個最優(yōu)控制問題,主要包括離散化和目標(biāo)函數(shù)設(shè)計(jì)兩部分。 將[0,tf]區(qū)間平均分成Nf份,每一個子區(qū)間為[ti-1,ti](i=1,2,…,Nf)。如圖3所示,在每個子區(qū)間內(nèi)設(shè)置K+1個插值點(diǎn){zi0,zi1,…,ziK},并通過拉格朗日多項(xiàng)式來描述控制變量,以v(t)為例,即 圖3 拉格朗日離散化Fig.3 Lagrange discretization (5) 其中,τ∈[0,1],τi表示高斯點(diǎn),當(dāng)K確定時可以離線計(jì)算。因此當(dāng)插值點(diǎn)足夠多時,就能很好地表示控制變量v(t)和φ(t)。此外,為了保證子區(qū)間之間變量的連續(xù)性,需要保證前后區(qū)間端點(diǎn)處的插值點(diǎn)相等,即 (6) 即 ziK=z(i+1)0 (7) 在用插值點(diǎn)描述控制變量之后,移動機(jī)器人的狀態(tài)變量就可以通過數(shù)值積分的方式進(jìn)行計(jì)算,如圖4所示,在數(shù)值積分之前,把前述的分段拉格朗日多項(xiàng)式等距時間均分成Nsp(足夠大)份,即v(t)可以表示為{v0,v1,…,vNsp-1}。 圖4 等距時間離散化Fig.4 Isometric time discretization 上一階段僅僅是將連續(xù)變量通過拉格朗日插值的形式進(jìn)行離散化,而第1節(jié)所述的約束條件也僅僅是針對插值點(diǎn),但是插值點(diǎn)之間的時刻并沒有被約束,這將引起如下問題:如圖5所示,即便插值點(diǎn)1、2、3均滿足控制變量約束條件,但由于控制變量的連續(xù)性,也仍然會存在某些不符合約束條件的時刻。此外,如圖6所示,盡管在離散化情況下機(jī)器人的運(yùn)動軌跡滿足了障礙物約束,但在連續(xù)時間內(nèi),圖示箭頭所指機(jī)器人運(yùn)動的下一時刻將會和障礙物發(fā)生碰撞,從而導(dǎo)致任務(wù)失敗。 圖5 連續(xù)變量越界Fig.5 Continuous variable out of bounds 圖6 連續(xù)變量避障失效示意圖Fig.6 Continuous variable obstacle avoidance failure 針對如圖5所示的問題,在數(shù)值積分之前, 將重新均分的各個離散化點(diǎn),即集合{v0,v1,…,vNsp-1}中的每個元素都進(jìn)行邊界約束檢查,若vi超出邊界線,則令vi=vmax或者令vi=vmin,將有效減少控制變量超出邊界的情況。 針對圖6所示的問題,本文在目標(biāo)函數(shù)設(shè)計(jì)中加入了懲罰函數(shù),對于機(jī)器人運(yùn)動過程中避障,基于式(4),得到障礙物的懲罰值 Qc=min((lABlAB-lAQlAB),lAQlAB, (8) 式(8)保證了點(diǎn)Q是以最小的代價位于障礙物外的,對于移動機(jī)器人終端約束也可以用類似的思想,以保證最終機(jī)器人位于終點(diǎn)所定義的矩形框內(nèi)。 因此,最終懲罰項(xiàng) (9) 為了將求解軌跡的可行解與不可行解區(qū)分開,本文引入一個足夠大的定值N來保證可行解的懲罰值絕對小于不可行解的懲罰值。顯然,若路徑能保證無障礙和滿足最終狀態(tài),那么其懲罰值為0。 根據(jù)前文所述,將離散化的插值點(diǎn)和移動機(jī)器人的運(yùn)動時間tf作為決策變量。然后,通過積分得到狀態(tài)變量,檢查其邊界約束,并將障礙物懲罰函數(shù)加入優(yōu)化準(zhǔn)則中。考慮到元啟發(fā)算法具有全局優(yōu)化的能力,本文采用了隨機(jī)分形搜索算法[31]作為整個優(yōu)化過程的求解器。 分形指的是具有自相似性的現(xiàn)象、圖像或者物理過程等,隨機(jī)分形表現(xiàn)在結(jié)構(gòu)或復(fù)雜度上具有統(tǒng)計(jì)意義上的自相似性,一般是通過萊維飛行、高斯游走等隨機(jī)規(guī)則來產(chǎn)生。隨機(jī)分形主要包括擴(kuò)散和更新兩個過程,擴(kuò)散過程是基于粒子的當(dāng)前位置,因此有利于尋找全局最優(yōu)解。 首先是種群的初始化,在這個過程中,基于約束條件隨機(jī)初始化種群中的每一個個體,第j個個體的初始化方程為 Pj=LB+ε(UB-LB) (10) 其中,LB和UB分別是求解問題向量的上下邊界,本文指的是控制變量轉(zhuǎn)向角和速度的上下限值,ε是在區(qū)間[0,1]上服從均勻分布的隨機(jī)數(shù)。 初始化種群之后,計(jì)算個體的適應(yīng)度函數(shù)以獲得最佳個體BP,然后所有個體都圍繞當(dāng)前的位置游走以搜索環(huán)境空間,隨機(jī)搜索算法采用高斯游走作為唯一的游走方式,即 (11) 式中Pi——第i個個體的位置 ε、ε′——區(qū)間[0,1]上服從均勻分布隨機(jī)數(shù) μBP、μP——高斯函數(shù)均值 σ——高斯參數(shù)標(biāo)準(zhǔn)差 μBP=|BP|,μP=|Pi|,高斯參數(shù)中的標(biāo)準(zhǔn)差為 (12) 第1次更新過程,首先根據(jù)個體的適應(yīng)度進(jìn)行排序,然后賦予每個個體性能級別,個體適應(yīng)度為 (13) 式中N——種群的個體數(shù)量 rank(Pi)——個體Pi在種群中的排序 之后判斷是否滿足Pai<ε,若滿足則更新個體Pi的第j個分量,否則保持不變,更新公式為 P′i(j)=Pr(j)-ε(Pt(j)-Pi(j)) (14) 式中P′i——個體Pi更新后的位置 Pr、Pt——種群中隨機(jī)選擇的個體 第2次更新過程主要是根據(jù)個體的分量進(jìn)行,對于更新后的P′i,判斷是否滿足P′ai<ε,若滿足則更新P′i的當(dāng)前位置,否則保持不變,更新公式為 (15) 式中P′r、P′t——第1次更新后種群中選擇的個體 若P″i對應(yīng)的適應(yīng)度優(yōu)于P′i對應(yīng)的適應(yīng)度,則用P″i更新替換掉P′i。 仿真實(shí)驗(yàn)在Matlab 2019b中展開,計(jì)算機(jī)環(huán)境是Windows10,處理器Intel(R) Core(TM) i7-10870H CPU @ 2.20 GHz 2.21 GHz,RAM 16 GB,本文所述算法中提到的一些參數(shù)設(shè)置如表1所示。為了驗(yàn)證本文所述算法的有效性,鑒于現(xiàn)在大多數(shù)的規(guī)劃算法均是將機(jī)器人建模為質(zhì)點(diǎn),與真實(shí)情況相差較大,在本仿真實(shí)驗(yàn)中,引入了“足跡”的概念,即表示各個時刻移動機(jī)器人在地面上的投影,以足跡和障礙物不發(fā)生交集來作為避障有效的判定,如1.3節(jié)所述。將建好的模型經(jīng)拉格朗日離散化處理,然后代入SFS算法中進(jìn)行迭代求解,最終得到最優(yōu)解。 表1 基于優(yōu)化算法的參數(shù)Tab.1 Parameter based on optimization algorithm 為驗(yàn)證本文所述算法的有效性,場景1隨意設(shè)置10個矩形障礙物,用戶可根據(jù)環(huán)境或者任務(wù)不同隨意指定起點(diǎn),本文取x1(0)=-40 m,y1(0)=15 m,終點(diǎn)設(shè)置在以(0,0)為中心,長為2.5 m、寬為1.5 m的終端盒子內(nèi)。初始方位角為0°,初始轉(zhuǎn)向角為0°,初始速度為0。從圖7a可以看出,所規(guī)劃的軌跡可以實(shí)現(xiàn)準(zhǔn)確避障,即說明優(yōu)化模型中的避障模型是有效的,此外終端約束也滿足,圖7b中的速度最大值控制在3.0 m/s,前輪轉(zhuǎn)角控制在0.714 rad內(nèi),即邊界約束有效,同時可以看出移動機(jī)器人的足跡和障礙物矩形的交集為空,因此針對離散化導(dǎo)致的避障失效問題也得到了有效解決。 圖7 障礙物較少場景Fig.7 Scenarios with fewer obstacles 場景2設(shè)置了10個障礙物并設(shè)置了一個狹窄區(qū)域,起點(diǎn)設(shè)置為x2(0)=-50 m,y2(0)=5 m,終點(diǎn)設(shè)置在以(0,0)為中心,長為2.5 m、寬為1.5 m的終端盒子內(nèi)。初始方位角為0°,初始轉(zhuǎn)向角為0°,初始速度為0。從圖8a可以看出,所規(guī)劃的軌跡可以實(shí)現(xiàn)準(zhǔn)確避障,即說明優(yōu)化模型中的避障模型是有效的,此外終端約束也嚴(yán)格滿足,圖8b中的速度最大值控制在3.0 m/s,前輪轉(zhuǎn)角控制在0.714 rad內(nèi),即邊界約束有效,同時可以看出移動機(jī)器人的足跡和障礙物矩形的交集為空,因此針對離散化導(dǎo)致的避障失效問題也得到了有效的解決,因此本文所述方法在狹窄區(qū)域內(nèi)仍具有一定的穩(wěn)定性。 圖8 狹窄區(qū)域場景Fig.8 Narrow area scenario 場景3設(shè)置了30個障礙物矩形區(qū)域,起點(diǎn)設(shè)置為x3(0)=-40 m,y3(0)=0 m,終點(diǎn)設(shè)置在以(0,0)為中心,長為2.5 m、寬為1.5 m的終端盒子內(nèi)。初始方位角為0°,初始轉(zhuǎn)向角為0°,初始速度為0。從圖9a可以看出,所規(guī)劃的軌跡可以實(shí)現(xiàn)準(zhǔn)確避障,即說明優(yōu)化模型中的避障模型是有效的,此外嚴(yán)格滿足終端約束,圖9b中的速度最大值控制在3.0 m/s,前輪轉(zhuǎn)角控制在0.714 rad內(nèi),即邊界約束有效,同時可以看出移動機(jī)器人的足跡和障礙物矩形的交集為空,因此針對離散化導(dǎo)致的避障失效問題也得到了有效的解決,在復(fù)雜環(huán)境下進(jìn)一步證明了本文所述方法具有較強(qiáng)的魯棒性。 圖9 障礙物較多場景Fig.9 Scenarios with many obstacles 采用Matlab隨機(jī)生成了10個場景,由于混合A*算法考慮了機(jī)器人的運(yùn)動學(xué)模型,而且算法中也加入了非線性優(yōu)化和非參數(shù)插值,因此將本文所述優(yōu)化算法與混合A*算法作比較,結(jié)果如表2所示,成功率是指移動機(jī)器人足跡不與矩形障礙物產(chǎn)生交集,如圖10虛線圓處所示,計(jì)算第4障礙物和第6障礙物與混合A*算法所規(guī)劃軌跡的最近距離,分別為0.312 m和0.965 m,而本文設(shè)定的移動機(jī)器人的寬為2 m,長為4 m,也就說明移動機(jī)器人在實(shí)際移動中會與障礙物發(fā)生碰撞,導(dǎo)致避障失效,即混合A*算法在狹窄區(qū)域內(nèi)并不有效,同時,基于優(yōu)化算法所得到的軌跡較短,時間也相對較小,效率更高。這里的軌跡長度是對求得的離散軌跡點(diǎn)求和,即 圖10 本文算法與混合A*算法運(yùn)行軌跡Fig.10 Proposed algorithm and hybrid A* algorithm running track 表2 本文算法與混合A*算法性能對比Tab.2 Performance comparison between proposed algorithm and hybrid A* algorithm (16) 此外,與現(xiàn)有文獻(xiàn)中的基于優(yōu)化的規(guī)劃算法比較,用于驗(yàn)證本文所提算法的求解質(zhì)量。選取文獻(xiàn)[32]中提到的優(yōu)化算法作為基準(zhǔn),用于驗(yàn)證其余算法的最優(yōu)性損失,假設(shè)算法X以代價值cX取得最優(yōu)解,文獻(xiàn)[33]算法以cbaseline為代價值取得最優(yōu)解,那么算法X的最優(yōu)性損失計(jì)算式為[34] (17) 很明顯最優(yōu)性損失越小,說明求解質(zhì)量越高。通過計(jì)算,本文所述算法最優(yōu)性損失為19.72%,文獻(xiàn)[32]算法為45.1%,文獻(xiàn)[33]算法為34.61%,因此本文所述算法在軌跡規(guī)劃的求解上質(zhì)量更高,輸出的軌跡具有更好的性能。 此外,驗(yàn)證SFS算法中迭代次數(shù)對于求解結(jié)果的影響。選擇場景1,對不同迭代次數(shù)下求得的目標(biāo)函數(shù)值作比較,如表3所示,從表3可以看出,迭代次數(shù)在大于500以后,目標(biāo)函數(shù)值的降低率趨緩,因此迭代次數(shù)并不是越大越好,選擇合適的迭代次數(shù)會增加求解效率。 表3 不同迭代次數(shù)SFS算法的目標(biāo)值Tab.3 Target values of different iterations of SFS algorithm (1)將軌跡規(guī)劃轉(zhuǎn)化為最優(yōu)控制問題,通過設(shè)置控制變量極值、障礙物避碰、起點(diǎn)終點(diǎn)狀態(tài)等優(yōu)化限制條件,采用隨機(jī)分形搜索算法的元啟發(fā)策略進(jìn)行求解,得到了移動機(jī)器人精確的移動軌跡,本文所述方法在復(fù)雜、狹窄區(qū)域均具有較好的表現(xiàn)。 (2)通過等距時間離散,解決了由離散化導(dǎo)致的離散點(diǎn)之間約束失效的問題,Matlab仿真實(shí)驗(yàn)顯示移動機(jī)器人的線速度不超過最大速度3.0 m/s,轉(zhuǎn)向角不超過最大轉(zhuǎn)角0.714 rad,均滿足變量的邊界約束。2 優(yōu)化求解策略
2.1 離散化階段


2.2 目標(biāo)函數(shù)設(shè)計(jì)


(lADlAD-lAQlAD),lAQlAD)3 優(yōu)化求解器
4 仿真實(shí)驗(yàn)
4.1 實(shí)驗(yàn)設(shè)置

4.2 障礙物較少場景驗(yàn)證

4.3 狹窄區(qū)域場景驗(yàn)證

4.4 復(fù)雜場景驗(yàn)證

4.5 仿真實(shí)驗(yàn)對比分析



5 結(jié)論