基于遺傳算法的移動機器人路徑規劃

楊 嘉，劉 虎，楊新坤，李文振，李富康，趙寧寧

（長安大學工程機械學院，西安 710064）

0 引言

隨著智能化的飛速發展，移動機器人的出現，給人們帶來了極大的方便。移動機器人被廣泛應用于軍事、制造、服務、農業等各個方面，而路徑規劃作為移動機器人領域的重要且基礎的問題之一，一直以來都是人們關注的焦點，也有越來越多的專家學者對其進行大量研究。研究移動機器人的路徑規劃問題具有重要的意義，常用的算法有遺傳算法、A*算法、蟻群算法以及快速隨機搜索樹算法等，陳亮等[1]在傳統遺傳算法的基礎上，對適應度函數進行優化，利用優化后的自適應遺傳算法使機器人路徑規劃質量得到顯著提升。王堯山等[2]為解決機器人路徑規劃中存在的收斂慢等問題，改進了遺傳算法，引入人工勢場法進行種群初始化，提出了基于種群多樣性程度評價的自適應選擇方法，設計了自適應交叉和變異概率，通過仿真實驗，證明了所提出改進遺傳算法的可行性和有效性。王雷等[3]針對基本遺傳算法的選擇和變異操作會在路徑規劃中產生不可行路徑這一問題，提出一種對選擇和變異操作進行改進并可以自適應調整的方式，提高了遺傳算法的尋優效率。田欣等[4]提出了一種基于解空間優化的遺傳算法，通過仿真實驗證明該優化算法在一定程度上可以解決機器人在路徑規劃法方面存在的早熟收斂問題。錢紅昇等[5]在分層算法的基礎上，對A*算法進行改進，在保證一定的搜索精度下提高了搜索效率。封聲飛等[6]針對傳統蟻群算法在路徑規劃中存在收斂速度和尋優能力不平衡等問題，提出一種自適應改進蟻群算法，通過實驗仿真驗證了改進算法的可行性與有效性。

本文將從移動機器人路徑規劃中的路徑長度與平滑度兩個方面進行研究討論，通過柵格地圖法建立機器人運動環境模型，構建關于路徑長度和平滑度的適應度函數，對路徑長度和平滑度的權重系數進行優化調整，采用輪盤賭的方法保留了部分非最優個體，防止算法陷入局部最優解，最后通過MATLAB 進行仿真，得到了迭代次數少、運行時間短、滿足移動機器人運動的最佳路徑。

1 問題描述與環境建模

本文是對移動機器人進行全局路徑規劃，即環境中的全部障礙物分布已知，要求移動機器人在與已知障礙物毫無碰撞的情況下，由起始位置運動至終點位置，從而使機器人獲得最佳移動路徑。

首先建立環境地圖，本文采用柵格法建立移動機器人的運動空間模型。柵格面積越小，環境信息表示越準確，若柵格面積越大，環境信息則不能被準確表示，極易出現碰撞現象。在采用柵格法建立運動環境模型時，柵格單元采用二進制信息表示，其中“1”表示障礙物柵格，“0”表示自由柵格，如圖中黑色部分為障礙物柵格，白色部分為自由柵格。建模后的機器人運動空間如圖1所示。

圖1 20×20柵格地圖

2 路徑規劃遺傳算法

2.1 初始化種群

初始化種群要求隨機產生不與障礙物柵格相碰撞的多條可行路徑。首先初始化時需要先按順序在每一行的柵格中隨機性的選出一個自由柵格，其中將路徑的第一個柵格和最后一個柵格設置為移動機器人的初始位置與終點位置，此處將柵格地圖中的第1個柵格設置為初始位置，第399個位置設置為終點位置，其次將從每一行柵格中選出的自由柵格連接為連續的路徑，在這一步中首先需要判斷選出的相鄰行中的自由柵格是否連續，其判斷方法為：

式中：xi+1、yi+1、xi、yi分別為相鄰兩個柵格的直角坐標，max 和abs 分別為最大值和絕對值。

ξ＝1 時說明兩個相鄰的自由柵格連續，否則不連續。對于不連續的取兩個自由柵格的中點柵格，中點柵格的坐標計算公式為：

若所得新柵格為黑色障礙物柵格，則按照上下左右的順序取新柵格的相鄰柵格，并判斷此柵格是否已經在路徑中，如果此柵格為自由柵格且不在路徑中，則插入兩個不連續柵格中間作為路徑，若遍歷上下左右4個柵格均無滿足條件的柵格，則刪除此條路徑；繼續判斷新插入的柵格和新插入的柵格的前一個柵格是否連續，若不連續則循環以上步驟，直到兩個柵格連續。以此類推循環以上步驟，直至所選的移動路徑為連續路徑。

2.2 適應度函數

由于本文所研究的移動機器人路徑規劃問題是從路徑長度和平滑度兩方面進行考慮的，所以適應度函數由兩部分組成。

（1）路徑長度方面

路徑長度的計算公式為：

由于在進行路徑規劃時要滿足路徑最短，而選擇方式采用的是輪盤賭的方式，因此適應度函數的第1部分為：

（2）路徑平滑度方面

根據機器人運動學和動力學的約束[7]，機器人運動時的拐彎不宜過大，而且相對平滑的路徑更加有利于機器人的運動，因此在進行路徑規劃時有平滑度的要求。路徑越平滑，相鄰3 點形成的角度越大，角度越大相鄰3 點之間的距離越大，所以將計算路徑中所有相鄰3點的距離作為適應度函數的第2部分，計算公式如下：

路徑中連續的3 點所組成的夾角分別有：平角（180°）、鈍角、直角以及銳角，計算所得的d′值與這4 種情況相對應，其中平滑度最好的是平角，鈍角與直角次之，而銳角這一情況不滿足機器人動力學的約束。因此，需要對除平角之外的其余3種情況進行懲罰，加上懲罰數可以優化不滿足約束條件的個體，懲罰系數分別取6、30和無窮大，在操作過程中具體可以根據實際情況變動懲罰系數的大小。懲罰之和的倒數就是所構建的適應度函數的第2部分。

根據兩部分的構成，需要對路徑長度和路徑平滑度的適應度函數取權重系數w1、w2，適應度函數公式為：

依據路徑長度與路徑平滑度間的權重選擇參數w1和w2。

2.3 遺傳操作

2.3.1 選擇方法

采用輪盤賭[8]的方式進行選擇，其中個體被選中的概率與其對應的適應度函數值成正相關，當種群大小為n時，個體i被選中遺傳到下一代的概率為：

采用輪盤賭的方式可以大概率地將適應度值大的個體選為父代個體用以產生新的個體，同時保留了部分非最優的個體，防止算法陷入局部最優解。

2.3.2 交叉方式

首先確定交叉概率pc的值，其次在0～1 之間隨機產生一個數，將其與交叉概率pc作比較，若產生的隨機數值小于pc值，則進行交叉操作，反之不作交叉操作。此處采用的是單點交叉[9]方式，即在兩條路徑中找出所有相同的點，再隨機選擇其中一個點，將之后的路徑進行交叉操作，具體流程如圖2所示。

圖2 交叉方式流程圖

圖3 變異方式流程圖

2.3.3 變異方式

首先確定變異概率pm，其次在0～1 之間隨機產生一個數，將其與變異概率pm作比較，若產生的隨機數值小于pm值，則進行變異操作，反之不作變異操作。變異方法是隨機選取路徑中除初始位置和終點位置之外的兩個柵格，并去除兩個柵格之間的路徑，以這兩個柵格為相鄰點，判斷這兩個點是否為連續柵格。若無法產生連續路徑，則重新選擇兩個柵格進行操作，直至完成變異操作，具體流程如圖3所示。

3 仿真結果

采用柵格地圖法建立20×20 的機器人運動環境，設置初始起點為0 柵格，終點為399 柵格。取種群數量n＝300，迭代次數取100次，pc＝0.8，pm＝0.1。

（1）取w1＝4，w2＝2，通過MATLAB進行仿真，運行結果如圖4～5 所示，可以得到在經過10 次左右的迭代算法已經收斂，在迭代次數為60次左右的時候所得平均路徑長度與最優路徑長度基本一致，最佳路徑長度為30.624，運行時間為3.703 s，由圖可以看出，其可行路徑中存在直角轉折的情況，所得路徑并不平滑，這種情況下一般的機器人行駛比較困難。

圖4 調整參數前的路徑規劃圖

圖5 調整參數前的路徑長度曲線圖

（2）對路徑長度和平滑度的權重系數進行調整，并對出現直角的情況加了較大的懲罰，經過多次仿真驗證，取w1＝1，w2＝7 時，通過MATLAB進行仿真，運行結果如圖6～7 所示，可得到在經過10 次左右的迭代算法已經收斂，在迭代次數為40次左右的時候所得平均路徑長度與最優路徑長度基本一致，最佳路徑長度為29.213 2，運行時間為2.588 s，所得路徑長度更短，運行時間更少，路徑也更加平滑。

圖6 調整參數后的路徑規劃圖

圖7 調整參數后的路徑長度曲線圖

4 結束語

本文主要實現了基于遺傳算法的靜態環境下的移動機器人路徑規劃，通過采用柵格地圖法建立機器人的運動環境模型，構建關于機器人路徑長度和平滑度的適應度函數，通過調整參數，優化仿真過程，使其在迭代次數最少、用時最短的情況下獲得最佳移動路徑。通過以上可以看出，所求解的可行路徑在平滑度方面仍不夠平滑，在后期的研究中可對適應度函數中平滑度的部分作進一步改進，使其得到的可行路徑更加平滑。