王鶴靜，王麗娜

(中國(guó)計(jì)量大學(xué) a.機(jī)電工程學(xué)院；b.浙江省智能制造質(zhì)量大數(shù)據(jù)溯源與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，杭州 310018)

0 引 言

機(jī)器人是人工智能的重點(diǎn)研究領(lǐng)域, 其中路徑規(guī)劃是機(jī)器人研究與發(fā)展中必不可少的核心內(nèi)容之一, 是機(jī)器人在一定環(huán)境中完成既定任務(wù)的基礎(chǔ), 機(jī)器人的路徑規(guī)劃能力直觀體現(xiàn)了其作業(yè)能力和風(fēng)險(xiǎn)管控能力。路徑規(guī)劃是指在規(guī)定區(qū)域內(nèi)規(guī)劃出一條從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)解路徑, 且要保證與障礙物無(wú)碰撞。機(jī)器人路徑規(guī)劃存在的難點(diǎn)問(wèn)題主要有環(huán)境建模計(jì)算量大、 算法收斂速度慢以及容易陷入局部最優(yōu)解問(wèn)題。

對(duì)于二維環(huán)境建模問(wèn)題, 主要采用柵格法進(jìn)行環(huán)境建模。柵格法對(duì)機(jī)器人工作環(huán)境的描述更直觀, 對(duì)障礙物和機(jī)器人相對(duì)位置的處理更簡(jiǎn)便, 可以最大程度上簡(jiǎn)化路徑的求解過(guò)程。而在三維環(huán)境中, 如水下機(jī)器人, 可以將平面柵格法進(jìn)行高度上的疊加, 將復(fù)雜的三維建模問(wèn)題簡(jiǎn)化為多個(gè)二維建模問(wèn)題, 在一定程度上提高了解路徑的質(zhì)量和路徑規(guī)劃算法的適應(yīng)能力。對(duì)于路徑規(guī)劃算法普遍存在的收斂速度慢和容易陷入局部最優(yōu)解問(wèn)題, 通常對(duì)算法進(jìn)行結(jié)構(gòu)上的優(yōu)化, 如增加算法參數(shù)的自適應(yīng)調(diào)整能力, 可以降低算法陷入局部最優(yōu)解的概率; 也可以將多個(gè)算法結(jié)合, 取長(zhǎng)補(bǔ)短, 優(yōu)化算法性能, 如蟻群算法可與人工勢(shì)場(chǎng)法結(jié)合, 利用人工勢(shì)場(chǎng)法生成初始可行路徑, 并調(diào)整該路徑和周?chē)鷧^(qū)域的初始信息素濃度, 可以極大加快蟻群算法的早期收斂速度。

綜上, 路徑規(guī)劃可以分為傳統(tǒng)算法路徑規(guī)劃和智能仿生算法路徑規(guī)劃兩類(lèi), 其中傳統(tǒng)路徑規(guī)劃算法又可以分為全局路徑規(guī)劃算法和局部路徑規(guī)劃算法。全局路徑規(guī)劃是在已知的環(huán)境中進(jìn)行路徑規(guī)劃, 環(huán)境信息已經(jīng)給定且障礙物位置等信息基本不發(fā)生變化, 一般只需按照事先規(guī)劃的全局路徑進(jìn)行工作即可。而局部路徑規(guī)劃是在未知的環(huán)境中進(jìn)行路徑規(guī)劃, 通過(guò)傳感器等工具獲取當(dāng)前的局部環(huán)境信息, 主要是動(dòng)態(tài)障礙物的位置信息等, 在此基礎(chǔ)上進(jìn)行路徑規(guī)劃和避障, 如水下機(jī)器人所處環(huán)境的障礙物分布極易發(fā)生改變, 機(jī)器人需要實(shí)時(shí)獲取環(huán)境信息進(jìn)行局部路徑規(guī)劃, 對(duì)其而言, 需要在全局路徑規(guī)劃的基礎(chǔ)上, 多次進(jìn)行局部路徑規(guī)劃,從而安全到達(dá)目標(biāo)點(diǎn)。在這種環(huán)境中, 局部路徑規(guī)劃更為重要。智能仿生路徑規(guī)劃算法是仿生學(xué)在路徑規(guī)劃問(wèn)題中的應(yīng)用。機(jī)器人路徑規(guī)劃算法框架見(jiàn)圖1, 本文從傳統(tǒng)路徑規(guī)劃和智能仿生路徑規(guī)劃兩方面分別給出一些常用算法, 并進(jìn)行分析總結(jié)。

圖1 機(jī)器人路徑規(guī)劃算法框架圖Fig.1 Framework of robot path planning algorithm

1 傳統(tǒng)算法路徑規(guī)劃

傳統(tǒng)路徑規(guī)劃算法可以根據(jù)對(duì)環(huán)境信息的把握程度分為全局路徑規(guī)劃算法和局部路徑規(guī)劃算法。

1.1 全局路徑規(guī)劃

全局路徑規(guī)劃主要應(yīng)用于給定環(huán)境信息的情況下進(jìn)行路徑規(guī)劃, 不要求機(jī)器人具有較強(qiáng)的實(shí)時(shí)計(jì)算能力。目前常用的全局路徑規(guī)劃算法主要有A*算法、 禁忌搜索算法等。

1.1.1 基于A*算法的路徑規(guī)劃 A*算法是一種常用的路徑規(guī)劃算法, 收斂速度快, 魯棒性較強(qiáng)。A*算法最早發(fā)表于1968年, 由Stanford研究院的Peter Hart, Nils Nilsson以及Bertram Raphael發(fā)表, 它可以算作是Dijkstra算法的擴(kuò)展, 由于借助啟發(fā)函數(shù)的引導(dǎo), A*算法通常擁有更好的性能[1-4]。A*算法的流程如圖2所示。其中, Open表和Close表分別存放算法還未遍歷的節(jié)點(diǎn)和已經(jīng)遍歷的節(jié)點(diǎn)。

圖2 A*算法流程圖Fig.2 Flow chart of A* algorithm

A*算法中單個(gè)節(jié)點(diǎn)的綜合優(yōu)先級(jí)由f(n)=g(n)+h(n)決定[2]。其中,f(n)是節(jié)點(diǎn)n的綜合優(yōu)先級(jí);g(n)是節(jié)點(diǎn)n距離起點(diǎn)的代價(jià);h(n)是節(jié)點(diǎn)n距離終點(diǎn)的預(yù)計(jì)代價(jià)。由h(n)值的變化可知, 啟發(fā)函數(shù)的調(diào)節(jié)可以改變算法的性能[3]。在實(shí)際問(wèn)題中, 算法的收斂速度可能是首要標(biāo)準(zhǔn), 路徑的長(zhǎng)度則是次要標(biāo)準(zhǔn), 可見(jiàn)A*算法的運(yùn)用較靈活, 這是其主要優(yōu)點(diǎn), 但也存在目標(biāo)不可達(dá)、 實(shí)時(shí)性差等缺陷。

近年來(lái), 針對(duì)A*算法在路徑規(guī)劃問(wèn)題的應(yīng)用上, 有許多不同看法。王維等[4]針對(duì)復(fù)雜室內(nèi)環(huán)境下移動(dòng)機(jī)器人路徑規(guī)劃中存在實(shí)時(shí)性差的問(wèn)題, 首先對(duì)算法運(yùn)行的當(dāng)前節(jié)點(diǎn)及之前節(jié)點(diǎn)的路徑估計(jì)代價(jià)以指數(shù)衰減的方式加權(quán), 使得離目標(biāo)點(diǎn)較遠(yuǎn)時(shí)能夠快速縮短與目標(biāo)點(diǎn)的距離, 在靠近目標(biāo)點(diǎn)之后進(jìn)行更為細(xì)致的搜索, 保證在障礙物情況復(fù)雜的情況下路徑依然具有可達(dá)性, 然后對(duì)生成的初始路徑以高次函數(shù)進(jìn)行平滑處理, 使得路徑更短。Shi等[5]針對(duì)傳統(tǒng)A*算法得出的路徑轉(zhuǎn)彎較多且不平滑, 并且在U形地區(qū)的路徑可能會(huì)與障礙物發(fā)生接觸的問(wèn)題, 先選擇余弦距離作為啟發(fā)式函數(shù), 加入方向信息并歸一化, 再用36階鄰域搜索矩陣解決U形彎曲擬合問(wèn)題, 最后提出了一種基于貝塞爾曲線的路徑處理方法, 使規(guī)劃的路徑曲率不斷變化。Liu等[6]針對(duì)機(jī)器人在物流倉(cāng)庫(kù)和制造車(chē)間的路徑規(guī)劃問(wèn)題提出了基于Delaunay三角剖分和改進(jìn)A*的動(dòng)態(tài)融合尋路算法(DFPA), 首先采用Delaunay三角剖分算法處理復(fù)雜障礙物, 生成Voronoi點(diǎn)作為尋路優(yōu)先節(jié)點(diǎn), 然后利用網(wǎng)格的概念提取障礙物邊緣, 為機(jī)器人尋路提供避障策略, 最后使用改進(jìn)A*算法搜索可行路徑。

王維等[4]的改進(jìn)算法收斂速度大大提高, 路徑更短且得到了平滑處理, 便于機(jī)器人進(jìn)行轉(zhuǎn)向等操作, 在復(fù)雜環(huán)境下具有較強(qiáng)的適應(yīng)性和實(shí)時(shí)性。Shi等[5]改進(jìn)的A*算法能夠很好地考慮機(jī)器人與障礙物的關(guān)系, 解決傳統(tǒng)A*算法路徑接觸障礙物的問(wèn)題, 并通過(guò)貝塞爾曲線處理生成的路徑, 達(dá)到平滑路徑的效果, 改進(jìn)后的A*算法能夠更好地在機(jī)器人自主導(dǎo)航中發(fā)揮全局引導(dǎo)作用。Liu等[6]提出的地圖構(gòu)建方法和尋路策略減少了移動(dòng)機(jī)器人的規(guī)劃路徑長(zhǎng)度、 路徑節(jié)點(diǎn)數(shù)量和整體轉(zhuǎn)彎消耗成本, 提高了路徑獲取成功率, 新的動(dòng)態(tài)地圖構(gòu)建方法和尋路策略對(duì)處理混沌地圖、 促進(jìn)智能導(dǎo)航和選址規(guī)劃具有重要的參考意義。

針對(duì)A*算法的改進(jìn)主要解決了算法在搜索速度和復(fù)雜環(huán)境中目標(biāo)可達(dá)性上的問(wèn)題, 切實(shí)提高了A*算法在路徑規(guī)劃上的實(shí)際應(yīng)用效果。

1.1.2 基于禁忌搜索算法的路徑規(guī)劃 禁忌搜索算法(tabu search, TS)是美國(guó)科學(xué)家Glover等[7]于1986年提出的一種優(yōu)化算法, 具有全局逐步尋優(yōu)的能力, 能很好地應(yīng)用于機(jī)器人的路徑規(guī)劃問(wèn)題。禁忌搜索算法是局部搜索算法的優(yōu)化與發(fā)展, 是一種基于貪婪思想的鄰域搜索算法, 但鄰域搜索算法最大的缺點(diǎn)就是容易陷入局部最優(yōu)[8], 為了解決這一問(wèn)題, 引入禁忌表, 形成了禁忌搜索算法, 使其具有了較強(qiáng)的全局搜索尋優(yōu)能力。應(yīng)用于路徑規(guī)劃問(wèn)題時(shí), 禁忌表主要是用來(lái)存放已經(jīng)搜索過(guò)的路徑點(diǎn), 表中的內(nèi)容是動(dòng)態(tài)更新的, 表的長(zhǎng)度稱(chēng)為禁忌長(zhǎng)度。搜索時(shí), 直接跳過(guò)禁忌表中已有的路徑點(diǎn), 從而使得算法具有全局搜索的特性。

禁忌搜索算法主要由禁忌表、 禁忌長(zhǎng)度[9]、 特赦準(zhǔn)則、 代價(jià)函數(shù)[10]和停止規(guī)則等部分組成。禁忌搜索算法應(yīng)用于路徑規(guī)劃問(wèn)題的流程如圖3所示。禁忌搜索算法的主要思想有以下3點(diǎn): ① 在進(jìn)行領(lǐng)域搜索時(shí)盡量避免循環(huán)行為的產(chǎn)生; ② 通過(guò)禁忌表實(shí)現(xiàn)只進(jìn)不退, 即跳過(guò)搜索過(guò)的路徑點(diǎn); ③ 算法旨在尋找全局最優(yōu)解, 要在局部最優(yōu)解的基礎(chǔ)上獲取更大的搜索區(qū)域, 實(shí)現(xiàn)全局尋優(yōu)。

圖3 禁忌搜索算法流程圖Fig.3 Flow chart of tabu search algorithm

禁忌搜索算法在搜索過(guò)程中可以接受劣解, 具有較強(qiáng)的“爬山”能力, 可以跳出局部最優(yōu)解, 轉(zhuǎn)向解空間的其他區(qū)域, 從而提高獲得更好的全局最優(yōu)解的概率, 是具有較強(qiáng)搜索能力的全局迭代尋優(yōu)算法[11]。然而, 在這些優(yōu)點(diǎn)之外, 禁忌搜索算法也存在容易陷入死鎖等問(wèn)題。

為了禁忌搜索算法在機(jī)器人路徑規(guī)劃問(wèn)題上的進(jìn)一步應(yīng)用, 研究者們作了許多優(yōu)化與改進(jìn)。Lee等[12]提出了基于混合禁忌搜索和2-opt路徑規(guī)劃的距離受限多機(jī)器人任務(wù)路徑規(guī)劃算法, 這是一個(gè)兩階段的啟發(fā)式算法, 旨在最大限度地減少時(shí)間和能量消耗, 協(xié)調(diào)多機(jī)器人任務(wù)的路徑。在第一階段, 使用禁忌搜索算法和2-opt節(jié)點(diǎn)交換方法生成單一最優(yōu)路徑; 再根據(jù)機(jī)器人編號(hào)將解決方案分成多個(gè)集群, 作為每個(gè)集群的初始解決方案。在第二階段, 結(jié)合2-opt路徑交換的禁忌算法被用于進(jìn)一步改進(jìn)每條路線的路線內(nèi)和路線間的解決方案。為了更好地解決未知環(huán)境下的路徑規(guī)劃問(wèn)題, Khaksar等[13]提出了基于采樣的禁忌搜索路徑規(guī)劃算法, 該方法是一種滿(mǎn)足低內(nèi)存和低計(jì)算要求的方法,在未知環(huán)境下基于采樣的禁忌搜索路徑規(guī)劃算法中, 禁忌搜索部分指導(dǎo)采樣, 在最有希望的區(qū)域找到樣本, 并使采樣過(guò)程更加智能。陳展等[14]提出了基于禁忌搜索的多自動(dòng)導(dǎo)引車(chē)(AGV)系統(tǒng)路徑優(yōu)化算法, 為了滿(mǎn)足多AGV系統(tǒng)的工作需要, 在任務(wù)區(qū)域內(nèi)求解出符合要求的可行路徑是必須解決的問(wèn)題。多AGV系統(tǒng)的路徑規(guī)劃問(wèn)題屬于NP問(wèn)題, 約束條件復(fù)雜、 問(wèn)題規(guī)模和求解難度大[15], 陳展等[14]將拓?fù)浣７ㄅc禁忌搜索算法結(jié)合, 在信息結(jié)構(gòu)更加靈活簡(jiǎn)潔的地圖中應(yīng)用禁忌搜索算法。

Lee等[12]的算法在路徑優(yōu)化和算法運(yùn)行時(shí)間方面都具有優(yōu)勢(shì), 得出的路徑更短, 更加平滑, 多個(gè)機(jī)器人之間協(xié)調(diào)完成任務(wù)消耗的能量更少。Khaksar等[13]的算法結(jié)合了禁忌搜索來(lái)實(shí)現(xiàn)智能采樣, 在路徑規(guī)劃過(guò)程中使用了兩種采樣策略, 包括均勻采樣和高斯采樣, 在不同類(lèi)型的環(huán)境中具有不同的效率, 得出的路徑長(zhǎng)度較其他算法更短, 運(yùn)行速度更快, 在內(nèi)存和計(jì)算方面要求更低。陳展等[14]的算法較傳統(tǒng)路徑規(guī)劃算法具有顯著優(yōu)越性: 當(dāng)?shù)貓D規(guī)模較大、 項(xiàng)目較為復(fù)雜時(shí), 與其他算法相比, 規(guī)劃路徑所需時(shí)間更少、 路徑長(zhǎng)度更短, 多AGV系統(tǒng)運(yùn)行更加流暢, 能耗明顯降低。

禁忌搜索算法與其他算法相結(jié)合后, 求解的路徑在長(zhǎng)度和平滑度等方面有明顯提升。當(dāng)結(jié)合適當(dāng)?shù)沫h(huán)境建模方法, 在更加簡(jiǎn)潔的地圖上進(jìn)行路徑規(guī)劃時(shí), 禁忌搜索算法的死鎖率也相應(yīng)降低, 效率提高, 有了更明顯的優(yōu)越性。

1.2 局部路徑規(guī)劃

局部路徑規(guī)劃是在環(huán)境信息未知的情況下進(jìn)行路徑規(guī)劃, 通過(guò)傳感器等工具實(shí)時(shí)獲取當(dāng)前的環(huán)境狀況, 從而進(jìn)行路徑規(guī)劃和實(shí)時(shí)避障。目前常用的局部路徑規(guī)劃算法有人工勢(shì)場(chǎng)法、 D*算法等。

1.2.1 基于人工勢(shì)場(chǎng)法的路徑規(guī)劃 1986年, Khatib首先提出人工勢(shì)場(chǎng)算法并應(yīng)用于到機(jī)器人路徑規(guī)劃領(lǐng)域[16]。人工勢(shì)場(chǎng)法的本質(zhì)是將機(jī)器人在規(guī)定區(qū)域內(nèi)的運(yùn)動(dòng)類(lèi)比于在虛擬力場(chǎng)中的合力運(yùn)動(dòng), 即障礙物對(duì)機(jī)器人產(chǎn)生使其遠(yuǎn)離當(dāng)前位置的斥力, 目標(biāo)點(diǎn)對(duì)機(jī)器人產(chǎn)生使其靠近目標(biāo)位置的吸力, 機(jī)器人在虛擬力場(chǎng)的合力方向指引下快速逼近目標(biāo)點(diǎn)位置。人工勢(shì)場(chǎng)算法具有結(jié)構(gòu)簡(jiǎn)潔明了、 生成路徑平滑易操作以及算法運(yùn)行穩(wěn)定的特點(diǎn)[17], 頗受研究人員的青睞。人工勢(shì)場(chǎng)法的收斂速度較快, 得出的路徑具有較高的可達(dá)性, 非常適合于對(duì)路徑生成實(shí)時(shí)性和安全性要求較高的規(guī)劃任務(wù), 得到的規(guī)劃路徑是最平滑、 最安全的[18]。

為了方便建立模型, 可將機(jī)器人和目標(biāo)點(diǎn)等效為質(zhì)點(diǎn)、 將障礙物等效為圓, 建立二維勢(shì)場(chǎng)模型, 如圖4所示。機(jī)器人從起點(diǎn)開(kāi)始, 根據(jù)合力方向確定下一個(gè)節(jié)點(diǎn), 直至目標(biāo)點(diǎn)。由此得到的一系列路徑點(diǎn), 整合之后就是可行路徑。由于人工勢(shì)場(chǎng)法是把所有環(huán)境信息轉(zhuǎn)變?yōu)樘摂M力場(chǎng)的斥力與引力, 忽略了障礙物的分布特點(diǎn), 僅通過(guò)最后的合力指向機(jī)器人的下一個(gè)運(yùn)動(dòng)節(jié)點(diǎn), 在復(fù)雜的現(xiàn)實(shí)環(huán)境中可能發(fā)生目標(biāo)不可達(dá)現(xiàn)象, 這是人工勢(shì)場(chǎng)法不能忽略的問(wèn)題。

圖4 人工勢(shì)場(chǎng)模型中機(jī)器人受力示意圖Fig.4 Force diagram of robot in artificial potential field model

針對(duì)人工勢(shì)場(chǎng)法的不足, 研究者從不同方面提出了許多改進(jìn)策略。劉義等[19]首先在算法中引入機(jī)器人與目標(biāo)點(diǎn)相對(duì)位置這一變量, 然后將原有的斥力場(chǎng)函數(shù)乘以一個(gè)系數(shù), 最終使得目標(biāo)點(diǎn)處的斥力場(chǎng)函數(shù)值為0。如此一來(lái), 不但解決了人工勢(shì)場(chǎng)法容易陷入局部最小值的問(wèn)題, 而且經(jīng)過(guò)優(yōu)化之后, 機(jī)器人在距離目標(biāo)點(diǎn)較近時(shí)不再因?yàn)槟繕?biāo)點(diǎn)引力減小, 障礙物斥力增強(qiáng)而減緩收斂速度甚至無(wú)法真正到達(dá)目標(biāo)點(diǎn)。Azzabi等[20]針對(duì)有限環(huán)境下傳統(tǒng)人工勢(shì)場(chǎng)法在移動(dòng)機(jī)器人路徑規(guī)劃時(shí)的局部極小值和障礙物附近目標(biāo)不可達(dá)問(wèn)題, 采用更強(qiáng)的吸引函數(shù)來(lái)保證機(jī)器人成功到達(dá)目標(biāo), 同時(shí)提出了一種新的排斥函數(shù), 當(dāng)檢測(cè)到局部極小值時(shí), 會(huì)激活一個(gè)虛逃逸力, 允許機(jī)器人從死鎖位置逃脫, 并沿著目標(biāo)方向平穩(wěn)地轉(zhuǎn)向, 遠(yuǎn)離障礙物。Fan等[21]基于改進(jìn)的人工勢(shì)場(chǎng)法, 提出了一種更高效率的水下機(jī)器人路徑規(guī)劃方法: 在排斥勢(shì)場(chǎng)函數(shù)中加入距離修正因子來(lái)求解障礙物附近目標(biāo)不可達(dá)問(wèn)題, 針對(duì)局部極小值問(wèn)題, 提出了正六邊形引導(dǎo)法; 針對(duì)動(dòng)態(tài)環(huán)境, 提出了運(yùn)動(dòng)目標(biāo)檢測(cè)和回避的相對(duì)速度法。該方法不僅考慮了運(yùn)動(dòng)物體的空間位置, 還考慮了運(yùn)動(dòng)物體速度的大小和方向。Zhao等[22]提出了基于改進(jìn)人工勢(shì)場(chǎng)法的評(píng)估碰撞風(fēng)險(xiǎn)的方法和避免碰撞的策略, 以解決多機(jī)器人系統(tǒng)協(xié)作執(zhí)行給定任務(wù)時(shí)機(jī)器人之間的動(dòng)態(tài)實(shí)時(shí)避碰問(wèn)題。碰撞風(fēng)險(xiǎn)評(píng)估方法基于機(jī)器人的運(yùn)動(dòng)方向和位置, 避碰策略基于人工勢(shì)場(chǎng)法和模糊推理系統(tǒng)。傳統(tǒng)的人工勢(shì)場(chǎng)法存在局部極小值的問(wèn)題, 該算法通過(guò)改進(jìn)排斥函數(shù)來(lái)優(yōu)化局部極小值。為了自適應(yīng)調(diào)整機(jī)器人的速度, 提高系統(tǒng)的安全性能, 采用模糊推理系統(tǒng)規(guī)劃?rùn)C(jī)器人的速度。

劉義等[19]主要通過(guò)修改斥力場(chǎng)函數(shù)對(duì)傳統(tǒng)人工勢(shì)場(chǎng)法進(jìn)行優(yōu)化, 較好地解決了傳統(tǒng)算法中的局部最小問(wèn)題, 這種優(yōu)化算法構(gòu)造簡(jiǎn)單, 可操作性較強(qiáng)。Azzabi等[20]的算法不僅能夠解決局部極小值和障礙物附近目標(biāo)不可達(dá)問(wèn)題, 而且與其他算法比較, 所得路徑長(zhǎng)度和算法運(yùn)行時(shí)間更短, 在收斂過(guò)程中不存在明顯振蕩, 性能更優(yōu)。Fan等[21]的算法經(jīng)仿真和真實(shí)環(huán)境的驗(yàn)證, 在水下機(jī)器人實(shí)時(shí)路徑規(guī)劃中具有良好的可行性和有效性, 能夠準(zhǔn)確避開(kāi)障礙物, 找到最優(yōu)路徑。Zhao等[22]的算法為多機(jī)器人系統(tǒng)中的每個(gè)機(jī)器人都規(guī)劃了從起始點(diǎn)到目標(biāo)點(diǎn)的無(wú)碰撞平滑最優(yōu)路徑,并且在真實(shí)環(huán)境的比較中, 收斂速度更快、 所得路徑更短, 機(jī)器人更快到達(dá)目標(biāo)點(diǎn)。

通過(guò)優(yōu)化斥力場(chǎng)函數(shù)等方法有效解決了人工勢(shì)場(chǎng)算法容易陷入局部最小值和障礙物附近目標(biāo)不可達(dá)問(wèn)題, 提高了機(jī)器人的避障率, 保障了算法在路徑規(guī)劃中的目標(biāo)可達(dá)性。

1.2.2 基于D*算法的路徑規(guī)劃 在A*算法的基礎(chǔ)上, Stentz提出了一種動(dòng)態(tài)路徑規(guī)劃算法, 即D*算法, 適用于動(dòng)態(tài)環(huán)境下的路徑規(guī)劃[23]。算法中Open、 Close和New 3個(gè)列表分別用來(lái)存儲(chǔ)未經(jīng)訪問(wèn)的節(jié)點(diǎn)、 已經(jīng)訪問(wèn)的節(jié)點(diǎn)以及待更新節(jié)點(diǎn)的路徑代價(jià), 并用A、B、C來(lái)表示[24]。

在利用 D*算法進(jìn)行路徑規(guī)劃的過(guò)程中, 機(jī)器人如果遇到障礙物, 需要重新尋找可行路徑以達(dá)到避障的目的時(shí), 算法能夠從存儲(chǔ)了路徑點(diǎn)信息的3個(gè)列表中找到當(dāng)前點(diǎn)和已規(guī)劃路徑的具體信息, 從而可以快速找到新的可行路徑以確保目標(biāo)可達(dá)。D*算法具有極佳的實(shí)時(shí)性, 使其更適合復(fù)雜環(huán)境下的動(dòng)態(tài)路徑規(guī)劃[25]。但是, D*算法通常在較大空間范圍內(nèi)搜索可行路徑點(diǎn), 使得算法的收斂速度無(wú)法令人滿(mǎn)意。

為了解決D*算法存在的問(wèn)題, 研究者們結(jié)合其他算法對(duì)D*算法進(jìn)行優(yōu)化。張希聞等[26]使用拓展Moore型元胞鄰居結(jié)構(gòu)來(lái)優(yōu)化路徑長(zhǎng)度, 結(jié)合跳點(diǎn)搜索算法來(lái)減少搜索時(shí)間, 較原D*算法收斂更快、 所得路徑更短。張賀等[27]采用改進(jìn)D*算法與A*算法、 動(dòng)態(tài)窗口法(DWA)相結(jié)合, 切實(shí)提高了算法的效率和實(shí)時(shí)性。Maurovic等[28]為了在自主探索未知環(huán)境時(shí)提高定位精度, 要求機(jī)器人重新訪問(wèn)以前看到的位置, 為此提出了一種主動(dòng)式定位與地圖構(gòu)建(simultaneous localization and mapping, SLAM)的路徑規(guī)劃算法, 該算法在機(jī)器人平穩(wěn)、 不間斷地向目標(biāo)位置移動(dòng)的同時(shí), 不斷提高機(jī)器人的定位精度, 基于D*最短路徑搜索算法可用于定位不確定性的情況下尋找最短路徑。

張希聞等[26]改進(jìn)后的D*算法規(guī)劃得出的路徑較傳統(tǒng)算法長(zhǎng)度更短、 遍歷節(jié)點(diǎn)減少, 具有較好的可操作性和實(shí)用性, 同時(shí)路徑更為平滑。張賀等[27]改進(jìn)的D*算法通過(guò)柵格更新的路徑重規(guī)劃方法在路徑避障效果上有了明顯提升, 在地圖中只有受障礙物影響的柵格需要進(jìn)行重新處理, 機(jī)器人的避障能力顯著提高, 算法的性能也有了質(zhì)的提升。Maurovic等[28]的主動(dòng)式SLAM路徑規(guī)劃算法能夠有效處理環(huán)境中的動(dòng)態(tài)變化信息, 包括移動(dòng)障礙物和機(jī)器人移動(dòng)時(shí)可能出現(xiàn)的定位需求。在真實(shí)環(huán)境的測(cè)試中, 機(jī)器人的路徑是連續(xù)的, 當(dāng)定位點(diǎn)出現(xiàn)時(shí), 機(jī)器人的速度不會(huì)快速改變, 這使得機(jī)器人運(yùn)動(dòng)更快, 探索更快, 同時(shí)提高了定位的準(zhǔn)確性; 當(dāng)動(dòng)態(tài)障礙物出現(xiàn)時(shí), 最短路徑僅局部改變, 從而確保了機(jī)器人到達(dá)目標(biāo)位置所需的時(shí)間不發(fā)生明顯變化。

通過(guò)改進(jìn)算法結(jié)構(gòu)和結(jié)合其他算法, D*算法在路徑規(guī)劃上的收斂速度、 實(shí)時(shí)性和避障能力有了明顯提高, 在實(shí)際環(huán)境中的應(yīng)用也不斷拓寬。

2 智能仿生算法路徑規(guī)劃

智能仿生算法是一類(lèi)模擬自然生物進(jìn)化或者群體社會(huì)行為的隨機(jī)搜索方法, 由于其求解時(shí)不依賴(lài)梯度信息, 故而廣泛應(yīng)用于路徑規(guī)劃等實(shí)際問(wèn)題[29]。智能仿生算法主要包括蟻群算法、 遺傳算法以及粒子群算法等。

2.1 基于蟻群算法的路徑規(guī)劃

蟻群算法 (ant colony optimization)首次出現(xiàn)于意大利學(xué)者M(jìn)arco Dorigo于1992發(fā)表的博士論文中, 其脫胎于自然界中的螞蟻因覓食需要而尋找前往食物源的最優(yōu)路徑的行為[30]。算法具有的創(chuàng)新性和正反饋機(jī)制優(yōu)勢(shì)使其廣泛應(yīng)用于路徑規(guī)劃問(wèn)題, 同時(shí), 算法具有較強(qiáng)的魯棒性, 輸出不易受外部擾動(dòng)的影響。

螞蟻在外出覓食的途中, 更傾向于選擇信息素濃度較高的路徑, 由此形成了一種正反饋機(jī)制, 這條路徑也就演變成了螞蟻前往食物源的最優(yōu)解路徑[31]。蟻群系統(tǒng)的基本結(jié)構(gòu)如圖5所示, 算法的兩個(gè)關(guān)鍵過(guò)程為狀態(tài)轉(zhuǎn)移和信息素更新[32]。

圖5 蟻群系統(tǒng)結(jié)構(gòu)圖Fig.5 Structure diagram of ant colony system

狀態(tài)轉(zhuǎn)移概率可表示為

(1)

其中:τij為節(jié)點(diǎn)i到節(jié)點(diǎn)j之間路徑的信息素濃度;ηij為啟發(fā)函數(shù);dij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的歐氏距離;α為信息素啟發(fā)因子, 表示信息素濃度對(duì)狀態(tài)轉(zhuǎn)移概率的影響;β為期望啟發(fā)因子, 表示路徑信息對(duì)狀態(tài)轉(zhuǎn)移概率的影響[33]。

信息素更新可表示為

τij(t+1)=(1-ρ)*τij(t)+Δτij(t),

(2)

其中:ρ為信息素?fù)]發(fā)系數(shù); 1-ρ則表示信息素殘留系數(shù); Δτij為本輪迭代中節(jié)點(diǎn)i到節(jié)點(diǎn)j之間路徑總的信息素濃度增量[34]。

蟻群算法最早應(yīng)用于旅行商問(wèn)題, 并逐漸在其他領(lǐng)域得到廣泛實(shí)踐與改良。在機(jī)器人路徑規(guī)劃、 交通擁堵?tīng)顩r下的車(chē)輛動(dòng)態(tài)路徑規(guī)劃及公眾場(chǎng)所人群疏散等多個(gè)領(lǐng)域, 都取得了令人滿(mǎn)意的結(jié)果[35-37]。蟻群算法應(yīng)用于機(jī)器人路徑規(guī)劃分為初始化、 解構(gòu)建和信息素更新3部分[38]。蟻群算法可以與其他算法進(jìn)行有機(jī)結(jié)合, 從而優(yōu)化其收斂速度慢和容易陷入局部最優(yōu)解問(wèn)題。

趙娟平等[39]為解決算法可能陷入局部最優(yōu)解的問(wèn)題, 引入差分演化算法和混沌擾動(dòng)因子改良算法中的信息素更新方式, 再根據(jù)障礙物分布的復(fù)雜程度、 路徑平滑需要以保證機(jī)器人轉(zhuǎn)向方便以及距離最短等指標(biāo)提出了新的綜合評(píng)價(jià)函數(shù)。Yang等[40]結(jié)合并行計(jì)算方法和精英策略, 提出了并行精英蟻群算法: 先生成初始可行路徑, 擴(kuò)大了蟻群的搜索多樣性, 加快了收斂速度, 并在此基礎(chǔ)上加入了拐點(diǎn)優(yōu)化算法——分段b樣條插值算法, 使得路徑更加平滑, 由此組成了穩(wěn)定性更好、 路徑更短更平滑、 環(huán)境適應(yīng)性更強(qiáng)的雙層蟻群優(yōu)化算法(DL-ACO)。Luo等[41]針對(duì)蟻群算法存在的局部最優(yōu)、 收斂速度慢、 搜索效率低等問(wèn)題, 提出了一種改進(jìn)的蟻群優(yōu)化算法: 在路徑規(guī)劃初期構(gòu)建了不等分配的初始信息素, 避免了早期規(guī)劃時(shí)的盲目搜索; 同時(shí), 采用偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則選擇路徑, 并根據(jù)當(dāng)前最優(yōu)解和迭代次數(shù)計(jì)算狀態(tài)轉(zhuǎn)移概率, 自適應(yīng)調(diào)整確定或隨機(jī)選擇的比例; 此外, 引入最優(yōu)解和最差解來(lái)改進(jìn)全局信息素更新方法, 引入動(dòng)態(tài)懲罰方法解決死鎖問(wèn)題。Chen等[42]為了克服蟻群系統(tǒng)在求解機(jī)器人路徑時(shí)的全局優(yōu)化能力不足, 容易陷入局部最優(yōu)解的缺點(diǎn), 提出了融合分流分層混合神經(jīng)網(wǎng)絡(luò)算法(SHAA)的自適應(yīng)蟻群算法: 為了綜合考慮算法的全局搜索能力和收斂速度, 提出了動(dòng)態(tài)自適應(yīng)信息素?fù)]發(fā)系數(shù); 同時(shí), 將SHAA算法的激活值概念引入到原啟發(fā)函數(shù)中。

趙娟平等[39]設(shè)計(jì)的算法在保證收斂速度的前提下提高了算法的創(chuàng)新性, 且保證算法可以得到全局最優(yōu)解, 將混沌擾動(dòng)因子引入算法的信息素更新方式中, 使得算法不會(huì)輕易陷入死鎖現(xiàn)象; 此外, 采用了綜合考慮環(huán)境中多種復(fù)雜因素, 而不僅僅只以最短路徑為標(biāo)準(zhǔn)的多目標(biāo)評(píng)價(jià)函數(shù), 在實(shí)際的復(fù)雜環(huán)境中算法也能規(guī)劃出行之有效、 令人滿(mǎn)意的路徑。Yang等[40]的算法采用雙層計(jì)算結(jié)構(gòu), 具有良好的穩(wěn)定性, 每次都能提供良好的可行解, 魯棒性較強(qiáng), 且當(dāng)機(jī)器人在平滑路徑上跟蹤時(shí), 可以避免顛簸, 簡(jiǎn)化運(yùn)動(dòng)控制。Luo等[41]的算法在多種模擬環(huán)境中與其他路徑規(guī)劃算法進(jìn)行比較, 證明了該算法的有效性和優(yōu)越性, 并且在障礙物越復(fù)雜的環(huán)境, 算法的收斂速度越是快于其他算法, 不易陷入局部最優(yōu)解, 有較強(qiáng)的魯棒性。Chen等[42]的算法不僅保證了在各種簡(jiǎn)單障礙物環(huán)境下路徑的優(yōu)越和收斂速度, 而且在復(fù)雜環(huán)境下也具有良好的全局搜索能力和魯棒性。

蟻群算法通過(guò)與其他算法的結(jié)合, 更好地解決了算法在實(shí)際環(huán)境中進(jìn)行路徑規(guī)劃時(shí)存在的死鎖現(xiàn)象、 收斂速度慢和局部極值問(wèn)題, 使得算法的可信賴(lài)程度大大提高。

2.2 基于遺傳算法的路徑規(guī)劃

遺傳算法最早是由美國(guó)的 John Holland于20世紀(jì)70年代提出, 是根據(jù)自然界中的生物進(jìn)化規(guī)律, 模擬其自然進(jìn)化過(guò)程而搜索最優(yōu)解的一種算法, 是一種基于自然選擇和自然遺傳的全局優(yōu)化算法[43]。在進(jìn)化過(guò)程中, 遺傳算法主要進(jìn)行選擇、 交叉、 變異3種操作, 經(jīng)過(guò)編碼的一個(gè)字符串對(duì)應(yīng)一個(gè)可行解, 遺傳算法的操作主要是針對(duì)多個(gè)可行解組成的群體進(jìn)行[44]。

1)選擇: 將父代個(gè)體的信息不作改變地復(fù)制傳遞給子代。每個(gè)個(gè)體對(duì)當(dāng)前環(huán)境的適應(yīng)度存在差異, 在復(fù)制過(guò)程中, 適應(yīng)度值越高的個(gè)體被選中復(fù)制的概率越大, 這一原則體現(xiàn)了自然界的優(yōu)勝劣汰法則, 使得群體中的優(yōu)秀個(gè)體所占比例不斷提高。隨著迭代的進(jìn)行, 適應(yīng)度值越高的路徑越容易被保存, 整體路徑不斷優(yōu)化。選擇操作采用輪盤(pán)賭方式進(jìn)行

(3)

其中:Pi為第i名個(gè)體被選中復(fù)制保存的概率;fi為第i名個(gè)體的適應(yīng)度值。

2)交叉: 主要使得同一代不同個(gè)體間的部分基因進(jìn)行交換, 產(chǎn)生不同基因組合的新個(gè)體, 有別于選擇操作的單純復(fù)制, 在擇優(yōu)的基礎(chǔ)上進(jìn)一步催生更加優(yōu)秀的個(gè)體。將交叉操作應(yīng)用于路徑規(guī)劃問(wèn)題時(shí), 有利于產(chǎn)生新的路徑, 在面對(duì)復(fù)雜環(huán)境或動(dòng)態(tài)障礙物時(shí)能有更多選擇。在進(jìn)行交叉操作之前, 要確定交叉概率Pc, 之后隨機(jī)生成概率Pi,Pi∈(0, 1), 如果Pi

3)變異: 可使個(gè)體的基因型發(fā)生突變, 從而提供更多的基因組合。上述兩種操作的實(shí)質(zhì)是擇優(yōu)和重組, 是在較小范圍內(nèi)尋找最優(yōu)解, 而變異操作增加了基因型種類(lèi), 使得排列組合有了更多可能性, 算法的尋優(yōu)范圍進(jìn)一步擴(kuò)大。應(yīng)用于路徑規(guī)劃時(shí), 變異操作可以增、 刪某個(gè)路徑點(diǎn)或者移動(dòng)該路徑點(diǎn), 從而獲得避開(kāi)障礙物的新路徑, 但是變異操作具有一定的不確定性, 所獲得路徑的適應(yīng)度值有提高或降低的可能。

在進(jìn)行變異操作之前, 要先確定變異概率Pv, 之后隨機(jī)生成概率Pj,Pj∈(0, 1), 如果Pj

圖6 遺傳算法流程圖Fig.6 Flow chart of genetic algorithm

遺傳算法的適應(yīng)度函數(shù)可表示為

(4)

其中:D為當(dāng)前規(guī)劃路徑的總長(zhǎng)度;N為路徑穿過(guò)的柵格數(shù), 規(guī)劃路徑越短, 則穿過(guò)的柵格數(shù)越少, 對(duì)應(yīng)的適應(yīng)度值f越大, 該路徑被選中保存至下一次迭代的概率越大[46]。

然而, 遺傳算法局部搜索能力較差、 易早熟、易陷入局部最優(yōu)的缺陷, 促使了大量學(xué)者對(duì)遺傳算法進(jìn)行優(yōu)化與改進(jìn)。Hao等[47]提出了基于多種群遷移遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃。該算法將一個(gè)較大的種群隨機(jī)劃分為若干個(gè)種群數(shù)目相同的小種群, 利用種群間的遷移機(jī)制代替選擇算子的篩選機(jī)制, 對(duì)交叉算子、 變異算子等操作也進(jìn)行了改進(jìn)。Karami等[48]提出了二維復(fù)雜環(huán)境下機(jī)器人運(yùn)動(dòng)規(guī)劃的自適應(yīng)遺傳算法, 設(shè)計(jì)了一種新的選擇算子,在每次迭代中, 如果需要, 將通過(guò)使用來(lái)自適應(yīng)度函數(shù)值的標(biāo)準(zhǔn)偏差的反饋信息來(lái)更新選擇性壓力。Chen等[49]提出了基于自適應(yīng)遺傳算法的足球機(jī)器人路徑規(guī)劃, 主要改變了遺傳操作中的交叉概率和變異概率。

Hao等[47]的算法通過(guò)使用新的算子或改進(jìn)原有算子, 打破了局部最優(yōu)解, 解決了種群個(gè)體嚴(yán)重同質(zhì)化的現(xiàn)象, 加快了算法的收斂速度, 提高了收斂個(gè)體的質(zhì)量, 其不僅適用于各種比例尺和各種障礙物分布的仿真地圖, 而且性能優(yōu)越。Karami等[48]的算法用自適應(yīng)選擇算子代替了遺傳算法中傳統(tǒng)的選擇算子, 自適應(yīng)選擇算子通過(guò)使用搜索過(guò)程的反饋信息, 即個(gè)體適應(yīng)值的標(biāo)準(zhǔn)偏差, 在整個(gè)算法運(yùn)行過(guò)程中適當(dāng)?shù)乜刂七x擇壓力; 此外, 選擇算子通過(guò)使用其新穎的自動(dòng)調(diào)整過(guò)程來(lái)防止過(guò)早收斂, 個(gè)體的多樣性被很好地保存, 將所提出的自適應(yīng)選擇算子引入遺傳算法切實(shí)提高了求解質(zhì)量。Chen等[49]的自適應(yīng)遺傳算法收斂速度明顯提高, 求解的路徑實(shí)現(xiàn)了即時(shí)的避障行為, 優(yōu)于傳統(tǒng)的遺傳算法。

針對(duì)遺傳算法, 通過(guò)新的機(jī)制代替原有的選擇算子或結(jié)合自適應(yīng)算法改變遺傳操作中的交叉概率和變異概率, 改善了其局部搜索能力較差、 易早熟和易陷入局部最優(yōu)的缺陷, 進(jìn)一步增強(qiáng)了算法的魯棒性和擴(kuò)展性。

2.3 基于粒子群優(yōu)化算法的路徑規(guī)劃

粒子群算法是1995年由美國(guó)的心理學(xué)家Kenndy和電氣工程師Eberhart首次提出來(lái)的一種集群優(yōu)化算法。粒子群優(yōu)化算法起源于對(duì)自然界中鳥(niǎo)群、 魚(yú)群覓食行為的研究, 并通過(guò)模擬群覓食行為中的相互合作機(jī)制尋求問(wèn)題的最優(yōu)解[50-52]。算法首先初始化分布在解空間中的粒子, 然后粒子經(jīng)過(guò)迭代尋找到全局最優(yōu)解。在迭代過(guò)程中, 粒子依據(jù)兩個(gè)極值來(lái)更新自身的速度和位置: 一是粒子個(gè)體極值(pbest), 二是解空間中的群體極值(gbest)。每個(gè)粒子都時(shí)刻更新速度, 以求搜索到全局最優(yōu)解。設(shè)解空間為n維, 則第i個(gè)粒子在時(shí)刻t的位置、 速度為

xi(t)=[xi1(t),xi2(t), …,xin(t)];

(5)

vi(t)=[vi1(t),vi2(t), …,vin(t)];

(6)

vi+1(t+1)=wvi(t)+c1r1(pbesti(t)-xi(t))+

c2r2(gbesti(t)-xi(t));

(7)

xi+1(t+1)=xi(t)+vi+1(t+1)。

(8)

其中:w為慣性權(quán)重系數(shù), 它決定了上次迭代速度保留的多少, 取適當(dāng)值可以保證粒子的均衡發(fā)展和探索能力;c1和c2為學(xué)習(xí)因子, 用于調(diào)控算法的局部收斂性;r1和r2為[0, 1]間分布的隨機(jī)數(shù), 用于增加種群多樣性[53]。

粒子群算法具有結(jié)構(gòu)簡(jiǎn)單、 參數(shù)簡(jiǎn)潔以及容易實(shí)現(xiàn)等優(yōu)點(diǎn), 因此, 被廣泛應(yīng)用于解決路徑規(guī)劃等問(wèn)題。粒子群算法應(yīng)用于機(jī)器人路徑規(guī)劃問(wèn)題的流程如圖7所示。其中, 每個(gè)粒子代表一條可行路徑, 粒子的維度分量則對(duì)應(yīng)該路徑上各節(jié)點(diǎn)與起始點(diǎn)至目標(biāo)點(diǎn)連線的距離。

圖7 粒子群算法流程圖Fig.7 Flow chart of particle swarm optimization

粒子群算法雖然在路徑規(guī)劃問(wèn)題上得到廣泛應(yīng)用, 但是其本身也存在缺點(diǎn): ① 算法比較容易陷入局部最優(yōu)解; ② 算法的收斂速度隨著迭代次數(shù)和搜索范圍的增加而不斷變慢, 甚至最終停滯; ③ 算法開(kāi)始時(shí)的參數(shù)設(shè)定大多是依據(jù)經(jīng)驗(yàn), 具有一定的不確定性。

為了提高粒子群算法在求解路徑規(guī)劃問(wèn)題上的可靠性, Wang等[54]提出了基于多目標(biāo)粒子群優(yōu)化算法的粗糙地形類(lèi)車(chē)移動(dòng)機(jī)器人路徑規(guī)劃方法: 先用一種新的工作空間建模方法對(duì)粗糙地形環(huán)境進(jìn)行建模, 尋找長(zhǎng)度和地形粗糙度最小的無(wú)碰撞可行路徑; 然后, 考慮類(lèi)車(chē)機(jī)器人的非完整約束, 采用基于多目標(biāo)粒子群優(yōu)化的方法進(jìn)行求解; 最后, 采用一種新的基于擁擠半徑的粒子全局最優(yōu)位置更新方法來(lái)增加種群多樣性, 當(dāng)路徑與障礙物發(fā)生碰撞時(shí), 采用非均勻因子來(lái)更新粒子的位置。Lian等[53]提出了基于3次樣條插值的混沌自適應(yīng)粒子群算法的機(jī)器人路徑規(guī)劃方法: 選擇多個(gè)路徑節(jié)點(diǎn)作為3次樣條插值的控制點(diǎn), 通過(guò)在起始點(diǎn)、 控制點(diǎn)和目標(biāo)點(diǎn)的路徑上插值, 形成光滑路徑; 采用甲蟲(chóng)覓食策略對(duì)粒子群算法的位置更新方程進(jìn)行了修正; 用三角函數(shù)對(duì)優(yōu)化算法的控制參數(shù)進(jìn)行自適應(yīng)調(diào)整; 在算法開(kāi)始時(shí), 粒子以較大的速度步長(zhǎng)在全局范圍內(nèi)搜索; 搜索后期, 粒子圍繞極值點(diǎn)進(jìn)行精細(xì)搜索; 利用混沌映射代替粒子群算法的隨機(jī)參數(shù), 提高了粒子群算法的多樣性, 保持了原有的隨機(jī)特性。Wang等[55]提出了基于改進(jìn)量子粒子群算法的水下機(jī)器人離線路徑規(guī)劃方法: 采用球面建模方法將不規(guī)則水下障礙物表示為具有特定半徑的球體; 針對(duì)傳統(tǒng)粒子群優(yōu)化算法在收斂和優(yōu)化能力上的局限性, 提出了量子粒子群優(yōu)化算法, 并對(duì)水下機(jī)器人的最佳路徑進(jìn)行了識(shí)別; 通過(guò)構(gòu)造適應(yīng)度函數(shù)以滿(mǎn)足路徑安全、 路徑長(zhǎng)度和路徑點(diǎn)角度變化3個(gè)因素的約束; 此外, 利用3次樣條插值算法對(duì)路徑進(jìn)行了光滑處理。Zhang等[56]提出了基于改進(jìn)局部粒子群算法的移動(dòng)機(jī)器人路徑規(guī)劃方法: 首先, 改進(jìn)了慣性權(quán)重、 加速和定位因子; 其次, 采用的擴(kuò)展高斯分布增加了粒子的多樣性, 而多樣性的增加可以幫助克服算法早熟的缺點(diǎn); 最后, 將平滑原理應(yīng)用于路徑規(guī)劃。

Wang等[54]的算法在仿真環(huán)境下較其他算法有最短的可行路徑, 且路徑最為平緩, 性能最優(yōu)。當(dāng)工作空間較大且環(huán)境較為復(fù)雜時(shí), 算法也不易陷入局部極小值, 可以搜索到全局最優(yōu)解, 能夠滿(mǎn)足粗糙地形的路徑規(guī)劃要求。Lian等[53]的改進(jìn)提高了傳統(tǒng)粒子群算法的全局搜索能力和收斂速度, 實(shí)現(xiàn)了靜態(tài)環(huán)境中的機(jī)器人最優(yōu)路徑規(guī)劃。該算法在不同環(huán)境中均具有較好性能和較強(qiáng)的魯棒性, 與其他路徑規(guī)劃算法相比, 解得的路徑更短、 更平滑。Wang等[55]提出的方法不需要對(duì)三維環(huán)境進(jìn)行網(wǎng)格建模, 節(jié)省了時(shí)間, 降低了計(jì)算成本, 具有更大的靈活性, 顯著提高了傳統(tǒng)算法的收斂性和優(yōu)化能力。在不同的實(shí)驗(yàn)環(huán)境下, 該算法較其他算法具有更強(qiáng)的路徑規(guī)劃能力和更高的穩(wěn)定性, 并能更快地收斂到最優(yōu)解。Zhang等[56]的算法能夠快速找到最優(yōu)路徑, 具有較高的精度和魯棒性, 在復(fù)雜、 大規(guī)模和三維環(huán)境中也具有一定的有效性。

粒子群算法結(jié)合其他策略對(duì)位置更新方式的改進(jìn), 極大提高了算法的全局搜索能力和收斂速度。算法經(jīng)過(guò)特定函數(shù)對(duì)參數(shù)的調(diào)整, 具有了更強(qiáng)的局部搜索能力, 魯棒性和靈活性有了明顯提升。

3 結(jié)論與建議

路徑規(guī)劃算法是機(jī)器人研究中無(wú)法規(guī)避的, 只有規(guī)劃的路徑符合要求, 機(jī)器人的作業(yè)能力才能有所保障。盡管路徑規(guī)劃算法種類(lèi)繁多, 但不可否認(rèn)的是, 單一算法大都有其局限性和片面性, 無(wú)法適用于所有問(wèn)題, 可以從以下三個(gè)方面進(jìn)行改進(jìn)。

(1)針對(duì)算法結(jié)構(gòu)上的缺陷進(jìn)行改進(jìn), 使得算法的穩(wěn)定性及魯棒性有一定程度的提高。

(2)機(jī)器人是多學(xué)科融合的產(chǎn)物, 各種算法相互借鑒、 有機(jī)融合。單獨(dú)一種算法有其局限性和片面性, 而多種算法的優(yōu)勢(shì)互補(bǔ)所形成的改進(jìn)算法將更具普遍性。

(3)機(jī)器人作業(yè)環(huán)境的復(fù)雜度隨機(jī)器人的廣泛應(yīng)用也不斷提高。在地形復(fù)雜且障礙物分布狀況不明朗的環(huán)境中, 在進(jìn)行機(jī)器人路徑規(guī)劃時(shí)要更加注重實(shí)時(shí)性和避障效率, 以此保證目標(biāo)點(diǎn)的可達(dá)和既定任務(wù)的完成。

以上論述的兩類(lèi)路徑規(guī)劃算法各有側(cè)重, 在處理某些復(fù)雜路徑問(wèn)題時(shí), 可搭配使用, 以提高路徑規(guī)劃的成功率。根據(jù)實(shí)際需求, 路徑規(guī)劃算法必將不斷優(yōu)化, 這是一個(gè)不斷進(jìn)步的過(guò)程。