智能體路徑規劃算法研究綜述

光曉亮 楊麗圓

摘 ?要：Agent路徑規劃指的是智能體在運動的過程中構成路徑的策略。從Agent的傳感器獲取到的障礙物信息為動靜的角度來看，路徑規劃有兩種規劃方式，一是智能體處于靜態環境下的路徑規劃，二是智能體處于動態環境下的路徑規劃。該文對近年來的路徑規劃算法進行相比較，指出未來路徑規劃的研究方向和趨勢。

關鍵詞：智能體 ?策略 ?路徑規劃

中圖分類號：TP2 ? 文獻標識碼：A ? ? ? ? ? ?文章編號：1672-3791（2019）05（a）-0023-02

路徑規劃是Agent系統設計中研究的中心問題。它基于一定的性能指標，比如Agent在進行路徑規劃時所走的長度最短、利用路徑規劃算法進行路徑搜索時所用的時間最少、路徑規劃完成之后Agent所消耗的能量最少等指標，在其任務區中搜尋出一條或多條從起始點到目標任務點的最優或近似最優路徑。路徑規劃應用于各個方面，例如：國防軍事、搶險救災、物流管理、道路交通、路由問題等。

1 ?路徑規劃研究現狀

經過這些年的研究，當前的路徑規劃算法有很多種類別和方案，每種算法各有所長，各有所短，并且其所適用的范圍也大有不同。有的算法適用于二維空間，而有的算法適用于三維空間。有的算法靈活性好，但計算的路徑并不太令人滿意，而有的算法盡管靈活性差一些但所規劃的路徑卻是使人滿意的，有著較好的平滑度并且路徑長度也較為合適。但是歸根結底都可以劃分為動靜態兩類路徑規劃算法，一個是靜態路徑規劃算法，另一個是動態路徑規劃算法。

2 ?靜態路徑規劃

Agent的傳感器獲取到的障礙物的信息是靜態的，并且所處任務空間的信息狀況是能夠獲得的，比如說溫度的高低、形態特征等信息，這個時候叫作靜態的路徑規劃。主要方法有：柵格法、可視圖法、概率路徑圖法、拓撲法等。下面對這幾種典型算法進行了相應的研究并分析其優缺點。

柵格法將Agent的任務空間按照二進制進行劃分，Agent在路徑規劃的時候能夠正常通過的區域通常情況下用數字0來表示，不能通過的區域也就是所謂的障礙物區域則用數字1來表示。在柵格法中，網格大小的設計尤為關鍵。一般情況下將網格的大小設計要根據所處環境或者是所需的性能指標來進行設計，如果要求的路徑精度高且對時間沒有要求的話可以將網格劃分得小一點，如果對規劃路徑的時間要求較高且對于路徑的長度要求不大，那么可以選擇的網格可以大一點，雖然得到的所規劃的路徑并不是路徑最短或者是平滑性特別好的路徑但是依舊可以滿足時間短的要求。當然，一般情況下盡量選擇的網格大小較為適中是比較好的方案。

可視圖法的基本思維是把智能體當作一個點，而后利用線段銜接Agent的起點、目標點和障礙物的所有頂點，此處所說的障礙物指的是多邊形的障礙物，并非圓形障礙物，由銜接的線段所構成的圖形叫作可視圖。在這種情況下可視化的圖形便將性能最優路徑問題轉換為了從start到destination的間隔最短問題。它還能夠使用一些優化算法來刪除一些多余的線段，進而提高Agent在進行路徑規劃時的搜索效率。但是這種方法沒有考慮到Agent比如形狀、大小等形態特征，招致Agent在經過障礙物時摩擦甚至碰撞障礙物，而且它欠缺靈活性，只適用于低維空間。

概率路徑圖法[1]在配置空間通過隨機抽樣構造路徑圖，然后通過查找法得到Agent的路徑規劃方案。這種算法一般情況下通過3步來進行路徑規劃：（1）任務空間樣點采樣;（2）對采樣點進行碰撞檢測;（3）判斷、檢查采樣點間的連通性。概率路徑圖法具有其復雜性與規劃空間的維度和規劃空間的大小無關，而只與路徑搜索的困難有關的獨特優勢，但是傳統的概率路徑圖方法效率較低。

拓撲法的基本思維是將任務空間進行相應的分類，通常情況下將任務空間分為三部分，分別是可行走空間、障礙物空間和介于可行走空間與障礙物空間的中間空間，而后搜尋每個子空間及其連接的子空間，接下來計算它們之間的連通性。從而建立了拓撲網絡。利用拓撲法進行路徑規劃，不僅降低了三維空間路徑規劃和上層空間路徑規劃的難度，并且能夠很好地接受Agent的移動所產生的位置誤差。因為一般來說，這種方法在運動過程中并不需要Agent的確切位置，然而當任務空間中的障礙物分布情況發生變化時，拓撲網絡的重建將是一個棘手的問題。

3 ?動態路徑規劃

任務空間中障礙物信息只知道一部分或者完全都不知道，傳感器從任務空間中獲取到的障礙物信息是動態的，稱為動態路徑規劃。主要方法有：人工勢場法、模糊邏輯法、蟻群算法等。接下來對這幾個路徑規劃算法分別進行介紹。

人工勢場法[2]的基本思想是人為地將移動智能體所處的空間虛擬成一個空間場，并且把目標點對智能體產生的場力稱為引力并且引力隨著距離的減小而增大，把障礙物對智能體產生的場力稱為斥力并且智能體與障礙物的距離越大斥力越小，任務空間中的勢場是目標點對Agent的引力和障礙物對Agent的斥力的合力，Agent通過合力從起始點到達目標點。與其他算法相比，人工勢場法通俗易懂，沒有繁瑣的計算量，并且生成的路徑較為光滑，但也存在著好多缺陷：當智能體經過狹小的通道時會有擺動現象從而導致路徑規劃失敗;動態環境適應性差;當智能體、目標點和障礙物處于同一條直線上時容易出現目標不可達問題或者陷入局部極小值問題等。由于該法存在上述的種種問題，一些學者便提出了相應的解決方案，如構造一個新的勢場函數，從而減少或使其不帶局部極小值點;引入了其他的場力，以引導Agent離開局部最小點;它還可以與模擬退火算法等其他搜索算法相結合，使用它們沒有局部極值的特點。

模糊邏輯算法基于經驗，通過查找表獲取規劃信息，模糊控制邏輯算法實時性好，不存在局部極小值問題。由于目前還沒有較為系統的理論方法來設計模糊隸屬函數及控制規則，所以如何設計隸屬函數和控制規則是研究者在利用此法時需要攻克的問題。

蟻群算法的原理是螞蟻在尋找食物的時候會遺留下激素。螞蟻之間通過激素留下的特殊氣味來進行彼此間的交流，螞蟻群在某一條路徑上所遺留下的激素越多氣味越大，團體內的其他螞蟻便根據激素所散發出的氣味的強度來選擇路徑。蟻群算法是一種新型的啟發式搜索算法，利用蟻群算法來解決比較復雜的優化問題時，有它的獨到之處，具有很強的尋路能力。但是它在進行路徑規劃的時候耗時且實時性差。它是一種基于群體的并行分布式進化算法，易于和其他的啟發式算法相結合。蟻群算法沒有統一系統的分析方法，還需要堅實的數學基礎，并且需要大量的實驗和長期實驗積累的經驗來進行參數的設定，不太適合用于路徑規劃。

4 ?結語

路徑規劃算法有很多，一些研究學者對那些傳統的、經典的算法所提出的改進算法亦有很多，但是依舊有很大的改進空間，在探究路徑規劃算法的過程中，可以綜合考慮各種因素，比如能量消耗、Agent自身特性等。在實際的環境中進行路徑規劃的時候，將上述兩種類型的算法有效的結合在一起，利用各自的優點來彌補各自的缺點，同時再結合良好的建模方案，從而得到最優或次優方案。目前雖然已有相應的算法應用于實體上，但依舊不太成熟，要是真正地將路徑規劃方法應用于生活當中，大量問題尚待發現和解決。

參考文獻

[1] 陳家照，張中位，徐福后.改進的概率路徑圖法[J].計算機工程與應用，2009，45（10）：54-55，58.

[2] 安林芳，陳濤，成艾國，等.基于人工勢場算法的智能車輛路徑規劃仿真[J].汽車工程，2017，39（12）：1451-1456.