劉長(zhǎng)吉,黃宴委
(福州大學(xué) 電氣工程與自動(dòng)化學(xué)院,福州 350116)
近年來,無人船得到越來越多的關(guān)注,其中路徑規(guī)劃是無人船研究領(lǐng)域的關(guān)鍵問題之一。路徑規(guī)劃旨在從障礙物環(huán)境中,找到一條從起始位置到目標(biāo)位置的無碰撞可行路徑。關(guān)于路徑規(guī)劃的研究有很多,使用了各種方法。每種方法在不同的環(huán)境中,都有其優(yōu)缺點(diǎn)。遺傳算法最初是由Holland提出的[1],被認(rèn)為是一種啟發(fā)式的,魯棒性強(qiáng)的優(yōu)化技術(shù),在大多數(shù)優(yōu)化問題中都能取得較好的效果[2]。Yao Z等人將遺傳算法應(yīng)用于靜態(tài)環(huán)境下移動(dòng)機(jī)器人的路徑規(guī)劃問題中[3],提出一個(gè)算術(shù)適應(yīng)度函數(shù)和兩個(gè)自定義遺傳算子,結(jié)果表明該方法在簡(jiǎn)單的環(huán)境中能夠較快獲得最優(yōu)解,但在復(fù)雜的環(huán)境中難以獲得最優(yōu)解。Zhang X等人提出一種改進(jìn)的遺傳算法[4],該方法利用可見空間的概念獲取初始種群,并提出兩種新的變異方法保證算法收斂到全局最優(yōu)解,雖然該方法在復(fù)雜環(huán)境下能獲得最優(yōu)解,但是計(jì)算過于復(fù)雜。Tuncer等人提出一種新的變異算子[5],該方法從離突變節(jié)點(diǎn)較近的所有自由節(jié)點(diǎn)集合中隨機(jī)選取一個(gè)節(jié)點(diǎn),然后根據(jù)適應(yīng)度函數(shù)值選取突變節(jié)點(diǎn),與其他方法相比,該方法的收斂速度較快效果較好。然而上述路徑規(guī)劃方法所生成的路徑都是由線段組成的,并不是光滑的路徑,這將迫使無人船在轉(zhuǎn)折角處停止,轉(zhuǎn)彎,重新啟動(dòng)才能沿著規(guī)劃好的路徑航行[6]。因此必須使路徑變得光滑。近十年來,貝塞爾曲線在光滑路徑規(guī)劃問題中得到越來越多的應(yīng)用[7-9]。Baoye等人提出一種新的移動(dòng)機(jī)器人平滑路徑規(guī)劃遺傳算法[9],該方法用于尋找最優(yōu)控制點(diǎn),確定基于貝塞爾曲線的光滑路徑。值得注意的是,這些方法著重于對(duì)遺傳算子的改進(jìn)和路徑光滑程度處理,而未考慮到實(shí)際機(jī)器人的機(jī)動(dòng)性能。由于無人船是一個(gè)高度欠驅(qū)動(dòng)的系統(tǒng)[10],因此在無人船航徑規(guī)劃中必須考慮無人船的機(jī)動(dòng)性能。
本文提出一種基于適應(yīng)度函數(shù)的無人船遺傳算法航徑規(guī)劃方法。在初始種群中,以染色體的路徑點(diǎn)作為貝塞爾曲線的控制點(diǎn),利用貝塞爾曲線優(yōu)化方法,將初始的折線路徑變成光滑的曲線路徑;在路徑選擇中,以無人船最小轉(zhuǎn)彎半徑為約束條件,設(shè)置路徑的最大曲率,在適應(yīng)度函數(shù)中添加曲率判斷,利用適應(yīng)度函數(shù)選擇出符合約束條件的曲線路徑。在仿真實(shí)驗(yàn)中,采用基于網(wǎng)格圖的方法構(gòu)建規(guī)劃環(huán)境,驗(yàn)證所提出方法的有效性。
本節(jié)在遺傳算法的初始種群中利用貝塞爾曲線,對(duì)初始種群生成的折線路徑進(jìn)行平滑優(yōu)化,在適應(yīng)度函數(shù)中添加曲率判斷,以最小轉(zhuǎn)彎半徑為約束條件設(shè)置曲線曲率,利用適應(yīng)度函數(shù)篩選出符合最小轉(zhuǎn)彎半徑約束的曲線路徑。改進(jìn)的遺傳算法路徑規(guī)劃流程圖如圖1所示。
圖1 改進(jìn)遺傳算法路徑規(guī)劃流程圖
將改進(jìn)遺傳算法應(yīng)用在路徑規(guī)劃問題中,主要分為以下幾個(gè)步驟:首先,先構(gòu)建路徑規(guī)劃所需要的規(guī)劃空間;然后根據(jù)染色體的編碼方式生成初始種群;緊接著將生成的初始種群中的染色體經(jīng)過貝塞爾曲線優(yōu)化;然后根據(jù)適應(yīng)度函數(shù)計(jì)算初始種群中染色體的適應(yīng)度值,并根據(jù)染色體適應(yīng)度值的大小對(duì)染色體進(jìn)行選擇;將選擇出的染色體經(jīng)過交叉和變異操作,以產(chǎn)生出適應(yīng)度值更佳的染色體,最后經(jīng)過不斷迭代,當(dāng)?shù)螖?shù)到達(dá)預(yù)期的次數(shù)時(shí),則停止迭代根據(jù)適應(yīng)度函數(shù)值篩選出最終的最優(yōu)路徑。
規(guī)劃空間指的是無人船路徑規(guī)劃所需要的環(huán)境區(qū)域,包含障礙物區(qū)域和無障礙物區(qū)域?,F(xiàn)有的路徑規(guī)劃方法大都使用網(wǎng)格圖的方法來表示規(guī)劃空間[4-5,11-12]。如圖2所示,白色網(wǎng)格表示自由區(qū)域,灰色網(wǎng)格表示障礙物區(qū)域。本文采用矩陣編碼的方法來表示網(wǎng)格位置[4],網(wǎng)格的位置由行索引和列索引決定。例如,b1,3表示第一行第三列的網(wǎng)格位置。
圖2 規(guī)劃空間示例
染色體表示在路徑規(guī)劃問題中生成的候選路徑。染色體是由起始節(jié)點(diǎn),目標(biāo)節(jié)點(diǎn)和無人船航行過程中所經(jīng)過的節(jié)點(diǎn)組成。這些節(jié)點(diǎn)通常被稱為染色體的基因。常用的染色體編碼方法主要有二進(jìn)制編碼,浮點(diǎn)數(shù)編碼,十進(jìn)制編碼和字符編碼。本文使用文獻(xiàn)[4]中的編碼方法來表示染色體,該方法對(duì)字符編碼進(jìn)行了一些改進(jìn),使其不需要解碼,并且能更直觀的表示各個(gè)節(jié)點(diǎn)的位置信息,如圖3所示。
圖3 染色體示例
傳統(tǒng)遺傳算法中初始種群的生成方式一般采用隨機(jī)生成的方法,即隨機(jī)生成一系列染色體。但在路徑規(guī)劃中,這些隨機(jī)生成的染色體可能包含一些不可行的路徑,導(dǎo)致這些路徑與障礙物相交。雖然通過遺傳算子不斷迭代的過程最終也能找到最優(yōu)解或接近最優(yōu)解。但這一迭代過程降低了算法的搜索速度,并增加了算法的計(jì)算時(shí)間。為了解決這個(gè)問題,將從自由區(qū)域中隨機(jī)選擇染色體的節(jié)點(diǎn)。首先在染色體生成之前先獲取障礙物區(qū)域,由于規(guī)劃空間采用矩陣編碼的方法表示,可以快速獲取障礙物的形狀和位置。然后從障礙物區(qū)域以外的自由區(qū)域中隨機(jī)選擇節(jié)點(diǎn)生成初始路徑。如圖3表示初始種群中的一條染色體,其中b1,1表示起始位置,b6,6表示目標(biāo)位置,b4,1,b4,4和b6,4表示所經(jīng)過的路徑點(diǎn)。
由于遺傳算法生成的路徑是折線路徑,并不是光滑的曲線路徑,如圖4所示。如果無人船沿著規(guī)劃好的折線路徑航行時(shí),必須在每個(gè)轉(zhuǎn)彎點(diǎn)停下來調(diào)整航向角再重新加速航行,這一過程既占用時(shí)間又損耗機(jī)器性能。因此,必須把折線路徑變成光滑的曲線路徑,使無人船無需停止調(diào)整航向角就能夠沿著規(guī)劃好的路徑航行。本文采用貝塞爾曲線來改進(jìn)初始種群平滑優(yōu)化,貝塞爾曲線是通過線性插值的方法來實(shí)現(xiàn)的,它能簡(jiǎn)潔完美的表達(dá)自由曲線和曲面,在計(jì)算機(jī)圖形學(xué)中得到了廣泛的應(yīng)用。因此,貝塞爾曲線是一種很好的曲線擬合工具。下面將介紹貝塞爾曲線實(shí)現(xiàn)的主要方法,首先將初始種群中染色體的n個(gè)路徑點(diǎn)當(dāng)做貝塞爾曲線的控制點(diǎn)p(j),j=0,1,2,…,n。如p(j)=(b1,1,b4,1,b4,4,b6,4,b6,6)是初始種群中的一條染色體,p(0)表示染色體中的第一個(gè)路徑點(diǎn)b1,1。貝塞爾曲線由這些路徑點(diǎn)定義如下:
(1)
其中:t是歸一化時(shí)間變量,p(j)=(xj,yj)T表示染色體中第j個(gè)路徑點(diǎn)的坐標(biāo)向量,xj和yj分別對(duì)應(yīng)x坐標(biāo)和y坐標(biāo)的分量,Bj,n(t)是伯恩斯坦基多項(xiàng)式表示貝塞爾曲線中的基函數(shù),定義如下:
j=0,1,2,...,n
(2)
優(yōu)化后的路徑如圖3實(shí)線路徑所示。貝塞爾曲線的導(dǎo)數(shù)也是由這些路徑點(diǎn)確定的,貝塞爾曲線的一階導(dǎo)數(shù)如下所示:
(3)
貝塞爾曲線的高階導(dǎo)數(shù)也可以通過計(jì)算得到。例如,貝塞爾曲線的二階導(dǎo)數(shù)表示為:
P″(t)=
(4)
在二維空間中,貝塞爾曲線關(guān)于t的曲率表示為:
(5)
圖4 初始路徑示例
無人船路徑規(guī)劃問題的目的是從起始位置到目標(biāo)位置之間找到一條最優(yōu)的無碰撞路徑。遺傳算法是通過適應(yīng)度函數(shù)來選擇路徑的,所以在適應(yīng)度函數(shù)中必須考慮路徑的平滑性和可行性。因此適應(yīng)度函數(shù)的選取至關(guān)重要,本文的一個(gè)關(guān)鍵概念是在適應(yīng)度函數(shù)中考慮無人船的機(jī)動(dòng)能力。由于無人船的轉(zhuǎn)彎半徑是有限的,為了保證路徑可行,只需對(duì)路徑的曲率進(jìn)行約束[13],無人船可行駛路徑的最大曲率可以表示為:
(6)
其中:Rmin是無人船的最小轉(zhuǎn)彎半徑。以此為約束條件,從優(yōu)化后的貝塞爾曲線路徑中篩選出符合最大曲率約束的路徑。遺傳算法是通過適應(yīng)度函數(shù)來選擇路徑的。因此,必須在適應(yīng)度函數(shù)中添加曲率判斷,定義如下:
(7)
d[p(j),p(j+1)]=
(8)
其中:f是適應(yīng)度函數(shù),p(j)是染色體上的第j個(gè)路徑點(diǎn),d是兩個(gè)節(jié)點(diǎn)之間的距離,xj和yj表示無人船當(dāng)前的水平和垂直位置,x( j+1)和y( j+1)表示無人船下一個(gè)路徑點(diǎn)的水平和垂直位置,k(t)是貝塞爾曲線的曲率計(jì)算公式,penalty是懲罰值。適應(yīng)度函數(shù)定義為路徑中每個(gè)路徑點(diǎn)之間的距離和路徑的曲率之和。如果路徑與障礙物相交,則在適應(yīng)度函數(shù)中加上一個(gè)懲罰值;如果路徑的曲率k(t)大于最大曲率kmax,則在適應(yīng)度函數(shù)上加上一個(gè)懲罰值,懲罰值必須大于工作環(huán)境中的最大路徑長(zhǎng)度。最后通過適應(yīng)度值的選取來篩選出符合曲率約束的路徑,適應(yīng)度值越小越好。
選擇算子的主要目的是通過適應(yīng)度函數(shù)值將初始種群中適應(yīng)度值較好的染色體保存下來,并移交給下一代。染色體的選擇過程主要分為三個(gè)步驟:第一步通過適應(yīng)度函數(shù)計(jì)算所有染色體的適應(yīng)度函數(shù)值;第二步將計(jì)算出的適應(yīng)度函數(shù)值按從小到大的順序進(jìn)行排序,并與各自對(duì)應(yīng)的染色體進(jìn)行配對(duì);第三步是根據(jù)適應(yīng)度函數(shù)值選擇適應(yīng)度值較小的染色體放入交配池中以產(chǎn)生新的染色體。交配池中包含兩個(gè)算子,一個(gè)是交叉算子,一個(gè)是變異算子。下面先介紹交叉算子,交叉算子的目的是交換染色體間的基因以產(chǎn)生新的染色體,避免陷入局部最優(yōu)解。本文采用單點(diǎn)交叉算子,從交配池中隨機(jī)選擇兩個(gè)染色體當(dāng)父代染色體,在父代中隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為交叉點(diǎn),將交叉點(diǎn)后的兩個(gè)父代染色體的基因相互交換。換句話說就是,第一個(gè)子代染色體是由第一個(gè)父代交叉點(diǎn)前的基因和第二個(gè)父代交叉點(diǎn)后的基因構(gòu)成的。第二個(gè)子代染色體是由第二個(gè)父代交叉點(diǎn)前的基因和第一個(gè)父代交叉點(diǎn)后的基因構(gòu)成的。交叉過程如圖5所示。
圖5 交叉過程
變異算子的目的是增加種群的多樣性,避免過早收斂的現(xiàn)象。本文的變異算子是基于文獻(xiàn)[5]中提出的。在現(xiàn)有的文獻(xiàn)研究中[3,11-12,14],該算子具有較好的效果。該方法首先從突變的染色體中隨機(jī)選擇一個(gè)不是起始或目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)作為突變節(jié)點(diǎn)。然后,定義一個(gè)集合,該集合由突變節(jié)點(diǎn)的所有可行鄰居點(diǎn)組成,由于采用矩陣編碼,可以很快獲得突變節(jié)點(diǎn)的鄰居集合。再依次從鄰居集合中選取一個(gè)節(jié)點(diǎn)代替突變節(jié)點(diǎn),并計(jì)算所有路徑的適應(yīng)度值。最后,選擇適應(yīng)度值最小的路徑節(jié)點(diǎn)替換原始突變節(jié)點(diǎn)。
本實(shí)驗(yàn)使用Python編程實(shí)現(xiàn),并運(yùn)行在一臺(tái)Intel Core i7處理器和8 GB內(nèi)存的計(jì)算機(jī)上。為了驗(yàn)證該方法的有效性,將其應(yīng)用于16×16的網(wǎng)格圖中,并與文獻(xiàn)[9]的方法進(jìn)行比較,其中包含12個(gè)障礙物區(qū)域,起始點(diǎn)位置為(1,1),目標(biāo)點(diǎn)位置為(15,15)。主要參數(shù)如下:無人船最小轉(zhuǎn)彎半徑Rmin=0.2 m,則最大曲率kmax=5 m-1,在[0,1]區(qū)間構(gòu)造具有80個(gè)樣本數(shù)的等差數(shù)列作為伯恩斯坦基多項(xiàng)式t的值,種群大小取80,最大迭代次數(shù)取100,交叉概率為1,變異概率為0.3,對(duì)于每個(gè)不可行路徑的罰值取100。如圖6為遺傳算法、平滑算法和本文方法在相同環(huán)境下形成的路徑比較。從圖中可以看出遺傳算法生成的路徑是折線路徑,并不適合無人船航行。平滑算法只對(duì)路徑進(jìn)行平滑優(yōu)化,并未添加曲率約束。使用本文方法生成的路徑更為平滑,曲率更小。圖7為平滑算法和本文方法生成路徑的曲率比較,從圖中可以看出平滑算法生成的路徑曲率過大,并不能滿足無人船最大曲率約束的曲線曲率,而本文算法生成路徑的曲率明顯小于最大曲率約束,因此可以得出本文方法生成的曲線路徑是符合無人船最小轉(zhuǎn)彎半徑約束的。圖8給出了平滑算法和本文方法每代最優(yōu)染色體的適應(yīng)度函數(shù)值,可以看出本文方法的收斂性更快。表1為平滑算法和本文方法的性能指標(biāo)對(duì)比,性能指標(biāo)有3個(gè):(1)最大曲率,用來評(píng)估路徑是否符合無人船最小轉(zhuǎn)彎半徑約束,該值小于5表示路徑符合無人船最小轉(zhuǎn)彎半徑約束;(2)平均適應(yīng)度函數(shù)值,該值是路徑長(zhǎng)度和曲率之和,該值越小表示路徑越短。(3)平均搜索時(shí)間,用來評(píng)估算法的時(shí)間性能,該值越小表示算法搜索時(shí)間越快。從表中看出本文方法生成的路徑符合無人船最小轉(zhuǎn)彎半徑約束,平均適應(yīng)度值和平均搜索時(shí)間均優(yōu)于平滑算法,說明本文方法性能更好。
圖6 路徑效果對(duì)比
圖7 路徑曲率比較
圖8 適應(yīng)度函數(shù)值比較
表1 平滑算法與本文算法的性能比較
最大曲率(1/m)平均適應(yīng)度值平均搜索時(shí)間/s平滑算法16.6360.710.76本文方法0.3052.350.59
本文提出一種基于適應(yīng)度函數(shù)的無人船遺傳算法航徑規(guī)劃方法,為了使遺傳算法生成的折線路徑變成曲線路徑,在遺傳算法初始種群中結(jié)合貝塞爾曲線優(yōu)化方法。在算法中考慮無人船機(jī)動(dòng)性能對(duì)航跡的約束,以最小轉(zhuǎn)彎半徑為約束條件設(shè)置最大曲率,利用適應(yīng)度函數(shù)篩選出符合無人船最小轉(zhuǎn)彎半徑約束的曲線路徑。通過仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了該方法生成的路徑能滿足無人船最小轉(zhuǎn)彎半徑的約束,更有利于無人船跟蹤航行。