極坐標(biāo)系下機器人路徑規(guī)劃算法

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

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

0 引言

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

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

1 算法分析

1.1 運動模型

根據(jù)機器人及障礙物大小，考慮實際工程情況，作假設(shè)：(1)機器人工作環(huán)境為靜態(tài)2維空間半圓區(qū)域；(2)將機器人及障礙物視為質(zhì)點.機器人在2維空間極坐標(biāo)系下運動模型見圖1，其中：K為起點；T為終點；Xi為機器人當(dāng)前位置.

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

圖1 機器人運動模型

(1)

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

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

1.2 雙模式路徑規(guī)劃算法

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

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

(2)

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

1.3 適應(yīng)度函數(shù)

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

(3)

式中：θi，θi-1為機器人當(dāng)前和下一中間目標(biāo)點的角度.

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

f=1/li.

(4)

該適應(yīng)度函數(shù)僅用到1個約束條件，計算簡單，避免傳統(tǒng)算法中適應(yīng)度函數(shù)多項加權(quán)求和引起優(yōu)化不穩(wěn)定問題.

1.4 重啟策略

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

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

(2)重啟方式：保留當(dāng)前代中適應(yīng)度最大的個體，隨機生成size-1個(size為初始種群中個體數(shù))個體，與保留的最優(yōu)個體構(gòu)成新的初始種群.

與傳統(tǒng)直角坐標(biāo)系下采用遺傳算法的路徑規(guī)劃算法比較，文中算法采用重啟策略可避免早熟現(xiàn)象，保證基因多樣性，提高算法收斂速度.

1.5 單純形交叉算子和自適應(yīng)變異算子

圖2 單純形交叉算子

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

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

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

(5)

(6)

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

采用自適應(yīng)的變異算子對種群進(jìn)行變異操作，產(chǎn)生新個體pj為

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

(7)

傳統(tǒng)類似于基因串的遺傳交叉方式產(chǎn)生的子代個體無方向性，單純形交叉算子克服此缺點，使交叉后子代趨近于最優(yōu)方向.

1.6 算法流程

圖3 路徑規(guī)劃算法流程

文中基于遺傳算法在極坐標(biāo)系下通過區(qū)域內(nèi)搜索路徑，利用選定的適應(yīng)度函數(shù)評估路徑長短，進(jìn)而確定最優(yōu)路徑，算法流程見圖3.經(jīng)過確定中間目標(biāo)點、避障判斷、遺傳算法尋優(yōu)、重啟等步驟，得到最短無碰撞路徑.

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

2 仿真分析

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

表1 極坐標(biāo)系下障礙物坐標(biāo)及起始點距離

仿真實驗?zāi)繕?biāo)點適應(yīng)度函數(shù)曲線和規(guī)劃路徑見圖4和圖5.由圖5可見，采用文中算法機器人避開全部障礙物.

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

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

圖5 文中算法規(guī)劃路徑

圖4 文中算法目標(biāo)點適應(yīng)度函數(shù)曲線

圖6 傳統(tǒng)算法目標(biāo)點適應(yīng)度函數(shù)曲線

圖7 傳統(tǒng)算法規(guī)劃路徑

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

3 結(jié)束語

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