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

楊 嘉，劉 虎，楊新坤，李文振，李富康，趙寧寧

（長(zhǎng)安大學(xué)工程機(jī)械學(xué)院，西安 710064）

0 引言

隨著智能化的飛速發(fā)展，移動(dòng)機(jī)器人的出現(xiàn)，給人們帶來了極大的方便。移動(dòng)機(jī)器人被廣泛應(yīng)用于軍事、制造、服務(wù)、農(nóng)業(yè)等各個(gè)方面，而路徑規(guī)劃作為移動(dòng)機(jī)器人領(lǐng)域的重要且基礎(chǔ)的問題之一，一直以來都是人們關(guān)注的焦點(diǎn)，也有越來越多的專家學(xué)者對(duì)其進(jìn)行大量研究。研究移動(dòng)機(jī)器人的路徑規(guī)劃問題具有重要的意義，常用的算法有遺傳算法、A*算法、蟻群算法以及快速隨機(jī)搜索樹算法等，陳亮等[1]在傳統(tǒng)遺傳算法的基礎(chǔ)上，對(duì)適應(yīng)度函數(shù)進(jìn)行優(yōu)化，利用優(yōu)化后的自適應(yīng)遺傳算法使機(jī)器人路徑規(guī)劃質(zhì)量得到顯著提升。王堯山等[2]為解決機(jī)器人路徑規(guī)劃中存在的收斂慢等問題，改進(jìn)了遺傳算法，引入人工勢(shì)場(chǎng)法進(jìn)行種群初始化，提出了基于種群多樣性程度評(píng)價(jià)的自適應(yīng)選擇方法，設(shè)計(jì)了自適應(yīng)交叉和變異概率，通過仿真實(shí)驗(yàn)，證明了所提出改進(jìn)遺傳算法的可行性和有效性。王雷等[3]針對(duì)基本遺傳算法的選擇和變異操作會(huì)在路徑規(guī)劃中產(chǎn)生不可行路徑這一問題，提出一種對(duì)選擇和變異操作進(jìn)行改進(jìn)并可以自適應(yīng)調(diào)整的方式，提高了遺傳算法的尋優(yōu)效率。田欣等[4]提出了一種基于解空間優(yōu)化的遺傳算法，通過仿真實(shí)驗(yàn)證明該優(yōu)化算法在一定程度上可以解決機(jī)器人在路徑規(guī)劃法方面存在的早熟收斂問題。錢紅昇等[5]在分層算法的基礎(chǔ)上，對(duì)A*算法進(jìn)行改進(jìn)，在保證一定的搜索精度下提高了搜索效率。封聲飛等[6]針對(duì)傳統(tǒng)蟻群算法在路徑規(guī)劃中存在收斂速度和尋優(yōu)能力不平衡等問題，提出一種自適應(yīng)改進(jìn)蟻群算法，通過實(shí)驗(yàn)仿真驗(yàn)證了改進(jìn)算法的可行性與有效性。

本文將從移動(dòng)機(jī)器人路徑規(guī)劃中的路徑長(zhǎng)度與平滑度兩個(gè)方面進(jìn)行研究討論，通過柵格地圖法建立機(jī)器人運(yùn)動(dòng)環(huán)境模型，構(gòu)建關(guān)于路徑長(zhǎng)度和平滑度的適應(yīng)度函數(shù)，對(duì)路徑長(zhǎng)度和平滑度的權(quán)重系數(shù)進(jìn)行優(yōu)化調(diào)整，采用輪盤賭的方法保留了部分非最優(yōu)個(gè)體，防止算法陷入局部最優(yōu)解，最后通過MATLAB 進(jìn)行仿真，得到了迭代次數(shù)少、運(yùn)行時(shí)間短、滿足移動(dòng)機(jī)器人運(yùn)動(dòng)的最佳路徑。

1 問題描述與環(huán)境建模

本文是對(duì)移動(dòng)機(jī)器人進(jìn)行全局路徑規(guī)劃，即環(huán)境中的全部障礙物分布已知，要求移動(dòng)機(jī)器人在與已知障礙物毫無碰撞的情況下，由起始位置運(yùn)動(dòng)至終點(diǎn)位置，從而使機(jī)器人獲得最佳移動(dòng)路徑。

首先建立環(huán)境地圖，本文采用柵格法建立移動(dòng)機(jī)器人的運(yùn)動(dòng)空間模型。柵格面積越小，環(huán)境信息表示越準(zhǔn)確，若柵格面積越大，環(huán)境信息則不能被準(zhǔn)確表示，極易出現(xiàn)碰撞現(xiàn)象。在采用柵格法建立運(yùn)動(dòng)環(huán)境模型時(shí)，柵格單元采用二進(jìn)制信息表示，其中“1”表示障礙物柵格，“0”表示自由柵格，如圖中黑色部分為障礙物柵格，白色部分為自由柵格。建模后的機(jī)器人運(yùn)動(dòng)空間如圖1所示。

圖1 20×20柵格地圖

2 路徑規(guī)劃遺傳算法

2.1 初始化種群

初始化種群要求隨機(jī)產(chǎn)生不與障礙物柵格相碰撞的多條可行路徑。首先初始化時(shí)需要先按順序在每一行的柵格中隨機(jī)性的選出一個(gè)自由柵格，其中將路徑的第一個(gè)柵格和最后一個(gè)柵格設(shè)置為移動(dòng)機(jī)器人的初始位置與終點(diǎn)位置，此處將柵格地圖中的第1個(gè)柵格設(shè)置為初始位置，第399個(gè)位置設(shè)置為終點(diǎn)位置，其次將從每一行柵格中選出的自由柵格連接為連續(xù)的路徑，在這一步中首先需要判斷選出的相鄰行中的自由柵格是否連續(xù)，其判斷方法為：

式中：xi+1、yi+1、xi、yi分別為相鄰兩個(gè)柵格的直角坐標(biāo)，max 和abs 分別為最大值和絕對(duì)值。

ξ＝1 時(shí)說明兩個(gè)相鄰的自由柵格連續(xù)，否則不連續(xù)。對(duì)于不連續(xù)的取兩個(gè)自由柵格的中點(diǎn)柵格，中點(diǎn)柵格的坐標(biāo)計(jì)算公式為：

若所得新柵格為黑色障礙物柵格，則按照上下左右的順序取新柵格的相鄰柵格，并判斷此柵格是否已經(jīng)在路徑中，如果此柵格為自由柵格且不在路徑中，則插入兩個(gè)不連續(xù)柵格中間作為路徑，若遍歷上下左右4個(gè)柵格均無滿足條件的柵格，則刪除此條路徑；繼續(xù)判斷新插入的柵格和新插入的柵格的前一個(gè)柵格是否連續(xù)，若不連續(xù)則循環(huán)以上步驟，直到兩個(gè)柵格連續(xù)。以此類推循環(huán)以上步驟，直至所選的移動(dòng)路徑為連續(xù)路徑。

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

由于本文所研究的移動(dòng)機(jī)器人路徑規(guī)劃問題是從路徑長(zhǎng)度和平滑度兩方面進(jìn)行考慮的，所以適應(yīng)度函數(shù)由兩部分組成。

（1）路徑長(zhǎng)度方面

路徑長(zhǎng)度的計(jì)算公式為：

由于在進(jìn)行路徑規(guī)劃時(shí)要滿足路徑最短，而選擇方式采用的是輪盤賭的方式，因此適應(yīng)度函數(shù)的第1部分為：

（2）路徑平滑度方面

根據(jù)機(jī)器人運(yùn)動(dòng)學(xué)和動(dòng)力學(xué)的約束[7]，機(jī)器人運(yùn)動(dòng)時(shí)的拐彎不宜過大，而且相對(duì)平滑的路徑更加有利于機(jī)器人的運(yùn)動(dòng)，因此在進(jìn)行路徑規(guī)劃時(shí)有平滑度的要求。路徑越平滑，相鄰3 點(diǎn)形成的角度越大，角度越大相鄰3 點(diǎn)之間的距離越大，所以將計(jì)算路徑中所有相鄰3點(diǎn)的距離作為適應(yīng)度函數(shù)的第2部分，計(jì)算公式如下：

路徑中連續(xù)的3 點(diǎn)所組成的夾角分別有：平角（180°）、鈍角、直角以及銳角，計(jì)算所得的d′值與這4 種情況相對(duì)應(yīng)，其中平滑度最好的是平角，鈍角與直角次之，而銳角這一情況不滿足機(jī)器人動(dòng)力學(xué)的約束。因此，需要對(duì)除平角之外的其余3種情況進(jìn)行懲罰，加上懲罰數(shù)可以優(yōu)化不滿足約束條件的個(gè)體，懲罰系數(shù)分別取6、30和無窮大，在操作過程中具體可以根據(jù)實(shí)際情況變動(dòng)懲罰系數(shù)的大小。懲罰之和的倒數(shù)就是所構(gòu)建的適應(yīng)度函數(shù)的第2部分。

根據(jù)兩部分的構(gòu)成，需要對(duì)路徑長(zhǎng)度和路徑平滑度的適應(yīng)度函數(shù)取權(quán)重系數(shù)w1、w2，適應(yīng)度函數(shù)公式為：

依據(jù)路徑長(zhǎng)度與路徑平滑度間的權(quán)重選擇參數(shù)w1和w2。

2.3 遺傳操作

2.3.1 選擇方法

采用輪盤賭[8]的方式進(jìn)行選擇，其中個(gè)體被選中的概率與其對(duì)應(yīng)的適應(yīng)度函數(shù)值成正相關(guān)，當(dāng)種群大小為n時(shí)，個(gè)體i被選中遺傳到下一代的概率為：

采用輪盤賭的方式可以大概率地將適應(yīng)度值大的個(gè)體選為父代個(gè)體用以產(chǎn)生新的個(gè)體，同時(shí)保留了部分非最優(yōu)的個(gè)體，防止算法陷入局部最優(yōu)解。

2.3.2 交叉方式

首先確定交叉概率pc的值，其次在0～1 之間隨機(jī)產(chǎn)生一個(gè)數(shù)，將其與交叉概率pc作比較，若產(chǎn)生的隨機(jī)數(shù)值小于pc值，則進(jìn)行交叉操作，反之不作交叉操作。此處采用的是單點(diǎn)交叉[9]方式，即在兩條路徑中找出所有相同的點(diǎn)，再隨機(jī)選擇其中一個(gè)點(diǎn)，將之后的路徑進(jìn)行交叉操作，具體流程如圖2所示。

圖2 交叉方式流程圖

圖3 變異方式流程圖

2.3.3 變異方式

首先確定變異概率pm，其次在0～1 之間隨機(jī)產(chǎn)生一個(gè)數(shù)，將其與變異概率pm作比較，若產(chǎn)生的隨機(jī)數(shù)值小于pm值，則進(jìn)行變異操作，反之不作變異操作。變異方法是隨機(jī)選取路徑中除初始位置和終點(diǎn)位置之外的兩個(gè)柵格，并去除兩個(gè)柵格之間的路徑，以這兩個(gè)柵格為相鄰點(diǎn)，判斷這兩個(gè)點(diǎn)是否為連續(xù)柵格。若無法產(chǎn)生連續(xù)路徑，則重新選擇兩個(gè)柵格進(jìn)行操作，直至完成變異操作，具體流程如圖3所示。

3 仿真結(jié)果

采用柵格地圖法建立20×20 的機(jī)器人運(yùn)動(dòng)環(huán)境，設(shè)置初始起點(diǎn)為0 柵格，終點(diǎn)為399 柵格。取種群數(shù)量n＝300，迭代次數(shù)取100次，pc＝0.8，pm＝0.1。

（1）取w1＝4，w2＝2，通過MATLAB進(jìn)行仿真，運(yùn)行結(jié)果如圖4～5 所示，可以得到在經(jīng)過10 次左右的迭代算法已經(jīng)收斂，在迭代次數(shù)為60次左右的時(shí)候所得平均路徑長(zhǎng)度與最優(yōu)路徑長(zhǎng)度基本一致，最佳路徑長(zhǎng)度為30.624，運(yùn)行時(shí)間為3.703 s，由圖可以看出，其可行路徑中存在直角轉(zhuǎn)折的情況，所得路徑并不平滑，這種情況下一般的機(jī)器人行駛比較困難。

圖4 調(diào)整參數(shù)前的路徑規(guī)劃圖

圖5 調(diào)整參數(shù)前的路徑長(zhǎng)度曲線圖

（2）對(duì)路徑長(zhǎng)度和平滑度的權(quán)重系數(shù)進(jìn)行調(diào)整，并對(duì)出現(xiàn)直角的情況加了較大的懲罰，經(jīng)過多次仿真驗(yàn)證，取w1＝1，w2＝7 時(shí)，通過MATLAB進(jìn)行仿真，運(yùn)行結(jié)果如圖6～7 所示，可得到在經(jīng)過10 次左右的迭代算法已經(jīng)收斂，在迭代次數(shù)為40次左右的時(shí)候所得平均路徑長(zhǎng)度與最優(yōu)路徑長(zhǎng)度基本一致，最佳路徑長(zhǎng)度為29.213 2，運(yùn)行時(shí)間為2.588 s，所得路徑長(zhǎng)度更短，運(yùn)行時(shí)間更少，路徑也更加平滑。

圖6 調(diào)整參數(shù)后的路徑規(guī)劃圖

圖7 調(diào)整參數(shù)后的路徑長(zhǎng)度曲線圖

4 結(jié)束語

本文主要實(shí)現(xiàn)了基于遺傳算法的靜態(tài)環(huán)境下的移動(dòng)機(jī)器人路徑規(guī)劃，通過采用柵格地圖法建立機(jī)器人的運(yùn)動(dòng)環(huán)境模型，構(gòu)建關(guān)于機(jī)器人路徑長(zhǎng)度和平滑度的適應(yīng)度函數(shù)，通過調(diào)整參數(shù)，優(yōu)化仿真過程，使其在迭代次數(shù)最少、用時(shí)最短的情況下獲得最佳移動(dòng)路徑。通過以上可以看出，所求解的可行路徑在平滑度方面仍不夠平滑，在后期的研究中可對(duì)適應(yīng)度函數(shù)中平滑度的部分作進(jìn)一步改進(jìn)，使其得到的可行路徑更加平滑。