避障路徑規劃的算法研究

張喜英 崔智超 欒文璐 楊帥

【摘? 要】 將遺傳算法應用于避障的路徑規劃，可根據遺傳算法的流程，將路徑長度設置為個體的適應度。首先將已知的工作環境進行建模，將障礙物與可行方格進行點化處理，并設置好起點與終點；隨后設置好相應的變異率等參數；最后，輸出適應度最高的路徑作為最優路徑。文章所應用的算法在MATLAB軟件上進行仿真實驗，實驗結果表明，文章設計出的算法得到了最短的路徑。該算法具有一定的可行性與實用價值。

【關鍵詞】 遺傳算法；避障路徑規劃；MATLAB仿真

一、遺傳算法

遺傳算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，它也是一種通過模擬自然進化過程搜索最優解的方法。

遺傳算法主要包括編碼、初始化種群、適應度函數建立、遺傳操作等步驟。應用遺傳算法來求解問題時，需要對子代基因進行反復的篩選、交叉和變異操作，最終得到符合條件的解或者迭代次數達到規定次數。遺傳算法主要包括編碼、初始化種群、適應度函數建立、遺傳操作等步驟。

二、路徑規劃研究概述

（一）按照搜索范圍劃分

全局規劃：通過對已知環境模型信息的處理，按照規劃出的路徑前進。全局規劃得出最優解，取決于周圍環境的參數。全局規劃往往是適用于范圍較小，環境復雜程度較低的空間，當環境模型較大時，全局規劃的計算量會增大，運算的時間會變長。

局部規劃：相比于全局規劃對整個空間的解析，局部規劃將所搜索的范圍局限于當前位置的周圍，使得在未知的環境中能夠具有有效的避障能力。應用局部規劃的實用性很高，與全局規劃相比，當環境發生變化的時候不用再對運行環境進行建模，這大大提高了算法的實用性。然而局部規劃可能會產生局部最優解，無法正常完成工作。

（二）按照工作環境劃分

靜態環境規劃：靜態環境是指工作的環境已知，不隨時間的變化而變化。在這種環境中，障礙物是靜止的，因而想要規劃出一條最優路徑較為簡單。靜態環境規劃主要被應用于工廠等環境單一的地方。

動態環境規劃：與靜態環境相反，動態環境規劃指的是在已知或者部分已知的環境中，存在有運動軌跡不明的障礙物，在這種情況下規劃出一條最優的路徑。

路徑規劃有如下特點：

1. 復雜性：當處于含有較多障礙物的環境或者處于動態環境中時，為了得到最優的路徑，要進行大量的計算。尤其是動態環境中，規劃的難度大幅提高。

2. 隨機性：當工作環境相對復雜時，需要處理各種的突發狀況以及不確定因素。

3. 約束性：按照規劃好的路徑前進時需要考慮到自身的大小、形狀等物理因素，還要考慮自身移動速度的問題，這些條件是設計過程的重要部分。

4. 多目標性：路徑規劃的最優解具有多種評判標準，有的要求路徑最短為優，有的要求到達時間最短，不可能完全達成所有目標，因此需要實時分析需求進而系統的權衡好各個要求。

三、避障路徑規劃方案算法的設計

將已知的工作環境進行建模，將障礙物與可行方格進行點化處理，并設置好起點與終點。具體過程如下：采用柵格建模的方法。其工作原理是將工作空間進行格式化處理，將工作的環境分割成大小相同的方格，空白部分表示可以行進的路徑，黑色的部分表示障礙物，并設置好Begin（開始）和End（結束）兩點，當兩方格的中心能夠相連時，表示為一條可行路徑，否則不能相連。其障礙物環境的構建遵從矩陣。 隨后設置好相應的變異率等參數，具體過程如下：

初始參數定義（染色體編碼）：在路徑規劃方面，由起點到終點的可行路徑即為遺傳算法中的一條染色體。染色體中每一個基因片段對應可行路徑片段，整個染色體可以看成是路徑結點坐標集合。

適應度函數：通過種群中個體的特征來判斷個體的適應程度。這里對適應度的定義即為路徑的長度。通過輸入一組節點坐標集合（個體），來得到所對應路徑的總長度，其用公式表示為：

生成初始種群：種群即個體的集合，這里的種群即為可行路徑的所有坐標集合。

計算個體的適應度：即將個體輸入至適應度函數。這里是將坐標集合輸入至適應度函數得出的路徑長度。

預設條件：當達到種群繁殖次數的最大數值或者連續進化次數達到某一數值后最優的解不發生變化。終止條件設置為達到運算規定次數，且連續多次最短路徑的結點集合不發生變化。

選擇運算：用于篩檢出計算至今符合條件的最優個體。這里表示將正在計算得出的路徑同上一次計算的路徑做比較，較短的一組路徑坐標集將會被保留。

交叉運算：指當兩條染色體達到配對條件以后，將各自的部分基因片段按照某種交叉方式來進行互換，得到兩條新染色體的過程。在該算法中，交叉過程即為在具有一個或者多個相同坐標點的兩條路徑坐標集合中，隨機將幾個位于同一位置的坐標進行交換，形成新的兩個坐標集合。

變異運算：染色體經過編碼后將以編碼串的形式表示，變異操作是將某段編碼串上的基因編碼數值隨機替換為新的可用編碼值，進而產生新的個體。這里將采用隨機變異的方法，將某條路徑集合中的坐標隨機變化為其他的坐標，形成新的路徑坐標集參與下次的運算。

根據遺傳算法參數設定方法，種群中個體的數目para.popsize=50，交叉概率para.pcrossover=0.6，進化的最大代數設置為150代。在路徑規劃的過程中，運動軌跡T可以劃分為一個個的線段，每一個有向線段的長度和即為所走路徑的長度。線段由兩點決定，以此為基礎，運動路徑可以看成是路徑點的集合表示為：

T={（X1，X2），（X2，X2），...（Xn-1，Xn-1）}

在路徑規劃的數據存儲過程中，路徑點的存儲采用坐標點的方式，根據坐標點Xi的數值來表示在當前環境中的位置。根據遺傳算法原理經過編碼所得的這條坐標集合路徑稱為已編碼的染色體，在尋路計算的過程中，多條路徑將會被記錄并進行比較，進而得到最符合條件的一條。

種群可以看成是自然界生物種群的一種形式，一組字符串結構，可以被稱為一個群體，通過隨機選取的方式可以達成種群初始化的目的。在路徑規劃算法中，隨機選取過程通過在除去起點與終點的空間內，隨機選擇坐標而表現，體現了種群的隨機性。該算法由于存儲的方法為坐標點存儲，因而算法中的種群可以看作為從出發點到目標點的所有可行路徑的坐標集合。

文章使用初始化種群的方法：通過最優個體不斷迭代的方法，以一群隨機個體為單位，依照預置的評判標準選擇出最優秀的個體，并放置到具有規模的種群中，重復該操作直到種群內個體達到飽和。具體步驟如下：

1. 首先設定好最大種群規模以及迭代次數等參數。

2. 由起點出發，以起點終點的位置方向為依據，隨機選擇下一個前進的位置，在柵格圖上表示為與當前位置相鄰的柵格。例如在圖2中對應的坐標為（5，9），根據起始點的位置存在有向右（6，9）、向右上（6，10）、向上（5，10）三個方向，可以隨機選擇。

3. 進行隨機選擇的過程中，判斷當前路徑是否為有效路徑的情況時，有如下兩種情況：一為當前位置遇到了障礙物；二為在當前位置向四周進行移動時超出了邊界。因此在算法中，兩方格如果不能相連或者路徑中存在有結點超出邊界的情況則該路徑為無效路徑，隨后重新進行隨機選擇。

在算法執行搜索的過程中，存在搜索點再次納入搜索，造成循環路徑的問題，為了減少算法的盲目性，將應用如下方法：在當前點附近隨機選擇一個點作為下次的路徑結點，隨后不停地重復該過程，在這個過程中所有經過路徑的節點均被標記為數字1，其他為0，未被標注的節點才會納入新路徑節點的選擇范圍。一條路徑選擇完畢后，標記全部移除。

適應度是個體對環境適應性的評判標準，適應度需要用適應度函數來進行計算，在路徑規劃當中，適應度函數通過規劃出的路徑長度作為評價標準，以此標準來構建適應度函數。該算法中忽略了體積速度等物理因素，因而僅結合路徑點的坐標數值這一個變量來對適應度函數來進行構建。

單條路徑所包含的個體數為n，Xn，Yn分別表示路徑節點的橫縱坐標，L為該路徑的總長度。

文章所使用的選擇方法為二元錦標賽選擇法，即從原種群中隨機選擇兩個個體進行比較，選擇最好的一個進入子代種群，隨后重復該過程，直到種群達到原先規模或者達到最大迭代次數。這里具體表現為隨機選擇兩條路徑，將其長度數值L進行比較，較短的那一個進入子代種群。

原始種群中無可用個體選擇結束。單點交叉法為文章的使用方法，單點交叉法即選出需要執行交叉操作的兩個個體，然后隨機選擇交叉點，將兩個個體在此點后的基因片段進行交換，交換后將形成兩個新的個體。該算法表現為某兩條可行路徑結點集合內結點與結點之間的交叉互換，用數學思想表示為坐標與坐標的變換，在該算法的運行過程中，當選擇好的兩個個體滿足了變異的概率p=0.04，則進入變異算子，這里采用的是基本位變異的方法，應用randperm函數隨機選取一個基因位進行變異，變異的位置也同樣適用randperm函數隨機定位，最后，輸出適應度最高的路徑作為最優路徑。整體遺傳算法的核心思路就是對可行路徑上的路徑節點進行隨機變異產生新的路徑點，進而形成新的可行路徑。遺傳算法得出最優路徑，通過節點之間的坐標平方相減再開方得出部分路徑，最后部分路徑相加來實現。

四、仿真結果與分析

為了證明設計的算法能夠進行在存在有障礙物下進行路徑規劃，將采用MATLAB R2018a軟件來進行對避障路徑規劃的模擬仿真。

設置好遺傳算法的工作環境，起始地點坐標為（1，1），目的地坐標為（10，10）， 圖1表示為一個10*10的矩陣，其橫縱向的數字個數代表著工作空間中所有的有效結點，其中0表示可移動的區域，1代表障礙物的位置。該算法中Begin起點與end終點的位置分別設置為（0，0）與（10，10）。在障礙物環境下自動尋路的仿真結果與路徑種群迭代圖如圖1、圖2所示。

路徑規劃部分根據種群迭代次數可知，在改變障礙物前，種群隨著迭代次數的增加，種群的目標值即運行的最短路徑長度不斷地減少，目標值曲線在14.94左右達到穩定值不再發生變化。根據結果數據可知在第一種障礙物環境下最短路徑為14.9。同理在第二種環境下，曲線在14.7左右達到穩定，根據仿真出來的數據結果可知，最短路徑為14.719。由仿真可知，當設置好起點與終點以后，所經過的路徑長度是隨著時間隨機變化的，但最終會在某個數值達到穩定，這個數值就是最短的路徑。

參考文獻：

［1］ 孫波，姜平，周根榮，等. 改進遺傳算法在移動機器人路徑規劃中的應用［J］. 計算機工程與應用，2019，55（17）：5-17.

［2］ 陳爾奎，吳梅花. 基于改進遺傳算法和改進人工勢場法的復雜環境下移動機器人路徑規劃［J］. 科學技術與工程，2018，18（33）：3-11.

［3］ Kai Yit，Parvathy Rajendran. Differential-evolution control parameter optimization for unmanned aerial vehicle path planning［J］. Systems，Man，and Cybernetics：IEEE Transactions on Systems，2019，43（06）：3-17.