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

江 怡

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

0 引言

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

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

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

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

1 基本概念

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

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

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

(1)

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

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

(2)

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

對于某系統中的被控對象，其上的傳感器在t時刻檢測到一組足夠密的數據(x1(t),y1(t),z1(t)),(x2(t),y2(t),z2(t)),…,(xn(t),yn(t),zn(t))，由這n個點可以確定系統在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代表的區域為被控對象t時刻的鄰域，經過Δt時刻，其邊界曲線ACB段變化為ADB所代表的邊界曲線，則被控對象t時刻的微分鄰域為ADBEF表示的區域。

2 微分鄰域創建的一般模型

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

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

圖3 微分領域示意圖

利用集合B可以得到t時刻的一個微分鄰域。此微分鄰域是由集合B中的n個點共同決定的，可以利用Lagrange插值、分段插值、牛頓插值等數值方法近似的得到微分鄰域邊界函數的表達式。為了簡單有效，本文采用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)分別表示智能車左前輪、右前輪在相對坐標系中的坐標。

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

a) Lagrange插值法

(9)

b) 分段線性插值法

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

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

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

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

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

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))}，根據B中元素的坐標分量的增量對集合B進行分類，將分量的增量相等或相差某一個常數且滿足相鄰條件所對應的點歸到一類，組成一個新的集合C={B1,B2,…,Bm}。對?Bj∈C，Bj由下述數學模型確定：

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)確定，設(5)確定的直線為lj，(7)確定的直線為rj。

b)確定最優鄰域

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

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

(12)

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

c)對求解結果進行判斷

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

d)減少分類個數

通過減少B的分類個數來達到目標，具體做法如下：

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

e)化不規則為規則

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

(13)

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

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

4 基于動態障礙物的梯形微分鄰域求解的仿真

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

圖4 t時刻汽車的位置

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

在圖4中，編號為1的矩形代表的智能車為被控對象，編號為2、3的矩形代表的智能車為動態障礙物。同時，智能車1、2、3的速度分別為v1、v2、v3，對于智能車1而言，智能車3的速度比智能車1快，智能車2的速度比智能車1慢，即滿足v3>v1>v2。若車載傳感器在當前時刻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時刻障礙點預測的變化位置

圖8 t時刻的微分鄰域

圖9 t時刻的微分鄰域

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

圖10 篩選出的微分鄰域

圖11 篩選出的微分鄰域

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

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

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

5 結語

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