李開榮, 胡倩倩

(揚(yáng)州大學(xué)信息工程學(xué)院, 江蘇 揚(yáng)州 225127)

近年來, 移動(dòng)機(jī)器人被廣泛應(yīng)用于各種生活場(chǎng)景．路徑規(guī)劃作為移動(dòng)機(jī)器人實(shí)現(xiàn)自主運(yùn)動(dòng)的關(guān)鍵技術(shù),是當(dāng)前移動(dòng)機(jī)器人領(lǐng)域最活躍的研究方向之一[1]．遺傳算法(genetic algorithm,GA)因其良好的擴(kuò)展性、魯棒性及快速隨機(jī)的搜索能力而成為移動(dòng)機(jī)器人路徑規(guī)劃研究的熱點(diǎn)方法[2]．然而,傳統(tǒng)的遺傳算法不僅收斂速度慢,而且易陷入早熟收斂．Zhang[3]通過對(duì)矩陣編碼和改進(jìn)變異算子,提出一種基于可見空間的改進(jìn)遺傳算法;Lamini等[4]提出一種改進(jìn)的同鄰域交叉算子求解機(jī)器人路徑規(guī)劃問題,有效避免了算法早熟收斂;宋宇等[5]采用快速擴(kuò)展隨機(jī)樹(rapidly-exploring random trees, RRT)算法生成初始路徑,并提出一種插入優(yōu)化算子有效改進(jìn)了傳統(tǒng)遺傳算法,得到不同環(huán)境下的全局最優(yōu)路徑;易欣等[6]提出一種基于元啟發(fā)式-自適應(yīng)遺傳算法,利用隨機(jī)Dijkstra算法創(chuàng)建初始種群,并采用自適應(yīng)算子代替常規(guī)選擇算子,有效避免了路徑規(guī)劃中的局部收斂問題．由于生產(chǎn)實(shí)際對(duì)移動(dòng)機(jī)器人運(yùn)行路徑的平滑性和安全性提出了更高要求,故越來越多的國(guó)內(nèi)外學(xué)者在移動(dòng)機(jī)器人的路徑規(guī)劃研究中引入曲線思想．Costanzi等[7]以移動(dòng)機(jī)器人的平面路徑規(guī)劃為研究對(duì)象,結(jié)合Bezier曲線,根據(jù)長(zhǎng)度和曲率對(duì)計(jì)算出的路徑進(jìn)行優(yōu)化,得到更為平滑的最優(yōu)路徑;徐巖等[8]運(yùn)用基于Q值的交互式遺傳算法(Q-standard improved genetic algorithm,Q-IGA)動(dòng)態(tài)搜索貝塞爾曲線控制點(diǎn),同時(shí)進(jìn)行路徑與控制點(diǎn)搜索,使得規(guī)劃出的路徑是一條距離較短且與障礙物保持安全距離的合理路徑,并降低機(jī)器人能耗,減少搜索時(shí)間;Ma等[9]基于Bezier曲線提出一種平滑路徑規(guī)劃算法(Bezier curve-smoothing algorithm, BCA),該算法在較長(zhǎng)的運(yùn)算時(shí)間下能夠得出一條無碰撞的最優(yōu)曲線運(yùn)行路徑．上述方法均未充分考慮算法的各個(gè)環(huán)節(jié)以及最優(yōu)路徑的平滑優(yōu)化問題,且大部分改進(jìn)算法的復(fù)雜度較高、運(yùn)行效率較低．本文通過對(duì)Bezier曲線進(jìn)行平滑優(yōu)化處理,提出一種融合Bezier的改進(jìn)遺傳算法以期快速規(guī)劃出移動(dòng)機(jī)器人在運(yùn)行環(huán)境中的最優(yōu)可行路徑和提高移動(dòng)機(jī)器人的運(yùn)行效率．

1 環(huán)境建模與路徑編碼

采用柵格法建立機(jī)器人的運(yùn)行環(huán)境模型,并做如下規(guī)定[10]:

1) 將移動(dòng)機(jī)器人視為一個(gè)質(zhì)點(diǎn), 并限定機(jī)器人的移動(dòng)空間為二維平面;

2) 在構(gòu)建的柵格地圖中所有障礙物均為靜態(tài)障礙物, 其大小和位置已知且不考慮其高度;

3) 如果障礙物大小不滿一個(gè)柵格, 則將其鋪滿該柵格, 并視為一個(gè)完整的障礙柵格進(jìn)行建模．

通過合理設(shè)計(jì)柵格的大小和數(shù)目, 建立如圖1所示的地圖模型, 其中柵格節(jié)點(diǎn)S,G分別為移動(dòng)機(jī)器人運(yùn)行的起始點(diǎn)和目標(biāo)點(diǎn),黑色為障礙柵格, 白色為自由柵格．由于整個(gè)柵格地圖處于一個(gè)直角坐標(biāo)系中, 故每一個(gè)柵格節(jié)點(diǎn)的序列號(hào)N均可與一個(gè)路徑點(diǎn)坐標(biāo)(x,y)對(duì)應(yīng)．假設(shè)柵格圖的大小為n×n, 則柵格序號(hào)和柵格坐標(biāo)的對(duì)應(yīng)關(guān)系為

圖1 移動(dòng)機(jī)器人運(yùn)行環(huán)境模型Fig.1 Mobile robot running environment model

(1)

為了盡可能縮短編碼長(zhǎng)度,本文采用柵格節(jié)點(diǎn)的序列號(hào)進(jìn)行編碼,并規(guī)定任意一條可行路徑的編碼序號(hào)都不能包含重復(fù)序號(hào)和障礙柵格所對(duì)應(yīng)的序號(hào)．由圖1可見,某一條可行路徑可表示為S-41-70-G．

2 本文算法

2.1 算法設(shè)計(jì)流程

首先對(duì)傳統(tǒng)遺傳算法的部分環(huán)節(jié)進(jìn)行改進(jìn),然后在改進(jìn)遺傳算法的基礎(chǔ)上引入Bezier曲線的概念,具體流程如下:

1) 初始化參數(shù), 采用柵格法建模,對(duì)節(jié)點(diǎn)序列號(hào)編碼;

2) 利用啟發(fā)式中值插入法建立初始種群, 生成M條初始可行路徑;

3) 根據(jù)多目標(biāo)適應(yīng)度函數(shù)計(jì)算每條初始路徑的適應(yīng)度值F(N);

4) 對(duì)路徑適應(yīng)度值排序,采用分層法選擇優(yōu)勢(shì)路徑個(gè)體并直接遺傳至下一代;

5) 根據(jù)交叉概率選擇一定數(shù)量的路徑個(gè)體進(jìn)行單點(diǎn)交叉操作;

6) 根據(jù)變異概率選擇一定數(shù)量的路徑個(gè)體進(jìn)行八鄰域單點(diǎn)變異操作;

7) 初始可行路徑在經(jīng)過遺傳操作后生成子代路徑．計(jì)算子代路徑個(gè)體的適應(yīng)度值,判斷改進(jìn)遺傳算法是否達(dá)到終止條件,若達(dá)到, 則該子代個(gè)體為最優(yōu)折線路徑,否則回到步驟3)循環(huán)遺傳操作;

8) 采用平滑優(yōu)化操作,以最優(yōu)折線路徑的路徑序列點(diǎn)作為Bezier曲線的控制點(diǎn)生成一條平滑曲線路徑;

9) 若平滑曲線路徑與障礙物發(fā)生碰撞, 則啟動(dòng)重規(guī)劃操作并新增控制點(diǎn)使曲線不斷貼近原折線路徑,直到消除曲線與障礙物的碰撞情況;

10) 輸出單移動(dòng)機(jī)器人的無碰撞最優(yōu)曲線路徑．

步驟1)～7)的目的是根據(jù)改進(jìn)遺傳算法生成最優(yōu)折線路徑, 步驟8)～10)則基于Bezier曲線對(duì)改進(jìn)遺傳算法生成的最優(yōu)折線路徑進(jìn)行平滑優(yōu)化操作, 輸出結(jié)果即全局最優(yōu)曲線路徑．由此可見, 融合Bezier遺傳算法的時(shí)間復(fù)雜度由遺傳算子、適應(yīng)度函數(shù)以及平滑操作共同決定, 整個(gè)算法的時(shí)間復(fù)雜度為O(OF(Ops+Opc+Opm)+OS), 其中OF為適應(yīng)度函數(shù)的復(fù)雜度,Ops,Opc,Opm分別為選擇、交叉、變異操作的時(shí)間復(fù)雜度,OS為平滑操作的時(shí)間復(fù)雜度．本文提出的分層選擇法較傳統(tǒng)輪盤賭算法的時(shí)間復(fù)雜度小, 適應(yīng)度函數(shù)雖考慮了多個(gè)指標(biāo), 但每個(gè)指標(biāo)的衡量方法都較精簡(jiǎn), 且平滑操作僅針對(duì)改進(jìn)遺傳算法生成的最優(yōu)解; 因此, 融合Bezier遺傳算法的時(shí)間復(fù)雜度僅在傳統(tǒng)遺傳算法的基礎(chǔ)上增加了1次OS．

2.2 初始化種群

采用一種啟發(fā)式中值插入法建立初始種群, 避免隨機(jī)生成法所致不可行路徑比重過大的問題, 具體過程如下:

1) 確定種群大小M;

2) 確定柵格地圖的大小n×n、移動(dòng)機(jī)器人路徑規(guī)劃的起始點(diǎn)S、目標(biāo)點(diǎn)G以及障礙柵格的數(shù)目f;

3) 生成M個(gè)從起始點(diǎn)S到目標(biāo)點(diǎn)G的路徑染色體:

① 隨機(jī)生成一個(gè)柵格序號(hào)Ni(Ni不屬于起點(diǎn)、終點(diǎn)或障礙柵格), 此時(shí)機(jī)器人的路徑可表示為S-Ni-G;

② 判斷路徑中相鄰節(jié)點(diǎn)是否連續(xù):

Δ=max{|xi+1-xi|, |yi+1-yi|},

(2)

其中(xi,yi), (xi+1,yi+1)分別為兩個(gè)相鄰路徑點(diǎn)Ni和Ni+1的直角坐標(biāo)．如果Δ=1, 則Ni和Ni+1是連續(xù)的, 否則兩點(diǎn)不連續(xù)．此時(shí), 通過中值法選擇下一個(gè)插入點(diǎn)填補(bǔ)間斷路徑,計(jì)算式如下:

(3)

圖2 八鄰域節(jié)點(diǎn)Fig.2 Eight neighborhood nodes

其中(x′i,y′i)為候補(bǔ)柵格坐標(biāo),d為柵格的行或列數(shù),N′i為候補(bǔ)柵格序號(hào)．如果計(jì)算所得N′i為自由柵格,則直接插入Ni與Ni+1之間, 否則隨機(jī)選取N′i的八鄰域節(jié)點(diǎn)中的自由柵格作為新插入的節(jié)點(diǎn)．節(jié)點(diǎn)N四周灰色區(qū)域即其八鄰域, 如圖2所示．若N′i的八鄰域中沒有自由柵格, 則表明本次操作無效, 可直接舍棄該個(gè)體．重復(fù)上述插入步驟, 以生成一條連續(xù)的可行路徑;

③ 不斷進(jìn)行以上操作,直至產(chǎn)生一個(gè)有M條不重復(fù)染色體的初始種群．

2.3 適應(yīng)度函數(shù)

為了在確保算法復(fù)雜度較小的同時(shí)加快遺傳算法的收斂, 并維持個(gè)體間的合理差距,找出能夠平穩(wěn)避開障礙物且快速到達(dá)目標(biāo)點(diǎn)的最優(yōu)路徑,現(xiàn)設(shè)計(jì)基于路徑長(zhǎng)度L(N)、路徑安全性S(N)和路徑能耗E(N)的多目標(biāo)適應(yīng)度函數(shù):

(4)

其中a,b,c分別為指標(biāo)L(N),S(N),E(N)的權(quán)重,a+b+c=10．路徑長(zhǎng)度為所有相鄰節(jié)點(diǎn)間的歐氏距離之和,

(5)

其中n為路徑節(jié)點(diǎn)的數(shù)量．路徑安全性函數(shù)

(6)

其中Si為節(jié)點(diǎn)i的安全性懲罰值．以路徑節(jié)點(diǎn)的八鄰域作為衡量該點(diǎn)與周圍障礙物之間的安全距離標(biāo)準(zhǔn), 如果某一路徑節(jié)點(diǎn)的八鄰域中不存在障礙柵格, 則該點(diǎn)為安全移動(dòng)點(diǎn); 否則,該點(diǎn)存在安全隱患,Si懲罰值加1．路徑能耗函數(shù)

(7)

圖3 移動(dòng)機(jī)器人拐彎方向?qū)?yīng)象限圖Fig.3 Quadrant map of mobile robot turning direction

其中Ei為節(jié)點(diǎn)i的能耗懲罰值,l表示路徑段．移動(dòng)機(jī)器人拐彎方向?qū)?yīng)象限如圖3所示．由圖3可見, 如果機(jī)器人在i點(diǎn)拐彎, 則以i點(diǎn)為原點(diǎn),i點(diǎn)的橫縱坐標(biāo)所在方向即分界線劃分象限．機(jī)器人發(fā)生拐彎且前進(jìn)方向在第二象限,Ei能耗懲罰值加1; 機(jī)器人前進(jìn)方向在第一象限或第四象限,Ei能耗懲罰值加3; 機(jī)器人前進(jìn)方向在第三象限,Ei能耗懲罰值加10．

2.4 遺傳操作

1) 選擇．初始化種群后共生成M個(gè)個(gè)體, 根據(jù)適應(yīng)度函數(shù)計(jì)算每個(gè)個(gè)體的適應(yīng)度值并按降序排列．將種群分為3等份, 每一份為一層．按序?qū)⒌谝粚舆m應(yīng)度值較大的一等份復(fù)制2份, 將第二層適應(yīng)度值中等的一等份復(fù)制1份, 最后一層適應(yīng)度較小的不復(fù)制, 從而形成子代種群．這樣既能保證優(yōu)秀的個(gè)體能夠遺傳到下一代, 又能維持種群的多樣性．其選擇方式如圖4所示．

圖4 選擇操作示意圖Fig.4 Select operation diagram

2) 交叉． 交叉操作的本質(zhì)是染色體的基因重組[11],即通過交換父代染色體的部分基因生成新的子代染色體．現(xiàn)采用單點(diǎn)交叉的方式進(jìn)行處理．隨機(jī)選取兩個(gè)父代個(gè)體中的一個(gè)相同序列號(hào)(起始點(diǎn)S和目標(biāo)點(diǎn)G除外),在此點(diǎn)處進(jìn)行交叉．如果兩個(gè)父代個(gè)體中不存在相同的序列號(hào),則不進(jìn)行交叉操作．

3) 變異． 變異操作是將某一個(gè)體染色體上的任意一個(gè)基因進(jìn)行變異處理生成一個(gè)新的染色體, 從而維持種群的多樣性[12]．傳統(tǒng)的單點(diǎn)變異或多點(diǎn)變異等處理方法極易產(chǎn)生不可行路徑,導(dǎo)致算法的運(yùn)行效率低下, 故筆者采用八鄰域單點(diǎn)變異的方法．隨機(jī)選取待變異路徑個(gè)體中的一個(gè)變異點(diǎn)Ni(起始點(diǎn)S和目標(biāo)點(diǎn)G除外), 在該變異點(diǎn)的八鄰域中隨機(jī)確定一個(gè)非障礙柵格N′i替換原有節(jié)點(diǎn)．按照初始路徑的生成方法, 將Ni-1到N′i以及N′i到Ni+1連接為無間斷路徑．若變異點(diǎn)的八鄰域中沒有可以選取的自由柵格或無法生成一條可行的無間斷路徑, 則按變異失敗處理, 即跳出此次變異操作并重新選取下一條待變異路徑個(gè)體及其變異點(diǎn)．

2.5 終止條件

終止條件是衡量遺傳算法是否能夠結(jié)束運(yùn)行的一個(gè)標(biāo)準(zhǔn)．本文終止條件如下:達(dá)到給定的進(jìn)化代數(shù)閾值50; 連續(xù)40次進(jìn)化種群的最優(yōu)適應(yīng)度值不變; 算法運(yùn)行時(shí)間超過5 min, 滿足條件之一即終止運(yùn)行．

2.6 Bezier曲線平滑操作

1) Bezier曲線． Bezier曲線[13]主要由數(shù)據(jù)點(diǎn)和控制點(diǎn)等節(jié)點(diǎn)與線段構(gòu)成, 其中數(shù)據(jù)點(diǎn)用于確定曲線的起始與結(jié)束位置, 控制點(diǎn)確定曲線的彎曲程度．考慮n階Bezier曲線, 其控制點(diǎn)表達(dá)式P(t)及n次伯恩斯坦多項(xiàng)式Bi,n(t)分別為:

(8)

(9)

圖5 Bezier曲線生成示意圖Fig.5 Schematic diagram of Bezier curve generation

當(dāng)n=1時(shí), 一階Bezier曲線是一條含2個(gè)節(jié)點(diǎn)的直線; 當(dāng)n=2時(shí), 二階Bezier曲線是一條含3個(gè)節(jié)點(diǎn)的拋物線; 當(dāng)n≥3時(shí), 是一條含n+1個(gè)節(jié)點(diǎn)的高階Bezier曲線．二階Bezier曲線的生成原理如圖5所示．

2) Bezier曲線的平滑優(yōu)化． 將改進(jìn)遺傳算法規(guī)劃所得折線路徑上的路徑節(jié)點(diǎn)作為Bezier曲線的控制點(diǎn)生成曲線路徑．根據(jù)Bezier曲線的性質(zhì)可知規(guī)劃所得曲線路徑不會(huì)與控制點(diǎn)連接而成的特征多邊形的外部障礙物發(fā)生碰撞．然而,控制點(diǎn)選取的疏密會(huì)導(dǎo)致原路徑與現(xiàn)路徑形成的特征多邊形內(nèi)部障礙物未發(fā)生碰撞,而平滑操作后的曲線路徑卻與相應(yīng)的內(nèi)部障礙物發(fā)生碰撞的情況．故可重規(guī)劃使得曲線路徑更貼近原路徑, 如圖6所示．選取發(fā)生碰撞情況的4個(gè)控制點(diǎn),在這4個(gè)點(diǎn)所形成的3條邊的中點(diǎn)處新增3個(gè)控制點(diǎn),根據(jù)這6個(gè)控制點(diǎn)重新平滑優(yōu)化．重復(fù)上述過程直至曲線路徑與障礙物無碰撞可能．

圖6 重規(guī)劃示意圖Fig.6 Re-planning diagram

圖7 融合Bezier遺傳算法規(guī)劃路徑Fig.7 Path planning based on Bezier-genetic algorithm

圖7為融合Bezier遺傳算法的規(guī)劃路徑示意圖, 其中虛折線為改進(jìn)遺傳算法生成的最優(yōu)折線路徑,空心圓圈為路徑序列點(diǎn),曲實(shí)線則為根據(jù)路徑序列點(diǎn)生成的最優(yōu)曲線路徑．由圖7可見, 融合Bezier曲線生成的路徑更短且更平滑．

3 仿真分析

圖8 3種環(huán)境下的最優(yōu)運(yùn)行路徑Fig.8 Optimal operating path in three environments

仿真實(shí)驗(yàn)在10 m×10 m、15 m×15 m、20 m×20 m等3種柵格環(huán)境模型中展開, 以驗(yàn)證算法的通用性．參數(shù)設(shè)置如下: 種群數(shù)量M=100, 最大進(jìn)化代數(shù)為50, 交叉概率為0.8, 變異概率為0.2, 路徑長(zhǎng)度權(quán)重a=6, 路徑安全性權(quán)重b=1, 路徑能耗權(quán)重c=3．融合Bezier遺傳算法的規(guī)劃結(jié)果如圖8所示, 其中虛折線代表改進(jìn)遺傳算法規(guī)劃得出的初始折線運(yùn)行路徑, 折線路徑上的空心點(diǎn)為路徑序列點(diǎn), 即生成Bezier曲線的初始控制點(diǎn), 實(shí)曲線代表最終生成的最優(yōu)曲線路徑．

表1為融合Bezier曲線前后改進(jìn)遺傳算法所規(guī)劃的路徑長(zhǎng)度對(duì)比結(jié)果．由圖8及表1可知: 融合Bezier遺傳算法生成的曲線路徑更短且路徑平滑度高, 完全解決了大角度轉(zhuǎn)彎的問題, 在直線運(yùn)行的區(qū)域曲線路徑也近似直線; 融合Bezier遺傳算法規(guī)劃得出的最優(yōu)運(yùn)行路徑更加符合實(shí)際場(chǎng)景的需求．

表1 融合Bezier前后改進(jìn)遺傳算法規(guī)劃的路徑長(zhǎng)度Tab.1 Comparison of path length between Bezier-genetic algorithm and improved genetic algorithm

表2 融合Bezier遺傳算法與BCA算法對(duì)比結(jié)果Tab.2 Comparison results of Bezier-genetic algorithm and BCA algorithm

圖9 2種算法在環(huán)境4中的最優(yōu)運(yùn)行路徑Fig.9 The optimal running path of the two algorithms in environment 4

現(xiàn)采用本文算法與BCA算法[9]在參數(shù)相同的情況下于環(huán)境4分別獨(dú)立執(zhí)行30次仿真實(shí)驗(yàn), 以消除隨機(jī)因素的影響, 結(jié)果如表2和圖9所示．由表2和圖9可知: 融合Bezier遺傳算法的最優(yōu)運(yùn)行路徑更為平緩且僅在控制點(diǎn)與障礙物相切處發(fā)生小曲率偏折; 本文算法的路徑長(zhǎng)度較BCA算法低6.7%, 算法運(yùn)行時(shí)間為BCA算法的10-6, 其原因?yàn)楸疚乃惴▋H對(duì)改進(jìn)遺傳算法生成的最優(yōu)解進(jìn)行平滑操作, 而BCA算法則對(duì)每一個(gè)初始種群都生成Bezier曲線再進(jìn)行遺傳迭代．

4 結(jié)論

本文設(shè)計(jì)了一種融合Bezier遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃問題．在初始種群的創(chuàng)建過程中采用啟發(fā)式中值插入法,有效提高了初始種群的質(zhì)量,加快了算法的收斂速度．以路徑長(zhǎng)度、路徑安全性和路徑能耗為評(píng)價(jià)指標(biāo),建立多目標(biāo)適應(yīng)度函數(shù),在盡可能減小路徑長(zhǎng)度的同時(shí)確保機(jī)器人始終朝著目標(biāo)點(diǎn)的方向前進(jìn),避免無謂的路徑能耗,一定程度上提高了規(guī)劃路徑的安全性．通過改進(jìn)的遺傳操作預(yù)防算法過早陷入局部最優(yōu),并以改進(jìn)遺傳算法生成的折線路徑的序列點(diǎn)作為Bezier曲線的控制點(diǎn),得出更符合實(shí)際應(yīng)用的平滑曲線路徑．結(jié)果表明,本文算法能夠在不同規(guī)模和復(fù)雜程度的環(huán)境中高效運(yùn)行,且收斂速度更快、路徑更短．本文算法在移動(dòng)機(jī)器人的路徑規(guī)劃問題領(lǐng)域具有一定的可行性與優(yōu)越性,今后將進(jìn)一步運(yùn)用至三維動(dòng)態(tài)環(huán)境．