徐巖 崔媛媛

摘? ?要：為在路徑規(guī)劃過程中得到一條適用于實際情況的最優(yōu)路徑，并克服遺傳算法自身固有的易收斂于局部最優(yōu)解和復(fù)雜度較高的缺點，提出一種基于Q-IGA（Q-standard Improved Genetic Algorithm）算法動態(tài)搜索貝塞爾曲線控制點的路徑規(guī)劃算法. 該算法摒棄利用貝塞爾曲線直接擬合最優(yōu)路徑的靜態(tài)方式，使路徑搜索與控制點搜索兩個過程同時進行;并且在選擇算子中添加一個判斷準(zhǔn)則，利用Q值檢驗法剔除相似度較高的解決方案，增強種群的多樣性;與此同時，優(yōu)化適應(yīng)度函數(shù)，加入機器人體積及轉(zhuǎn)彎角度帶來的代價，使選擇出的路徑是一條距離較短且與障礙物保持安全距離的合理路徑. 仿真結(jié)果表明，Q-IGA算法比改進人工勢場法和混合遺傳算法得到的路徑更為合理，可降低機器人耗能，減少搜索時間，更適于實際的工業(yè)應(yīng)用.

關(guān)鍵詞：移動機器人;路徑規(guī)劃;Q-IGA;貝塞爾曲線

中圖分類號：TP242? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標(biāo)志碼：A

Q-IGA-based Path Planning with Dynamically Fitted Bezier Curve

XU Yan，CUI Yuanyuan?

（School of Electrical and Information Engineering，Tianjin University，Tianjin 300072，China）

Abstract：In path planning，in order to obtain an optimal path suitable for actual situation and overcome the inherent shortcomings of genetic algorithm，such as easy converging to local optimal and high complexity，a Q-standard Improved Genetic Algorithm （Q-IGA） based path planning algorithm with dynamically fitted Bezier curve is proposed in this paper. The proposed algorithm replaces the static fitting method of directly using Bezier curve in order to simultaneously search the path and control points of Bezier curve. What's more，an additional judgment criterion based on Q value is added into selection operator，which can eliminate the solutions with high similarity and enhance the diversity of the population. At the same time，the proposed method optimizes the fitness function by taking robot volume and turning angle into consideration，so that the selected path is not only short but also a reasonable path which keeps a safe distance from the obstacles. Simulation results show that the paths produced by Q-IGA algorithm are more reasonable than those produced by improved artificial potential field algorithm and hybrid genetic algorithm. As it can reduce the search time and the energy consumption of the robot，the proposed method is more suitable for practical industrial applications.

Key words：mobile robot;path planning;Q-IGA;Bezier curve

隨著計算機技術(shù)、控制理論、傳感器技術(shù)和人工智能等眾多交叉學(xué)科的發(fā)展成熟[1]，自導(dǎo)航機器人技術(shù)得到快速發(fā)展，各式各樣的機器人被應(yīng)用于科學(xué)研究、工業(yè)生產(chǎn)、家居生活等眾多領(lǐng)域. 自導(dǎo)航機器人技術(shù)不僅是移動機器人完成高難度任務(wù)的基石，也是機器人智能化成熟的重要標(biāo)志[2]. 控制自導(dǎo)航機器人運動的算法[3]主要由定位算法、導(dǎo)航控制算法以及路徑規(guī)劃算法3部分組成. 在路徑搜索過程中安全避障是機器人順利完成任務(wù)的前提，因此路徑規(guī)劃方法的優(yōu)劣對機器人作業(yè)具有重要影響，并且在無人機[4]、無人車等領(lǐng)域也具有廣泛的應(yīng)用. 路徑規(guī)劃的目的是尋找一條從起始點到目標(biāo)點的無碰撞最優(yōu)路徑. 目前，已有很多研究者致力于路徑規(guī)劃算法研究，從早期的柵格法、可視圖法、人工勢場法[5]等傳統(tǒng)算法到遺傳算法、粒子群算法等智能算法以及衍生出的改進算法等[6]，研究不斷深入并取得豐碩成果. 然而傳統(tǒng)路徑規(guī)劃算法依舊存在很大的局限性，因此智能算法憑借其獨特的優(yōu)良性能成為研究重點. 由于遺傳算法的進化算子具有各態(tài)歷經(jīng)性，使其能夠有效處理具有概率意義的全局搜索，并且搜索過程不需要限制問題的內(nèi)在性質(zhì)，因而在解決路徑規(guī)劃問題方面脫穎而出.

Tuncer和Yildirim提出一種改進的遺傳算法，通過建立含有障礙物信息的代價矩陣，將地圖特征信息引入初始種群中，并采用動態(tài)參數(shù)設(shè)置策略，在變異算子中加入預(yù)測過程，有效提高了算法的搜索效率和計算精度[7];Tsai等人提出將兩種精英遺傳算法并行執(zhí)行，并在其中加入遷移算子，使種群保持較好的多樣性，抑制其過早收斂[8]. 為了解決惡劣環(huán)境下的全局路徑規(guī)劃問題，Hu等人提出了一種基于知識的遺傳算法，將不同環(huán)境區(qū)域的先驗知識整合到特定的遺傳算子中，并結(jié)合局部搜索技術(shù)，使其能在復(fù)雜的靜態(tài)和動態(tài)環(huán)境中找到最優(yōu)或接近最優(yōu)的機器人路徑[9];Alajlan等人提出將遺傳算法與路徑最小化原則結(jié)合，在執(zhí)行選擇算子過程中生成最小化原則，在變異階段使用此規(guī)則，有效縮短了路徑長度[10];Lau等人提出一種利用模糊邏輯引導(dǎo)遺傳算法進行隨機搜索的方法[11]，模糊邏輯的作用是在連續(xù)迭代10次后動態(tài)調(diào)整交叉概率和變異概率. 該方法使遺傳算法的計算效率有效提高，在不同環(huán)境下的適應(yīng)能力有效增強;鄧乾旺等人提出多目標(biāo)優(yōu)化操作的遺傳算法，添加記憶算子為插入算子和變異算子選取合適的方向和步長[12].

雖然以上各種優(yōu)化方法克服了遺傳算法固有的一些缺點，例如：提升了對新空間的探索能力以防止過早收斂到局部最優(yōu)解;降低復(fù)雜度以防止在個體數(shù)量較多時計算效率過低. 然而，對于應(yīng)用在實際生產(chǎn)生活環(huán)境中的機器人路徑導(dǎo)航系統(tǒng)，很多時候所需最優(yōu)結(jié)果不一定是上述方法中所描述的最短路徑. 相對地，更希望得到一條“合理”的路徑. 在這里，合理的路徑被定義為這樣一條路徑，即：路徑既沒有穿過障礙物，也不會緊緊貼著障礙物行進，并且盡可能少的做出大角度的轉(zhuǎn)彎，在滿足上述條件的前提下，使得路程盡可能最短.

因此，針對上述問題與需求，提出一種利用Q-IGA算法協(xié)同搜索貝塞爾曲線控制點的方法. 該方法避免了傳統(tǒng)算法中先生成最優(yōu)路徑再利用貝塞爾曲線擬合出平滑路徑造成的步驟繁瑣，使路徑的平滑與搜索過程并行執(zhí)行. 并且在遺傳算法的選擇算子中利用Q值檢驗法的思想判斷種群內(nèi)解方案的多樣性，去掉相似度較高的解，增強其勘探能力，使算法搜索效率提高. 同時該算法通過修正適應(yīng)度函數(shù)公式，加入除路徑長度外的其他代價因素，使生成的路徑滿足前文所述對路徑合理性的要求. 仿真結(jié)果表明：Q-IGA算法相較于改進人工勢場法和混合遺傳算法，可以得到與障礙物保持一定安全距離的平滑路徑且計算效率更高. 在機器人應(yīng)用中，該方法為避免能量耗竭提供了一種有效途徑，特別是在動態(tài)資源有限的機器人應(yīng)用中.

1? ?數(shù)學(xué)模型

1.1? ?遺傳算法

利用遺傳算法求解路徑規(guī)劃問題包含以下幾個基本步驟：首先隨機產(chǎn)生一個初始種群，然后計算種群內(nèi)每一個個體的適應(yīng)度值并利用選擇算子篩選出適應(yīng)度值較高的個體參與迭代，在迭代中按照一定的概率進行交叉和變異操作積累優(yōu)良基因，然后再次計算種群內(nèi)新個體的適應(yīng)度值，反復(fù)迭代直至輸出最佳個體及最優(yōu)解.

1.2? ?貝塞爾曲線

貝塞爾曲線具有良好的幾何特性，在計算機圖形學(xué)中得到廣泛的應(yīng)用. 貝塞爾曲線的最大優(yōu)點之一是，如果控制點構(gòu)成的多邊形是凸多邊形，即其特征多邊形是凸的，則貝塞爾曲線也是凸的. 此特點使得貝塞爾曲線具有良好的擬合特性.

給定R3：B：[0，1]→R3，它代表n+1個控制點，i=0，1，…，n . n次貝塞爾曲線可由n次Bernestein基多項式組成的參數(shù)曲線表示，定義為[13]：

P（t）= pi Bi，n（t），t∈[0，1]? ? （1）

式中：t表示歸一化時間變量;Bi，n（t）是Bernestein基多項式，代表貝塞爾曲線中的基函數(shù)，其表達式定義如下：

Bi，n（t）=Ci

nti（1-t）n-i=ti（1-t）n-i，

i = 0，1，…，n? ? ?（2）

貝塞爾曲線的導(dǎo)數(shù)由控制點決定，其一階導(dǎo)數(shù)可以表示為：

[P] （t）==nBi，n-1（t）（Pi+1 - Pi）? ? ?（3）

在二維空間中，貝塞爾曲線相對于t的曲率可以表示為：

K（t）= =? ? （4）

式中：R（t）為曲率半徑;[p] x（t）、[p] y（t）、[p]x（t）、[p]y（t）分別為貝塞爾曲線坐標(biāo)分量對x和y的一階導(dǎo)數(shù)和二階導(dǎo)數(shù).

2? ?基于Q-IGA的動態(tài)搜索策略

2.1? ?環(huán)境建模

機器人行進的環(huán)境為一個二維平面空間，平面中的障礙物設(shè)置為靜態(tài)、隨機和已知的任意不規(guī)則多邊形，其頂點由環(huán)形列表表示. 與柵格法相比，該方法易于解決復(fù)雜的環(huán)境信息問題，且占用的資源較少.

2.2? ?機器人運動學(xué)模型

考慮到機器人自身的位姿以及運動狀態(tài)，首先建立運動學(xué)模型對它進行描述. 如圖1所示：圓矩形表示機器人，在t時刻其位姿可用xt，yt，θt 3個參量表示. 其中（xt，yt）表示機器人在二維平面內(nèi)的位置;θ代表機器人運動方向與x軸的夾角，初始為0;?代表機器人的行駛方向和當(dāng)前位置與目標(biāo)點連線的夾角;機器人運動的角速度為ω;質(zhì)心的線速度為v，由于線速度垂直于兩輪之間的連線，因此它在x軸和 y軸的分量分別為：

vx = vcos θ? ? ?（5）

vy = vsin θ? ? ?（6）

由式（5）（6）消去v可得：

vx sin θ - vy cos θ = 0? ? ? （7）

設(shè)某一時刻機器人運動狀態(tài)為q = [Vx，Vy，θ]，其中，Vx，Vy分別為考慮了角速度影響的機器人等效線速度在x軸和y軸的分量. 類比式（7）可得，在笛卡爾坐標(biāo)系下，移動機器人的約束條件方程為：

A（q）q = 0? ? ? （8）

A（q） = [-sin θ，cos θ，0]? ? ? （9）

則由單位時間內(nèi)θ = ω，結(jié)合式（5）（6）可得機器人位于某點的運動模型為：

機器人的線速度和角速度分別為：

v =? ? ? ?（11）

ω =? ? ? ?（12）

式中：vL和vR分別為機器人左右兩輪的線速度;R為運動半徑. 將機器人的線速度和角速度以及運動半徑代入運動模型中可得機器人位于某一點的運動方程為：

將運動學(xué)模型引入路徑規(guī)劃過程后，即為路徑規(guī)劃算法增加一個約束條件：通過不斷減小?，使機器人朝向目標(biāo)點方向持續(xù)運動.

2.3? ?動態(tài)并行擬合策略

在以往的研究中，利用貝塞爾曲線平滑路徑的過程是一個獨立的過程，即在產(chǎn)生最優(yōu)路徑后再用貝塞爾曲線進行靜態(tài)擬合，這樣會增加計算步驟使算法繁瑣. 因此利用Q-IGA算法在搜索路徑點的同時協(xié)同搜索最合適的控制點P作為貝塞爾曲線的控制點，利用選出的控制點可生成較短的最佳路徑.

本文建立的環(huán)境模型為多面障礙物平面模型，所以首先將環(huán)境地圖以圖片格式輸入并對其進行二值化處理，使其相當(dāng)于具有多個像素點的網(wǎng)格地圖. 每一個網(wǎng)格相當(dāng)于一個基因，其值可以為0或1，當(dāng)該網(wǎng)格是貝塞爾曲線的控制點時，其值取為1，當(dāng)該網(wǎng)格不是貝塞爾曲線的控制點時，其值取為0. 若該網(wǎng)格被障礙物覆蓋，則其值設(shè)為-1，不可作為控制點.

因此遺傳算法初始種群內(nèi)的每個染色體編碼方式為二進制編碼，基因值為0或1即代表路徑點是不是待選控制點. 若路徑穿過障礙物，即穿過值為-1的網(wǎng)格點，則此路徑點會在后續(xù)的遺傳操作中通過避障操作移除.

在路徑規(guī)劃過程中保證路徑的連續(xù)性十分重要，在此定義低階連續(xù)性準(zhǔn)則如下[14]：

1）連接起始點的一條線段具有0階連續(xù)性.

2）在兩條線段的連接處，用等效切線保證一階連續(xù)性.

3）三階以上貝塞爾曲線由曲率連續(xù)性保證其連續(xù)性.

考慮到計算復(fù)雜度，在滿足連續(xù)性的條件下，貝塞爾曲線的階次越低越好. 本文采用三階貝塞爾曲線生成平滑路徑，如圖2（a）所示. 三階貝塞爾曲線有4個控制點N0，N1，N2，N3. α和γ分別表示向量N0N1，N1 N2，N2 N3之間的夾角. 三階貝塞爾曲線定義如下：

Q（t）=B0（1-t）3+3B1（1-t）2t+3B2（1-t）2t+B3t2

（14）

[N0][N1][g][N2][α][h][k][N3][γ][N2][N3][N0][N1][o1][o2][o3][M3][M1][M2][γ][M0]

圖2（b）為根據(jù)搜索得到的控制點擬合出的一組三階貝塞爾曲線，（控制點分別為N0，N1，N2，N3和M0，M1，M2，M3）. 三階貝塞爾曲線成對出現(xiàn)能夠保證曲率的連續(xù)性（從0單調(diào)遞增到kmax，再單調(diào)遞減到0）.

2.4? ?優(yōu)化選擇算子增加種群適應(yīng)性

在Q-IGA算法中，依據(jù)遺傳算法基本步驟，首先隨機產(chǎn)生一個種群X = {x0，x2，…，xn}，它包含S條染色體，每條染色體為一個路徑規(guī)劃方案，染色體的結(jié)構(gòu)可以表示為xs = {u1，u2，…，up}. 優(yōu)化算法的問題之一是求解過程具有很強的隨機性，這導(dǎo)致迭代結(jié)果易損失多樣性. 為提高遺傳算法生成解的多樣性，對選擇算子進行優(yōu)化. 通過計算每次迭代種群內(nèi)不同路徑方案之間的差異度，為選擇算子增加一個判斷準(zhǔn)則，保證種群內(nèi)可行解的多樣性. 算法設(shè)置的判斷準(zhǔn)則為：在每次迭代中，只有種群的相似性指標(biāo)低于閾值η時，這些方案才可保留進入下一次迭代.? η的初始值為（0，1）中的一個隨機值. 在迭代過程中，η的值從初始值線性下降到0. 在算法模型中，使用衰減因子a=0.99代表衰減率，即η的衰減公式為：ηt+1 = aηt，當(dāng)t趨近于無窮時，η趨近于0. 因此，優(yōu)化的選擇過程拒絕相同和過于相近的解決方案同時存在，有助于遺傳算法避免局部最優(yōu)問題，增強其勘探能力. 在每一次迭代中，η都會減小，這意味著在搜索后期趨近于最優(yōu)解時迭代得到的路徑方案越來越相近，即在搜索開始和結(jié)束之間得到了平衡.

算法借鑒Q值檢驗法思想判斷種群多樣性. 根據(jù)路徑模型，定義兩個解決方案x1，x2之間的Q值為：

式中：N11代表兩染色體中對應(yīng)位置基因值都為1的數(shù)量;N00代表兩染色體中對應(yīng)位置基因值都為0的數(shù)量;N01代表x1染色體基因值為0的位置對應(yīng)x2基因值為1的數(shù)量;N10代表x1染色體基因值為1的位置對應(yīng)x2基因值為0的數(shù)量.

若兩個染色體，x1 = [1 1 0 0 1 1 0 0 1 0]，x2 = [1 0 1 0 1 0 1 0 1 1]，則二者之間的Q值為：

綜上，種群相似性q為計算得到的所有個體兩兩Q值的平均值，即：

2.5? ?優(yōu)化適應(yīng)度函數(shù)

遺傳算法的另一重要步驟是計算個體適應(yīng)度值. 從常識可以得知，在相似的運動環(huán)境中，機器人的運動能耗與運動距離成正相關(guān)，即運動距離越長，耗能越多. 傳統(tǒng)的遺傳算法通過適應(yīng)度函數(shù)判斷路徑長短，可以保證機器人在完成運動目標(biāo)的前提下盡可能縮短機器人的運動距離. 然而如前文所述，這樣得到的路徑有可能與障礙物距離過近、或出現(xiàn)耗能較大的大角度轉(zhuǎn)彎. 因此在本文提出的算法中，適應(yīng)度函數(shù)將轉(zhuǎn)彎角度、機器人體積也作為評價因素，優(yōu)化目標(biāo)為使重新定義的適應(yīng)度函數(shù)值最大.

2.5.1? ?距離因素

在遺傳算法完成控制點搜索后，路徑長度D即可表示為：

D = d（pi，pi + 1）? ? ? ?（18）

式中n為控制點的數(shù)量，路徑長度可以由貝塞爾曲線的積分來計算，計算公式為：

D=P（t）dt=pi Bi，n（t）dt=（19）

2.5.2? ?機器人體積

在理想環(huán)境中，移動機器人被視為一個粒子，并不考慮其體積對行進過程的影響. 然而，在實際應(yīng)用中，機器人在運動過程中不僅要避開障礙物，而且應(yīng)與障礙物保持一定的安全距離. 在經(jīng)典的路徑規(guī)劃算法中，為保證最優(yōu)路徑為最短路徑，常常會導(dǎo)致機器人緊靠障礙物或墻壁等限制情況出現(xiàn).

因此算法對經(jīng)典適應(yīng)度函數(shù)計算方法做出優(yōu)化. 對于無法穿過的障礙物，用+∞來描述其代價. 這樣，障礙物附近某個點對于機器人運動的代價定義為：

式中：k1為歸一化系數(shù);d是機器人中心距離障礙物的距離;d0是機器人的外形尺寸，如圖3所示. 當(dāng)機器人與障礙物之間的距離小于機器人的尺寸時，其代價為+∞，此時適應(yīng)度函數(shù)值為0，即認(rèn)為機器人在這種條件下會與障礙物發(fā)生碰撞;當(dāng)其與障礙物的距離大于機器人的尺寸時，其代價值呈高斯函數(shù)衰減，即希望在一定范圍內(nèi)機器人盡可能遠離障礙物.

2.5.3? ?機器人轉(zhuǎn)彎角度

路徑轉(zhuǎn)角過大或過于頻繁不僅影響機器人的工作效率，在運動距離同等的條件下，還會消耗更多的能量. 雖然隨著鋰電池等可充電電池技術(shù)近年來的快速發(fā)展和成熟，機器人的續(xù)航時間越來越長，但是充電時間長等缺點仍然限制著機器人的循環(huán)使用效率. 因此，算法將轉(zhuǎn)彎角度因素引入適應(yīng)度函數(shù)，將每個拐點因轉(zhuǎn)彎所帶來的代價定義為：

R2（n） = k2? ? ? （21）

式中：α為轉(zhuǎn)彎角度，包括路徑方向改變引起的角度變化以及引入機器人運動學(xué)模型后其自身旋轉(zhuǎn)時的角速度帶來的轉(zhuǎn)彎角度;k2為歸一化系數(shù).

經(jīng)過轉(zhuǎn)彎優(yōu)化后的效果如圖4所示，虛線路徑代表的是轉(zhuǎn)彎優(yōu)化前的路徑，實線路徑代表的是轉(zhuǎn)彎優(yōu)化后的路徑. 可以看出，優(yōu)化后的路徑較優(yōu)化前的路徑轉(zhuǎn)彎次數(shù)更少，且轉(zhuǎn)彎角度更加平滑，更適合于實際的工業(yè)應(yīng)用.

2.5.4? ?最終的適應(yīng)度函數(shù)公式

綜合路徑長度因素、機器人自身體積和機器人轉(zhuǎn)彎角度帶來的代價，適應(yīng)度函數(shù)最終被修正為：

f =? ? ? ?（22）

式中：D為路徑長度; R1（n）為機器人體積代價;R2（n）為機器人轉(zhuǎn)彎角度代價.算法的迭代目標(biāo)為使新定義的適應(yīng)度函數(shù)值達到最大.

綜上，基于Q-IGA動態(tài)擬合貝塞爾曲線的路徑規(guī)劃算法流程如圖5所示.

3? ?仿真實驗與分析

3.1? ?參數(shù)設(shè)置

算法的仿真實驗環(huán)境為MATLAB2016，系統(tǒng)環(huán)境為Windows 7，運行內(nèi)存為2GB，處理器為Intel（R）Celeron CPU 1000 @1.80GHz. 在進行仿真實驗前，首先需要設(shè)置合理的參數(shù)使算法得到最優(yōu)解.

3.1.1? ?遺傳算法參數(shù)設(shè)置

如圖6（a）所示，隨著迭代次數(shù)和種群數(shù)量的增加，每次迭代所得最優(yōu)解的性能得到改善，路徑長度減小，計算時間增加，經(jīng)過150次迭代后路徑長度趨于穩(wěn)定;而種群規(guī)模對算法性能的影響如圖6（d）所示，在規(guī)模超過110以后，路徑長度趨于穩(wěn)定. 綜合

考慮路徑長度和計算時間兩個因素，算法將迭代次數(shù)設(shè)為160次，種群規(guī)模設(shè)為110，在保證計算時間不會過長的前提下，還能獲得較短的路徑. 在此僅展示了第一幅不規(guī)則障礙物地圖參數(shù)選擇實驗，其余兩個地圖環(huán)境下的參數(shù)選擇方法與此類似.

3.1.2? ?網(wǎng)格粒度大小設(shè)置

由經(jīng)驗可知，地圖不同分辨率對路徑規(guī)劃算法性能會造成一定影響，因此針對Q-IGA算法在第一幅地圖中設(shè)置不同的網(wǎng)格粒度探討其對算法性能的影響. 由表1可知，隨著網(wǎng)格粒度的增加，算法的執(zhí)行時間越來越短，但是路徑規(guī)劃成功率受到的影響有所降低. 因此為在較短的時間內(nèi)保證較高的路徑規(guī)劃成功率，實驗中將網(wǎng)格粒度設(shè)置為0.5，其余兩幅地圖情況同理.

3.2? ?未考慮運動模型的路徑結(jié)果分析

在仿真實驗中從簡單到復(fù)雜設(shè)置了3種地圖環(huán)境，如圖7（a）（b）（c）所示，分別為不規(guī)則障礙物地圖（大小為20×20），窄帶障礙物地圖（大小為30×30）和迷宮圖（大小為45×45）. 每種地圖環(huán)境下都驗證了3種算法的性能，其中路徑1是改進人工勢場法[15]產(chǎn)生的路徑，路徑2是混合遺傳算法[16]（IHGA）產(chǎn)生的路徑，路徑3是Q-IGA算法產(chǎn)生的路徑.

3.2.1? ?路徑結(jié)果分析

結(jié)合圖7中不同環(huán)境下的路徑結(jié)果特點和表2中不同路徑的長度可知，雖然路徑3 的長度不是最短的（較人工勢場法略長，較混合遺傳算法較短），但路徑3的性能優(yōu)于路徑1和路徑2，其轉(zhuǎn)彎更少且平滑度更高，與障礙物也保持一定的安全距離，可避免機器人與障礙物發(fā)生摩擦碰撞的情況，更適合移動機器人的實際應(yīng)用.

3.2.2? ?時間性能分析

本文提出的算法旨在得到合理路徑的同時提高算法的搜索效率，因此對混合遺傳算法、Q-IGA算法和改進人工勢場法3種算法的時間性能進行了考察. 由表3數(shù)據(jù)可知，3種算法在第2幅地圖中的執(zhí)行時間較長，結(jié)合表2中的路徑長度可知，這是因為第2幅地圖中迂回轉(zhuǎn)彎較多，路徑搜索方向變化較大，路徑較長，因此路徑規(guī)劃算法執(zhí)行時間較長. 3種算法中，Q-IGA算法在時間上比改進人工勢場法略長，這是由于遺傳算法有編解碼過程，因此時間略長是合理的. 但Q-IGA算法比混合遺傳算法執(zhí)行時間更短，這說明其在獲得最優(yōu)路徑的同時有效提高了算法的時間效率.

3.3? ?考慮運動模型的路徑結(jié)果分析

為驗證運動學(xué)模型對路徑規(guī)劃結(jié)果的影響，在ROS環(huán)境中，結(jié)合機器人運動學(xué)模型，對路徑規(guī)劃結(jié)果進行了進一步的仿真，并利用RVIZ工具將路徑可視化，其結(jié)果如圖8所示. 實驗中，利用ROS系統(tǒng)的導(dǎo)航功能包設(shè)置機器人初始狀態(tài)參數(shù)，令其線速度為2 m/s，角速度為0.05 rad/s，當(dāng)前運動方向與目標(biāo)點連線方向的夾角?為75°，運動半徑R為2. 圖中路徑1為未加入運動學(xué)模型、改進人工勢場法產(chǎn)生的路徑，其為折線;路徑2和路徑3分別為加入運動學(xué)模型后、混合遺傳算法和Q-IGA算法產(chǎn)生的路徑，其為曲線. 由圖可知，3種算法均產(chǎn)生了無碰撞路徑，與3.2.1節(jié)未加入運動學(xué)模型得到的路徑2相比，在加入運動學(xué)模型后，原本為折線的路徑成為曲線，這說明在實際應(yīng)用中，由于機器人自身位姿和運動速度的影響，它并不會按照既定的折線型路徑行走，這就使實際路徑和規(guī)劃路徑產(chǎn)生了偏差. 而與3.2.1節(jié)

未加入運動學(xué)模型得到的路徑3相比，Q-IGA算法在未使用運動學(xué)模型時就是平滑的，與結(jié)合運動學(xué)模型的路徑效果一致，并且在平滑的基礎(chǔ)上可與障礙物保持一定的安全距離，因此更符合機器人的實際應(yīng)用場景，路徑更加合理.

4? ?結(jié)? ?論

本文提出一種基于Q-IGA算法動態(tài)擬合貝塞爾曲線的路徑規(guī)劃算法. 通過優(yōu)化遺傳算法的選擇算子，使種群多樣性增加，避免算法陷入局部最優(yōu)，加快收斂速度. 通過修正適應(yīng)度函數(shù)公式，使路徑不會緊貼障礙物行進. 通過并行搜索路徑點和控制點，使路徑搜索與平滑過程有機結(jié)合，增強了路徑的自適應(yīng)性且提高了算法效率. 與改進人工勢場法[15]和混合遺傳算法[16]相比，Q-IGA算法不僅保證路徑長度較短，而且使機器人旋轉(zhuǎn)更加靈活，可與障礙物保持更為安全的距離，滿足對路徑合理性的要求，因此可以降低能耗，更適合于實際應(yīng)用.

參考文獻

[1]? CAI P，CAI Y，CHANDRASEKARAN I. Parallel genetic algorithm based automatic path planning for crane lifting in complex environments[J]. Automation in Construction，2016，62（1）：133—147.

[2]? ? MOHAMMED G A，HOU M. Optimization of active muscle force-length models using least squares curve fitting[J]. IEEE Transactions on Biomedical Engineering，2016，63 （3）：630—635.

[3]? ? CIMURS R，HWANG J，SUH I H. Bezier curve-based smoothing for path planner with curvature constraint[C]//IEEE International Conference on Robotic Computing （IRC）. 2017：241—248.

[4]? ? 羅隆福，李冬，鐘杭. 基于改進RRT的無人機電力桿塔巡檢路徑規(guī)劃[J]. 湖南大學(xué)學(xué)報（自然科學(xué)版），2018，45（10）：80—86.

LUO L F，LI D，ZHONG H. Path planning of unmanned aircraft inspection for electric towers based on advanced RRT algorithm[J]. Journal of Hunan? Univercity （Natrual Sciences），2018，45（10）：80—86.（In Chinese）

[5]? ? CHEN C，GENG P W，ZHANG X C. Research on USV path planning based on improved artificial potential field method[J]. Ship Engineering，2015 （9）：179—183.

[6]? ? ARANA-DANIEL N，GALLEGOS A A，LPEZ-FRANCO C，et al.? Smooth global and local path planning for mobile robot using? particle swarm optimization radial basis functions，splines and? Bezier curves [C]//IEEE Congress on Evolutionary Computation （CEC）. 2014：175—182.

[7]? ? TUNCER A，YILDIRIM M. Dynamic path planning of mobile robots with improved genetic algorithm[J]. Computers & Electrical Engineering，2012，38 （6） ：1564—1572.

[8]? ? TSAI C C，HUANG H C，CHAN C K. Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation [J]. IEEE Transactions on Industrial Electronics，2011，58 （10）：4813—4821.

[9]? ? HU Y，YANG S X. A knowledge based genetic algorithm for path planning of a mobile robot[C]//Proceedings of IEEE International Conference on Robotics and Automation （ICRA'04）. IEEE，2004：4350—4355.

[10]? ALAJLAN A. KOUB?A I. CH?ARI H. Bennaceur，et al. Global Mtuspath planning for mobile robots in large-scale grid environmening genetic algorithms[C]//Proceedings of? International Conference on Individual and Collective Behaviors in? Robotics （ICBR）. 2013：1—8.

[11]? LAU H C，CHAN T M，TSUI W T，et al. Application of genetic algorithms to solve the multidepot vehicle routing problem[J]. IEEE Transactions on Automation Science and Engineering，2010，7（2）：383—393.

[12]? 鄧乾旺，高禮坤，羅正平，等. 基于多目標(biāo)遺傳算法的起重機吊裝路徑規(guī)劃[J]. 湖南大學(xué)學(xué)報（自然科學(xué)版），2014，41（1）：63—69.

DENG Q W，GAO L K，LUO Z P，et al. Lifting path planning of crane based on multi-objective genetic algorithm[J].Journal of Hunan? Univercity（Natrual Sciences），2014，41（1）：63—69. （In Chinese）

[13]? MOHAMMED G A，HOU M. Optimization of active muscle force-length modelsusing least squares curve fitting[J].IEEE Transactions on Biomedical Engineering，2016，63 （3）：630—635.

[14]? CIMURS R ，HWANG J，SUH I H. Bezier curve-based smoothing for path planner with curvature constraint [C]// IEEE International Conference on Robotic Computing （IRC）. IEEE，2017：241—248.

[15]? LIU L F，SHI R X，LI S D，et al.Path planning for UAVS based on improved artificial potential field method through changing the repulsive potential function [C]//Navigation and Control Conference （CGNCC）.2016：319—328.

[16]? ZHANG W C，XU Y M，XIE J P. Path planning of USV based on improved hybrid genetic algorithm[C]//Navigation Conference （ENC）.2019：312—319.