避障路徑規(guī)劃的算法研究

張喜英 崔智超 欒文璐 楊帥

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

【關(guān)鍵詞】 遺傳算法；避障路徑規(guī)劃；MATLAB仿真

一、遺傳算法

遺傳算法（Genetic Algorithm）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，它也是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法。

遺傳算法主要包括編碼、初始化種群、適應(yīng)度函數(shù)建立、遺傳操作等步驟。應(yīng)用遺傳算法來(lái)求解問(wèn)題時(shí)，需要對(duì)子代基因進(jìn)行反復(fù)的篩選、交叉和變異操作，最終得到符合條件的解或者迭代次數(shù)達(dá)到規(guī)定次數(shù)。遺傳算法主要包括編碼、初始化種群、適應(yīng)度函數(shù)建立、遺傳操作等步驟。

二、路徑規(guī)劃研究概述

（一）按照搜索范圍劃分

全局規(guī)劃：通過(guò)對(duì)已知環(huán)境模型信息的處理，按照規(guī)劃出的路徑前進(jìn)。全局規(guī)劃得出最優(yōu)解，取決于周圍環(huán)境的參數(shù)。全局規(guī)劃往往是適用于范圍較小，環(huán)境復(fù)雜程度較低的空間，當(dāng)環(huán)境模型較大時(shí)，全局規(guī)劃的計(jì)算量會(huì)增大，運(yùn)算的時(shí)間會(huì)變長(zhǎng)。

局部規(guī)劃：相比于全局規(guī)劃對(duì)整個(gè)空間的解析，局部規(guī)劃將所搜索的范圍局限于當(dāng)前位置的周圍，使得在未知的環(huán)境中能夠具有有效的避障能力。應(yīng)用局部規(guī)劃的實(shí)用性很高，與全局規(guī)劃相比，當(dāng)環(huán)境發(fā)生變化的時(shí)候不用再對(duì)運(yùn)行環(huán)境進(jìn)行建模，這大大提高了算法的實(shí)用性。然而局部規(guī)劃可能會(huì)產(chǎn)生局部最優(yōu)解，無(wú)法正常完成工作。

（二）按照工作環(huán)境劃分

靜態(tài)環(huán)境規(guī)劃：靜態(tài)環(huán)境是指工作的環(huán)境已知，不隨時(shí)間的變化而變化。在這種環(huán)境中，障礙物是靜止的，因而想要規(guī)劃出一條最優(yōu)路徑較為簡(jiǎn)單。靜態(tài)環(huán)境規(guī)劃主要被應(yīng)用于工廠等環(huán)境單一的地方。

動(dòng)態(tài)環(huán)境規(guī)劃：與靜態(tài)環(huán)境相反，動(dòng)態(tài)環(huán)境規(guī)劃指的是在已知或者部分已知的環(huán)境中，存在有運(yùn)動(dòng)軌跡不明的障礙物，在這種情況下規(guī)劃出一條最優(yōu)的路徑。

路徑規(guī)劃有如下特點(diǎn)：

1. 復(fù)雜性：當(dāng)處于含有較多障礙物的環(huán)境或者處于動(dòng)態(tài)環(huán)境中時(shí)，為了得到最優(yōu)的路徑，要進(jìn)行大量的計(jì)算。尤其是動(dòng)態(tài)環(huán)境中，規(guī)劃的難度大幅提高。

2. 隨機(jī)性：當(dāng)工作環(huán)境相對(duì)復(fù)雜時(shí)，需要處理各種的突發(fā)狀況以及不確定因素。

3. 約束性：按照規(guī)劃好的路徑前進(jìn)時(shí)需要考慮到自身的大小、形狀等物理因素，還要考慮自身移動(dòng)速度的問(wèn)題，這些條件是設(shè)計(jì)過(guò)程的重要部分。

4. 多目標(biāo)性：路徑規(guī)劃的最優(yōu)解具有多種評(píng)判標(biāo)準(zhǔn)，有的要求路徑最短為優(yōu)，有的要求到達(dá)時(shí)間最短，不可能完全達(dá)成所有目標(biāo)，因此需要實(shí)時(shí)分析需求進(jìn)而系統(tǒng)的權(quán)衡好各個(gè)要求。

三、避障路徑規(guī)劃方案算法的設(shè)計(jì)

將已知的工作環(huán)境進(jìn)行建模，將障礙物與可行方格進(jìn)行點(diǎn)化處理，并設(shè)置好起點(diǎn)與終點(diǎn)。具體過(guò)程如下：采用柵格建模的方法。其工作原理是將工作空間進(jìn)行格式化處理，將工作的環(huán)境分割成大小相同的方格，空白部分表示可以行進(jìn)的路徑，黑色的部分表示障礙物，并設(shè)置好Begin（開(kāi)始）和End（結(jié)束）兩點(diǎn)，當(dāng)兩方格的中心能夠相連時(shí)，表示為一條可行路徑，否則不能相連。其障礙物環(huán)境的構(gòu)建遵從矩陣。 隨后設(shè)置好相應(yīng)的變異率等參數(shù)，具體過(guò)程如下：

初始參數(shù)定義（染色體編碼）：在路徑規(guī)劃方面，由起點(diǎn)到終點(diǎn)的可行路徑即為遺傳算法中的一條染色體。染色體中每一個(gè)基因片段對(duì)應(yīng)可行路徑片段，整個(gè)染色體可以看成是路徑結(jié)點(diǎn)坐標(biāo)集合。

適應(yīng)度函數(shù)：通過(guò)種群中個(gè)體的特征來(lái)判斷個(gè)體的適應(yīng)程度。這里對(duì)適應(yīng)度的定義即為路徑的長(zhǎng)度。通過(guò)輸入一組節(jié)點(diǎn)坐標(biāo)集合（個(gè)體），來(lái)得到所對(duì)應(yīng)路徑的總長(zhǎng)度，其用公式表示為：

生成初始種群：種群即個(gè)體的集合，這里的種群即為可行路徑的所有坐標(biāo)集合。

計(jì)算個(gè)體的適應(yīng)度：即將個(gè)體輸入至適應(yīng)度函數(shù)。這里是將坐標(biāo)集合輸入至適應(yīng)度函數(shù)得出的路徑長(zhǎng)度。

預(yù)設(shè)條件：當(dāng)達(dá)到種群繁殖次數(shù)的最大數(shù)值或者連續(xù)進(jìn)化次數(shù)達(dá)到某一數(shù)值后最優(yōu)的解不發(fā)生變化。終止條件設(shè)置為達(dá)到運(yùn)算規(guī)定次數(shù)，且連續(xù)多次最短路徑的結(jié)點(diǎn)集合不發(fā)生變化。

選擇運(yùn)算：用于篩檢出計(jì)算至今符合條件的最優(yōu)個(gè)體。這里表示將正在計(jì)算得出的路徑同上一次計(jì)算的路徑做比較，較短的一組路徑坐標(biāo)集將會(huì)被保留。

交叉運(yùn)算：指當(dāng)兩條染色體達(dá)到配對(duì)條件以后，將各自的部分基因片段按照某種交叉方式來(lái)進(jìn)行互換，得到兩條新染色體的過(guò)程。在該算法中，交叉過(guò)程即為在具有一個(gè)或者多個(gè)相同坐標(biāo)點(diǎn)的兩條路徑坐標(biāo)集合中，隨機(jī)將幾個(gè)位于同一位置的坐標(biāo)進(jìn)行交換，形成新的兩個(gè)坐標(biāo)集合。

變異運(yùn)算：染色體經(jīng)過(guò)編碼后將以編碼串的形式表示，變異操作是將某段編碼串上的基因編碼數(shù)值隨機(jī)替換為新的可用編碼值，進(jìn)而產(chǎn)生新的個(gè)體。這里將采用隨機(jī)變異的方法，將某條路徑集合中的坐標(biāo)隨機(jī)變化為其他的坐標(biāo)，形成新的路徑坐標(biāo)集參與下次的運(yùn)算。

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

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

在路徑規(guī)劃的數(shù)據(jù)存儲(chǔ)過(guò)程中，路徑點(diǎn)的存儲(chǔ)采用坐標(biāo)點(diǎn)的方式，根據(jù)坐標(biāo)點(diǎn)Xi的數(shù)值來(lái)表示在當(dāng)前環(huán)境中的位置。根據(jù)遺傳算法原理經(jīng)過(guò)編碼所得的這條坐標(biāo)集合路徑稱為已編碼的染色體，在尋路計(jì)算的過(guò)程中，多條路徑將會(huì)被記錄并進(jìn)行比較，進(jìn)而得到最符合條件的一條。

種群可以看成是自然界生物種群的一種形式，一組字符串結(jié)構(gòu)，可以被稱為一個(gè)群體，通過(guò)隨機(jī)選取的方式可以達(dá)成種群初始化的目的。在路徑規(guī)劃算法中，隨機(jī)選取過(guò)程通過(guò)在除去起點(diǎn)與終點(diǎn)的空間內(nèi)，隨機(jī)選擇坐標(biāo)而表現(xiàn)，體現(xiàn)了種群的隨機(jī)性。該算法由于存儲(chǔ)的方法為坐標(biāo)點(diǎn)存儲(chǔ)，因而算法中的種群可以看作為從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的所有可行路徑的坐標(biāo)集合。

文章使用初始化種群的方法：通過(guò)最優(yōu)個(gè)體不斷迭代的方法，以一群隨機(jī)個(gè)體為單位，依照預(yù)置的評(píng)判標(biāo)準(zhǔn)選擇出最優(yōu)秀的個(gè)體，并放置到具有規(guī)模的種群中，重復(fù)該操作直到種群內(nèi)個(gè)體達(dá)到飽和。具體步驟如下：

1. 首先設(shè)定好最大種群規(guī)模以及迭代次數(shù)等參數(shù)。

2. 由起點(diǎn)出發(fā)，以起點(diǎn)終點(diǎn)的位置方向?yàn)橐罁?jù)，隨機(jī)選擇下一個(gè)前進(jìn)的位置，在柵格圖上表示為與當(dāng)前位置相鄰的柵格。例如在圖2中對(duì)應(yīng)的坐標(biāo)為（5，9），根據(jù)起始點(diǎn)的位置存在有向右（6，9）、向右上（6，10）、向上（5，10）三個(gè)方向，可以隨機(jī)選擇。

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

在算法執(zhí)行搜索的過(guò)程中，存在搜索點(diǎn)再次納入搜索，造成循環(huán)路徑的問(wèn)題，為了減少算法的盲目性，將應(yīng)用如下方法：在當(dāng)前點(diǎn)附近隨機(jī)選擇一個(gè)點(diǎn)作為下次的路徑結(jié)點(diǎn)，隨后不停地重復(fù)該過(guò)程，在這個(gè)過(guò)程中所有經(jīng)過(guò)路徑的節(jié)點(diǎn)均被標(biāo)記為數(shù)字1，其他為0，未被標(biāo)注的節(jié)點(diǎn)才會(huì)納入新路徑節(jié)點(diǎn)的選擇范圍。一條路徑選擇完畢后，標(biāo)記全部移除。

適應(yīng)度是個(gè)體對(duì)環(huán)境適應(yīng)性的評(píng)判標(biāo)準(zhǔn)，適應(yīng)度需要用適應(yīng)度函數(shù)來(lái)進(jìn)行計(jì)算，在路徑規(guī)劃當(dāng)中，適應(yīng)度函數(shù)通過(guò)規(guī)劃出的路徑長(zhǎng)度作為評(píng)價(jià)標(biāo)準(zhǔn)，以此標(biāo)準(zhǔn)來(lái)構(gòu)建適應(yīng)度函數(shù)。該算法中忽略了體積速度等物理因素，因而僅結(jié)合路徑點(diǎn)的坐標(biāo)數(shù)值這一個(gè)變量來(lái)對(duì)適應(yīng)度函數(shù)來(lái)進(jìn)行構(gòu)建。

單條路徑所包含的個(gè)體數(shù)為n，Xn，Yn分別表示路徑節(jié)點(diǎn)的橫縱坐標(biāo)，L為該路徑的總長(zhǎng)度。

文章所使用的選擇方法為二元錦標(biāo)賽選擇法，即從原種群中隨機(jī)選擇兩個(gè)個(gè)體進(jìn)行比較，選擇最好的一個(gè)進(jìn)入子代種群，隨后重復(fù)該過(guò)程，直到種群達(dá)到原先規(guī)模或者達(dá)到最大迭代次數(shù)。這里具體表現(xiàn)為隨機(jī)選擇兩條路徑，將其長(zhǎng)度數(shù)值L進(jìn)行比較，較短的那一個(gè)進(jìn)入子代種群。

原始種群中無(wú)可用個(gè)體選擇結(jié)束。單點(diǎn)交叉法為文章的使用方法，單點(diǎn)交叉法即選出需要執(zhí)行交叉操作的兩個(gè)個(gè)體，然后隨機(jī)選擇交叉點(diǎn)，將兩個(gè)個(gè)體在此點(diǎn)后的基因片段進(jìn)行交換，交換后將形成兩個(gè)新的個(gè)體。該算法表現(xiàn)為某兩條可行路徑結(jié)點(diǎn)集合內(nèi)結(jié)點(diǎn)與結(jié)點(diǎn)之間的交叉互換，用數(shù)學(xué)思想表示為坐標(biāo)與坐標(biāo)的變換，在該算法的運(yùn)行過(guò)程中，當(dāng)選擇好的兩個(gè)個(gè)體滿足了變異的概率p=0.04，則進(jìn)入變異算子，這里采用的是基本位變異的方法，應(yīng)用randperm函數(shù)隨機(jī)選取一個(gè)基因位進(jìn)行變異，變異的位置也同樣適用randperm函數(shù)隨機(jī)定位，最后，輸出適應(yīng)度最高的路徑作為最優(yōu)路徑。整體遺傳算法的核心思路就是對(duì)可行路徑上的路徑節(jié)點(diǎn)進(jìn)行隨機(jī)變異產(chǎn)生新的路徑點(diǎn)，進(jìn)而形成新的可行路徑。遺傳算法得出最優(yōu)路徑，通過(guò)節(jié)點(diǎn)之間的坐標(biāo)平方相減再開(kāi)方得出部分路徑，最后部分路徑相加來(lái)實(shí)現(xiàn)。

四、仿真結(jié)果與分析

為了證明設(shè)計(jì)的算法能夠進(jìn)行在存在有障礙物下進(jìn)行路徑規(guī)劃，將采用MATLAB R2018a軟件來(lái)進(jìn)行對(duì)避障路徑規(guī)劃的模擬仿真。

設(shè)置好遺傳算法的工作環(huán)境，起始地點(diǎn)坐標(biāo)為（1，1），目的地坐標(biāo)為（10，10）， 圖1表示為一個(gè)10*10的矩陣，其橫縱向的數(shù)字個(gè)數(shù)代表著工作空間中所有的有效結(jié)點(diǎn)，其中0表示可移動(dòng)的區(qū)域，1代表障礙物的位置。該算法中Begin起點(diǎn)與end終點(diǎn)的位置分別設(shè)置為（0，0）與（10，10）。在障礙物環(huán)境下自動(dòng)尋路的仿真結(jié)果與路徑種群迭代圖如圖1、圖2所示。

路徑規(guī)劃部分根據(jù)種群迭代次數(shù)可知，在改變障礙物前，種群隨著迭代次數(shù)的增加，種群的目標(biāo)值即運(yùn)行的最短路徑長(zhǎng)度不斷地減少，目標(biāo)值曲線在14.94左右達(dá)到穩(wěn)定值不再發(fā)生變化。根據(jù)結(jié)果數(shù)據(jù)可知在第一種障礙物環(huán)境下最短路徑為14.9。同理在第二種環(huán)境下，曲線在14.7左右達(dá)到穩(wěn)定，根據(jù)仿真出來(lái)的數(shù)據(jù)結(jié)果可知，最短路徑為14.719。由仿真可知，當(dāng)設(shè)置好起點(diǎn)與終點(diǎn)以后，所經(jīng)過(guò)的路徑長(zhǎng)度是隨著時(shí)間隨機(jī)變化的，但最終會(huì)在某個(gè)數(shù)值達(dá)到穩(wěn)定，這個(gè)數(shù)值就是最短的路徑。

參考文獻(xiàn)：

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

［2］ 陳爾奎，吳梅花. 基于改進(jìn)遺傳算法和改進(jìn)人工勢(shì)場(chǎng)法的復(fù)雜環(huán)境下移動(dòng)機(jī)器人路徑規(guī)劃［J］. 科學(xué)技術(shù)與工程，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.