李少波， 宋啟松， 李志昂， 張星星， 柘龍炫

(貴州大學(xué)機(jī)械工程學(xué)院，貴陽 550025)

從20世紀(jì)60年代起，科學(xué)家們就開始對機(jī)器人進(jìn)行研究，到現(xiàn)在為止機(jī)器人已經(jīng)在工業(yè)生產(chǎn)，交通，醫(yī)療等領(lǐng)域得到廣泛應(yīng)用。機(jī)器人路徑規(guī)劃是機(jī)器人領(lǐng)域的一個關(guān)鍵任務(wù)，即在各種場景中尋找從起始位置到目標(biāo)位置耗時最少，路徑最短，無碰撞且最優(yōu)的路徑[1]。

對機(jī)器人路徑規(guī)劃的研究一直是中外智能機(jī)器人研究的關(guān)鍵內(nèi)容。從目前的相關(guān)研究分析可知，各種智能算法已廣泛應(yīng)用在機(jī)器人路徑規(guī)劃研究中并取得了階段性的進(jìn)展，這些智能算法包括遺傳算法、蟻群算法、粒子群算法、模糊算法、神經(jīng)網(wǎng)絡(luò)算法、人工蜂群算法、A*算法等。

現(xiàn)綜合相關(guān)文獻(xiàn)，全面介紹各類遺傳算法在機(jī)器人路徑規(guī)劃中的研究進(jìn)展，并對未來發(fā)展方向做出展望，為遺傳算法在機(jī)器人路徑規(guī)劃的推廣應(yīng)用提供相關(guān)資料。

1 遺傳算法

通過查閱機(jī)器人路徑規(guī)劃研究相關(guān)文獻(xiàn)，將2015年至2019年6月的EI(工程索引)和SCI(科學(xué)引文索引)論文數(shù)量等進(jìn)行比較如圖1所示。

圖1 智能算法論文數(shù)量對比

從圖1可以直觀地看出，近5年來對機(jī)器人路徑規(guī)劃的研究中以遺傳算法論文數(shù)量最多，粒子群算法、蟻群算法、模糊算法和神經(jīng)網(wǎng)絡(luò)算法次之，人工蜂群算法最少。結(jié)果表明遺傳算法在機(jī)器人路徑規(guī)劃中研究最多，應(yīng)用最廣，是當(dāng)今機(jī)器人路徑規(guī)劃研究的主流，極具發(fā)展前景。

1.1 遺傳算法特點

遺傳算法是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法，與其他應(yīng)用于機(jī)器人路徑規(guī)劃的智能算法相比，遺傳算法應(yīng)用更廣，使用更頻繁，優(yōu)點更明確。遺傳算法的優(yōu)點和缺點見表1。

表1 遺傳算法優(yōu)缺點對比

1.2 遺傳算法類型

遺傳算法類型眾多，中外研究人員在基本遺傳算法基礎(chǔ)上提出更多改進(jìn)算法，這些遺傳算法的分類如圖2所示。其中，混合遺傳算法是遺傳算法與其他智能算法結(jié)合而形成的，包含遺傳-蟻群混合算法、遺傳-粒子群混合算法、遺傳-人工蜂群混合算法、遺傳-模擬退火混合算法、遺傳-神經(jīng)網(wǎng)絡(luò)混合算法、模糊遺傳算法、混沌遺傳算法等。

圖2 遺傳算法類型

2 路徑規(guī)劃

2.1 路徑規(guī)劃類型

根據(jù)機(jī)器人關(guān)于環(huán)境的認(rèn)識，路徑規(guī)劃可分為兩類：第一類機(jī)器人具有被建模為地圖的環(huán)境的先驗知識，因此可以基于可用地圖計劃路徑，此類路徑稱為全局路徑規(guī)劃[2]，全局路徑規(guī)劃屬于靜態(tài)規(guī)劃；第二類路徑規(guī)劃假設(shè)機(jī)器人沒有環(huán)境的先驗信息，因此它必須感測障礙物位置并在搜索過程中實時構(gòu)建預(yù)估的環(huán)境地圖，以避開障礙物并獲取朝向目標(biāo)位置的合適路徑。此類路徑稱為局部路徑規(guī)劃[3]，局部路徑規(guī)劃屬于動態(tài)規(guī)劃。

根據(jù)研究環(huán)境的信息特點，路徑規(guī)劃還可以分為離散域范圍內(nèi)的路徑規(guī)劃和連續(xù)域范圍內(nèi)的路徑規(guī)劃，離散域范圍內(nèi)的路徑規(guī)劃屬于一維靜態(tài)優(yōu)化問題，即環(huán)境信息簡化后的路線優(yōu)化問題，而連續(xù)范圍內(nèi)的路徑規(guī)劃問題則是連續(xù)性多維動態(tài)環(huán)境下的問題。

2.2 路徑規(guī)劃步驟

路徑規(guī)劃的一般步驟為環(huán)境建模，路徑搜索，路徑平滑，而遺傳算法在機(jī)器人路徑規(guī)劃中的步驟如圖3所示。

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

2.2.1 地圖的建立和種群編碼

編號與坐標(biāo)轉(zhuǎn)換公式為

x=int(N/Gsize)+1

(1)

y=N%Gsize+1

(2)

式中：Gsize為每行柵格數(shù)；int為取整操作；N為柵格總數(shù)；x、y為坐標(biāo)。

2.2.2 初始化種群

柵格連續(xù)判別方法為

d=max{abs(xi+1-xi),abs(yi+1-yi)}

(3)

式(3)中：d為相鄰兩點距離，如果d=1,則柵格連續(xù)，否則不連續(xù)。

2.2.3 適應(yīng)度函數(shù)計算

適應(yīng)度函數(shù)公式為

(4)

式(4)中：D為路徑總長度；f為適應(yīng)度函數(shù)。路徑越短，柵格數(shù)目越少，適應(yīng)度值越大。

2.2.4 選擇方法

采用基于概率的輪盤賭方法為

(5)

式(5)中：Pi為個體概率；fi為個體適應(yīng)度。

2.2.5 交叉方式

確定交叉概率Pc，產(chǎn)生0～1隨機(jī)數(shù)P，若P

2.2.6 變異方式

確定變異概率Pm，產(chǎn)生0～1隨機(jī)數(shù)P，若P

3 應(yīng)用領(lǐng)域

3.1 導(dǎo)航領(lǐng)域

3.1.1 無人機(jī)

針對無人機(jī)導(dǎo)航中迂回問題，中國Li等[4]采用分層遺傳算法評估任務(wù)區(qū)內(nèi)威脅源，自動縮小迂回范圍。結(jié)果表明，能以較低代價獲得較短路徑，并有效減少繞行，但未能解決迂回中時間較長問題。美國Von Moll等[5]采用改進(jìn)染色體編碼的遺傳算法減少周期性重復(fù)行走所有站點所用時間。

針對無人機(jī)在不確定性環(huán)境中導(dǎo)航問題，巴西Arantes等[6]采用多種群遺傳算法與可見性圖結(jié)合來規(guī)劃導(dǎo)航路線進(jìn)而降低風(fēng)險，并對無人機(jī)緊急迫降導(dǎo)航進(jìn)行模擬[7]，但可靠性不高，僅停留在理論層面。中國對多維復(fù)雜環(huán)境中固定翼[8]無人機(jī)導(dǎo)航進(jìn)行多次仿真，結(jié)果表明，能在實際中生成可靠性極高的威脅規(guī)避路徑。

3.1.2 車輛

針對交通擁堵問題，突尼斯Chebbi等[9]采用遺傳算法對實際交通問題的參數(shù)進(jìn)行整定，但未能應(yīng)用到實踐中。中國He等[10]將遺傳算法應(yīng)用到基于全球定位系統(tǒng)(GPS)和地理信息系統(tǒng)(GIS)的車輛導(dǎo)航監(jiān)控系統(tǒng)，從而實現(xiàn)對車輛的精確定位和實時指揮，為車輛規(guī)劃合理路線，緩解城市交通道路網(wǎng)的擁堵。

針對無人駕駛汽車安全性問題：日本Kurosaka等[11]將模糊邏輯和遺傳算法相結(jié)合應(yīng)用于無人駕駛導(dǎo)航中，但未解決安全性問題，且技術(shù)性不強(qiáng)。中國對無人駕駛汽車導(dǎo)航系統(tǒng)進(jìn)行了深入研究，可在現(xiàn)實環(huán)境中實時自動導(dǎo)航和避障，安全性能高[12]。姜勇等[13]還將遺傳算法和反向傳播神經(jīng)網(wǎng)絡(luò)相結(jié)合應(yīng)用于地下無人駕駛汽車導(dǎo)航中，可以模擬人輸出行為進(jìn)行控制，自適應(yīng)能力強(qiáng)，前沿性高。

3.1.3 帆船和水下機(jī)器人

針對海上復(fù)雜多變環(huán)境導(dǎo)航問題，俄羅斯Yanchin等[14]采用并行遺傳算法在復(fù)雜海道上建立船舶最優(yōu)航線。中國Liu等[15]提出基于遺傳算法的避碰決策方法，具有較低的避碰成本，可應(yīng)用于導(dǎo)航實踐。巴西Santos等[16-17]采用遺傳算法對多艘帆船逆風(fēng)情況下的航向和初始路徑進(jìn)行優(yōu)化，設(shè)計出導(dǎo)航中的短期路徑規(guī)劃。

針對水下導(dǎo)航控制精度問題：中國張磊[18]采用遺傳算法優(yōu)化模糊控制器控制精度，減少航速誤差，使水下機(jī)器人在海流干擾的導(dǎo)航中仍具有更好的穩(wěn)定性。楊帥等[19]將分?jǐn)?shù)階技術(shù)和遺傳算法相結(jié)合對航向控制器控制參數(shù)進(jìn)行自動整定，實用性強(qiáng)，魯棒性好。

3.2 探索領(lǐng)域

3.2.1 太空探索

中內(nèi)外學(xué)者都對太空探索做了深入的研究。其中，日本Uwano等[20]提出探索偏向遺傳算法對月球表面進(jìn)行持續(xù)探測。韓國Jung等[21]采用多目標(biāo)遺傳算法優(yōu)化火星探測飛機(jī)的低雷諾數(shù)翼型的阻力系數(shù)。中國Liu等[22]采用非顯性排序遺傳算法來優(yōu)化月球探測器的減震器，從而使月球探測器著陸穩(wěn)定性得到改進(jìn)。印度Raja等[23]采用遺傳算法規(guī)劃出六輪火星車在粗糙地形中穿越各種障礙的最安全最優(yōu)路徑。美國Mott等[24]采用遺傳算法優(yōu)化火星軌道參數(shù)，實現(xiàn)機(jī)器人實時導(dǎo)航和通信定位?，F(xiàn)階段對太空探索未取得太大成效，但機(jī)器人對太空探索仍然具有潛在價值。

3.2.2 搜索與救援

(1)空中搜救:奧地利Hayat等[25]將遺傳算法應(yīng)用于多目標(biāo)無人機(jī)搜索和救援，可縮短區(qū)域覆蓋和與地面網(wǎng)絡(luò)連接的時間，結(jié)果表明，隨著無人機(jī)數(shù)量增加，總體任務(wù)完成時間可縮短65%。但通信信號在未知環(huán)境中可能會消失，因此，需要增強(qiáng)信號的連通性。

(2)陸地搜救：中國Zhu[26]將多種群遺傳算法應(yīng)用于帶有履帶機(jī)構(gòu)的車輛，使其進(jìn)行復(fù)雜曲線跟蹤，能適應(yīng)更加復(fù)雜的搜索和救援環(huán)境。這種搜救方式速度較慢，在履帶車輛速度方面需加以改進(jìn)。

(3)礦井搜救：中國Bai等[27]將遺傳算法和模糊神經(jīng)網(wǎng)絡(luò)相結(jié)合應(yīng)用于具有4個正交關(guān)節(jié)的煤礦救援蛇形機(jī)器人，提高了定位精度，能更好地獲取煤礦井下人員的方位信息。但搜救范圍較窄，應(yīng)增大機(jī)器人路徑覆蓋范圍。

現(xiàn)階段，遺傳算法在搜索和救援領(lǐng)域取得了很大進(jìn)展，不僅可以進(jìn)行上述搜救，還可進(jìn)行海上群體搜救、城市搜索救援等。

3.2.3 環(huán)境探索

(1)未知環(huán)境：印度Bhargava等[28]采用遺傳算法、實時強(qiáng)化學(xué)習(xí)和控制器協(xié)作的機(jī)器人對未知環(huán)境進(jìn)行探測，這種方法能耗較小，速度較快，但不能靈活應(yīng)對環(huán)境中出現(xiàn)的各種障礙物。美國Gunasekaran等[29]先用超聲波-激光傳感器探測未知環(huán)境與障礙物距離，再用遺傳算法規(guī)劃機(jī)器人路徑，可以精確避障。目前在未知環(huán)境探索中機(jī)器人實時信息反饋極為關(guān)鍵，需要深入研究。

(2)復(fù)雜環(huán)境：沙特阿拉伯Alsouly等[30]采用智能交叉遺傳算法優(yōu)化靜態(tài)和動態(tài)環(huán)境中的搜索過程，結(jié)果表明，此算法比靜態(tài)中的A*算法和動態(tài)中的改進(jìn)遺傳算法在環(huán)境搜索的執(zhí)行時間上更加快速，但耗能較大。馬來西亞Samadi等[31]采用改進(jìn)遺傳算法解決復(fù)雜環(huán)境下距離，安全性，能量問題，使機(jī)器人路徑軌跡最短，安全性最高，耗能最少。

3.3 農(nóng)業(yè)領(lǐng)域

遺傳算法不僅可以對農(nóng)業(yè)產(chǎn)值進(jìn)行預(yù)測，還可以對農(nóng)業(yè)機(jī)器人進(jìn)行路徑規(guī)劃，能節(jié)省時間，提高效率。目前，國內(nèi)外已將遺傳算法廣泛應(yīng)用在農(nóng)業(yè)機(jī)器人路徑規(guī)劃中。

(1)國外：針對精密農(nóng)業(yè)環(huán)境存在凹面障礙物的問題，法國Pham等[32]采用遺傳算法最大限度的實現(xiàn)覆蓋路徑規(guī)劃并縮短機(jī)器人路徑長度。針對溫室內(nèi)農(nóng)藥噴灑作業(yè)路徑規(guī)劃問題，美國Mahmud等[33]設(shè)計虛擬溫室環(huán)境，采用非支配排序遺傳算法規(guī)劃移動機(jī)器人最佳路徑。

(2)中國：目前在采摘機(jī)器人上應(yīng)用廣泛，Liang等[34]采用遺傳算法優(yōu)化滑模控制，大大提高采果機(jī)器人位置跟蹤的響應(yīng)速度，減小位置偏差，使控制系統(tǒng)能跟蹤到預(yù)期軌跡。Zou等[35]采用非線性規(guī)劃遺傳算法調(diào)整西瓜采摘機(jī)械臂采摘路徑和姿態(tài)，減少對西瓜的不必要損傷。Cao等[36]采用遺傳算法對荔枝采摘機(jī)器人生成的避障路徑進(jìn)行平滑處理，可使路徑長度縮短20%。Hu等[37]用遺傳算法對高速插秧移栽機(jī)器人進(jìn)行尺寸綜合，使其可達(dá)工作空間接近需要的工作空間，提高了插秧成功率。

3.4 醫(yī)療領(lǐng)域

遺傳算法不僅可以應(yīng)用在醫(yī)學(xué)圖像加密，去噪，還廣泛應(yīng)用于手術(shù)機(jī)器人的路徑規(guī)劃，目前已經(jīng)取得了突出成就。

(1)國外：美國Wang等[38]采用非支配排序遺傳算法等多種進(jìn)化算法來優(yōu)化機(jī)器人配藥路徑軌跡，使多機(jī)器人在互不干擾的情況下以最短的路徑來抓取藥物。意大利Stroppa等[39]使用遺傳算法求解多邊形擬合問題，應(yīng)用于患者的神經(jīng)康復(fù)。韓國Nguyen等[40]采用遺傳算法來解決外科手術(shù)機(jī)器人系統(tǒng)布局和路徑規(guī)劃問題，使機(jī)器人末端執(zhí)行器與解剖位置偏差降低到毫米級別。印度Roy等[41]采用遺傳算法優(yōu)化腦電控制機(jī)器人手臂運動軌跡，使運動障礙患者使用腦電圖信號來靈活控制機(jī)械臂的活動。

(2)中國： Niu等[42]采用非支配遺傳算法來解決微創(chuàng)手術(shù)中多機(jī)器人碰撞問題，優(yōu)化了機(jī)器人運動學(xué)性能指標(biāo)和剛度指標(biāo)，提高了絕對位置精度和重復(fù)位置精度。Ye等[43]采用改進(jìn)遺傳算法和改進(jìn)概率路標(biāo)法結(jié)合來解決非共面輻射治療，可在緊湊區(qū)域內(nèi)與放射治療系統(tǒng)配合，避免碰撞并節(jié)省時間。Liu等[44]采用遺傳算法優(yōu)化豬腹截面軌跡，還可跟蹤尸體腹腔切割的軌跡。結(jié)果表明，該方法不會產(chǎn)生明顯損傷，提高了效率和質(zhì)量。

3.5 工業(yè)領(lǐng)域

3.5.1 工業(yè)車間調(diào)度

一組作業(yè)在多機(jī)器人之間運輸是個非確定性困難(non-deterministic polynomial hard，NPH)問題，針對這個問題，中外提出了不同的解決方案。

(1)國外：突尼斯Nouri等[45]將基于鄰域的遺傳算法應(yīng)用于搜索空間的全局搜索，使機(jī)器人動態(tài)規(guī)劃操作更加簡單，但消耗時間較長。伊朗Zabihzadeh等[46]將基于雙信息素的蟻群算法和遺傳算法相結(jié)合來提高機(jī)器人運動速度，縮短零件轉(zhuǎn)移時間，從而解決耗時較長。

(2)中國：在多機(jī)器人制造單元車間調(diào)度中，Yang 等[47]采用遺傳算法構(gòu)建多機(jī)器人運輸關(guān)鍵運動路徑，盡量減少最大運輸時間。

3.5.2 焊接機(jī)器人

(1)國外：韓國Thao等[48]采用遺傳算法來預(yù)測自動氣體金屬弧焊的運動軌跡并生成智能模型，效率不高。南非Ogbemhe等[49]采用遺傳算法等智能方法對焊接機(jī)器人進(jìn)行焊縫跟蹤和軌跡規(guī)劃，但誤差較大，精確度不高。

(2)中國：Wang等[50]采用雙全局最優(yōu)遺傳算法-粒子群算法來解決多焊接接頭路徑規(guī)劃困難問題，但難以獲得最佳路徑。Shen[51]采用遺傳蟻群混合算法解決焊接機(jī)器人路徑規(guī)劃中收斂速度和優(yōu)化度之間的矛盾，已取得良好的應(yīng)用。Tong等[52]采用遺傳算法和離散粒子群優(yōu)化算法來優(yōu)化焊接路徑，可提高效率并降低成本。

3.5.3 其他工業(yè)領(lǐng)域

遺傳算法還可以應(yīng)用于表面雙層噴涂[53]，比單層噴涂更加均勻；應(yīng)用于工業(yè)機(jī)械臂[54]，可減少能耗；應(yīng)用于碼垛機(jī)器人[55]，可優(yōu)化關(guān)節(jié)軌跡進(jìn)而消除抖動。

3.6 物流領(lǐng)域

現(xiàn)今，物聯(lián)網(wǎng)迅猛發(fā)展，物流作為新興行業(yè)在世界各地得到快速發(fā)展，以貨物運輸和車間自動導(dǎo)引小車(automated guided vehicle, AGV)為代表。

3.6.1 物流運輸

(1)國外：針對貨物運輸中集裝箱裝卸問題，土耳其Erdem[56]采用遺傳算法生成貨物裝載到集裝箱的最大適應(yīng)數(shù)量，從而降低運輸成本。針對復(fù)雜物料供應(yīng)量問題，丹麥Nielsen等[57]采用遺傳算法來提高機(jī)器人運輸效率，用于解決大規(guī)模問題。

(2)中國：針對運輸系統(tǒng)車輛調(diào)度問題，Li等[58]將遺傳算法和貪婪算法相結(jié)合，規(guī)劃車輛路徑軌跡，能有效縮短車輛響應(yīng)時間。針對行走運輸機(jī)器人快速移動能耗過大問題， Zhu等[59]采用遺傳算法規(guī)劃行走機(jī)器人移動軌跡中的過渡角，進(jìn)而降低系統(tǒng)能耗，在運輸機(jī)器人戶外操作中有重要意義。

3.6.2 AGV小車

(1)國外：馬來西亞Umar等[60]采用混合多目標(biāo)遺傳算法生成完整的AGV動態(tài)調(diào)度路徑和詳細(xì)的路由路徑，并優(yōu)化了AGV作業(yè)延遲時間。

(2)中國：針對多AGV路徑規(guī)劃問題，Cheng等[61]采用改進(jìn)的小生境遺傳算法，設(shè)計出三種無碰撞優(yōu)化路徑。Liu等[62]將遺傳算法結(jié)合到多AGV系統(tǒng)中，對多AGV進(jìn)行離線和在線兩個階段的路徑調(diào)度，改變其速度和路徑，使其運動協(xié)調(diào)一致。中國學(xué)者還對AGV在靜態(tài)環(huán)境和動態(tài)環(huán)境下的路徑軌跡優(yōu)化進(jìn)行了相應(yīng)研究。

3.7 軍事領(lǐng)域

遺傳算法在軍事領(lǐng)域也有一些關(guān)鍵性的應(yīng)用，目前，中外都將其應(yīng)用在無人機(jī)的軍事活動中，且取得了不俗的成就，但也仍有缺陷需要改進(jìn)。

(1)國外：針對缺乏可靠通信網(wǎng)絡(luò)的未知遙遠(yuǎn)環(huán)境，美國Mousavi等[63]采用量子遺傳算法行成大規(guī)模軍用無人機(jī)聯(lián)盟，合理規(guī)劃無人機(jī)的任務(wù)和最短路徑，減少資源消耗。針對高維動態(tài)環(huán)境，加拿大Roberge等[64]采用遺傳算法實時快速調(diào)整軍用固定翼型無人機(jī)最優(yōu)安全路徑軌跡，最大限度降低能耗和平均飛行高度，避免被敵方雷達(dá)探測到。針對復(fù)雜多變戰(zhàn)場環(huán)境，西班牙Ramirez-Atencia等[65]針對復(fù)雜多變戰(zhàn)場環(huán)境，將多目標(biāo)遺傳算法應(yīng)用于無人機(jī)和地面聯(lián)合軍事系統(tǒng)中，規(guī)劃地面車輛位置和行動，但難以規(guī)劃出最優(yōu)路徑。

(2)中國：針對日益復(fù)雜的戰(zhàn)場環(huán)境，Cao等[66]采用遺傳算法在探測到敵方雷達(dá)的最小停留時間內(nèi)，進(jìn)行最短路徑組合優(yōu)化，從而實現(xiàn)不同基地多無人機(jī)協(xié)同偵察。

3.8 其他領(lǐng)域

遺傳算法不僅在以上領(lǐng)域取得突破性進(jìn)展，在其他領(lǐng)域內(nèi)也有相應(yīng)的一些成就。在不同類型機(jī)器人路徑規(guī)劃上也有廣泛應(yīng)用，如輪式機(jī)器人、柔順機(jī)器人、娛樂機(jī)器人、仿生機(jī)器人等。

4 路徑規(guī)劃技術(shù)難點

4.1 最短路徑問題

在路徑規(guī)劃中，最短路徑問題是現(xiàn)階段的一個技術(shù)難點，通過改進(jìn)遺傳算法中的編碼方式、適應(yīng)度函數(shù)、選擇算子可規(guī)劃出最短路徑。

4.1.1 編碼

(1)實數(shù)編碼：直接用實數(shù)表示基因，容易理解且不需要解碼過程，但容易過早收斂，從而陷入局部最優(yōu)。因此，應(yīng)減緩陷入局部最優(yōu)的速度，在過早收斂方面需要加以改進(jìn)。

(2)二進(jìn)制編碼：穩(wěn)定性高，種群多樣性大，但需要的存儲空間大，需要解碼且難以理解。因此，在降低解碼難度和釋放存儲空間方面需要加以改進(jìn)。

對于路徑優(yōu)化問題，現(xiàn)階段一般有以上兩種編碼方式，但其各有利弊，可以考慮將兩種編碼方式相結(jié)合來提高路徑優(yōu)化的能力。

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

適應(yīng)度函數(shù)是遺傳算法進(jìn)化的驅(qū)動力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，適應(yīng)度函數(shù)值越大，解的質(zhì)量越高?，F(xiàn)階段，傳統(tǒng)適應(yīng)度函數(shù)值很難增加，路徑優(yōu)化能力有限，應(yīng)當(dāng)提出新的適應(yīng)度函數(shù)來提高優(yōu)化能力，在機(jī)器人路徑規(guī)劃優(yōu)化中應(yīng)結(jié)合路徑軌跡自身的要求選擇相應(yīng)的適應(yīng)度函數(shù)。

4.1.3 遺傳算子

(1)選擇：遺傳算法中，最優(yōu)個體的保留是現(xiàn)階段的一個難點。傳統(tǒng)輪盤賭選擇方法具有隨機(jī)性，在選擇過程中可能會丟掉較好的個體，使用精英保留機(jī)制可將前代最優(yōu)個體直接選擇，更多類似精英保留機(jī)制的選擇方法是未來研究的重點。

(2)交叉：遺傳算法中，待交叉的染色體交換部分基因的序列具有不確定性。在交叉過程中需要提高甄別最優(yōu)基因序列的能力，盡量選取父代染色體中最優(yōu)基因進(jìn)行交叉。優(yōu)秀基因最大覆蓋的交叉方式是未來研究的重點。

(3)變異：遺傳算法中，變異方法產(chǎn)生優(yōu)秀后代的可能性極低，因為變異不確定性極大，不一定能產(chǎn)生最優(yōu)基因。因此應(yīng)盡量減少變異概率，使用優(yōu)秀基因進(jìn)行變異操作。采用變異提高種群多樣性是未來研究的重點。

4.2 最少耗時問題

在路徑規(guī)劃中，最少耗時問題是現(xiàn)階段另一個技術(shù)難點。路徑規(guī)劃中消耗時間的長短主要取決于遺傳算法生成路段數(shù)量、拓?fù)鋽?shù)據(jù)讀取效率、臨時表排序效率這三部分。耗時問題研究如圖4所示。

圖4 耗時問題研究

4.2.1 分區(qū)規(guī)劃

在路經(jīng)規(guī)劃中，遍歷的路段越多，耗時越大，將路段劃分成相對獨立的起點區(qū)域、中間區(qū)域、終點區(qū)域。先采用正向鄰接表對起點區(qū)域進(jìn)行規(guī)劃，逆向鄰接表對終點區(qū)域進(jìn)行規(guī)劃，然后再對中間區(qū)域路線進(jìn)行規(guī)劃，最后整合路線。這樣既可獲取近似最優(yōu)路線，也可避免路線冗余。

在分區(qū)規(guī)劃中，采用升降級機(jī)制如圖5所示，起點區(qū)域總體向上升級，即低等級路段過渡到高等級路段；終點區(qū)域總體向下降級，即高等級路段過渡到低等級路段；中間區(qū)域總體上保持高等級路段。此方式可有效減少遍歷路段數(shù)量，提高規(guī)劃效率。

圖5 分區(qū)規(guī)劃升降級機(jī)制

4.2.2 抽象層規(guī)劃

在路徑規(guī)劃中，拓?fù)鋽?shù)據(jù)讀取效率越高，越能節(jié)省時間。采用抽象層規(guī)劃將拓?fù)鋽?shù)據(jù)分成主干、枝干、詳細(xì)三個層次，可逐層快速讀取拓?fù)鋽?shù)據(jù)。難點在于如何抽象以及三層次之間的連接?，F(xiàn)階段可根據(jù)路段等級進(jìn)行抽象層劃分，至于層次間連接，則主要是高低級路段的映射關(guān)系。

在抽象層規(guī)劃中，可利用機(jī)器對機(jī)器(machine-to-machine，M2M)思想處理抽象層聯(lián)通問題，如在圖幅內(nèi)進(jìn)行連通性分析或者以圖幅為最底層，用圖幅出入度構(gòu)建圖幅連通拓?fù)潢P(guān)系。抽象層之間聯(lián)通與映射是未來研究的重點。

4.2.3 排序方法

在路徑規(guī)劃中，臨時表排序效率易被忽視，應(yīng)加以重視，常用排序方法有冒泡排序、斐波那契堆、最小堆。其中，堆排序方法效率較高，而斐波那契堆和最小堆的效率高低在不同場景的路徑規(guī)劃中有變化，應(yīng)根據(jù)場景自動調(diào)整排序方法。

4.3 實時性問題

在路徑規(guī)劃中，實時性問題是現(xiàn)階段丞待解決的難點。路徑規(guī)劃過程中遇到的外界環(huán)境在不停變化，障礙信息需要實時反饋給機(jī)器人，可通過傳感器和運動控制器來實時規(guī)劃路徑。

4.3.1 傳感器

在路徑規(guī)劃中，基于傳感器數(shù)據(jù)進(jìn)行實時規(guī)劃，首先采用“雙向搜索多邊形構(gòu)造”搜索出復(fù)雜障礙物的包圍多邊形，然后以包圍多邊形頂點構(gòu)造基于障礙物和機(jī)器人關(guān)系的可視圖，以可視圖為基礎(chǔ)進(jìn)行實時路徑規(guī)劃。

4.3.2 運動控制器

在路徑規(guī)劃中，將最優(yōu)行進(jìn)路徑中的第一個節(jié)點定義為控制器目標(biāo)點。目標(biāo)點對機(jī)器人產(chǎn)生吸引勢，障礙物產(chǎn)生排斥勢，以吸引勢和排斥勢構(gòu)成矢量和輸入條件計算出機(jī)器人行進(jìn)速度和轉(zhuǎn)角。在此輸出控制基礎(chǔ)上實時調(diào)整自身姿態(tài)，從而逃避障礙物走向目標(biāo)點。

5 結(jié)論和展望

隨著機(jī)器人的廣泛應(yīng)用，遺傳算法在路徑規(guī)劃中已經(jīng)取得了大量的研究成果，但是遺傳算法仍然存在許多問題，在理論和應(yīng)用研究方面還有進(jìn)一步的發(fā)展空間。根據(jù)近些年來相關(guān)資料總結(jié)，未來發(fā)展主要集中在以下幾個方面。

(1)混合算法：遺傳算法及其他智能算法都有其局限性，但這些算法之間具有互補(bǔ)性。針對實際路徑規(guī)劃中出現(xiàn)遺傳算法難以解決的新問題，可將遺傳算法與其他智能算法相結(jié)合，乃至兩種或則三種算法相結(jié)合，取長補(bǔ)短，從而產(chǎn)生一系列更優(yōu)秀的混合算法，解決更多難題。目前中外的一些學(xué)者正在不斷地發(fā)掘不同的混合算法來解決實際路徑規(guī)劃難。

(2)未知復(fù)雜環(huán)境應(yīng)用：目前中外在高維動態(tài)復(fù)雜環(huán)境下機(jī)器人路徑規(guī)劃方面的研究較少，在未知環(huán)境下進(jìn)行路徑規(guī)劃面臨巨大挑戰(zhàn)，但也極具前景。在未來，星際探索、軍事戰(zhàn)爭、交通領(lǐng)域等都是在未知復(fù)雜的高維空間下進(jìn)行，會存在很多危險和障礙，因此以后必須要將機(jī)器人路徑規(guī)劃研究重點放在未知復(fù)雜環(huán)境下。

(3)多機(jī)器人協(xié)作：目前機(jī)器人應(yīng)用場合越來越多，單機(jī)器人已無法滿足現(xiàn)有需求，需多機(jī)器人相互協(xié)作。這樣可節(jié)省時間提高效率，但多機(jī)器人比單機(jī)器人在路徑規(guī)劃上更加復(fù)雜，更有難度。因此，多機(jī)器人協(xié)調(diào)工作機(jī)制是未來研究重點。

(4)仿生機(jī)器人：近年來，中外學(xué)者將生物運動機(jī)理中得到的啟發(fā)應(yīng)用到機(jī)器人設(shè)計上，從而研發(fā)出仿生機(jī)器人，仿生機(jī)器人涉及空中、陸地、海洋中的生物研制出如無人機(jī)、仿生魚、仿生蜘蛛等，這些仿生機(jī)器人在路徑規(guī)劃上的研究幫助人類解決了很多難題，因此，未來可以設(shè)計出更多仿生機(jī)器人解決尚未解決的難題。