機器人路徑規劃算法綜述

王鶴靜，王麗娜

(中國計量大學 a.機電工程學院；b.浙江省智能制造質量大數據溯源與應用重點實驗室，杭州 310018)

0 引 言

機器人是人工智能的重點研究領域, 其中路徑規劃是機器人研究與發展中必不可少的核心內容之一, 是機器人在一定環境中完成既定任務的基礎, 機器人的路徑規劃能力直觀體現了其作業能力和風險管控能力。路徑規劃是指在規定區域內規劃出一條從起始點到目標點的最優解路徑, 且要保證與障礙物無碰撞。機器人路徑規劃存在的難點問題主要有環境建模計算量大、 算法收斂速度慢以及容易陷入局部最優解問題。

對于二維環境建模問題, 主要采用柵格法進行環境建模。柵格法對機器人工作環境的描述更直觀, 對障礙物和機器人相對位置的處理更簡便, 可以最大程度上簡化路徑的求解過程。而在三維環境中, 如水下機器人, 可以將平面柵格法進行高度上的疊加, 將復雜的三維建模問題簡化為多個二維建模問題, 在一定程度上提高了解路徑的質量和路徑規劃算法的適應能力。對于路徑規劃算法普遍存在的收斂速度慢和容易陷入局部最優解問題, 通常對算法進行結構上的優化, 如增加算法參數的自適應調整能力, 可以降低算法陷入局部最優解的概率; 也可以將多個算法結合, 取長補短, 優化算法性能, 如蟻群算法可與人工勢場法結合, 利用人工勢場法生成初始可行路徑, 并調整該路徑和周圍區域的初始信息素濃度, 可以極大加快蟻群算法的早期收斂速度。

綜上, 路徑規劃可以分為傳統算法路徑規劃和智能仿生算法路徑規劃兩類, 其中傳統路徑規劃算法又可以分為全局路徑規劃算法和局部路徑規劃算法。全局路徑規劃是在已知的環境中進行路徑規劃, 環境信息已經給定且障礙物位置等信息基本不發生變化, 一般只需按照事先規劃的全局路徑進行工作即可。而局部路徑規劃是在未知的環境中進行路徑規劃, 通過傳感器等工具獲取當前的局部環境信息, 主要是動態障礙物的位置信息等, 在此基礎上進行路徑規劃和避障, 如水下機器人所處環境的障礙物分布極易發生改變, 機器人需要實時獲取環境信息進行局部路徑規劃, 對其而言, 需要在全局路徑規劃的基礎上, 多次進行局部路徑規劃,從而安全到達目標點。在這種環境中, 局部路徑規劃更為重要。智能仿生路徑規劃算法是仿生學在路徑規劃問題中的應用。機器人路徑規劃算法框架見圖1, 本文從傳統路徑規劃和智能仿生路徑規劃兩方面分別給出一些常用算法, 并進行分析總結。

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

1 傳統算法路徑規劃

傳統路徑規劃算法可以根據對環境信息的把握程度分為全局路徑規劃算法和局部路徑規劃算法。

1.1 全局路徑規劃

全局路徑規劃主要應用于給定環境信息的情況下進行路徑規劃, 不要求機器人具有較強的實時計算能力。目前常用的全局路徑規劃算法主要有A*算法、 禁忌搜索算法等。

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

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

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

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

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

針對A*算法的改進主要解決了算法在搜索速度和復雜環境中目標可達性上的問題, 切實提高了A*算法在路徑規劃上的實際應用效果。

1.1.2 基于禁忌搜索算法的路徑規劃 禁忌搜索算法(tabu search, TS)是美國科學家Glover等[7]于1986年提出的一種優化算法, 具有全局逐步尋優的能力, 能很好地應用于機器人的路徑規劃問題。禁忌搜索算法是局部搜索算法的優化與發展, 是一種基于貪婪思想的鄰域搜索算法, 但鄰域搜索算法最大的缺點就是容易陷入局部最優[8], 為了解決這一問題, 引入禁忌表, 形成了禁忌搜索算法, 使其具有了較強的全局搜索尋優能力。應用于路徑規劃問題時, 禁忌表主要是用來存放已經搜索過的路徑點, 表中的內容是動態更新的, 表的長度稱為禁忌長度。搜索時, 直接跳過禁忌表中已有的路徑點, 從而使得算法具有全局搜索的特性。

禁忌搜索算法主要由禁忌表、 禁忌長度[9]、 特赦準則、 代價函數[10]和停止規則等部分組成。禁忌搜索算法應用于路徑規劃問題的流程如圖3所示。禁忌搜索算法的主要思想有以下3點: ① 在進行領域搜索時盡量避免循環行為的產生; ② 通過禁忌表實現只進不退, 即跳過搜索過的路徑點; ③ 算法旨在尋找全局最優解, 要在局部最優解的基礎上獲取更大的搜索區域, 實現全局尋優。

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

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

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

Lee等[12]的算法在路徑優化和算法運行時間方面都具有優勢, 得出的路徑更短, 更加平滑, 多個機器人之間協調完成任務消耗的能量更少。Khaksar等[13]的算法結合了禁忌搜索來實現智能采樣, 在路徑規劃過程中使用了兩種采樣策略, 包括均勻采樣和高斯采樣, 在不同類型的環境中具有不同的效率, 得出的路徑長度較其他算法更短, 運行速度更快, 在內存和計算方面要求更低。陳展等[14]的算法較傳統路徑規劃算法具有顯著優越性: 當地圖規模較大、 項目較為復雜時, 與其他算法相比, 規劃路徑所需時間更少、 路徑長度更短, 多AGV系統運行更加流暢, 能耗明顯降低。

禁忌搜索算法與其他算法相結合后, 求解的路徑在長度和平滑度等方面有明顯提升。當結合適當的環境建模方法, 在更加簡潔的地圖上進行路徑規劃時, 禁忌搜索算法的死鎖率也相應降低, 效率提高, 有了更明顯的優越性。

1.2 局部路徑規劃

局部路徑規劃是在環境信息未知的情況下進行路徑規劃, 通過傳感器等工具實時獲取當前的環境狀況, 從而進行路徑規劃和實時避障。目前常用的局部路徑規劃算法有人工勢場法、 D*算法等。

1.2.1 基于人工勢場法的路徑規劃 1986年, Khatib首先提出人工勢場算法并應用于到機器人路徑規劃領域[16]。人工勢場法的本質是將機器人在規定區域內的運動類比于在虛擬力場中的合力運動, 即障礙物對機器人產生使其遠離當前位置的斥力, 目標點對機器人產生使其靠近目標位置的吸力, 機器人在虛擬力場的合力方向指引下快速逼近目標點位置。人工勢場算法具有結構簡潔明了、 生成路徑平滑易操作以及算法運行穩定的特點[17], 頗受研究人員的青睞。人工勢場法的收斂速度較快, 得出的路徑具有較高的可達性, 非常適合于對路徑生成實時性和安全性要求較高的規劃任務, 得到的規劃路徑是最平滑、 最安全的[18]。

為了方便建立模型, 可將機器人和目標點等效為質點、 將障礙物等效為圓, 建立二維勢場模型, 如圖4所示。機器人從起點開始, 根據合力方向確定下一個節點, 直至目標點。由此得到的一系列路徑點, 整合之后就是可行路徑。由于人工勢場法是把所有環境信息轉變為虛擬力場的斥力與引力, 忽略了障礙物的分布特點, 僅通過最后的合力指向機器人的下一個運動節點, 在復雜的現實環境中可能發生目標不可達現象, 這是人工勢場法不能忽略的問題。

圖4 人工勢場模型中機器人受力示意圖Fig.4 Force diagram of robot in artificial potential field model

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

劉義等[19]主要通過修改斥力場函數對傳統人工勢場法進行優化, 較好地解決了傳統算法中的局部最小問題, 這種優化算法構造簡單, 可操作性較強。Azzabi等[20]的算法不僅能夠解決局部極小值和障礙物附近目標不可達問題, 而且與其他算法比較, 所得路徑長度和算法運行時間更短, 在收斂過程中不存在明顯振蕩, 性能更優。Fan等[21]的算法經仿真和真實環境的驗證, 在水下機器人實時路徑規劃中具有良好的可行性和有效性, 能夠準確避開障礙物, 找到最優路徑。Zhao等[22]的算法為多機器人系統中的每個機器人都規劃了從起始點到目標點的無碰撞平滑最優路徑,并且在真實環境的比較中, 收斂速度更快、 所得路徑更短, 機器人更快到達目標點。

通過優化斥力場函數等方法有效解決了人工勢場算法容易陷入局部最小值和障礙物附近目標不可達問題, 提高了機器人的避障率, 保障了算法在路徑規劃中的目標可達性。

1.2.2 基于D*算法的路徑規劃 在A*算法的基礎上, Stentz提出了一種動態路徑規劃算法, 即D*算法, 適用于動態環境下的路徑規劃[23]。算法中Open、 Close和New 3個列表分別用來存儲未經訪問的節點、 已經訪問的節點以及待更新節點的路徑代價, 并用A、B、C來表示[24]。

在利用 D*算法進行路徑規劃的過程中, 機器人如果遇到障礙物, 需要重新尋找可行路徑以達到避障的目的時, 算法能夠從存儲了路徑點信息的3個列表中找到當前點和已規劃路徑的具體信息, 從而可以快速找到新的可行路徑以確保目標可達。D*算法具有極佳的實時性, 使其更適合復雜環境下的動態路徑規劃[25]。但是, D*算法通常在較大空間范圍內搜索可行路徑點, 使得算法的收斂速度無法令人滿意。

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

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

通過改進算法結構和結合其他算法, D*算法在路徑規劃上的收斂速度、 實時性和避障能力有了明顯提高, 在實際環境中的應用也不斷拓寬。

2 智能仿生算法路徑規劃

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

2.1 基于蟻群算法的路徑規劃

蟻群算法 (ant colony optimization)首次出現于意大利學者Marco Dorigo于1992發表的博士論文中, 其脫胎于自然界中的螞蟻因覓食需要而尋找前往食物源的最優路徑的行為[30]。算法具有的創新性和正反饋機制優勢使其廣泛應用于路徑規劃問題, 同時, 算法具有較強的魯棒性, 輸出不易受外部擾動的影響。

螞蟻在外出覓食的途中, 更傾向于選擇信息素濃度較高的路徑, 由此形成了一種正反饋機制, 這條路徑也就演變成了螞蟻前往食物源的最優解路徑[31]。蟻群系統的基本結構如圖5所示, 算法的兩個關鍵過程為狀態轉移和信息素更新[32]。

圖5 蟻群系統結構圖Fig.5 Structure diagram of ant colony system

狀態轉移概率可表示為

(1)

其中:τij為節點i到節點j之間路徑的信息素濃度;ηij為啟發函數;dij為節點i到節點j的歐氏距離;α為信息素啟發因子, 表示信息素濃度對狀態轉移概率的影響;β為期望啟發因子, 表示路徑信息對狀態轉移概率的影響[33]。

信息素更新可表示為

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

(2)

其中:ρ為信息素揮發系數; 1-ρ則表示信息素殘留系數; Δτij為本輪迭代中節點i到節點j之間路徑總的信息素濃度增量[34]。

蟻群算法最早應用于旅行商問題, 并逐漸在其他領域得到廣泛實踐與改良。在機器人路徑規劃、 交通擁堵狀況下的車輛動態路徑規劃及公眾場所人群疏散等多個領域, 都取得了令人滿意的結果[35-37]。蟻群算法應用于機器人路徑規劃分為初始化、 解構建和信息素更新3部分[38]。蟻群算法可以與其他算法進行有機結合, 從而優化其收斂速度慢和容易陷入局部最優解問題。

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

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

蟻群算法通過與其他算法的結合, 更好地解決了算法在實際環境中進行路徑規劃時存在的死鎖現象、 收斂速度慢和局部極值問題, 使得算法的可信賴程度大大提高。

2.2 基于遺傳算法的路徑規劃

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

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

(3)

其中:Pi為第i名個體被選中復制保存的概率;fi為第i名個體的適應度值。

2)交叉: 主要使得同一代不同個體間的部分基因進行交換, 產生不同基因組合的新個體, 有別于選擇操作的單純復制, 在擇優的基礎上進一步催生更加優秀的個體。將交叉操作應用于路徑規劃問題時, 有利于產生新的路徑, 在面對復雜環境或動態障礙物時能有更多選擇。在進行交叉操作之前, 要確定交叉概率Pc, 之后隨機生成概率Pi,Pi∈(0, 1), 如果Pi

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

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

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

遺傳算法的適應度函數可表示為

(4)

其中:D為當前規劃路徑的總長度;N為路徑穿過的柵格數, 規劃路徑越短, 則穿過的柵格數越少, 對應的適應度值f越大, 該路徑被選中保存至下一次迭代的概率越大[46]。

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

Hao等[47]的算法通過使用新的算子或改進原有算子, 打破了局部最優解, 解決了種群個體嚴重同質化的現象, 加快了算法的收斂速度, 提高了收斂個體的質量, 其不僅適用于各種比例尺和各種障礙物分布的仿真地圖, 而且性能優越。Karami等[48]的算法用自適應選擇算子代替了遺傳算法中傳統的選擇算子, 自適應選擇算子通過使用搜索過程的反饋信息, 即個體適應值的標準偏差, 在整個算法運行過程中適當地控制選擇壓力; 此外, 選擇算子通過使用其新穎的自動調整過程來防止過早收斂, 個體的多樣性被很好地保存, 將所提出的自適應選擇算子引入遺傳算法切實提高了求解質量。Chen等[49]的自適應遺傳算法收斂速度明顯提高, 求解的路徑實現了即時的避障行為, 優于傳統的遺傳算法。

針對遺傳算法, 通過新的機制代替原有的選擇算子或結合自適應算法改變遺傳操作中的交叉概率和變異概率, 改善了其局部搜索能力較差、 易早熟和易陷入局部最優的缺陷, 進一步增強了算法的魯棒性和擴展性。

2.3 基于粒子群優化算法的路徑規劃

粒子群算法是1995年由美國的心理學家Kenndy和電氣工程師Eberhart首次提出來的一種集群優化算法。粒子群優化算法起源于對自然界中鳥群、 魚群覓食行為的研究, 并通過模擬群覓食行為中的相互合作機制尋求問題的最優解[50-52]。算法首先初始化分布在解空間中的粒子, 然后粒子經過迭代尋找到全局最優解。在迭代過程中, 粒子依據兩個極值來更新自身的速度和位置: 一是粒子個體極值(pbest), 二是解空間中的群體極值(gbest)。每個粒子都時刻更新速度, 以求搜索到全局最優解。設解空間為n維, 則第i個粒子在時刻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為慣性權重系數, 它決定了上次迭代速度保留的多少, 取適當值可以保證粒子的均衡發展和探索能力;c1和c2為學習因子, 用于調控算法的局部收斂性;r1和r2為[0, 1]間分布的隨機數, 用于增加種群多樣性[53]。

粒子群算法具有結構簡單、 參數簡潔以及容易實現等優點, 因此, 被廣泛應用于解決路徑規劃等問題。粒子群算法應用于機器人路徑規劃問題的流程如圖7所示。其中, 每個粒子代表一條可行路徑, 粒子的維度分量則對應該路徑上各節點與起始點至目標點連線的距離。

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

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

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

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

粒子群算法結合其他策略對位置更新方式的改進, 極大提高了算法的全局搜索能力和收斂速度。算法經過特定函數對參數的調整, 具有了更強的局部搜索能力, 魯棒性和靈活性有了明顯提升。

3 結論與建議

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

(1)針對算法結構上的缺陷進行改進, 使得算法的穩定性及魯棒性有一定程度的提高。

(2)機器人是多學科融合的產物, 各種算法相互借鑒、 有機融合。單獨一種算法有其局限性和片面性, 而多種算法的優勢互補所形成的改進算法將更具普遍性。

(3)機器人作業環境的復雜度隨機器人的廣泛應用也不斷提高。在地形復雜且障礙物分布狀況不明朗的環境中, 在進行機器人路徑規劃時要更加注重實時性和避障效率, 以此保證目標點的可達和既定任務的完成。

以上論述的兩類路徑規劃算法各有側重, 在處理某些復雜路徑問題時, 可搭配使用, 以提高路徑規劃的成功率。根據實際需求, 路徑規劃算法必將不斷優化, 這是一個不斷進步的過程。