楊坤，程鵬

（1.沈陽工學(xué)院，遼寧 撫順 113122；2.沈陽理工大學(xué)，遼寧 沈陽 110159）

0 引言

機(jī)器人路徑規(guī)劃一直是學(xué)術(shù)界追蹤的熱點(diǎn)問題，其核心目標(biāo)是身處存在阻礙的環(huán)境中，如何給機(jī)器人找出一條路徑，使其既能夠避開障礙物，又能夠到達(dá)指定目標(biāo)位置。需要考慮到如何獲取環(huán)境信息、如何表示環(huán)境、如何進(jìn)行路徑執(zhí)行以及如何獲取知識(shí)等多方面內(nèi)容。

路徑規(guī)劃可以分為在線路徑規(guī)劃和離線路徑規(guī)劃。前者是一種基于傳感器信息的環(huán)境未知的路徑規(guī)劃方法，并且必須在線規(guī)劃路徑。后者是基于環(huán)境的全局路徑規(guī)劃，適用于靜態(tài)環(huán)境的先驗(yàn)完整信息，并且必須離線規(guī)劃路徑。靜態(tài)路徑規(guī)劃意味著機(jī)器人工作所在的環(huán)境是已知的且是靜態(tài)的。在機(jī)器人移動(dòng)之前，路徑的選定是依照既定的環(huán)境信息進(jìn)行規(guī)劃的，擇出最佳路徑后，使機(jī)器人沿著選定路徑從始發(fā)點(diǎn)到目的地。一般來說，可選路徑的數(shù)目不只一條。在實(shí)際應(yīng)用中，通常需要在某種特定情況下選擇出一條最佳路徑。通用標(biāo)準(zhǔn)包括最短路徑，最短用時(shí)以及最低能耗[1-2]。此外，為了提升機(jī)器人在路徑規(guī)劃方面的效率并更好地滿足實(shí)時(shí)性要求，通常將遺傳算法和模擬退火算法引入機(jī)器人的靜態(tài)路徑規(guī)劃和設(shè)計(jì)中。遺傳算法雖然可以從概率的角度隨機(jī)找到全局最優(yōu)解，而模擬退火算法能夠去除局部最優(yōu)解，恰好彌補(bǔ)了遺傳算法局部尋優(yōu)差的弊端。因此，遺傳算法與模擬退火算法的聯(lián)合是解決靜態(tài)路徑規(guī)劃問題的一種方法。

1 遺傳模擬退火算法

遺傳模擬退火(Genetic Simulated Annealing，GSA)算法是將遺傳算法和模擬退火算法相結(jié)合的一種優(yōu)化算法。它不僅包含遺傳算法的并行性和全局性，而且包含模擬退火算法的退火性和局部搜索能力。GSA算法的基本流程：

（1）參數(shù)的選取：群體規(guī)模為n，遺傳代數(shù)最值為N，初始溫度T=T0。

（2）初始溫度變更次數(shù)l=0，0代種群Pl(k)，k=0。

（3）對(duì)現(xiàn)有種群執(zhí)行以下步驟，直至產(chǎn)生下批種群。

①在初始群體Pl(k)中算出適應(yīng)函數(shù)fi(t1)；依據(jù)適應(yīng)函數(shù)的概率分布從Pl(k)中選n個(gè)染色體形成種群Pls(k+1)。

②按常規(guī)遺傳算法對(duì)染色體種群Pls(k+1)交叉，得到種群Plc1(k+1)；在種群Plc1(k+1)中參與交叉操作的單值i和單值j，接收概率Pi和Pj如式1和2所示。經(jīng)迭代，生成新種群Plc1(k+1)。

其中，種群Pls(k+1)中某單值i的目標(biāo)值是f(i)，種群Plc1(k+1)中某單值i的目標(biāo)值是f(i')；種群Pls(k+1)中某單值j的目標(biāo)值是f(j)，種群Plc1(k+1)中某單值j的目標(biāo)值是f(j')。

③根據(jù)常規(guī)遺傳算法對(duì)種群Plc(k+1)進(jìn)行再變異獲得Plm1(k+1)；然后依公式（2.1）中的概率對(duì)變異后的個(gè)體進(jìn)行接受，生成新種群Plm(k+1)。

④Pl(k)=Plm(k+1)，k=k+1。觀測(cè)遺傳代數(shù)，若代數(shù)為N，則轉(zhuǎn)到步驟③，若小于N，則轉(zhuǎn)向步驟①。

（4）將溫度變更，tl+1=d(t1)，Pl1(k)=Pl(k)，l=l+1，k=0。如果滿足條件，停止，輸出最優(yōu)解；不滿足，則轉(zhuǎn)向步驟①。

2 機(jī)器人的靜態(tài)環(huán)境建模

環(huán)境建模是機(jī)器人通過控制傳感器感知外部環(huán)境，從而建立適合于描述外部環(huán)境的數(shù)學(xué)模型的過程。關(guān)鍵在于障礙物的表示，通?？梢灶A(yù)測(cè)全球環(huán)境數(shù)據(jù)。環(huán)境建模利用數(shù)學(xué)模型來概括已知機(jī)器人的視角。環(huán)境建模是機(jī)器人進(jìn)行路徑規(guī)劃和規(guī)避障礙的核心操作。路徑規(guī)劃方法中，被專家學(xué)者最為關(guān)注的方法之一就是網(wǎng)格解耦方法，它將機(jī)器人的能動(dòng)空間劃分為若干簡(jiǎn)單的網(wǎng)格，進(jìn)而形成一個(gè)連接圖，在該圖上搜索從起始網(wǎng)格到目標(biāo)網(wǎng)格的路徑。該方法可以確保只要在起點(diǎn)和目標(biāo)點(diǎn)之間存在一條路徑，就可以完整地搜索該路徑[4-5]。

假定機(jī)器人處于二維工作空間內(nèi)，障礙物的大小、所在坐標(biāo)以及各項(xiàng)參數(shù)均保持不變，將此二維工作空間分成等大的網(wǎng)格，其面積限制在機(jī)器人可以自由移動(dòng)的范圍。若是網(wǎng)格中不存在任何阻擋，則為自由網(wǎng)格；否則稱為障礙網(wǎng)格。網(wǎng)格由自由網(wǎng)格和障礙網(wǎng)格組成。機(jī)器人環(huán)境工作空間建立如圖1所示。圖中黑色區(qū)域是障礙網(wǎng)格。

圖1 機(jī)器人環(huán)境的建立

3 路徑規(guī)劃方法設(shè)計(jì)與仿真

3.1 路徑規(guī)劃求解流程

圖2所示為基于GSA算法的路徑規(guī)劃問題求解過程。其流程可用下述步驟來描述[5-6]。

圖2 GSA算法的路徑規(guī)劃問題求解過程

步驟1：遺傳代數(shù)t初始值設(shè)為0；初始路徑集合選用隨機(jī)P(t)。

步驟2：選定初始路徑值T=max。

步驟3：評(píng)價(jià)P(t)中各條路徑的適應(yīng)值

步驟5：由交叉算子進(jìn)行子代路徑交叉操作

步驟6：由變異算子進(jìn)行子代路徑變異操作

步驟7：評(píng)價(jià)P''(t)中各條路徑的適應(yīng)值

步驟8：假設(shè)上述遺傳操作是由P(t)中的父代路徑PI和PJ生成：P''(t)中的子代路徑CI和CJ（I，J=1,2,...,M），選定概率Pi和Pj，將PI、PJ設(shè)為新路徑，選定概率(1-Pi)和(1-Pj)，將CI和CJ設(shè)為新路徑，進(jìn)而產(chǎn)生單代遺傳后的新路徑

步驟9：由擇優(yōu)選擇模型保留最佳路徑

步驟10：停止判斷條件。若不滿足停止條件，則根據(jù)降溫表設(shè)定溫度T，t=t-1，返回步驟3。

當(dāng)達(dá)到停止條件或增加到設(shè)定迭代次數(shù)時(shí)，即可獲得當(dāng)前最佳路徑，算法結(jié)束。

3.2 仿真結(jié)果

為了驗(yàn)證所提出方法的合理性和正確性，本文以Visual C++6.0為仿真工具，設(shè)M為種群個(gè)數(shù)，值為50，Pc為交叉概率，值為0.6，Pm為變異概率，值為0.01，n為編碼長(zhǎng)度，值為16，即選用16個(gè)點(diǎn)構(gòu)成單路。圖3和圖4分別為迭代4次和5次時(shí)的仿真結(jié)果，路徑規(guī)劃最優(yōu)曲線如圖所示，該路徑無尖峰點(diǎn)，已知障礙物大小、方位及其參數(shù)不變。

圖3 迭代4次對(duì)應(yīng)的路徑規(guī)劃結(jié)果

圖4 迭代5次對(duì)應(yīng)的路徑規(guī)劃結(jié)果

4 結(jié)語

在對(duì)機(jī)器人傳統(tǒng)路徑規(guī)劃算法進(jìn)行分析的基礎(chǔ)上，實(shí)現(xiàn)機(jī)器人靜態(tài)路徑規(guī)劃利用了GSA算法，驗(yàn)證了該方法的合理性和正確性，為后續(xù)機(jī)器人領(lǐng)域的研究提供了技術(shù)支撐。