基于微分鄰域和粗糙集的動態(tài)障礙路況下智能車的控制

江 怡

(中國民用航空飛行學(xué)院 計算機學(xué)院，四川 廣漢 618307)

0 引言

智能自主移動設(shè)備在障礙路況中的避障控制與路徑選擇是智能系統(tǒng)的重要組成部分，已有大量的專家、學(xué)者對智能自主移動設(shè)備的避障控制算法進行了研究，其關(guān)鍵在于根據(jù)設(shè)備、障礙物的位置信息及障礙物的形狀大小來選擇合適的局部路徑以達到安全行駛的目的。目前已取得了許多突破性的進展，但是這些避障控制算法大多是基于模糊控制[1-3]、神經(jīng)網(wǎng)絡(luò)控制[4-5]等。模糊控制是基于人的經(jīng)驗來提取相應(yīng)的控制規(guī)則，再根據(jù)這些規(guī)則建立相應(yīng)的隸屬函數(shù)和推理控制方法，但通常情況下隸屬函數(shù)的建立相對困難，且存在一定的誤差，不能確?？刂频臏?zhǔn)確性。而神經(jīng)網(wǎng)絡(luò)方法在控制工程中需要輸入大量的經(jīng)驗值，其控制效果表現(xiàn)一般。

智能車在障礙路況中的避障控制與路徑選擇是自動駕駛技術(shù)重要的組成部分，基于鄰域系統(tǒng)[1]的動態(tài)決策與控制模型是處理和實現(xiàn)智能駕駛技術(shù)的一種有效途徑，其主要思想源于智能生物隨時隨地的動態(tài)決策和行為方式。智能生物可以根據(jù)當(dāng)前時刻的周圍環(huán)境特點圈定一定的范圍作為其安全活動范圍，安全范圍之外的一切事物都視為與之無關(guān)、靜止的，一旦外界事物侵犯了圈定的范圍，生物會做出相應(yīng)的決策和行為來確保自身的安全。我們可以將此思想用于整個決策過程，使無限、復(fù)雜的決策環(huán)境轉(zhuǎn)變?yōu)橐粋€有限、局部的簡單環(huán)境，即將宏觀上復(fù)雜的動態(tài)決策過程分解為一系列微觀上簡單的靜態(tài)決策過程。其要點在于一旦確定了局部的環(huán)境鄰域，該鄰域外的一切事物都可以看作是與之無關(guān)的和靜止的，從而可視為對鄰域內(nèi)所做的決策沒有影響的事物。該方法由兩步完成：首先根據(jù)當(dāng)前狀態(tài)，在其鄰域系統(tǒng)中按照某種方法找出滿意的可行鄰域，并將其看作靜止不變的；其次在滿意的可行鄰域內(nèi)按照某種滿意優(yōu)化控制算法給出控制量并實施控制動作[6]。而一個過程或事件的整體動態(tài)決策過程可看成無數(shù)個局部環(huán)境鄰域內(nèi)行為的順序疊加結(jié)果。圖1給出了行駛在實際道路中汽車的鄰域示意圖。

圖1 實際道路中汽車的鄰域示意

在道路上行駛的汽車會遇到各式各樣的障礙物，而障礙物可分為靜態(tài)障礙物和動態(tài)障礙物，后者主要是指相對于此汽車行駛的其他車輛。按照上述思想，對于靜態(tài)障礙物，文獻[7]給出了基于粗糙集和鄰域系統(tǒng)的控制方法，對于動態(tài)障礙物，結(jié)合當(dāng)前時刻智能車安裝的各種傳感器收集到的信息的變化趨勢，對下一短暫時刻信息的改變情況作出相應(yīng)的預(yù)測，再結(jié)合微分鄰域固有的避障性，通過折線法建立相應(yīng)的微分鄰域，對此微分鄰域所代表的區(qū)域進行分類、篩選，再取覆蓋粗糙集模型下的下近似將不規(guī)則的鄰域化為規(guī)則的。由此得到的可行鄰域中控制規(guī)則的選取方法與文獻[7]中靜態(tài)障礙物中的一致，最后進行決策。為了驗證方法的有效性，利用Matlab進行了仿真實驗，其中，用于仿真的道路邊界是由正弦函數(shù)按法線法[8]構(gòu)造的等距曲線而生成的，而障礙物采用隨機函數(shù)給出。仿真結(jié)果表明梯形微分鄰域與經(jīng)驗駕駛者的駕駛范圍相近。

1 基本概念

定義2.4.1(鄰域[9])設(shè)X是一個論域，x為X內(nèi)一個對象，稱X的某個特定子集(可以不包含x)為x的鄰域，記作N(x)。

定義2.4.2(鄰域系統(tǒng)[8,9])設(shè)X是一個論域，x為X內(nèi)一個對象，由x的所有鄰域所構(gòu)成的集族稱為對象x的一個鄰域系統(tǒng)，記做NS(x)。而論域X中所有對象鄰域系統(tǒng)的并集稱為論域X的鄰域系統(tǒng)，記作NS(X)。

按照上述定義，有：NS(x)={A|A?X且A是對象x的鄰域}。

(1)

定義2.4.4(微分鄰域[9])設(shè)Ψ(t)為系統(tǒng)在t時刻鄰域的邊界，當(dāng)t有增量時Δt，鄰域的邊界Ψ(t)也有相應(yīng)的改變量ΔΨ(t)，以Ψ(t)+ΔΨ(t)為邊界的鄰域稱為原鄰域Φ(t)的微分鄰域，記作Ω(t)。

由微分鄰域的定義知，系統(tǒng)的微分鄰域為滿足一組條件的區(qū)域，即Ω(t)={(x1(t),…,xn(t))|(x1(t),…,xn(t))滿足條件S}，其中S可取為式子(2)。

(2)

對于智能自主移動裝置而言，例如機器人、無人駕駛飛機、智能車等，顯然其實用鄰域位于三位立體空間之中，下面將研究在三維空間中的鄰域及其相關(guān)的數(shù)學(xué)模型。

對于某系統(tǒng)中的被控對象，其上的傳感器在t時刻檢測到一組足夠密的數(shù)據(jù)(x1(t),y1(t),z1(t)),(x2(t),y2(t),z2(t)),…,(xn(t),yn(t),zn(t))，由這n個點可以確定系統(tǒng)在t時刻的一個鄰域Φ(t)={(ω1(t),…,ωn(t))|(ω1(t),…,ωn(t))滿足條件S}，其中S可取為：

(3)

ωi=(xi(t),yi(t),zi(t))，i=1,2,…,n。

Ω(t)={(?1(t),…,?n(t))|(?1(t),…,?n(t))滿足條件S}，其中S為：

(4)

圖2 微分鄰域的幾何意義

如圖2所示，ACBEF代表的區(qū)域為被控對象t時刻的鄰域，經(jīng)過Δt時刻，其邊界曲線ACB段變化為ADB所代表的邊界曲線，則被控對象t時刻的微分鄰域為ADBEF表示的區(qū)域。

2 微分鄰域創(chuàng)建的一般模型

汽車在道路上行駛時，不僅會遇到靜止的障礙物，還會遇到運動著的障礙物，例如相對行駛的汽車、行人、突然躥出的小狗等。考慮到方法的類同性，下面主要針對同路行駛的車輛為障礙的情形進行研究。

為了更直觀地反映智能車在道路上的位向信息，設(shè)在世界坐標(biāo)系的基礎(chǔ)上以智能車前軸為x軸，縱向方向為y軸，前軸中點為原點建立一個相對直角坐標(biāo)系(參照圖3)。

圖3 微分領(lǐng)域示意圖

利用集合B可以得到t時刻的一個微分鄰域。此微分鄰域是由集合B中的n個點共同決定的，可以利用Lagrange插值、分段插值、牛頓插值等數(shù)值方法近似的得到微分鄰域邊界函數(shù)的表達式。為了簡單有效，本文采用Lagrange插值法[10-12]和分段線性插值法[13-15]進行處理。

對于t時刻的n個觀測量(X1(t),Y1(t)),(X2(t),Y2(t)),…,(Xn(t),Yn(t))，其微分鄰域Ω(t)= {(x(t),y(t))|(x(t),y(t))滿足條件S}，其中S由式(5)、(6)、(7)決定。

y(t)≤Pn(x)

(6)

(8)

其中(xA,yA)、(xB,yB)分別表示智能車左前輪、右前輪在相對坐標(biāo)系中的坐標(biāo)。

式(5)、(6)、(7)的幾何意義如圖3所示。其中，矩形ABCD為智能車的外形輪廓，ABFE代表的區(qū)域為當(dāng)前時刻智能車的可行鄰域，AE由式(5)確定，曲線EF由式(6)確定，BF由式(7)確定，則ABFE區(qū)域中的點滿足式(8)。

a) Lagrange插值法

(9)

b) 分段線性插值法

第二，數(shù)據(jù)組織、存儲和管理功能。該功能主要用于提高存儲空間利用率和方便存取效果，同時提供多種存取方法，如索引查找、Hash查找、順序查找等。

Lagrange插值法的數(shù)學(xué)思想清晰明了，其數(shù)學(xué)表達式是對稱的，易于記憶，且結(jié)構(gòu)緊湊，與各節(jié)點的順序無關(guān)。但是當(dāng)增加或者減少一個節(jié)點時，其表達式整體上都要發(fā)生改變，需要重新計算，大大增加了計算量；另一方面，多項式的次數(shù)會隨著節(jié)點數(shù)的增加而增加，增加了計算量且容易出現(xiàn)Runge現(xiàn)象，不利于有效的逼近被插函數(shù)。

而分段線性插值法是用折線將t時刻的n個觀測量兩兩相連，得到微分鄰域的邊界函數(shù)。分段線性插值法的計算簡潔方便，且增加或者減少一個節(jié)點時，只影響某局部范圍的表示式，很大程度上減少了計算量。基于算法的簡便性和實用性，本文采用分段線性插值法來近似微分鄰域邊界函數(shù)的表達式。

3 梯形微分鄰域的求解模型

由上述模型得到的微分鄰域一般為一個不規(guī)則的區(qū)域。在實際問題中，不規(guī)則的鄰域用于控制時對于控制規(guī)則的建立通常比較困難，不利于控制模型的建立，為了算法的簡便性，我們需要將不規(guī)則的微分鄰域化為規(guī)則的，其思想和做法如下。

a)分類

對于集合A={(x1(t),y1(t)),(x2(t),y2(t)),…,(xn(t),yn(t))}，考慮點的增量得到的集合為B={(X1(t),Y1(t)),(X2(t),Y2(t)),…,(Xn(t),Yn(t))}，根據(jù)B中元素的坐標(biāo)分量的增量對集合B進行分類，將分量的增量相等或相差某一個常數(shù)且滿足相鄰條件所對應(yīng)的點歸到一類，組成一個新的集合C={B1,B2,…,Bm}。對?Bj∈C，Bj由下述數(shù)學(xué)模型確定：

Bj={(Xj1(t),Yj1(t)),(Xj2(t),Yj2(t)),…,(Xjt(t),Yjt(t))}

對?Bj∈C，Bj為B的一個子集，即Bj?B，j=1,2,…,m，且Bj確定了t時刻的一個微分鄰域Ωj(t)，Ωj(t)={(x(t),y(t))|(x(t),y(t))滿足條件Sj}，其中Sj由式(5)、(7)、(9)確定，設(shè)(5)確定的直線為lj，(7)確定的直線為rj。

b)確定最優(yōu)鄰域

利用如下優(yōu)化模型從Ωj(t)選擇一個作為t時刻的微分鄰域：

max{min{|Yj1|，…，|Yjt|}}

(12)

其中d為被控對象的寬度，ε為某個大于零的常數(shù)。

c)對求解結(jié)果進行判斷

若b)中優(yōu)化模型的解存在，則轉(zhuǎn)到e)；若為空集，即Ωj(t)的寬度都小于被控對象的寬度，則進行下一步。

d)減少分類個數(shù)

通過減少B的分類個數(shù)來達到目標(biāo)，具體做法如下：

令D={B1∪B2,B2∪B3,…,Bm-1∪Bm}，即將相鄰的兩類歸為一類，將原來m類變?yōu)閙-1類。再由式(11)得到此優(yōu)化模型的解。若解為空集，則繼續(xù)減少B的分類個數(shù)，令E={B1∪B2∪B3,B2∪B3∪B4,…,Bm-2∪Bm-1∪Bm}，即將D中相鄰的兩類歸為一類，再由式(11)得到此優(yōu)化模型的解。若解為空集，繼續(xù)上述步驟，直到得到此優(yōu)化模型的解Ωp(t)，則Ωp(t)為t時刻的微分鄰域。

e)化不規(guī)則為規(guī)則

設(shè)Ωp(t)由點集{(Xp1(t),Yp1(t)),(Xp2(t),Yp2(t)),…(Xpr(t),Ypr(t))}確定。Ωp(t)的形狀一般情況下是不規(guī)則的，Ωp(t)={(x(t),y(t))|(x(t),y(t))滿足條件Sp}，其中Sp由式(5)(7)(9)確定。將不規(guī)則的Ωp(t)化為規(guī)則的梯形微分鄰域，以L1、L2作為梯形的兩邊，h作為梯形的高，得到一個梯形鄰域T(t)，即T(t)={ (x,y)| (x,y)滿足條件S}，其中S可取為：

(13)

其中(xA,yA)、(xB,yB)分別表示智能車左前輪、右前輪在相對坐標(biāo)系中的坐標(biāo)。

通過改變h得到一系列的梯形鄰域T(t)，然后取覆蓋粗糙集模型意義下的下近似作為t時刻的梯形微分鄰域。

4 基于動態(tài)障礙物的梯形微分鄰域求解的仿真

對于動態(tài)障礙物的梯形微分鄰域求解的仿真實現(xiàn)，本文利用正弦函數(shù)作為道路的邊界曲線函數(shù)來進行仿真，具體的方法參照文獻[7]，且令道路的寬度為7 m，再采用文獻[7]中的智能車的仿真模型，得到如圖4所示的仿真結(jié)果圖。

圖4 t時刻汽車的位置

圖5 t時刻傳感器采集到的點

在圖4中，編號為1的矩形代表的智能車為被控對象，編號為2、3的矩形代表的智能車為動態(tài)障礙物。同時，智能車1、2、3的速度分別為v1、v2、v3，對于智能車1而言，智能車3的速度比智能車1快，智能車2的速度比智能車1慢，即滿足v3>v1>v2。若車載傳感器在當(dāng)前時刻t采集到一組點集為：

A={(0.5,1.8),(0.75,1.93),(0.79,1.84),(0.81,1.66),(1.3,1.7),(1.32,1.6),(1.34,1.5),(1.36,1.4),(1.25,1.34),(1.25,1.16),(1.35,1.08)(1.17,1.02)}。

點集A如圖5中小實心黑點所示，利用上文中式(5)、(7)、(9)得到時刻t的可行鄰域，如圖6所示。

圖6 時刻t的可行鄰域

圖7 t+t時刻障礙點預(yù)測的變化位置

圖8 t時刻的微分鄰域

圖9 t時刻的微分鄰域

將得到的新的n個點利用上文式(5)、(7)、(9)，我們可以得到時刻t的微分可行鄰域，如圖8中虛線部分所示，更直觀的如圖9所示。

圖10 篩選出的微分鄰域

圖11 篩選出的微分鄰域

對于圖9得到的t時刻的微分鄰域，再利用上文中的梯形微分鄰域的求解模型對此微分鄰域進行篩選，得到如圖10所示的微分鄰域。篩選出的t時刻的微分鄰域更直觀的如圖11所示。

再利用梯形微分鄰域的求解模型對此微分鄰域進行規(guī)則化，得到如圖12所示的梯形微分鄰域。

圖12 t時刻的梯形微分鄰域

5 結(jié)語

本文利用微分鄰域固有的避障作用和覆蓋粗糙集模型的特點來處理動態(tài)障礙路況下智能車的控制，其方法為利用分段線性插值法得到微分鄰域邊界曲線的表達式，再基于鄰域的區(qū)域分類和覆蓋粗糙集模型的下近似得到梯形可行鄰域，達到了預(yù)測的效果，實現(xiàn)了保守且安全的控制，使智能車在行車過程中在保障安全的前提下能以較高的效率行駛。