基于遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃方法

張健

（安徽三聯(lián)學(xué)院計(jì)算機(jī)工程學(xué)院，安徽合肥230001）

基于遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃方法

張健

（安徽三聯(lián)學(xué)院計(jì)算機(jī)工程學(xué)院，安徽合肥230001）

機(jī)器人路徑規(guī)劃是機(jī)器人領(lǐng)域的一項(xiàng)重要課題，不同于以往在遺傳算法過程中考慮路徑平滑度的方法，本文提出了一種將遺傳算法過程與路徑平滑過程分開的機(jī)器人路徑規(guī)劃新方法。先設(shè)計(jì)可變長(zhǎng)編碼方式的簡(jiǎn)單遺傳算法產(chǎn)生較優(yōu)的折線路徑，再引入一類新的帶形狀參數(shù)的回旋螺線對(duì)其進(jìn)行平滑操作，以撫平較大轉(zhuǎn)角。整個(gè)路徑規(guī)劃過程，只需輸入障礙物坐標(biāo)即可自適應(yīng)地選擇參數(shù)以產(chǎn)生機(jī)器人行走路徑。仿真結(jié)果表明，將遺傳算法過程與路徑平滑過程分離的做法能降低遺傳算法本身復(fù)雜度，所以設(shè)計(jì)的平滑操作不僅提高了路徑平滑度，還可以減少路徑長(zhǎng)度。

移動(dòng)機(jī)器人；遺傳算法；回旋螺線；平滑操作；路徑規(guī)劃

機(jī)器人路徑規(guī)劃是機(jī)器人領(lǐng)域的一項(xiàng)重要課題，它實(shí)際上是一個(gè)復(fù)雜的非線性規(guī)劃問題，主要解決在含有障礙物的環(huán)境中為機(jī)器人尋找一條從起點(diǎn)到終點(diǎn)的無碰行走路徑的問題，該路徑應(yīng)滿足長(zhǎng)度短、使用時(shí)間少、平滑度高等標(biāo)準(zhǔn)。機(jī)器人路徑規(guī)劃方法的好壞對(duì)機(jī)器人的安全性及工作效率等起到至關(guān)重要作用。目前機(jī)器人路徑規(guī)劃的方法有圖搜索法、Dijkstra算法[1]、人工勢(shì)場(chǎng)法等，這些算法都有各自的優(yōu)點(diǎn)，但是總體來說還存在著適應(yīng)性低、算法復(fù)雜高等問題。作為優(yōu)化算法的一種，遺傳算法[2]在機(jī)器人路徑規(guī)劃這類復(fù)雜的非線性優(yōu)化問題中顯示出很好的魯棒性，已得到了廣泛應(yīng)用。該算法雖然定義了平滑、截?cái)嗟冗z傳操作，能局部調(diào)整機(jī)器人行走路徑的轉(zhuǎn)角，有效考慮了路徑的平滑度問題，但在不同程度上增加了遺傳算法本身的復(fù)雜性。因此，引入回旋螺線，將遺傳過程與平滑操作分開，達(dá)到提高路徑平滑度、縮短路徑長(zhǎng)度的要求，也減小遺傳算法本身復(fù)雜度。

1 回旋螺線相關(guān)問題

1.1 回旋螺線

回旋螺線[3]是一種用Fresnel積分構(gòu)造的平面曲線，它的曲率與弧長(zhǎng)成正比。這里引入一種帶形狀參數(shù)λ（0≤λ≤1）的推廣的Fresnel積分，利用這種積分構(gòu)造的回旋螺線，當(dāng)λ=0.5時(shí)即成為標(biāo)準(zhǔn)的回旋螺線。

定義1曲線

稱為推廣的回旋螺線，簡(jiǎn)稱回旋螺線，其中比例因子α為正數(shù)，形狀因子0≤λ≤1,θ表示切角變差，C（θ；λ）及S（θ；λ）為帶形狀參數(shù)λ的推廣的Fresnel積分，

1.2 回旋螺線偶[3]

定義2回旋螺線偶是由兩條回旋螺線

組合而成，其中Pi（i=0,1）是它們的起點(diǎn)，αi是起點(diǎn)處的比例因子，Ti是起點(diǎn)處的單位切向量，Ni是起點(diǎn)處的單位法向量。要求這兩條回旋螺線之間保持G2連續(xù)，即它們的終點(diǎn)重合，且終點(diǎn)處的切向量平行，不帶符號(hào)的曲率相等。

2 基于遺傳算法與回旋螺線的機(jī)器人路徑規(guī)劃新算法

傳統(tǒng)的遺傳算法在提高機(jī)器人路徑平滑性問題上，多數(shù)采取改寫適應(yīng)度函數(shù)或增加遺傳操作的方法。為了降低遺傳算法本身的復(fù)雜性，靈活調(diào)整路徑中的轉(zhuǎn)角，提出了將平滑過程與遺傳算法過程分開的做法，下面將分別進(jìn)行詳細(xì)討論。

2.1 遺傳算法描述

將機(jī)器人簡(jiǎn)化為質(zhì)點(diǎn)，假設(shè)障礙物為凸多邊形。將障礙物的各邊界向外擴(kuò)張一定的安全距離，形成新的障礙物，這樣即使路徑與新障礙物的某頂點(diǎn)重合，實(shí)際上也與原障礙物保持有安全距離。

（1）編碼方式

所謂編碼是指將問題的解空間轉(zhuǎn)換到遺傳編碼空間的過程。編碼對(duì)于算法的種群多樣化和搜索能力等性能有較大的影響，對(duì)于機(jī)器人路徑規(guī)劃問題，本文采取浮點(diǎn)數(shù)變長(zhǎng)編碼方式，染色體[4]由路徑節(jié)點(diǎn)的笛卡爾坐標(biāo)序列構(gòu)成。一系列點(diǎn)的連接構(gòu)成了染色體，表示是一條可行或者不可行路徑。

（2）種群初始化

遺傳算法的種群初始化過程有很多種，在研究該算法時(shí)，通常隨機(jī)產(chǎn)生初始化種群，該方式生成的初始種群優(yōu)點(diǎn)是適用于任何問題，不依賴于某個(gè)具體問題，缺點(diǎn)是無法確保種群的合理性，算法的高效性也無法確定。本文采用的是在隨機(jī)產(chǎn)生初始種群方式的基礎(chǔ)上增加啟發(fā)式方法，這樣既能提高路徑生成的效率，又能較科學(xué)地體現(xiàn)解空間的信息。

初始種群產(chǎn)生步驟：

step1染色體的個(gè)體包含的中間點(diǎn)個(gè)數(shù)（包含坐標(biāo)）均是隨機(jī)產(chǎn)生；

step2已知路徑中的起點(diǎn)和終點(diǎn)，在無障礙物情況下，該路徑是距離最短、最平滑，借助這一信息可以啟發(fā)式地產(chǎn)生個(gè)體中的其他中間點(diǎn)，達(dá)到提高算法的搜索效率。

（3）適應(yīng)度函數(shù)[5]

在前面的障礙物為凸多邊形環(huán)境表示中已將障礙物邊界向外擴(kuò)充一定的安全距離，且后文還將引入回旋螺線偶對(duì)路徑進(jìn)行平滑操作，故適應(yīng)度函數(shù)只需包括路徑的長(zhǎng)度以及判斷是否與障礙物相碰。適應(yīng)度函數(shù)為

（4）遺傳操作

1)選擇算子：采取輪盤賭方法實(shí)現(xiàn)選擇操作。

2)交叉算子：采取單點(diǎn)交叉的方法。由于是變長(zhǎng)編碼，故兩個(gè)染色體的交叉可以不在同一位置。若新產(chǎn)生的個(gè)體長(zhǎng)度超過了染色體長(zhǎng)度上限，則舍去。

3)變異算子：個(gè)體以一定的概率進(jìn)行變異，范圍為整個(gè)空間，以增加種群多樣性。

（5）遺傳算法終止條件

1)在進(jìn)化過程中適應(yīng)度函數(shù)具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出，則算法終止。

2)種群的適應(yīng)度和最優(yōu)個(gè)體適應(yīng)度不再增加時(shí)，則算法終止。

3)迭代次數(shù)達(dá)到預(yù)設(shè)的代數(shù)時(shí)，預(yù)設(shè)代數(shù)一般設(shè)置在100~500代，則算法終止。

2.2 基于回旋螺線的平滑操作

為了保證機(jī)器人轉(zhuǎn)彎時(shí)的安全性，在適應(yīng)度函數(shù)中增加了路徑平滑度的遺傳算子[6]，若一條路徑中所有節(jié)點(diǎn)的轉(zhuǎn)角之和較大，則降低其適應(yīng)度，從而使該條路徑更容易被淘汰。該方法有效地考慮了路徑平滑度的問題，以較高的效率生成一條較優(yōu)的無碰折線路徑。

現(xiàn)在引入一種帶形狀參數(shù)的推廣的回旋螺線，對(duì)已產(chǎn)生較優(yōu)的無碰折線路徑進(jìn)行平滑操作，通過自適應(yīng)地選擇形狀參數(shù)，從而生成最終平滑的路徑。先介紹在單個(gè)節(jié)點(diǎn)處引入回旋螺線的平滑操作，然后介紹多個(gè)節(jié)點(diǎn)處的平滑操作。

為了簡(jiǎn)化遺傳算法，以較高的效率得到一條較優(yōu)的無碰折線路徑，前面所述的遺傳過程中暫時(shí)省去了路徑平滑度的考慮，此時(shí)的路徑可能含有較大的轉(zhuǎn)角，如圖1中的角α及β。根據(jù)機(jī)器人的具體情況預(yù)先設(shè)定一個(gè)安全轉(zhuǎn)角，依次判斷此路徑上的各個(gè)節(jié)點(diǎn)處的轉(zhuǎn)角大小，當(dāng)超過預(yù)定的安全角度時(shí)，本文將引入上述推廣的回旋螺線偶對(duì)其進(jìn)行平滑操作。

圖1 折線路徑中的大轉(zhuǎn)角

不妨設(shè)Pi點(diǎn)處轉(zhuǎn)角α超過了安全角度，需要對(duì)該點(diǎn)進(jìn)行平滑操作。如圖2，在Pi及其相鄰的兩個(gè)節(jié)點(diǎn)的連線上選取中點(diǎn)A和B，將A、Pi、B等3個(gè)點(diǎn)看作控制頂點(diǎn)，選擇形狀參數(shù)λ，生成回旋螺線偶作為新路徑代替原有折線路徑。這樣，就達(dá)到平滑轉(zhuǎn)角的目的，同時(shí)也縮短了路徑長(zhǎng)度。

圖2 大轉(zhuǎn)角處的平滑操作

若生成的回旋螺線偶碰撞了障礙物，需對(duì)其進(jìn)行調(diào)整。由于受λ=0.5的限制，通過移動(dòng)控制點(diǎn)來避開障礙物，無需移動(dòng)任一控制點(diǎn)，只需增大形狀參數(shù)λ的值就可以使回旋螺線偶更貼近控制多邊形，從而控制其避開障礙物。需要注意的是，形狀參數(shù)λ越大時(shí)，回旋螺線偶越貼近原折線路徑，不利于機(jī)器人的轉(zhuǎn)彎安全。從這一角度考慮，形狀參數(shù)λ應(yīng)越小越好，且此時(shí)路徑長(zhǎng)度也會(huì)縮短。然而，當(dāng)λ過小時(shí)，回旋螺線偶遠(yuǎn)離控制多邊形，很可能碰撞障礙物。故在操作時(shí)，令λ（0≤λ≤1）取值從初始值0.1開始，以步長(zhǎng)0.1增加，自適應(yīng)地選取形狀參數(shù)λ的值，使其滿足定義1條件且產(chǎn)生的路徑不碰撞障礙物的最小值。

當(dāng)路徑中含有多個(gè)較大的轉(zhuǎn)角時(shí)，依次對(duì)每個(gè)轉(zhuǎn)角進(jìn)行平滑處理。如圖3所示，不妨設(shè)Pi及Pi+1處轉(zhuǎn)角均超過了安全角度，分別對(duì)他們進(jìn)行平滑操作。Pi點(diǎn)處的平滑操作與上述相同，下面對(duì)Pi+2點(diǎn)進(jìn)行平滑操作。在Pi+1及Pi+2連線上選取中點(diǎn)C，以B、Pi+1、C為控制點(diǎn)生成回旋螺線偶代替原有Pi+1點(diǎn)處的折線路徑。

作為圓弧與圓弧、直線與直線或圓弧與直線之間的過渡曲線，回旋螺線偶與控制多邊形相結(jié)合生成的樣條曲線能達(dá)到G2連續(xù)。所以回旋螺線偶可以很好地嵌入到遺傳算法得到的折線路徑中，使新產(chǎn)生的路徑能保持較高連續(xù)性。同時(shí)，每個(gè)轉(zhuǎn)角處的平滑操作相互獨(dú)立，即它們的形狀參數(shù)可以獨(dú)立取值，這樣可以通過形狀參數(shù)來局部調(diào)整路徑的形狀，靈活方便。此平滑操作能有效提高機(jī)器人轉(zhuǎn)彎時(shí)的安全性，也縮短了原有折線路徑的長(zhǎng)度[7]。

圖3 多個(gè)轉(zhuǎn)角的平滑處理

3 仿真實(shí)驗(yàn)及結(jié)果分析

3.1 不同環(huán)境下的仿真實(shí)驗(yàn)

本文設(shè)計(jì)的路徑規(guī)劃方法，只需輸入環(huán)境坐標(biāo)，就可以自適應(yīng)地得到最終的平滑路徑。為了驗(yàn)證算法的有效性，下面分別在特殊障礙物、規(guī)則障礙物和不規(guī)則多障礙物的環(huán)境中分別進(jìn)行了3組仿真實(shí)驗(yàn)。

特殊障礙物環(huán)境如圖4所示，其中3個(gè)長(zhǎng)條狀物體為障礙物，機(jī)器人的起點(diǎn)為（0，50），終點(diǎn)為（100，50），此環(huán)境雖然障礙物稀少，但障礙物較大且分布獨(dú)特。圖5為規(guī)則的多障礙物環(huán)境，圖中排列有序的小正方形為一個(gè)個(gè)障礙物，機(jī)器人起點(diǎn)為（0，30），終點(diǎn)為（100，80），此環(huán)境中障礙物分布均勻，但數(shù)量較多。圖6為不規(guī)則的多障礙物環(huán)境，圖中散亂的多邊形為一個(gè)個(gè)障礙物，機(jī)器人起點(diǎn)為（0，0），終點(diǎn)為（100，100），此環(huán)境中障礙物形狀不規(guī)則、分布雜亂、且數(shù)量較多。

圖4 特殊多障礙物環(huán)境圖

圖5 規(guī)則多障礙物環(huán)境

圖6 不規(guī)則多障礙物環(huán)境

特殊障礙物環(huán)境中的仿真實(shí)驗(yàn)。由于障礙物的特殊性，傳統(tǒng)的單純基于遺傳算法的路徑規(guī)劃方法所得路徑難免有較大轉(zhuǎn)角。圖7的折線即為本文遺傳算法部分得到的機(jī)器人避障行走路徑，包含節(jié)點(diǎn)P1，P2，P3，P4，P5，其中P2，P3及P4的轉(zhuǎn)角均超過了預(yù)定的安全角度90度，應(yīng)對(duì)它們進(jìn)行平滑操作。如圖8所示，取P1，P2的中點(diǎn)A，取P2，P3的中點(diǎn)B，取P3，P4的中點(diǎn)C，取P4，P5的中點(diǎn)D，以A，P2，B為P2處的控制點(diǎn)，以B，P3，C為P3處的控制點(diǎn)，以C，P4，D為P4處的控制點(diǎn)，分別對(duì)各點(diǎn)自適應(yīng)地選取形狀參數(shù)，λ（0≤λ≤1）從0.1開始，以步長(zhǎng)0.1增加。經(jīng)計(jì)算，當(dāng)3個(gè)節(jié)點(diǎn)的形狀參數(shù)分別取λ=0.7，λ=0.5，λ=0.3時(shí)，均為首次滿足定義1中回旋螺線偶生成條件的最小形狀參數(shù)。圖8中曲線即為各節(jié)點(diǎn)處首次生成的回旋螺線偶，虛線為控制多邊形，即原有折線路徑。

圖7 遺傳算法所得折線路徑

經(jīng)計(jì)算發(fā)現(xiàn)，此時(shí)P2及P3點(diǎn)處首次生成的回旋螺線偶已經(jīng)能夠避開障礙物，故不再增加其形狀參數(shù)的取值。而P4點(diǎn)處當(dāng)λ=0.3時(shí)雖然滿足回旋螺線偶生成條件，但所產(chǎn)生的路徑會(huì)碰撞障礙物，需要繼續(xù)增加λ的取值。經(jīng)計(jì)算，直至λ=0.5時(shí)，生成的回旋螺線偶不碰撞障礙物，如圖9，故最終取P4的形狀參數(shù)為λ=0.5。

圖8 自適應(yīng)選擇參數(shù)過程

圖9 最終的平滑路徑

在第2組規(guī)則多障礙環(huán)境中進(jìn)行路徑規(guī)劃仿真實(shí)驗(yàn)，該仿真實(shí)驗(yàn)過程與第1組的實(shí)驗(yàn)過程相同。如圖10，折線為遺傳算法部分得到的路徑，包含節(jié)點(diǎn)P1，P2，P3。曲線為對(duì)P2點(diǎn)進(jìn)行平滑操作后產(chǎn)生的回旋螺線，其控制點(diǎn)為P2，P1P2的中點(diǎn)A和P2P3的中點(diǎn)B，最終自適應(yīng)選取P4形狀參數(shù)為λ=0.4。

圖10 規(guī)則多障礙物環(huán)境下最終的平滑路徑

同理，在第3組不規(guī)則多障礙物環(huán)境中的仿真實(shí)驗(yàn)過程與前兩組相同。如圖11，最終自適應(yīng)選取P4形狀參數(shù)為λ=0.6。

圖11 不規(guī)則多障礙物環(huán)境下最終的平滑路徑

由上述仿真結(jié)果可以明顯看出，在3種不同的障礙物環(huán)境中，利用回旋螺線偶對(duì)折線路徑進(jìn)行平滑操作后，都達(dá)到了平滑路徑的效果，路徑總長(zhǎng)度也得到一定程度的縮短。特別是在第1組仿真結(jié)果的特殊障礙物分布情形下，克服了傳統(tǒng)遺傳算法中大轉(zhuǎn)角問題。同時(shí)，也降低了遺傳算法本身的復(fù)雜度。

3.2 與Dijkstra算法的比較

將本文所提出的遺傳算法過程與路徑平滑過程分開的方法與基于Dijkstra算法的路徑規(guī)劃方法進(jìn)行比較，在上述3組不同環(huán)境中進(jìn)行的多次實(shí)驗(yàn)結(jié)果表明，本文提出的路徑規(guī)劃方法得到的最優(yōu)路徑長(zhǎng)度小于基于Dijkstra算法的得到的最優(yōu)路徑長(zhǎng)度，且所使用的平均搜索路徑時(shí)間小于基于Dijkstra算法使用的平均搜索路徑時(shí)間，至少可以節(jié)約5%的搜索時(shí)間。

通過上述比較，發(fā)現(xiàn)遺傳算法過程與路徑平滑過程分開的方法在時(shí)間復(fù)雜度上優(yōu)于Dijkstra算法，在解決路徑規(guī)劃問題方面有一定的優(yōu)勢(shì)。

4 結(jié)束語

傳統(tǒng)的遺傳算法在提高機(jī)器人路徑平滑性的問題上，多數(shù)采取改寫適應(yīng)度函數(shù)或增加遺傳操作的方法，本文則采用遺傳算法過程與路徑平滑過程分開的辦法。遺傳算法產(chǎn)生較優(yōu)路徑后，引入一種新的帶形狀參數(shù)的回旋螺線偶對(duì)其進(jìn)行平滑操作。整個(gè)路徑規(guī)劃過程只需輸入障礙物坐標(biāo)就可以自適應(yīng)的選擇參數(shù)生成平滑的路徑，且只需改變形狀參數(shù)就可以靈活調(diào)節(jié)路徑與障礙物坐標(biāo)距離。仿真結(jié)果表明，引入回旋螺線將遺傳過程與平滑操作分開的方法能達(dá)到提高路徑平滑度、縮短路徑長(zhǎng)度的要求，同時(shí)也減小了遺傳算法本身的復(fù)雜度。

[1]孫自廣，李春貴，王秦.基于改進(jìn)遺傳算法的機(jī)器人路徑規(guī)劃[J].自動(dòng)化與儀表，2009，24（6）：5-7.

[2]李良先.自主型足球機(jī)器人路徑規(guī)劃與避障策略研究[D].焦作：河南理工大學(xué)，2011.

[3]郝博，秦麗娟，姜明洋.基于改進(jìn)遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃方法研究[J].計(jì)算機(jī)工程與科學(xué)，2010，32（7）：104-107.

[4]石鐵峰.改進(jìn)遺傳算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)仿真,2011，28（4）：193-195.

[5]廖衛(wèi)強(qiáng),李振宇.基于遺傳勢(shì)場(chǎng)法的足球機(jī)器人路徑規(guī)劃[J].集美大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，14（2）：179-184.

[6]浦定超.基于遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃的研究[D].合肥：合肥工業(yè)大學(xué)，2010.

[7]李剛，魚佳欣，郭道通,等.基于改進(jìn)遺傳算法的機(jī)器人路徑規(guī)劃與仿真[J].計(jì)算技術(shù)與自動(dòng)化，2015（2）：24-27.

Path Planning Method for Mobile Robot Based on Genetic Algorithm

ZHANG Jian
(School of Computer Engineering，Anhui Sanlian University，Hefei，Anhui 230001，China)

Robot path planning is an important topic in the field of robotics.Considering the path different from the past in the smoothness of the process of genetic algorithm method,a genetic algorithm process is presented by smoothing the path separate from the new path planningmethod.After calculating a path using simplified GAmethod with a variable length coding, a new type of clothoid curvewith wipe parameter is introduced to smooth the sharp turns.In the entire path planning process, the parameter can be chosen adaptively to generate a robot’s walk path as soon as the barrier’s coordinate is entered.The simulation results show that the method of separating smooth process from GA process simplifies GA method.The proposed method can efficiently decrease the path length aswell as increase the path smoothness.

mobile robot；genetic algorithm；cyclotron curve smooth；path planning

TP242

A

1007-4260(2016)04-0048-05

時(shí)間：2017-1-3 17:19

http://www.cnki.net/kcms/detail/34.1150.N.20170103.1719.014.html

2016-03-14

安徽省教育廳高校自然科學(xué)研究項(xiàng)目(KJ2013B090)和安徽三聯(lián)學(xué)院2016年度校級(jí)科研基金（xtcx2016002）。

張健，男，安徽泗縣人，碩士，安徽三聯(lián)學(xué)院計(jì)算機(jī)工程學(xué)院講師，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)。

E-mail:626742382@qq.com

10.13757/j.cnki.cn34-1150/n.2016.04.014