極坐標系下機器人路徑規劃算法

李艷輝， 曲萃萃， 樊曉克， 劉彥昌

( 1. 東北石油大學 電氣信息工程學院，黑龍江 大慶 163318； 2. 淄博職業學院 電子電氣工程學院，山東 淄博 255314； 3.東北石油大學 秦皇島分校，河北 秦皇島 066004 )

0 引言

機器人避障問題為機器人研究領域的熱點，成果被應用于工業、農業、軍事等方面.其主要研究內容為搜索一條從起始狀態到目標狀態的最優或近似最優無碰撞路徑[1-3].李天成等描述一種基于扇形柵格地圖的路徑規劃算法，解決移動機器人靜態避障路徑規劃問題，但采用的模型復雜[4]；朱毅等提出一種基于行為的方法，解決未知環境信息下勢場法路徑規劃的局部極小問題，但計算量大，實時性差[5]；梁瑾等應用并聯神經網絡結構與模擬退火算法相結合的方法，得到一條最優平滑路徑，但計算所需時間較長[6]；Chen M等采用最小化風險和最小化能量消耗為目標函數，研究基于改進蟻群算法的路徑規劃問題[7]，但不能保證尋得路徑最短[8]；遺傳算法提供一種求解復雜系統優化問題的通用框架，對問題種類有很強的魯棒性[9]，被廣泛應用于機器人避障研究[10].

考慮機器人避障模型的復雜性、初始種群的多樣性及實時性等問題，相對于傳統直角坐標系下采用遺傳算法進行路徑規劃[11-15]，筆者提出一種極坐標系下基于遺傳算法的路徑規劃算法.該算法將角度作為編碼對象，同一半圓上產生初始種群，可更好地保持種群多樣性；引入雙避障模式，克服傳統算法在尋優過程中避障所引起的時間贅余；在有障礙物模式中采用重啟策略，克服遺傳算法易早熟的缺點；提出單純形交叉算子，使子代趨近于最優父代.仿真結果表明：該算法在適應度函數復雜程度、算法實時性、規劃的路徑長度上優于傳統直角坐標系下算法.

1 算法分析

1.1 運動模型

根據機器人及障礙物大小，考慮實際工程情況，作假設：(1)機器人工作環境為靜態2維空間半圓區域；(2)將機器人及障礙物視為質點.機器人在2維空間極坐標系下運動模型見圖1，其中：K為起點；T為終點；Xi為機器人當前位置.

將K與T連線所在的極軸n等分，中間目標點Xi坐標為(ri,θi)(i=1,2,…,n-1)，其中ri，θi分別為Xi在極坐標下的半徑和角度.機器人運動模型表示為

圖1 機器人運動模型

(1)

式中：w為同心圓的步長.

研究目的為在極坐標系下采用遺傳算法搜索最優中間目標點，將其與起點、終點順次連接，得到最短無碰撞路徑.與傳統直角坐標系下路徑編碼方式比較，極坐標系下路徑編碼方式把角度作為編碼對象，將復雜的二維編碼簡化為一維編碼優化問題.

1.2 雙模式路徑規劃算法

傳統直角坐標系下基于遺傳算法的路徑規劃算法，沒有根據障礙物位置信息判斷下一最優中間目標點是否需要遺傳算法尋優獲得，使算法尋優時間增加、實時性降低.文中算法分為有障礙物和無障礙物2種模式.

有障礙物模式表示機器人處于有障礙區，采用布爾變量SO表征該模式，SO=1為模式被激活，采用遺傳算法作為路徑規劃算法，在極坐標系下對下一中間目標點角度編碼，尋找最優中間目標點.無障礙物模式表示機器人處于無障礙區，采用布爾變量SNO表征該模式，SNO=1為模式被激活，采用直接向目標點行進方式作為路徑規劃算法，尋找最優中間目標點.2種模式表示為

(2)

當Ci=1(i=1,2,3)時表示事件發生，其中：i=1表示極坐標系下半徑為ri的圓周外范圍；i=2表示極坐標系下半徑為ri-1的圓周內范圍；i=3表示極坐標系下半徑為ri-1和ri之間的圓環范圍.

1.3 適應度函數

適應度函數是影響遺傳算法收斂性和魯棒性的主要因素.機器人路徑規劃的目的為總路徑最短，即要求每段路徑最短.機器人第i段路徑li可表示為

(3)

式中：θi，θi-1為機器人當前和下一中間目標點的角度.

障礙物位置對適應度函數的影響在初始種群選取時排除，只要θi選取時不與障礙物的安全角度φ相交，機器人即可成功避障.因此，可用li的倒數作為適應度函數f，表示為

f=1/li.

(4)

該適應度函數僅用到1個約束條件，計算簡單，避免傳統算法中適應度函數多項加權求和引起優化不穩定問題.

1.4 重啟策略

避障模式下利用遺傳算法尋優時采用重啟策略，如果當前代收斂，則隨機產生1個新的大小相同的初始種群，此種群保留上一代最優個體，其余個體在整個搜索空間內隨機產生.重啟策略的判斷條件及方式為

(1)判斷條件：判斷當前種群是否收斂，如果收斂且當前代數小于進化代數g(g為給定值)，則采用重啟動策略；

(2)重啟方式：保留當前代中適應度最大的個體，隨機生成size-1個(size為初始種群中個體數)個體，與保留的最優個體構成新的初始種群.

與傳統直角坐標系下采用遺傳算法的路徑規劃算法比較，文中算法采用重啟策略可避免早熟現象，保證基因多樣性，提高算法收斂速度.

1.5 單純形交叉算子和自適應變異算子

圖2 單純形交叉算子

遺傳算法的交叉算子選擇借鑒單純形法思想[16]，提出新的實數單純形交叉算子(見圖2).選擇步驟為

(1)當代種群中設概率pc=0.6，選擇2個個體(θi,θi+1)，分別為∠CMD和∠BMD，設fθi+1>fθi，交叉后子代趨近于f較大的父代θi+1.

=β(θi+1-θi)+θi,

(5)

(6)

式(5-6)中：β為交叉系數，在0.5～1.0間隨機產生.

采用自適應的變異算子對種群進行變異操作，產生新個體pj為

pj=0.10-0.01j/size,j=1,2,…,size.

(7)

傳統類似于基因串的遺傳交叉方式產生的子代個體無方向性，單純形交叉算子克服此缺點，使交叉后子代趨近于最優方向.

1.6 算法流程

圖3 路徑規劃算法流程

文中基于遺傳算法在極坐標系下通過區域內搜索路徑，利用選定的適應度函數評估路徑長短，進而確定最優路徑，算法流程見圖3.經過確定中間目標點、避障判斷、遺傳算法尋優、重啟等步驟，得到最短無碰撞路徑.

相對于傳統直角坐標系下采用遺傳算法的路徑規劃，文中算法在極坐標系下建立運動模型，對角度進行路徑編碼，路徑尋優過程中提出雙避障模式，借鑒重啟策略及單純形方法，更好地保持種群多樣性，減少尋優時間、多樣性，提高算法收斂速度.

2 仿真分析

采用文中算法進行仿真實驗，極角坐標系下障礙物坐標與起始點距離見表1，采用雙避障模式遺傳算法.其他參數設置為：初始種群size=20；進化代數g=100；起點及終點等分數n=50.

表1 極坐標系下障礙物坐標及起始點距離

仿真實驗目標點適應度函數曲線和規劃路徑見圖4和圖5.由圖5可見，采用文中算法機器人避開全部障礙物.

為與直角坐標系下采用遺傳算法的路徑規劃對比，將極坐標系下障礙物坐標轉換為直角坐標，采用同樣的起始點距離及參數設置.在直角坐標系下利用遺傳算法進行路徑規劃，仿真實驗適應度函數曲線和規劃路徑見圖6和圖7.由圖7可見，機器人未能避開全部障礙物.

設起始距離為100～500 cm時，不同算法仿真實驗運行時間及規劃路徑長度見表2.由表2可見：文中算法尋優得到的路徑長度為122.15～520.19cm，與傳統直角坐標系采用遺傳算法比較平均路徑長度縮短20.8%，平均運行時間節省75.9%.對比不同算法仿真實驗適應度函數曲線和規劃路徑，文中算法較傳統直角坐標系下算法適應度函數大，尋優次數少，規劃路徑短，實時性好.

圖5 文中算法規劃路徑

圖4 文中算法目標點適應度函數曲線

圖6 傳統算法目標點適應度函數曲線

圖7 傳統算法規劃路徑

表2 不同算法運行時間和規劃路徑長度

3 結束語

提出一種極坐標系下基于遺傳算法的機器人路徑規劃算法，應用于機器人路徑尋優.算法采用雙避障模式，加入重啟策略和單純形交叉算子.與傳統直角坐標系下采用遺傳算法路徑規劃結果比較，文中算法規劃得到的平均運行時間低于傳統算法的75.9%，平均規劃路徑長度小于傳統算法的20.8%.該路徑規劃算法及2種障礙物模式對解決實際工程中機器人避障和路徑規劃問題具有一定參考意義.