基于正反饋自適應遺傳算法的機器人路徑滾動規劃

摘 要:針對傳統遺傳算法求解機器人路徑規劃問題存在的收斂速度較慢的缺陷，將螞蟻算法、模擬退火算法、滾動規劃和遺傳算法相結合，提出了一種新穎的基于正反饋自適應遺傳算法的滾動規劃。仿真實驗表明，即使在復雜的未知環境下，利用本算法也可以規劃出一條全局優化路徑，且能安全避碰。

關鍵詞:路徑規劃; 遺傳算法;滾動規劃; 自適應

中圖分類號:TP242.6文獻標志碼:A

文章編號:1001-3695(2010)06-2037-03

doi:10.3969/j.issn.1001-3695.2010.06.011

Robot path planning based on positive feedback adaptive genetic algorithm

HU Xi-ling， GUO Hai-tao

(College of Information Science Engineering， Ludong University， Yantai Shandong 264025， China)

Abstract:In order to improve the convergence speed of traditional genetic algorithm for path planninn of robot，presented a new robot path planning based on positive feedback adaptive genetic algorithm by integrating ant algorithm， simulated annealing algorithm，rolling planning and genetic algorithm.Computer experiment results demonstrate that the proposed algorithm can be used to solve the path planning for mobile robot even in the complex unknown environment， and achieve the successful obstacle avoidance.

Key words:path planning; genetic algorithm; rolling planning; adaptive

機器人路徑規劃是指移動機器人在工作空間中搜索一條從起點到目標點的最優或近似最優的無碰路徑。由于它是研究機器人控制的基礎問題，得到廣泛的研究和關注。如何保證在復雜環境下規劃出的機器人路徑是全局最優或基本最優一直是這一領域的一個研究難題。已有不少學者提出了解決未知環境下機器人路徑規劃的方法和策略，如基于滾動窗口的規劃方法[1]、蟻群算法[2]、粒子群算法[3]等。其中遺傳算法是通過模擬生物的進化過程而實現的一種最優化方式。遺傳算法由于具有優良的全局尋優能力和隱含的并行計算特性，保證了該方法應用于機器人路徑規劃的可能性和有效性[4]，因此有許多學者將遺傳算法應用到機器人路徑規劃中[5，6]。但是，由于遺傳算法從概率上來說，群體中的優秀個體和全局最優解之間的親和度要大于群體中其他個體和全局最優解之間的親和度;而且，與優秀個體有較大親和度的個體也應有較高的適應度。優秀個體所體現的特征信息能否被充分利用將是決定該算法優化能力的一個重要因素。簡言之，遺傳算法對系統中的反饋信息沒有充分利用， 往往導致無為的冗余迭代， 造成求解效率不高。基于此，借鑒蟻群算法， 在交叉與變異算子中引入正反饋機制， 可以提高遺傳算法的收斂速度。根據研究現狀及不足，本文研究了一種全新的基于遺傳算法的移動機器人路徑滾動規劃算法。該方法首先將目標點映射到機器人視野域內側邊界處，由機器人探測環境，利用正反饋遺傳算法完成機器人靜態局部最優路徑的搜索，機器人根據規劃好的局部路徑前進一步。每前進一步，都重復這一過程，因此，機器人在動態局部優化路徑引導下，可沿一條全局較優的路徑安全地到達終點。仿真實驗結果表明，即使在障礙物非常復雜的地理環境中，用本算法也能迅速規劃出一條優化路徑，且能安全地到達終點，效果十分令人滿意。

1 環境描述

機器人路徑規劃就是在工作環境中尋找一個從起始點到目標點的序列，這些點及相鄰點之間的連線不與環境中障礙物相交，且在所有這樣的序列中，該序列的代價(如路徑長度、費用等)最小。機器人的工作環境在坐標系XOY中，start為機器人的出發點，goal為目標點，黑色實心物體表示障礙物，機器人路徑規劃即是尋找一個點的序列P:

P={start，p1，p2，…，pn，goal}

其中pj(j=1，2，…，n)不為障礙物點，其與相鄰點的連接不與環境中的任何障礙物相交，且滿足路徑代價最小(路徑規劃中對障礙物作相應膨脹處理)。在機器人的工作環境中以start-goal作為X軸，以start作為原點新建一個坐標系X′O′Y′，如圖1所示。將線段start-goal進行n+1等分，在每一個等分點作X′的垂線，得到一組平行Y′的線{L1，L2，…，Ln}，機器人路徑與此組并行線的交點即是機器人路徑序列。這樣優化路徑就簡化為一維的y坐標編碼優化問題。在初始化種群時每一條路徑的區別僅僅是各個路徑點縱坐標的不同而橫坐標是相同的，在計算時只把縱坐標作為基因進行編碼， 橫坐標不變，可以節省計算時間。

2 基于正反饋遺傳算法的滾動規劃基本原理及算法

2.1 算法的相關定義

假設Rob無先驗的環境知識，對探測到的環境信息無記憶功能;任一時刻， Rob只能探測到以自己當前位置為中心、r為半徑區域內的環境信息(探測時間忽略不記);Rob能向任意方向行走，步長為δ(0<δ≤r)。Rob在二維平面上運動，其工作區域為WS。WS為凸多邊形，其內部分布著有限個靜態障礙物Obs1，Obs2，…，Obsn，任意障礙物Obsi 中的點構成閉凸集Oi，WS中的點構成閉凸集W。

為了敘述方便，進一步作出如下約束和定義:

定義1 P P∈W，POi(i=1，2，…，n)，則稱P為可行點，所有可行點的集合稱為可行域，記為FD。

定義2 View(PR(t))={P|P∈W，d(P，PR(t))≤r}稱為Rob在點PR(t)處的視野域，亦即該點的滾動窗口。其中PR(t)∈FD。

假設機器人Rob的當前位置為PR(t)，算法首先將全局目標點映射到機器人Rob的視野域view的邊界內側作為局部子目標點gsub，Rob每前進一步，都需要用傳感器探測其view內的環境信息;再通過局部路徑規劃獲得一條Rob在視野域內的最短局部路徑。Rob每前進一步，都進行局部路徑規劃過程，當gsub與goal 重合時，Rob根據當前規劃出的最優路徑直接走向goal。本算法中Rob總是以最終目標點的方向為前進目標，其特點是利用gsub來引導機器人。圖2給出了在view環境下找到的局部優化路徑。其中d為gsub與view任意邊界間的距離，取1。Rob每走一步，修改的是一條局部路徑而不是一步，加上局部路徑較短，因而可以保證機器人行走安全避碰，又可使機器人Rob所走路徑全局最優或較優。

2.2 正反饋遺傳算法原理

1)正反饋思想

在圖1中，將平行線組{L1，L2，…，Ln}以O′X′為基準進行劃分(劃分單位大小參照機器人的大小R)，劃分結果如圖3所示。圖中只對其中一條垂線作劃分。

在遺傳算法中引入二維實數矩陣(ai×j)n×m。其中n對應start-goal之間的垂線的個數，m對應所有垂線中劃分單位的最大個數，該矩陣所有元素初始化為一相等的較小實數值。在算法每次迭代結束時，根據所得的可行路徑對相應的矩陣元素按下式進行更新:

ai×j=ai×j+c(1)

其中:c為一常數。

同時，對矩陣中的所有元素值按下式作揮發處理:

ai×j=(1-ρ)ai×j(2)

其中:ρ稱為揮發因子(0<ρ<1)。

例如在算法一次迭代結束之后，可行路徑中有一條可行路徑經過了圖3中的pj點，則對相應的數組元素aj×1作如下處理:

aj×1=aj×1+c

對這一可行路徑中的其他節點及其他可行路徑所對應的矩陣元素值進行同樣處理。之后，對所有矩陣元素值作如下處理:

ai×j=(1-ρ)ai×j

矩陣中某一元素值越高，則在可行路徑中其對應的節點被選中參與交叉及變異運算的概率就越小。

2)適應度函數

定義start為p0點、goal為pn+1點。某條可行路徑i的代價C(i)依式(3)計算:

C(i)=∑nj=0d(pj，pj+1)(3)

其中:d(pi，pj)表示pi、pj兩點之間的距離，依式(4)計算。

d(pj，pj+1)=(x′pj-x′pj+1)2+(y′pj-y′pj+1)2=(d(p0，pn+1)m+1)2+(y′pj-y′pj+1)2(4)

適應度函數是遺傳算法收斂性和穩定性的重要影響因素，路徑的規劃要求滿足兩個條件，即免碰撞和路徑最短。因此個體i的適應度函數F(i)依式(5)計算:

F(i)=1C(i)+L(5)其中:L為與路徑i相交的障礙物個數，C(i)依式(3)計算。

3)遺傳算子

遺傳算法在實際應用中常常出現收斂速度慢和早熟等現象，主要是因為早期的優良個體由于適應值大大高于群體的平均適應值，當按比例進行選擇時，該個體很快就會在群體中占據絕對的比例，而其他個體被淘汰，這樣就造成早熟現象。借鑒模擬退火策略，個體i被選中的概率依式(6)計算。

P(i)=f(i)∑Mi=1f(i)(6)

其中:M為種群的大小，f(i)的計算依式(7)計算:

f(i)=aF(i)+e-et/Te+et/T(Fmax-Fmax)(7)

其中:F(i)依式(5)計算，Fmax為當前最大適應值，Fmin為當前最小適應值，a為大于零的常數，t為當前迭代次數，T為最大迭代次數。

遺傳算法的交叉率和變異率很難選擇，較小的交叉率和變異率將導致遺傳算法收斂速度慢，而過大的交叉率和變異率又會破壞后期的優良個體，導致收斂速度慢甚至無法收斂。所以需要一個自適應的機制，隨著遺傳算法的過程來調整交叉率Pc和變異率pm。

Pc=pc1(fmax-f ′)/(fmax-favg) favg≤f ′

pc2 favg>f ′(8)

Pm=pm1(fmax-f)/(fmax-favg) favg≤f

pm2 favg>f(9)

其中:fmax為當前種群最大適應函數值，favg為當前種群平均適應函數值，f′為雜交個體中適應函數較大個體的適應函數值，f為變異個體的適應函數值;pc1、pc2、pm1、pm2為正常數。

4)添加節點算子

當子代個體出現與障礙物相交的情況時，根據沿墻導航的方法對不可行路徑進行調整，在與障礙物相交的兩個相鄰節點之間的自由區域產生一個新的節點，并加入到當前的個體路徑節點序列之中，如圖4所示。若順時針和逆時針兩個方向有兩條到達該段終點的路徑，選擇路徑較短的一條。坐標的選取依據式(10)計算:

B′x=Ax+rand×(Ax-Bx)

B′y=Ay±rand×Ay(10)

5)刪除節點算子

刪除算子可以減少路徑中的多余節點，當某代個體中出現可明顯刪除的節點，且并不會導致與障礙物的碰撞發生時，則刪除該節點，如圖5所示。可以看出，刪除操作有利于減少染色體長度，提高算法的運行速度，同時可以減少不可行路徑中不可行路段的個數，從而改善路徑的質量。

2.3 正反饋遺傳算法滾動規劃步驟

為保持機器人路徑序列中每一點都在約束環境中，需對y′i(i=1，2，…，n)加以限定:

y′imin≤y′i≤y′imax(11)

其中:y′imin、y′imax分別為約束環境中對應位置的上下邊界。

具體路徑規劃算法如下:

a)產生任意的起點start和goal并對有關參數進行初始化。

b)將目標點goal映射到Rob視野域view邊界外作為局部子目標;若有與goal相同，規劃結束;否則轉c)。其中產生局部子目標的映射算法如下:

在t時刻Rob的視野域為view(PR(t))，若有d(PR，goal)=r-δ，則取gsub=goal，此時即為gsub與goal相同;否則令

d(PR，gsub)=r-δ且min d(gsub，goal)(12)

其中，r為Rob的視野域view的半徑;δ為Rob的行走步長，兩參數均為已知;PR與goal點的坐標為已知，由式(12)可求出goal映射到子目標點gsub的坐標xj、yj。

c)Rob在當前位置PR(t)進行環境探測。

d)初始化種群的大小為M、迭代次數T，隨機生成M個點的序列(y′1，y′2，…，y′n，)，初始化(ai×j)n×m數組元素的值及c，初始化揮發因子ρ。

e)對路徑上的pi、pi+1(0≤i≤n)判斷線段pipi+1是否與障礙物相交，若相交，則滑動y′i+1，使其與障礙物相離。

f)依式(5)計算每個個體適應值。

g)依式(6)做選擇操作，按照賭盤法選擇當前群體中適應度較高的個體;依式(8)(9)進行交叉、變異操作。

h)用刪除算子和添加算子優化路徑。

i)根據得到的可行路徑，按照式(1)(2)對(ai×j)n×m數組元素值進行更新。

j)迭代次數t自動加1，判斷t是否到達指定的迭代次數T，若未達到轉f)，否則繼續。

k)選出當前群體中最優的個體，若gsub不等于goal，Rob按照此個體表示的局部最優路徑向前進一步并返回b);否則Rob按照此個體表示的局部最優路徑直接走向目標點。

3 仿真實驗

1)靜態環境仿真

筆者在靜態未知環境中做了大量的實驗，實驗環境為奔騰ⅣCPU 3.06 GHz，512 MB內存，Visual C++ 6.0，工作環境初始大小為500×300，起始點start(50，30)，目標點goal(396.2，230)。實驗結果如圖6所示。

為了進一步分析本文算法能得到全局優化路徑的原理，圖7給出了實驗過程中的分解子過程。其中(a)為路徑規劃開始，(b)為路徑規劃中間過程。圖中細線圓為相應位置的機器人視野域，邊界上的×號為局部子目標點，粗曲線為已規劃路徑。由圖7可以看出，Rob僅沿每次規劃的局部路徑走一步，但它構成了全局的一種引導趨勢，從而使得不僅能避碰，且所走路徑全局最優或較優。

2)動態環境仿真

文獻[2]的動態避碰策略的基本思想是將機器人視野域內的動態障礙物沿其運動方向延伸為一較大的靜態障礙物，從而將動態避碰問題轉換為靜態避碰問題。筆者借鑒此思想，在動態環境中進行了仿真實驗，并將實驗結果與文獻[7]中的相關算法進行了對比。圖中規則多邊形表示靜態障礙物，圓圈表示動態障礙物。

為證明正反饋思想在本算法中起到加速收斂的作用，在實驗過程中，把最終目標點直接作為子目標，不再利用滾動窗口規劃，即與文獻[7]同環境、同條件比較。兩算法的迭代次數均設置為100次時，規劃結果如圖8所示。

從圖8可以看出，本文算法的路徑優化效果強于文獻[7]中的方法，另外，筆者還在實驗中增加文獻[7]中算法的迭代次數，當迭代次數增加到130次時，文獻[7]的路徑規劃結果同圖8(a)所示一致。由此可見，本文的正反饋機制在復雜環境下亦能夠起到提高遺傳算法收斂速度的作用。另外在圖8中的環境中，兩算法分別運行30次，結果發現文獻[7]的算法有時找不到可行路徑，成功率(找到可行路徑的比例)為95.2%，而對于本文算法來說，成功率達100%，且迭代次數較少。

4 結束語

如何在復雜的未知靜態環境中規劃出機器人路徑全局最優或較優一直是這一領域的一個研究難題。由于缺乏全局環境信息，無法進行有效的離線規劃，只能依靠機器人傳感器的探測范圍進行局部規劃，很難保證機器人所走的路徑全局最優或較優，甚至易引起死鎖和振蕩等。本文將螞蟻算法、模擬退火算法、滾動規劃和遺傳算法相結合，充分利用機器人實時探測到的局部環境信息，在滾動窗口內局部快速規劃，取得了較好的效果。仿真實驗表明該算法可行有效，對不同復雜度的環境均具有較好的適應能力。

參考文獻:

[1]張純剛，席裕庚.全局環境未知時基于滾動窗口的機器人路徑規劃[J].中國科學(E輯)，2001，31(1):51-58.

[2]朱慶保.全局未知環境下多機器人運動螞蟻導航算法[J].軟件學報，2006，19(9):1890-1898.

[3]QIN Yuan-qing， SUN De-bao. Path planning for mobile robot using the particle swarm optimization with mutation operator[C]//Proc of the 3rd International Conference on Machine Learning and Cybernetics.2004:2473-2478.

[4]梁曉輝，吳威，趙沁平.大規模真實地形數據中的全局路徑規劃方法——基于遺傳算法的研究[J].計算機研究與發展，2002，39(3):301-306.

[5]KOENING S， LIHACHEV M， Fast replanning for navigation in unknown terrain[J].IEEE Trans on Robotics，2005，21(3):354-363.

[6]王雪松，高陽，程玉虎，等. 知識引導遺傳算法實現機器人路徑規劃[J].控制與決策，2009，24(7):1043-1049.

[7]MAHIOUBI H， BAHRAMI F， LUCAS C. Path planning in an environment with static and dynamic obstacles using genetic algorithm[C]//Proc of IEEE Congress on Evolutionary Computation.2006:16-21.