智能體路徑規(guī)劃算法研究綜述

光曉亮 楊麗圓

摘 ?要：Agent路徑規(guī)劃指的是智能體在運(yùn)動(dòng)的過程中構(gòu)成路徑的策略。從Agent的傳感器獲取到的障礙物信息為動(dòng)靜的角度來看，路徑規(guī)劃有兩種規(guī)劃方式，一是智能體處于靜態(tài)環(huán)境下的路徑規(guī)劃，二是智能體處于動(dòng)態(tài)環(huán)境下的路徑規(guī)劃。該文對(duì)近年來的路徑規(guī)劃算法進(jìn)行相比較，指出未來路徑規(guī)劃的研究方向和趨勢(shì)。

關(guān)鍵詞：智能體 ?策略 ?路徑規(guī)劃

中圖分類號(hào)：TP2 ? 文獻(xiàn)標(biāo)識(shí)碼：A ? ? ? ? ? ?文章編號(hào)：1672-3791（2019）05（a）-0023-02

路徑規(guī)劃是Agent系統(tǒng)設(shè)計(jì)中研究的中心問題。它基于一定的性能指標(biāo)，比如Agent在進(jìn)行路徑規(guī)劃時(shí)所走的長(zhǎng)度最短、利用路徑規(guī)劃算法進(jìn)行路徑搜索時(shí)所用的時(shí)間最少、路徑規(guī)劃完成之后Agent所消耗的能量最少等指標(biāo)，在其任務(wù)區(qū)中搜尋出一條或多條從起始點(diǎn)到目標(biāo)任務(wù)點(diǎn)的最優(yōu)或近似最優(yōu)路徑。路徑規(guī)劃應(yīng)用于各個(gè)方面，例如：國(guó)防軍事、搶險(xiǎn)救災(zāi)、物流管理、道路交通、路由問題等。

1 ?路徑規(guī)劃研究現(xiàn)狀

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

2 ?靜態(tài)路徑規(guī)劃

Agent的傳感器獲取到的障礙物的信息是靜態(tài)的，并且所處任務(wù)空間的信息狀況是能夠獲得的，比如說溫度的高低、形態(tài)特征等信息，這個(gè)時(shí)候叫作靜態(tài)的路徑規(guī)劃。主要方法有：柵格法、可視圖法、概率路徑圖法、拓?fù)浞ǖ?。下面?duì)這幾種典型算法進(jìn)行了相應(yīng)的研究并分析其優(yōu)缺點(diǎn)。

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

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

概率路徑圖法[1]在配置空間通過隨機(jī)抽樣構(gòu)造路徑圖，然后通過查找法得到Agent的路徑規(guī)劃方案。這種算法一般情況下通過3步來進(jìn)行路徑規(guī)劃：（1）任務(wù)空間樣點(diǎn)采樣;（2）對(duì)采樣點(diǎn)進(jìn)行碰撞檢測(cè);（3）判斷、檢查采樣點(diǎn)間的連通性。概率路徑圖法具有其復(fù)雜性與規(guī)劃空間的維度和規(guī)劃空間的大小無關(guān)，而只與路徑搜索的困難有關(guān)的獨(dú)特優(yōu)勢(shì)，但是傳統(tǒng)的概率路徑圖方法效率較低。

拓?fù)浞ǖ幕舅季S是將任務(wù)空間進(jìn)行相應(yīng)的分類，通常情況下將任務(wù)空間分為三部分，分別是可行走空間、障礙物空間和介于可行走空間與障礙物空間的中間空間，而后搜尋每個(gè)子空間及其連接的子空間，接下來計(jì)算它們之間的連通性。從而建立了拓?fù)渚W(wǎng)絡(luò)。利用拓?fù)浞ㄟM(jìn)行路徑規(guī)劃，不僅降低了三維空間路徑規(guī)劃和上層空間路徑規(guī)劃的難度，并且能夠很好地接受Agent的移動(dòng)所產(chǎn)生的位置誤差。因?yàn)橐话銇碚f，這種方法在運(yùn)動(dòng)過程中并不需要Agent的確切位置，然而當(dāng)任務(wù)空間中的障礙物分布情況發(fā)生變化時(shí)，拓?fù)渚W(wǎng)絡(luò)的重建將是一個(gè)棘手的問題。

3 ?動(dòng)態(tài)路徑規(guī)劃

任務(wù)空間中障礙物信息只知道一部分或者完全都不知道，傳感器從任務(wù)空間中獲取到的障礙物信息是動(dòng)態(tài)的，稱為動(dòng)態(tài)路徑規(guī)劃。主要方法有：人工勢(shì)場(chǎng)法、模糊邏輯法、蟻群算法等。接下來對(duì)這幾個(gè)路徑規(guī)劃算法分別進(jìn)行介紹。

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

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

蟻群算法的原理是螞蟻在尋找食物的時(shí)候會(huì)遺留下激素。螞蟻之間通過激素留下的特殊氣味來進(jìn)行彼此間的交流，螞蟻群在某一條路徑上所遺留下的激素越多氣味越大，團(tuán)體內(nèi)的其他螞蟻便根據(jù)激素所散發(fā)出的氣味的強(qiáng)度來選擇路徑。蟻群算法是一種新型的啟發(fā)式搜索算法，利用蟻群算法來解決比較復(fù)雜的優(yōu)化問題時(shí)，有它的獨(dú)到之處，具有很強(qiáng)的尋路能力。但是它在進(jìn)行路徑規(guī)劃的時(shí)候耗時(shí)且實(shí)時(shí)性差。它是一種基于群體的并行分布式進(jìn)化算法，易于和其他的啟發(fā)式算法相結(jié)合。蟻群算法沒有統(tǒng)一系統(tǒng)的分析方法，還需要堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，并且需要大量的實(shí)驗(yàn)和長(zhǎng)期實(shí)驗(yàn)積累的經(jīng)驗(yàn)來進(jìn)行參數(shù)的設(shè)定，不太適合用于路徑規(guī)劃。

4 ?結(jié)語

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

參考文獻(xiàn)

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

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