移動機器人路徑規(guī)劃仿真研究

1、    移動機器人路徑規(guī)劃仿真研究    梁凱 陳志軍 閆學勤摘 要： 在移動機器人有效路徑規(guī)劃問題的研究中，針對傳統(tǒng)移動機器人有效路徑規(guī)劃算法收斂速度慢、搜索時間長、尋優(yōu)能力差等問題，提出一種人工魚群算法與遺傳算法相結(jié)合的有效路徑規(guī)劃算法。通過柵格法對機器人運動環(huán)境進行建模，在靜態(tài)環(huán)境下使用人工魚群算法進行初始路徑規(guī)劃，將規(guī)劃所得的初始路徑作為遺傳算法的初始種群，并使用改進的遺傳算法進行迭代優(yōu)化，尋求一條從起點到目標點的全局最優(yōu)有效路徑。大量仿真結(jié)果表明，該混合算法相比其他算法，具有較快的收斂速度和較強的尋優(yōu)能力。關(guān)鍵詞： 移動機器人； 路徑規(guī)劃； 遺

2、傳算法； 人工魚群算法； 最優(yōu)有效路徑； 人工魚群遺傳算法： tn911.1?34； tp242 ： a ： 1004?373x（2018）17?0167?06abstract： an efficient path planning algorithm combining artificial fish swarm algorithm and genetic algorithm （afsa?ga） is proposed to overcome the problems of slow convergence speed， long search time and poor search ab

3、ility existing in the traditional effective path planning algorithms for mobile robot. the grid method is used to model the robot motion environment. the artificial fish swarm algorithm is used in the static environment to plan the initial path. the planned initial path is used as the initial popula

4、tion of the genetic algorithm， and the improved genetic algorithm is used for iterative optimization to seek a global optimal efficient path from the starting point to the target point. a large number of simulation results show that the hybrid algorithm has faster convergence speed and stronger opti

5、mization ability than other algorithms.keywords： mobile robot； path planning； genetic algorithm； artificial fish swarm algorithm； optimal effective path； afsa?ga0 引 言移動機器人的路徑規(guī)劃在機器人學領(lǐng)域是最基本同時也是很重要的一個研究課題。它被學者們描述為：如果給機器人確定一個所要運動的環(huán)境，還有起點和期望的終點，那么機器人就可以根據(jù)任務(wù)要求（如路徑是否最短、能量是否消耗最少或時間使用是否最短）來尋求一條運動軌跡，該軌跡要滿足能連接

6、起點和終點，還能躲開環(huán)境中的障礙物，則這樣的運動軌跡稱為最優(yōu)或次優(yōu)的有效路徑。國內(nèi)外眾多學者對移動機器人的路徑規(guī)劃問題進行了廣泛的研究，并取得了一定的成果。傳統(tǒng)的路徑規(guī)劃方法有自由空間法1、可視圖法、人工勢場法等2，但均存在不足。如自由空間法在獲取最優(yōu)路徑上得不到保證；可視圖法當起點和目標點位置發(fā)生變化時，需要重新構(gòu)造可視圖，降低路徑規(guī)劃的效率3；人工勢場法會忽略一些有價值的障礙物分布信息，從而陷入局部最小值等4。近年來，一些學者提出將神經(jīng)網(wǎng)絡(luò)算法、蟻群算法、模擬退火算法、粒子群算法等智能算法應(yīng)用于機器人的路徑規(guī)劃中，雖然都取得了一定的研究成果，但這些智能算法的缺點也非常突出。例如文獻5中提出

7、的基于蟻群算法的移動機器人路徑規(guī)劃方法，雖然一定程度上提高了機器人路徑規(guī)劃的效率，但傳統(tǒng)的蟻群算法后期易陷入局部最優(yōu)解使得收斂速度較慢，不適合求解連續(xù)優(yōu)化問題，因此也不適用于復雜環(huán)境下的移動機器人路徑規(guī)劃。文獻6對遺傳算法在機器人的路徑規(guī)劃上進行了研究，但傳統(tǒng)的遺傳算法容易出現(xiàn)早熟現(xiàn)象、局部尋優(yōu)能力也較差，無法保證可靠性的要求。文獻7研究了基于粒子群算法的移動機器人路徑規(guī)劃，但粒子群算法后期搜索能力不強，易陷入局部最優(yōu)解求解質(zhì)量不高。針對上述問題，本文提出了一種人工魚群算法與遺傳算法相結(jié)合的改進算法。該混合算法中，在靜態(tài)柵格環(huán)境下使用人工魚群算法來規(guī)劃初始路徑，將得到的初始路徑作為遺傳算法的初

8、始種群，再通過改進的遺傳算法對初始種群進行迭代優(yōu)化，最后求出全局最優(yōu)解。通過仿真實驗對比發(fā)現(xiàn)，混合算法具有較快的收斂速度和較強的尋優(yōu)能力。1 移動機器人路徑規(guī)劃原理移動機器人有效路徑規(guī)劃是指在一個所要運動的環(huán)境中，機器人根據(jù)任務(wù)要求來尋求一條最優(yōu)有效運動軌跡，該軌跡可以連接起點和目標點，同時還能躲開環(huán)境中的障礙物。機器人路徑規(guī)劃主要包括以下兩個步驟：1） 環(huán)境模型的建立，根據(jù)機器人的真實運動環(huán)境建立相關(guān)的抽象環(huán)境模型。2） 路徑搜索方法，即尋找能實現(xiàn)任務(wù)要求的路徑搜索算法。綜上所述可知，機器人路徑規(guī)劃的關(guān)鍵技術(shù)是路徑搜索算法。當前的傳統(tǒng)遺傳算法實現(xiàn)路徑規(guī)劃時存在收斂速度慢，路徑規(guī)劃時間長，尋優(yōu)

9、能力差等問題。本文將用人工魚群算法和遺傳算法相結(jié)合的混合算法解決傳統(tǒng)方法存在的問題。2 人工魚群遺傳算法的機器人有效路徑規(guī)劃2.1 環(huán)境建模本文采用柵格法對機器人工作空間進行建模。假設(shè)機器人工作在含有障礙物的10×10的二維靜態(tài)空間，即起點、目標點和障礙物位置信息已知且不發(fā)生變化。用大小相同的柵格對機器人二維工作空間進行劃分，如果柵格內(nèi)有障礙，這樣的柵格叫不可行柵格，相反叫可行柵格。劃分后的工作空間如圖1所示，圖中黑色區(qū)域為不可行柵格，其余的為可行柵格。2.2 人工魚群算法基本原理人工魚群算法（afsa）是一種模仿魚類行為的群體智能優(yōu)化算法。該算法通過模擬魚類的覓食、聚群和追尾來實現(xiàn)

10、最優(yōu)路徑的搜索。人工魚群算法多用于解決連續(xù)空間的優(yōu)化問題，然而基于柵格的機器人路徑規(guī)劃是一個離散的優(yōu)化問題。因此，當用人工魚群算法解決基于柵格的機器人路徑規(guī)劃問題時，需要對人工魚群算法進行新的定義和說明。2.2.1 相關(guān)基本定義2.2.2 人工魚的行為策略人工魚的覓食行為是自由搜索的行為，另外兩個行為是追逐最優(yōu)點的行為。為了提高人工魚的搜索能力，本文對人工魚行為策略做以下描述：覓食行為：設(shè)人工魚所在柵格為gi，其食物濃度為hgi，在neighborgi中選擇gj作為下一步要走的位置，其食物濃度為hgj。設(shè)t為從可行鄰域柵格中選擇柵格的次數(shù)，設(shè)trynumber為從可行鄰域柵格中選擇柵格的最大次

11、數(shù)，則覓食過程步驟為：1） 設(shè)置參數(shù)t和trynumber的大小。2） 設(shè)人工魚所在柵格為gi，在其可行鄰域柵格中選擇gj作為下一步要走的位置，則有g(shù)j=random（neighborgi）。3） 判斷hgj< p>4） 判斷t>trynumber是否成立，如果不成立，轉(zhuǎn)步驟2）；如果成立，轉(zhuǎn)步驟5）。5） 移動到柵格gj。2.3 遺傳算法基本原理遺傳算法的基本思想是對于要研究的問題，在其可行解中初始化一個種群，該種群是由多個個體組成，每個個體都是由基因編碼構(gòu)成。初始生成的種群通過優(yōu)勝劣汰的原理進行逐代演化，最終會生成越來越好的個體，而且每一代種群中個體的優(yōu)劣程度都可以通過適

12、應(yīng)度函數(shù)來體現(xiàn)。種群中的個體可以通過選擇、交叉和變異等操作來生成新一代種群個體，且新一代種群中的個體會變得越來越好。當滿足最后的迭代終止條件時，把末代群體中最優(yōu)的個體經(jīng)過解碼等操作還原為原問題的解，那么這個解就是所要求得的近似最優(yōu)解。通過上面的分析，可以發(fā)現(xiàn)遺傳算法主要包括：1） 初始種群，其規(guī)模一般為50200；2） 適應(yīng)度函數(shù)，用于評價個體優(yōu)劣程度；3） 選擇操作，為了使好的個體以更大的概率遺傳到下一代；4） 交叉操作，是遺傳算法中起核心作用的操作，交叉概率一般為0.51；5） 變異操作，變異能拓展新的搜索空間，使種群保持多樣性，變異概率一般為0.050.1。遺傳算法操作步驟：1） 設(shè)置問

13、題參數(shù)并編碼；2） 初始化種群；3） 計算每個個體的適應(yīng)度函數(shù)；4） 執(zhí)行遺傳操作；5） 產(chǎn)生下一代種群；6） 判斷是否滿足所設(shè)定的最大迭代次數(shù)，如果滿足，則執(zhí)行步驟7），否則執(zhí)行步驟3）；7） 輸出最優(yōu)個體。2.4 人工魚群遺傳算法遺傳算法由于其較好的全局尋優(yōu)能力和較強的并行計算能力而被廣泛應(yīng)用到路徑規(guī)劃領(lǐng)域。但是遺傳算法容易受到初始種群的影響，因為初始種群質(zhì)量的好壞直接影響遺傳算法的計算效率和獲取全局極值的速度。所以本文通過將人工魚群算法和遺傳算法相混合，即把人工魚搜索到的路徑解當作遺傳算法的初始解，再通過遺傳操作進行迭代優(yōu)化最終來求解全局最優(yōu)解。2.4.1 初始種群的產(chǎn)生1） 設(shè)定擁擠度

14、因子，視野域半徑r，最大選擇柵格次數(shù)trynumber，人工魚總數(shù)n，種群大小pop_size，設(shè)種群個體數(shù)目計數(shù)器n=0，為每個種群個體創(chuàng)建路徑表gpathn，同時為每條人工魚創(chuàng)建路徑表pathk。2） 把n條人工魚放在起點gstart，并且把gstart加入路徑表pathk（k=1，2，n）。令k=1，k用來累計魚群。3） 設(shè)人工魚fk所在柵格位置為gk，其可行相鄰柵格域為neighborgk。設(shè)人工魚fk下一步移動到柵格gnext，則柵格gnext=random（neighborgk）。4） 人工魚fk在柵格位置gk通過執(zhí)行追尾行為和聚群行為，選擇使得hgnext取值最小的行為作為最終要

15、執(zhí)行的行為，缺省行為記為覓食行為。5） 把gnext加入到路徑表pathk，判斷人工魚fk是否到達ggoal，如果到達，則保存路徑pathk到gpathn，轉(zhuǎn)步驟7）；否則，若k< p>6） 當所有人工魚都走過一步之后，若沒有人工魚到達終點柵格ggoal，令k=1，轉(zhuǎn)步驟3）。7） n=n+1，如果npop_size，算法結(jié)束，產(chǎn)生大小為pop_size的初始種群。如果n< p>2.4.2 適應(yīng)度函數(shù)的建立適應(yīng)度函數(shù)是評價個體好壞的一種有效手段。首先根據(jù)任務(wù)要求建立適應(yīng)度函數(shù)，然后通過適應(yīng)度函數(shù)計算各個個體的適應(yīng)度值大小，通過求得的適應(yīng)度值的大小來判斷個體的優(yōu)劣程度。本

16、文以路徑最短作為任務(wù)要求，通過規(guī)定適應(yīng)度函數(shù)越大代表路徑越好，適應(yīng)度函數(shù)越小代表路徑越差來建立適應(yīng)度函數(shù)，則適應(yīng)度函數(shù)公式可寫為：2.4.3 遺傳操作1） 選擇操作。選擇操作就是把適應(yīng)度值較大的個體以比較大的概率被選擇遺傳到下一代。本文采用比例選擇操作，具體步驟是：通過求出每一個個體的適應(yīng)度值來算出總的適應(yīng)度值；再求出每一個個體的適應(yīng)度值與總的適應(yīng)度值的比值，它表示了個體被選擇遺傳到下一代的概率；通過模仿賭盤操作來確定每個個體被選擇的次數(shù)。以個體k為例，個體k被選擇的概率為pk=lki=1pop_sizeli，其中種群大小為pop_size，再計算個體k的累積概率qk=i=1kpi。在01范圍

17、內(nèi)生成一個隨機數(shù)，若滿足qk-1<qk，則選中個體k，這種選擇方法可以讓適應(yīng)度函數(shù)值較大的個體以較大的概率被選擇遺傳到下一代，這也確保了優(yōu)秀個體能很好地繁衍到下一代。2） 交叉操作。交叉操作就是在種群中通過選擇兩個父代個體讓其進行基因片段的互換以此產(chǎn)生子代個體。目前交叉操作的方式有很多，單點交叉和多點交叉應(yīng)用的最多且效果顯著，然而兩者本質(zhì)差別不大，所以本文采用單點交叉方式。具體方法是：為了保證交叉后產(chǎn)生的個體不是間斷路徑，在配對的兩個個體中選擇在相同柵格位置進行交叉，如果相同柵格有很多，則在它們中只要選擇一個進行交叉就可以了，如果被選的兩個父代個體沒有共同的柵格，則不執(zhí)行交叉操作。3）

18、變異操作。變異能拓展新的搜索空間，使種群保持多樣性，當種群趨于局部收斂時，可以通過變異防止出現(xiàn)早熟現(xiàn)象。一般情況下變異操作會使得路徑變成間斷路徑，同時會給算法增加難度和運算時間。本文變異操作步驟為：先在路徑中任意選擇一個節(jié)點但該節(jié)點不能是起點和終點，然后通過選擇隨機數(shù)來確定該被選節(jié)點的位置，對被選擇的位置通過變異概率判斷是否要刪除，刪除之后的路徑會被分成上下兩段；把上半段的終點看成路徑起點，把下半段的起點看成路徑終點，再采用本文人工魚群算法的覓食行為將斷開的兩段路徑給連接起來使之成為一條連續(xù)路徑。2.4.4 終止條件本文終止條件設(shè)為：算法進化代數(shù)達到了設(shè)定的最大值。2.4.5 算法流程人工魚群

19、遺傳算法流程如圖2所示。3 仿真結(jié)果與分析為了驗證本文人工魚群遺傳算法的可行性和優(yōu)越性，在10×10的柵格環(huán)境下對該混合算法進行模擬仿真，并與傳統(tǒng)遺傳算法進行比較，仿真過程中混合算法的參數(shù)設(shè)置為：=0.6，n=10，r=4，trynumber=3，pop_size=100，迭代次數(shù)為50，交叉概率pc=0.6，變異概率pm=0.1。傳統(tǒng)遺傳算法的參數(shù)設(shè)置為：初始種群大小為100，迭代次數(shù)為50，pc=0.6，pm=0.1。通過matlab仿真軟件對混合算法和傳統(tǒng)遺傳算法平均運行30次，每次50代，對兩種算法在獲得最優(yōu)解方面進行了研究，兩種算法獲得的最優(yōu)有效路徑如圖3所示，兩種算法在獲

20、得最優(yōu)有效路徑所需迭代次數(shù)的對比如圖4所示。圖3為兩種算法在柵格環(huán)境下找到的最優(yōu)有效路徑，其起點為柵格序號1，終點為柵格序號100，通過柵格序號表示該最短路徑為1 2 13 23 33 44 55 56 66 76 87 97 98 99 100，其長度為15.656 9。圖4是兩種算法各運行30次，對兩種算法在獲得最優(yōu)解所需迭代次數(shù)進行了比較。從圖中可以看到，人工魚群遺傳算法收斂速度較快可以在平均16代以內(nèi)收斂找到全局最優(yōu)解，且前期的搜索速度較快，而遺傳算法平均將近42代才能找到全局最優(yōu)解，且前期搜索速度較慢。為了更好說明本文算法的優(yōu)越性，下面將在10×10的柵格環(huán)境中對本文算法和

21、其他算法運行30次進行比較，在各算法相同參數(shù)下比較結(jié)果總結(jié)于表1。從表1分析可得知，在獲取路徑長度方面，本文算法在獲取最優(yōu)路徑上要明顯好于其他兩種算法，傳統(tǒng)遺傳算法在獲取最優(yōu)有效路徑上的穩(wěn)定性最差，其次是文獻8算法。在規(guī)劃成功率上，文獻8算法和本文算法都可以保證獲得有效路徑，但遺傳算法不能確保獲得有效路徑。在路徑規(guī)劃耗時上，文獻8算法平均用時最短，其次是本文算法，雖然文獻8算法規(guī)劃用時短，但不能保證路徑的質(zhì)量。在平均迭代次數(shù)上，本文算法所需迭代次數(shù)最少。綜上性能分析可以發(fā)現(xiàn)，本文算法在迭代次數(shù)和尋優(yōu)能力上要明顯好于其他算法。驗證了本文算法的可行性和優(yōu)越性。4 結(jié) 語針對由于初始種群的影響而使得

22、傳統(tǒng)遺傳算法收斂速度慢、尋優(yōu)能力差的問題，本文提出一種人工魚群算法與遺傳算法相結(jié)合的混合算法解決該問題。通過對本文算法與其他算法進行仿真比較可以看出，本文算法在尋優(yōu)能力和迭代次數(shù)上明顯好于其他算法，驗證了本文算法在有效路徑規(guī)劃上的可行性和優(yōu)越性。注：本文通訊作者為陳志軍。參考文獻1 張捍東，鄭睿，岑豫皖.移動機器人路徑規(guī)劃技術(shù)的現(xiàn)狀與展望j.系統(tǒng)仿真學報，2005（2）：439?443.zhang handong， zheng rui， cen yuwan. present situation and prospect of mobile robot path planning technol

23、ogy j. journal of system simulation， 2005（2）： 439?443.2 張穎，吳成東，原寶龍.機器人路徑規(guī)劃方法綜述j.控制工程，2003（z1）：152?155.zhang ying， wu chengdong， yuan baolong. a survey of path planning methods for robot j. control engineering， 2003（s1）： 152?155.3 張琦，馬家辰，馬立勇.基于簡化可視圖的環(huán)境建模方法j.東北大學學報（自然科學版），2013，34（10）：1383?1386.zhang q

24、i， ma jiachen， ma liyong. an environment modeling method based on simplified view j. journal of northeastern university （natural science edition）， 2013， 34（10）： 1383?1386.4 趙榮齊.基于人工勢場法的機器人路徑規(guī)劃研究d.濟南：山東大學，2008.zhao rongqi. research on robot path planning based on artificial potential field method d.

25、jinan： shandong university， 2008.5 張銀玲，牛小梅.蟻群算法在移動機器人路徑規(guī)劃中的仿真研究j.計算機仿真，2011，28（6）：231?234.zhang yinling， niu xiaomei. simulation research of ant colony algorithm in mobile robot path planning j. computer simulation， 2011， 28（6）： 231?234.6 楊獻峰，付俊輝.移動機器人路徑規(guī)劃的仿真研究j.計算機仿真，2012，29（7）：223?226.yang xianfeng， fu junhui. simulation research on path planning of mobile robot j. computer simulation， 2012， 29（7）： 223?226.7 魯?shù)?粒子群算法在移動機器人路徑規(guī)