江 怡

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

0 引言

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

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

圖1 實(shí)際道路中汽車的鄰域示意

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

1 基本概念

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

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

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

(1)

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

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

(2)

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

對(duì)于某系統(tǒng)中的被控對(duì)象，其上的傳感器在t時(shí)刻檢測(cè)到一組足夠密的數(shù)據(jù)(x1(t),y1(t),z1(t)),(x2(t),y2(t),z2(t)),…,(xn(t),yn(t),zn(t))，由這n個(gè)點(diǎn)可以確定系統(tǒng)在t時(shí)刻的一個(gè)鄰域Φ(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ū)域?yàn)楸豢貙?duì)象t時(shí)刻的鄰域，經(jīng)過Δt時(shí)刻，其邊界曲線ACB段變化為ADB所代表的邊界曲線，則被控對(duì)象t時(shí)刻的微分鄰域?yàn)锳DBEF表示的區(qū)域。

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

汽車在道路上行駛時(shí)，不僅會(huì)遇到靜止的障礙物，還會(huì)遇到運(yùn)動(dòng)著的障礙物，例如相對(duì)行駛的汽車、行人、突然躥出的小狗等?？紤]到方法的類同性，下面主要針對(duì)同路行駛的車輛為障礙的情形進(jìn)行研究。

為了更直觀地反映智能車在道路上的位向信息，設(shè)在世界坐標(biāo)系的基礎(chǔ)上以智能車前軸為x軸，縱向方向?yàn)閥軸，前軸中點(diǎn)為原點(diǎn)建立一個(gè)相對(duì)直角坐標(biāo)系(參照?qǐng)D3)。

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

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

對(duì)于t時(shí)刻的n個(gè)觀測(cè)量(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)分別表示智能車左前輪、右前輪在相對(duì)坐標(biāo)系中的坐標(biāo)。

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

a) Lagrange插值法

(9)

b) 分段線性插值法

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

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

而分段線性插值法是用折線將t時(shí)刻的n個(gè)觀測(cè)量兩兩相連，得到微分鄰域的邊界函數(shù)。分段線性插值法的計(jì)算簡潔方便，且增加或者減少一個(gè)節(jié)點(diǎn)時(shí)，只影響某局部范圍的表示式，很大程度上減少了計(jì)算量?；谒惴ǖ暮啽阈院蛯?shí)用性，本文采用分段線性插值法來近似微分鄰域邊界函數(shù)的表達(dá)式。

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

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

a)分類

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

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

對(duì)?Bj∈C，Bj為B的一個(gè)子集，即Bj?B，j=1,2,…,m，且Bj確定了t時(shí)刻的一個(gè)微分鄰域Ω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)選擇一個(gè)作為t時(shí)刻的微分鄰域：

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

(12)

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

c)對(duì)求解結(jié)果進(jìn)行判斷

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

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

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

令D={B1∪B2,B2∪B3,…,Bm-1∪Bm}，即將相鄰的兩類歸為一類，將原來m類變?yōu)閙-1類。再由式(11)得到此優(yōu)化模型的解。若解為空集，則繼續(xù)減少B的分類個(gè)數(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時(shí)刻的微分鄰域。

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

設(shè)Ωp(t)由點(diǎn)集{(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作為梯形的高，得到一個(gè)梯形鄰域T(t)，即T(t)={ (x,y)| (x,y)滿足條件S}，其中S可取為：

(13)

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

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

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

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

圖4 t時(shí)刻汽車的位置

圖5 t時(shí)刻傳感器采集到的點(diǎn)

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

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)}。

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

圖6 時(shí)刻t的可行鄰域

圖7 t+t時(shí)刻障礙點(diǎn)預(yù)測(cè)的變化位置

圖8 t時(shí)刻的微分鄰域

圖9 t時(shí)刻的微分鄰域

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

圖10 篩選出的微分鄰域

圖11 篩選出的微分鄰域

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

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

圖12 t時(shí)刻的梯形微分鄰域

5 結(jié)語

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