一種基於種群多樣性的自適應多目標機器人避障算法
2023-05-18 13:13:26 2
一種基於種群多樣性的自適應多目標機器人避障算法
【專利摘要】本發明涉及一種基於種群多樣性的自適應多目標機器人避障算法。按以下步驟進行：步驟一：對環境進行建模,種群初始化，並判斷種群個體與障礙物之間的關係；步驟二：基於種群多樣性的自適應多目標機器人路徑規划算法；步驟三：對所得的結果進行路徑平滑處理，最後得到該地圖中機器人行走的最優路徑。本發明方法具有以下有益效果：本發明提出一種基於種群多樣性的自適應調整遺傳參數的改進方法，給出了一種快速有效的全局路徑規劃方法。進一步拓寬了機器人的應用範圍，提高了算法的魯棒性。本發明的方法相比於其他方法而言，顯著提高了算法對於路徑規劃問題的處理速度。
【專利說明】一種基於種群多樣性的自適應多目標機器人避障算法【技術領域】
[0001]本發明公開了一種基於種群多樣性的多目標機器人避障方法，屬於人工智慧領域。
技術背景
[0002]移動機器人是智能控制技術中的一個重要領域，已經被廣泛應用在軍事、工業、農業和教育等領域。路徑規劃是移動機器人系統中的一個重要內容，他直接影響機器人完成任務的質量。其任務就是實現使機器人在其工作環境中能夠自主的從起點運動到終點，同時滿足一定的約束條件，約束條件包括不與障礙物碰撞；運動路徑最短；運動軌跡儘量光滑等。多目標進化算法(MOEA)是一類模擬生物進化機制而形成的全局性概率優化搜索方法，在20世紀90年代中期開始迅速 發展，其發展可以分為兩個階段。第一階段主要有兩種方法即不基於Pareto優化的方法和基於Pareto優化的方法；第二個階段就是在此基礎上提出了外部集這個概念，外部集存放的是當前代的所有非支配個體，從而使解集保持較好的分布度。這個時期提出的多目標進化算法更多地強調算法的效率和有效性。在這兩個階段中，比較典型的多目標進化算法有NSGA2、PESA2和SPEA2等。
[0003]
【發明內容】
[0004]本發明的目的在於針對現有技術的不足，提供一種基於種群多樣性的多目標機器人路徑避障方法。根據本發明的方案，提出了一種基於種群多樣性的多目標機器人避障方法，包括以下步驟:
步驟一:對環境進行建模，種群初始化，並判斷種群個體與障礙物之間的關係。
[0005]步驟二:基於種群多樣性的自適應多目標機器人路徑規划算法。
[0006]步驟三:對所得的結果進行路徑平滑處理，最後得到該地圖中機器人行走的最優路徑。
[0007]相比現有技術，本發明方法具有以下有益效果:
一般的進化算法採用固定的遺傳參數，種群進化容易陷入局部收斂，當搜索空間特別不規則時，表現地尤為明顯。不能根據種群的進化情況進行自適應調整，這限制了算法的收斂速度，這就使得進化走向局部收斂的可能性增加。本發明提出一種基於種群多樣性的自適應調整遺傳參數的改進方法，給出了一種快速有效的全局路徑規劃方法。進一步拓寬了機器人的應用範圍，提高了算法的魯棒性。本發明的方法相比於其他方法而言，顯著提高了算法對於路徑規劃問題的處理速度。
【專利附圖】
【附圖說明】
[0008]圖1是本文機器人避障算法的流程圖。
[0009]圖2、3、4是本文算法與未改進算法的收斂分析圖。[0010]圖5、6是本文避障機器人行走的最優路徑圖。
【具體實施方式】
[0011]下面結合附圖對本發明作具體說明。所描述的實施範例僅是為了說明的目的，而不是對本發明範圍的限制。
[0012]步驟一:對環境進行建模，種群初始化，並判斷種群個體與障礙物之間的關係。
[0013](1)環境建模:多邊形表示障礙物，點表示機器人，確定機器人的起始點與終止點。
[0014](2)種群初始化:將起點和終點做一條直線連線，將該直線看成是新的橫坐標軸XX，做垂直於XX的新的縱坐標軸YY。將該直線若干等分，下面就可以在每條等分線上分別隨機取一點，形成初始種群個體。
[0015](3)判斷種群個體是否在障礙物內
若在障礙物內或在邊緣上，則刪除該點，並重新生成初始點，否則保留該點。隨機點與障礙物的關係在這裡採用射線法進行判別。所謂射線法是以隨機點為端點向左做平行於X軸的射線L，然後計算該射線L與障礙物的焦點。若焦點為偶數個，說明隨機點在障礙物外部；若焦點為奇數個，說明隨機點在障礙物內部，那麼需要刪除此點。但是有些特殊的情況需要考慮，比如L與某障礙物的邊重合或平行，則計算焦點沒有意義，因此障礙物中水平的邊不做考慮；另外，射線L恰好經過障礙物的某個端點時，若端點所在障礙物的邊中縱坐標的值大於另一端點的縱坐標的值，則計數；否則不計數。
[0016](4)判斷機器人路徑是否與障礙物相交
首先取第一個障礙物的第一條邊和隨機點結構的第一條邊，根據線段所在邊的直線方程來計算折線與障礙物邊是否相交。循環操作，計算出每條折線與每個障礙物的每條邊的交點。判定交點是否在障礙物邊所在線段的範圍。若某路徑段與障礙物的某條邊相交，我們採用重新生成第二個路徑點的方式重新初始化該點，一直到所有路徑與障礙物均不相交為止。
[0017]步驟二:基於種群多樣性的自適應多目標機器人路徑規划算法
(I)計算種群個體的適應度，並進行環境選擇。如果外部存檔集的規模超過約定值，利用修剪過程降低其大小，如果大小比約定值小，則從種群個體中選取支配個體填滿之。
[0018](2)判斷是否滿足終止條件。若滿足，則返回結果並結束，否則繼續。
[0019](3)對種群進行錦標賽選擇
(4)計算種群多樣性指數 其中種群多樣性指數醜定義如下:
【權利要求】
1.一種基於種群多樣性的自適應多目標機器人避障算法，其特徵在於，按以下步驟進行: 步驟一:對環境進行建模，種群初始化，並判斷種群個體與障礙物之間的關係； 步驟二:基於種群多樣性的自適應多目標機器人路徑規划算法； 步驟三:對所得的結果進行路徑平滑處理，最後得到該地圖中機器人行走的最優路徑。
2.根據權利要求1所述的一種基於種群多樣性的自適應多目標機器人避障算法，其特徵在於， 步驟一:對環境進行建模，種群初始化，並判斷種群個體與障礙物之間的關係: (1)環境建模:多邊形表示障礙物，點表示機器人，確定機器人的起始點與終止點； (2)種群初始化:將起點和終點做一條直線連線，將該直線看成是新的橫坐標軸XX，做垂直於XX的新的縱坐標軸YY，將該直線若干等分，下面就可以在每條等分線上分別隨機取一點，形成初始種群個體； (3)判斷種群個體是否在障礙物內: 若在障礙物內或在邊緣上，則刪除該點，並重新生成初始點，否則保留該點；隨機點與障礙物的關係採用射線法進行判別； (4)判斷機器人路徑是否與障礙物相交: 首先取第一個障礙物的第一條邊和隨機點結構的第一條邊，根據線段所在邊的直線方程來計算折線與障礙物邊是否相交；循環操作，計算出每條折線與每個障礙物的每條邊的交點，判定交點是否在障礙物邊所在線段的範圍，若某路徑段與障礙物的某條邊相交，採用重新生成第二個路徑點的方式重新初始化該點，一直到所有路徑與障礙物均不相交為止。
3.根據權利要求1所述的一種基於種群多樣性的自適應多目標機器人避障算法，其特徵在於， 步驟二:基於種群多樣性的自適應多目標機器人路徑規划算法: (1)計算種群個體的適應度，並進行環境選擇，如果外部存檔集的規模超過約定值，利用修剪過程降低其大小，如果大小比約定值小，則從種群個體中選取支配個體填滿之； (2)判斷是否滿足終止條件，若滿足，則返回結果並結束，否則繼續； (3)對種群進行錦標賽選擇； (4)計算種群多樣性指數； 其中種群多樣性指數H定義如下:H丄
mAX( I )
^ = -Σ F.(2) 其中，η表示物種數目，？.表示種群內第個物種佔總數的比例。為了定量的分析種群多樣性，我們定義數值D為物種聚集距離，如果若干個體之間的聚集距離均小於D ,那麼它們之間存在著足夠高的的相似度，這些個體構成一個物種； (5)按照自適應調整公式對交叉變異概率進行調整: 基於種群多樣性的自適應交叉變異概率調整公式如下:
4.根據權利要求1所述的一種基於種群多樣性的自適應多目標機器人避障算法，其特徵在於， 步驟三、對所得的結果進行路徑平滑處理並且輸出結果: 在算法結束後，對所得到的機器人路徑進行平滑處理，具體方法運用計算幾何的方法求解兩條線段之間夾角的情況；如果是鈍角的話不做特殊處理，如果是銳角或者是直角的話，也就是說機器人在拐彎時的角度過大，因此就需要修改路徑，需要將夾角為銳角或直角的兩條相鄰的邊上增加結點，經過平滑處理後，最後得到該地圖中機器人行走的最優路徑。
【文檔編號】G01C21/00GK104035438SQ201310563216
【公開日】2014年9月10日 申請日期:2013年11月14日 優先權日:2013年11月14日
【發明者】胡凱, 翁理國, 夏旻 申請人:揚州西岐自動化科技有限公司