避障機器人路徑規(guī)劃算法的研究

賓海茵 吳超龍 趙琳

摘? 要：結合移動機器人的實際應用場景，針對常規(guī)算法規(guī)劃出的路徑存在折點多、轉彎角度過大、與障礙物距離較小、搜索的路徑較長等問題，對在柵格地圖下混合全局路徑規(guī)劃與局部路徑規(guī)劃算法進行了研究，采用人工勢場算法與蟻群算法混合，為移動機器人規(guī)劃出全局最優(yōu)路徑，同時實時躲避局部障礙物。經過仿真測試，移動機器人可以根據全局路徑規(guī)劃的路徑得到最優(yōu)的整體路徑，通過局部路徑規(guī)劃算法避開局部區(qū)域的障礙物，使移動機器人能夠從起點平穩(wěn)無碰撞地行駛至目標點。

關鍵詞：智能算法；機器人路徑規(guī)劃；移動機器人；避障機器人

中圖分類號：TP242? ? 文獻標識碼：A? 文章編號：2096-4706（2023）07-0157-04

Abstract： Aiming at the problems of many inflection points， too large turning angle， small distance from obstacles， and long search path in the path planned by conventional algorithms， this paper combines with the practical application scenario of mobile robots， studies the hybrid global path planning and local path planning algorithms under grid maps， uses the hybrid artificial potential field algorithm and ant colony algorithm to plan the global optimal path for mobile robots， and avoids local obstacles at the same time. Through the simulation test， the mobile robot can obtain the optimal overall path according to the path planned by the global path planning， and avoid the obstacles in the local area through the local path planning algorithm， so that the mobile robot can travel without collision from the starting point to the target point smoothly.

Keywords： intelligent algorithm; robot path planning; mobile robot; obstacle avoidance robot

0? 引? 言

移動機器人的路徑規(guī)劃是機器人學的重要研究領域，也是人工智能和機器人學的一個非常重要的結合。不管移動機器人的應用如何，在工作過程中往往需要沿著工作區(qū)域的最佳路徑或非最佳路徑進行（如最小路徑長度、最合適路徑等）。路徑規(guī)劃問題可以看作是一種受制約的優(yōu)化問題，它需要完成路徑規(guī)劃，自我定位和避障操作，路徑算法的改進實質上也是滿足一定約束條件下的改進問題。路徑規(guī)劃是移動機器人導航中最重要的任務之一，通過路徑規(guī)劃移動機器人在無人控制的情況下，可以對環(huán)境已“清楚”會出現的障礙物以及可能出現的障礙物進行分析和避讓，即在有障礙物的環(huán)境中尋找從開始狀態(tài)到目標狀態(tài)不發(fā)生碰撞的路徑，從而進行自主行駛完成相應任務。機器人面對復雜多變的室外環(huán)境，通過對算法的優(yōu)化改進來提高機器人的性能，路徑規(guī)劃的實時避障性、路徑平滑性、規(guī)劃有效性就成為了路徑規(guī)劃算法的核心研究內容。

因此將對移動機器人路徑規(guī)劃技術進行分析和研究，結合機器人的實際應用，考慮機器人在跟隨路徑時的適應性，為移動機器人規(guī)劃最優(yōu)路徑，探討了人工勢場算法和蟻群算法的融合算法，利用蟻群算法進行全局路徑規(guī)劃，再利用人工勢場算法進行局部路徑規(guī)劃，并針對人工勢場算法和蟻群算法可能會出現的問題，進行改進和優(yōu)化，使移動機器人獲得一條可以在實際應用中繞過障礙物安全平穩(wěn)到達目標點的最優(yōu)平滑路徑。

1? 國內外發(fā)展現狀

隨著科技的發(fā)展，在移動機器人路徑規(guī)劃領域，國內外許多研究學者進行了深入研究和改進，取得了許多成果。根據機器人對環(huán)境信息的理解程度，路徑規(guī)劃問題可分為環(huán)境信息完全已知的全局路徑規(guī)劃和環(huán)境信息不完全了解或部分不了解的局部路徑規(guī)劃兩類[1]。其中，全局路徑規(guī)劃主要有拓撲法、柵格法、可視圖法等。局部路徑規(guī)劃方法主要有人工勢場法、遺傳算法、神經網絡算法等。目前，路徑規(guī)劃技術雖然取得了相當大的成果，但方法之間有優(yōu)缺點[2]，任何一種方法都不能適用于任何環(huán)境。雖然我國對移動機器人的起步較晚，但是在國家的大力支持下，我國對移動機器人技術日漸成熟[3]。

根據路徑算法原理特點進行劃分，目前常用的路徑規(guī)劃方法可以分為傳統(tǒng)算法和智能仿生算法兩類。傳統(tǒng)的人工勢場算法常有局部最小值不易脫離和無法到達目標點的問題，為解決這些問題，張琪等[4]針對傳統(tǒng)人工勢場法在避障路徑規(guī)劃存在的缺陷，增加逃逸子因數，在Krogh算法的基礎上對人工勢場進行改進并提出了新的人工勢場函數，修復了無法到達障礙物附件上的目標點的問題，并驗證了改進人工勢場算法的有效性。

隨著環(huán)境的復雜性和空間性的增加，對移動機器人的需求越來越大，傳統(tǒng)的算法結合已經沒辦法滿足需求，它的實用性下降，計算量增大，由此，機器人領域的學者提出了一系列智能優(yōu)化算法。例如，神經網絡與遺傳算法的結合、粒子群與遺傳算法的結合、粒子群與灰狼算法結合。李真等[5]針對粒子群算法易陷入局部最優(yōu)的缺點，提出了最差改進策略和最優(yōu)粒子擾動策略，并將灰狼算法的優(yōu)勢引入粒子群算法進一步提高算法的搜索能力，由此提高了粒子群的多樣性以及最優(yōu)粒子進行擾動使粒子群跳出局部最優(yōu)。

隨著近年來人工智能技術的興起。傳統(tǒng)與智能路徑規(guī)劃算法的日益成熟推動了兩者的結合，例如柵格法與遺傳算法、粒子群算法等的融合、人工勢場法與人工神經網絡（ANN）、蟻群算法以及遺傳算法等的融合。例如，段建民等[6]通過引入填平勢場使勢場函數跳出局部極小值，并利用人工勢場算法對遺傳算法規(guī)劃路徑進行優(yōu)化，在改進的基礎上尋求全局最優(yōu)解的策略。李航宇等[7]采用了柵格法環(huán)境建模，對遺傳算法上引入刪減及增添算子，采用了動態(tài)自適應策略，對算法的運算效率有了很大的提高。

2? 機器人路徑規(guī)劃

在機器人領域的研究，移動機器人路徑規(guī)劃已經取得了大量的成果，但是對于某些實際場景仍然有局限性。移動機器人在不同的應用領域有不同的要求和問題[8]，因此，在關注具體需求和實際應用場景的同時，可以保證全局路徑規(guī)劃的有效性和及時性，優(yōu)化拐角的路徑、提高平滑性、確保移動機器人安全繞過障礙到達終點，能夠得到對工作環(huán)境更合適的最佳路徑規(guī)劃路線。

2.1? 柵格法繪制地圖

移動機器一般使用柵格法構建空間環(huán)境，實質上就是對機器人工作空間進行單元分割?？臻g環(huán)境通常使用四叉樹或八叉樹來表示，并通過規(guī)劃算法進行路徑搜索。柵格數據就是將分割后的各單元網格賦予相應的屬性值來象征實體，使場景所有物進行二值化，矩陣中的1代表障礙物，對應黑色柵格，0代表可移動空間，對應白色柵格。如圖1所示。

2.2? 蟻群算法規(guī)劃路徑

2.2.1? 蟻群算法原理

蟻群算法由Marco Dorigo等提出的一種用于尋找優(yōu)化路徑的概率型算法，他們在研究觀察螞蟻覓食過程中，發(fā)現蟻群的協(xié)作上表現出一些智能的行為[2]。從圖2可以看出，假設螞蟻從蟻巢即起點A向食物源B行走，第一波螞蟻行走方向是隨機的，蟻群的選擇有三條路徑，剛開始三條路徑上的螞蟻數量差不多。螞蟻尋到食物立即將部分食物立即返回運輸，由于路徑C距離較短，螞蟻很快能在起終點往返，重復頻率快，螞蟻在單位時間內來回移動的次數越多，它們留下的信息素就越多，更是吸引更多的螞蟻選擇C路徑，因此越來越多的螞蟻聚集到最短路徑上，得到一條從起點到終點的最優(yōu)路徑。

2.2.2? 蟻群算法的仿真

通過圖3中的蟻群算法仿真可以看出，可以在柵格地圖中尋到一條最優(yōu)路徑，并且可以避讓障礙物，因此將引用蟻群算法為機器人規(guī)劃全局路徑。但是應用到實際生活中，仍存在一些拐角過多、路線不夠平滑的缺點。

2.3? 人工勢場法規(guī)劃路徑

人工勢場法由Khatib提出的一種虛擬力法，其基本內容是將移動機器人所在環(huán)境抽象化，即周圍環(huán)境下的機器人運動抽象為一種人造的引力勢場運動，重力電位場在環(huán)境中的目標點周圍形成，斥力電位場在障礙物上形成。目標點對機器人產生引力，障礙物對機器人產生斥力，兩者合力控制機器人的動作[9]。多用于局部路徑規(guī)劃。其優(yōu)點是計算速度快，能在環(huán)境中實時避障，路徑平滑且有一定的魯棒性。從圖4可以看到就相較于蟻群算法圖3規(guī)劃出的路徑，人工勢場規(guī)劃的路徑更平滑，使實際應用中機器人的行駛更安全。從圖4人工勢場算法規(guī)劃的仿真可以觀察到，所規(guī)劃的路徑平滑無碰撞到達終點，這符合最初在實際情況下機器人需要考慮的問題，為改善算法問題，這里引入人工勢場算法，結合人工勢場的作用機理，融合算法的特點來為機器人進行局部路徑規(guī)劃。

2.4? 人工勢場-蟻群融合算法規(guī)劃路徑

通過對蟻群和人工勢場算法的仿真，可以觀察到，蟻群算法的路徑在經過拐角的時候緊貼障礙物，所規(guī)劃的路徑出現多處折點，在機器人的實際應用中，需考慮機器人的尺寸和運動學以及動力學的約束，否則容易與障礙物發(fā)生碰撞，且路徑的不平滑性，對于機器人而言，可能存在不易轉彎的困難，而多余的折點也是不必要出現的。通過人工勢場算法的仿真，雖然其路徑是一條平滑的路徑，但是由于機器人行進的過程中只考慮最近的障礙物，面對復雜道路，可能使得規(guī)劃出的路徑不是最優(yōu)解。傳統(tǒng)人工勢場算法并不適用作全局路徑規(guī)劃，一般用作局部路徑規(guī)劃。

因此從機器人實際應用的角度出發(fā)，結合實際考慮問題，利用單一算法其特點，將人工勢場算法與蟻群算法混合，使用蟻群算法進行全局路徑規(guī)劃，根據全局規(guī)劃路徑再使用人工勢場方法進行局部路徑規(guī)劃。為在工作空間活動的機器人設計最佳且平滑的路徑，使移動機器人能平穩(wěn)從起始點到終點無碰撞且平滑的到達終點。

3? 融合算法路徑規(guī)劃仿真

3.1? 地圖構建

仿真實驗將利用MATLAB進行路徑規(guī)劃算法仿真。其仿真環(huán)境為25×25的柵格地圖?？紤]到機器人的尺寸，為了更方便分析不同算法的不同路徑和最終混合的效果，更直接地觀察移動機器人無碰撞行駛的過程，將人工勢場地圖的方格大小設為5，蟻群柵格地圖方格大小設為1，通過地圖的比例縮小，減少蟻群算法的計算量和收斂速度的同時兼顧解決全局路徑規(guī)劃與局部路徑規(guī)劃的主要問題，此外，兩者地圖坐標是可以相互對應的，所規(guī)劃的路線可以通過坐標的轉換在相同的空間地圖內行駛。如圖5所示。

3.2? 單一算法規(guī)劃路徑仿真

使用蟻群算法規(guī)劃，得出如圖6中的規(guī)劃路徑，但其中機器人被看作一個質點，路線緊貼障礙物，沒有考慮到機器人的尺寸。如果應用到機器人上則會發(fā)生碰撞，且所規(guī)劃的路徑不平滑，這對機器人的移動產生阻礙。

使用人工勢場算法規(guī)劃仿真，規(guī)劃出了一條平滑的路徑，但由于算法的每次檢測周期只考慮距離最近的障礙物，面對復雜的環(huán)境無法做出最佳策略，可能規(guī)劃出的對于全局路徑規(guī)劃不是最優(yōu)解的線路。

將勢場蟻群結合，可以解決上述問題。使用蟻群算法進行全局路徑規(guī)劃，將規(guī)劃的全局獲得的路徑傳送到人工勢場算法中，人工勢場算法就會沿著全局運行移動，分段式的行駛，逐漸靠近目標點。

3.3? 兩種算法結合的仿真

圖7開始對機器人移動路徑進行仿真實驗，觀察全局路徑規(guī)劃的蟻群算法與對局部路徑規(guī)劃的人工勢場算法的結合效果。

相較于算法結合之前規(guī)劃出來的路徑，該仿真可以觀察到機器人更加安全的通過拐點并與障礙物保持安全的距離，避免移動機器人和障礙物發(fā)生碰撞，增強了其平滑性，使機器人更平滑到達終點，規(guī)劃出工作空間的最優(yōu)路徑，使用更少的時間完成從起點到終點的移動。在實際應用中，機器人可以更安全平穩(wěn)的從起點向終點移動，解決了算法出現多折角和不是最優(yōu)解的問題。

4? 結? 論

移動機器人在實際應用中受很多復雜因素的影響，因此機器人在自主移動中需要考慮的問題有很多。為機器人更適應環(huán)境，考慮到實際的應用場景，以是否能安全通過拐角、路徑平滑性和最優(yōu)路徑的問題展開對路徑算法的研究，通過蟻群算法的全局與人工勢場法的局部路徑規(guī)劃結合，為機器人規(guī)劃出一條安全平穩(wěn)的路徑。通過仿真證明，經過兩者的結合，所規(guī)劃的路徑可以更好讓機器人適應工作環(huán)境并安全平穩(wěn)的從起點移動到終點。

參考文獻：

[1] 劉自強.無人駕駛低速電動車的路徑規(guī)劃和控制系統(tǒng)的設計與實現 [D].成都：電子科技大學，2020.

[2] 吳保勝，郭宇，王發(fā)麟，等.基于改進蟻群算法的線纜路徑規(guī)劃技術研究 [J].計算機工程與應用，2018，54（10）：236-241.

[3] 孫凌宇，冷明，朱平，等.移動機器人路徑規(guī)劃算法的研究 [J].井岡山大學學報：自然科學版，2010，31（2）：56-59+64.

[4] 張琪，田甜，欒天宇，等.基于改進人工勢場算法的無人船路徑規(guī)劃 [J].艦船科學技術，2022，44（9）：63-68+78.

[5] 李真，王帆，王冉珺.一種結合灰狼算法的粒子群優(yōu)化算法 [J].計算機測量與控制，2021，29（10）：217-222.

[6] 段建民，陳強龍.基于改進人工勢場-遺傳算法的路徑規(guī)劃算法研究 [J].國外電子測量技術，2019，38（3）：19-24.

[7] 李航宇，郭曉利.考慮多因素的自適應遺傳算法機器人路徑規(guī)劃 [J].制造業(yè)自動化，2022，44（10）：76-78+95.

[8] 王梓強，胡曉光，李曉筱，等.移動機器人全局路徑規(guī)劃算法綜述 [J].計算機科學，2021，48（10）：19-29.

[9] 郭銀景，劉琦，鮑建康，等.基于人工勢場法的AUV避障算法研究綜述 [J].計算機工程與應用，2020，56（4）：16-23.

作者簡介：賓海茵（2000—），女，漢族，廣西貴港人，本科在讀，研究方向：智能控制系統(tǒng)的設計；吳超龍（2000—），男，漢族，廣西貴港人，本科在讀，研究方向：智能控制系統(tǒng)的設計；趙琳（1981—），女，漢族，河北定州人，講師，碩士研究生，研究方向：通信技術、智能控制技術。