基于神經網絡和遺傳算法的移動機器人路徑規劃
2007-01-01 00:00:00劉玲王耀南況菲張輝
計算機應用研究 2007年2期
摘 要：提出一種基于神經網絡和遺傳算法的路徑規劃算法。采用神經網絡模型對機器人的環境信息進行描述，利用神經網絡的輸出建立遺傳算法的適應度函數；然后使用遺傳算法優化路徑。在該算法中將需規劃路徑的二維編碼簡化成一維編碼。仿真結果表明提出的路徑規劃方法是正確和有效的。
關鍵詞：路徑規劃； 神經網絡； 遺傳算法； 移動機器人
中圖法分類號：TP18文獻標識碼：A
文章編號：1001—3695(2007)02—0264—02
路徑規劃是移動機器人導航的最基本環節之一，它是依據某個或某些優化準則(如工作代價最小、行走路線最短及時間最短等)，在其工作空間中找到一條從起始狀態到目標狀態能避開障礙物的最優路徑[1]。將人工神經網絡[2，3]和遺傳算法[4]等智能方法應用于機器人運動軌跡自動生成和移動機器人路徑規劃是一種有效的方法。文獻[5]給出了一種神經網絡路徑規劃算法，引入了神經網絡結構和模擬退火算法，計算簡單，能避免某些局部極值情況，且具有并行性及易于從二維空間推廣到三維空間等優點。但在該算法中，路徑搜索運動方向受各參數影響大，因此，當具體環境結構改變時，各個加權參數及模擬退火初始溫度和降溫速度都必須重新調整。針對這一問題對以上方法進行改進，仍然采用神經網絡對機器人的運動環境進行描述，但不再采用模擬退火算法而是采用遺傳算法進行路徑搜索。神經網絡作為一個高度并行的分布式系統，為解決機器人系統實時性要求很高的問題提供了可能性，并應用于智能自主移動機器人導航與路徑規劃等方面。遺傳算法優越性[4]在于它不需要采用確定性的搜索策略，只利用結構化和隨機性信息，使滿足目標的決策獲得最大的生存可能。因此，在改變具體環境結構時，不需要大范圍變動參數，只需對遺傳群體規模和遺傳代數稍加改動即可。
1 機器人運動環境的神經網絡描述
移動機器人工作在具有靜態障礙物的環境中，要求從起始地點無碰撞地移動到目標點。為研究方便，對工作空間作如下假設：①移動機器人在有限二維空間中能朝各個方向移動并且不考慮高度信息；②把障礙物邊界向外擴展機器人本體在長、寬方向上最大尺寸的1/2，機器人可看作質點忽略不計；③障礙物用凸多邊形（如長方形）逼近，一個凹多邊形可以用幾個凸多邊形的組合來表示。
圖1給出了一個代表障礙物的長方形及其四個不等式的約束條件。由圖1可知，通過判斷一個點的坐標是否同時滿足四個不等式的要求即可知道該點是否位于障礙物內部。環境內一點Pi(xi， yi)與障礙物長方形的位置可用圖2所示的神經網絡模型來表示。此網絡結構采用三層結構，輸入層的兩個節點分別表示給定路徑點Pi的橫坐標xi和縱坐標yi；頂層節點的輸出為障礙物的碰撞罰函數（碰撞罰函數是對路徑點與障礙物碰撞程度的量化）；中間層節點的閾值為不等式中的常數項。中間層到頂層的連接權系數均為1，輸入層到中間層的連接權系數為不等式中變量x，y的系數，頂層節點的閾值取為不等式的個數減去0.5后的負數。
移動機器人的工作環境往往有多個障礙物，而且一條路徑也由多個路徑點組成，所以把一個路徑點的碰撞罰函數定義為路徑上所有中間路徑點的碰撞罰函數之和。一個點的碰撞罰函數是通過它對各個障礙物的神經網絡表示得到的。 圖3表示多個障礙物環境的神經網絡模型。圖中每一層表示一個中間路徑點。
2 遺傳算法路徑規劃
遺傳算法（GA）是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型。它采用簡單的編碼技術來表示各種復雜的結構，并通過對一組編碼表示進行簡單的遺傳操作和優勝劣汰的自然選擇來指導學習和確定搜索的方向。遺傳算法作為一種新的全局優化搜索算法，以其簡單通用、魯棒性強、適合于并行處理以及應用范圍廣等顯著特點，奠定了它作為21世紀關鍵智能計算方法之一的地位。選擇、交叉和變異是遺傳算法的三個主要操作算子，它們構成了所謂的遺傳操作，使遺傳算法具有了其他傳統方法所沒有的特性。遺傳算法中包含了如下五個基本要素：①參數編碼；②出示群體的設定；③適應度函數的設計；④遺傳操作設計；⑤控制參數設定（主要是指群體大小和使用遺傳操作的概率等）。遺傳算法的基本處理流程如圖4所示。
2.1 編碼
遺傳算法中影響計算時間的主要因素是編碼長度和搜索空間。太長的編碼長度和太大的搜索空間都會使計算時間迅速增長。這里采用簡化編碼長度技術，把路徑的二維編碼簡化為一維編碼[6]，編碼技術如圖5所示。算法規劃的路徑就是在起始點與目標點之間確定能避開障礙物的最優路徑的點序列坐標(xi，yi)，在工作空間坐標系xoy中，路徑點序列的坐標是二維的，為降低編碼長度，對坐標系進行坐標轉換，轉換后的坐標系是xo′y，x軸為起始點與目標點的連線，然后把x軸等分成x1，x2，…，xn，那么優化的路徑點就簡化為一維的y坐標編碼優化問題。編碼采用浮點數形式，編碼格式如圖6所示。
2.2 確定適應度函數
局部動態避障路徑規劃要求滿足兩個條件，即避障和路徑最短。下面分別介紹兩個條件的實現過程。
（1）任意路徑點不在任意一個障礙物內，即路徑點(xi，yi)不能落入障礙物區域，機器人運動環境信息的神經網絡模型式（1）的輸出，路徑點不在障礙物內的適應度函數fit1可表示為
式中，i為工作空間的所有路徑點，n為障礙物的個數。式(6)表明，如果路徑點(xi， yi)不在障礙物內，那么適應度為1；否則為0。
（2）路徑最短的適應度函數fit2可以確定為
采用各項評價函數加權求和是確定適應度函數的典型方法[6]。這種方法的缺點是各個權系數比較難調整和確定，容易引起優化不穩定，這是因為各個權系數不是恒定不變的，而是隨著路徑和障礙物的變化而變化的。因此，這里采用各項評價函數相乘作為最后遺傳算法的綜合適應度函數，表示為
2.3 遺傳操作
(1)生成出示種群。初始化種群在工作空間中垂直于x1，x2，…，xn的垂線（圖4）上隨機選擇，種群規模反映了工作空間內隨機產生的路徑條數。規模越大，產生的路徑越精確而且容易找到全局最優解，但搜索時間也相應會越長。一般取20—100。本文種群規模取為30。
(2)復制操作。本文采用不同于傳統復制算子的方法輪盤選擇法[4]。具體選擇過程描述如下：
①依次累計群體內各個體的適應度，得相應的累計值Si，最后一個累計值為Sn；
②在[0，Sn]區間內產生均勻分布的隨機數R；
③依次用Si與R相比較，第一個出現Si大于或等于R的個體i被選為復制對象；
④重復②，③，直至滿足所需要的個體數目（由復制概率Pr控制）。
以上輪盤選擇方法既符合適者生存原則，又保持了個體性態的多樣性，克服了早熟問題。
（3）交叉操作。首先將復制產生的個體隨機兩兩配對，然后隨機地選擇交叉點（本文采用雙點交叉），對匹配的個體按雜交概率Pc進行交叉繁殖，產生一對新的個體。
（4）變異操作。交叉后的子代個體基因按小概率擾動經歷變異，通常取很小的值，一般取0.001—0.14。本文在新的個體中加入[-0.15，0.15]之間的零均值高斯白噪聲作為隨機擾動，尋找最優解。
（5）終止條件。本文采用規定遺傳代數。
3 試驗仿真
為了驗證所述方法的有效性，本文在仿真軟件MATLAB6.5.1上進行試驗仿真。試驗中，取節點數n=30，群體規模m=30，遺傳算子Pr=0.2，Pc=0.6，最大遺傳代數g根據環境復雜程度作適當調整。圖7為單個障礙物的仿真效果，其最大遺傳代數g=600。圖8為多障礙物復雜環境下的路徑規劃仿真效果，其中取節點數n=30，群體規模m=30，最大遺傳代數g=1 000，遺傳算子與上同。可見無論機器人環境復雜與否，該算法路徑搜索效果和速度均較為理想。
4 結論
本文研究已知障礙物形狀和位置環境下的全局路徑規劃問題，結合人工神經網絡和遺傳算法提出了一個路徑規劃算法。沿用文獻[5]中的神經網絡環境描述，采用遺傳算法進行路徑搜索，并給出了遺傳算法的詳細搜索步驟。仿真結果表明，這種結合神經網絡和遺傳算法的移動機器人無碰撞路徑規劃算法是可行的。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
