馬帥 王子銘

摘 要：移動機(jī)器人技術(shù)是近年來發(fā)展起來的一門重要學(xué)科，而路徑規(guī)劃是機(jī)器人研究領(lǐng)域的一個重要分支，它融合了機(jī)電工程、傳感技術(shù)、自動控制、計算機(jī)技術(shù)及人工智能等多學(xué)科的最新研究成果，是當(dāng)前人們最為熱衷的科學(xué)技術(shù)研究方向之一。本文分析了目前廣泛應(yīng)用的移動機(jī)器人路徑規(guī)劃研究方法，詳細(xì)介紹了環(huán)境建模方法和路徑搜索算法，最后展望了移動機(jī)器人路徑規(guī)劃技術(shù)的發(fā)展趨勢。

關(guān)鍵詞：移動機(jī)器人;環(huán)境建模;路徑規(guī)劃

中圖分類號：TP24文獻(xiàn)標(biāo)識碼：A文章編號：1003-5168（2020）29-0014-03

Abstract： Mobile robot technology is an important subject developed in recent years， and path planning is an important branch in the field of robotics， which integrates the latest research results of multiple disciplines such as electromechanical engineering， sensor technology， automatic control， computer technology and artificial intelligence， and is one of the most popular scientific and technological research directions. This paper analyzed the currently widely used mobile robot path planning research methods， introduced the environment modeling method and path search algorithm in detail， and finally looked forward to the development trend of mobile robot path planning technology.

Keywords： mobile robot;environment modeling;path planning

路徑規(guī)劃技術(shù)在移動機(jī)器人技術(shù)研究領(lǐng)域中處于非常關(guān)鍵的地位，其目的是在移動機(jī)器人執(zhí)行任務(wù)的周圍環(huán)境有障礙物的情況下，依據(jù)某一種評價方法（所用經(jīng)濟(jì)代價最小或任務(wù)路徑最短等），尋找出一條由初始狀態(tài)（包含運動姿態(tài)和位置）到達(dá)目標(biāo)狀態(tài)的最優(yōu)的無障礙路徑。移動機(jī)器人的關(guān)鍵功能之一就是路徑規(guī)劃，是其實施避障任務(wù)和自主導(dǎo)航的基礎(chǔ)，根據(jù)對環(huán)境信息的理解層次的不同，按其規(guī)劃范圍，可分為全局路徑規(guī)劃和局部路徑規(guī)劃[1]。全局路徑規(guī)劃又稱離線規(guī)劃，主要依據(jù)當(dāng)前全局環(huán)境中掌握的所有信息，在全局地圖上尋找全局最優(yōu)路徑或者是次優(yōu)路徑，它的作用是導(dǎo)引移動機(jī)器人向目標(biāo)位置移動;局部路徑規(guī)劃是指在機(jī)器人運動過程中，利用自身裝載的多種傳感器來獲取機(jī)器人周圍的環(huán)境信息，并規(guī)劃一條有效路徑，通常具有較高的靈活性和實時性。

1 路徑規(guī)劃主要研究思路

路徑規(guī)劃是智能化和信息化技術(shù)在移動機(jī)器人應(yīng)用研究中的重要表現(xiàn)，在操作者發(fā)出指令后，它可以自主添加執(zhí)行任務(wù)細(xì)節(jié)，是完成其他高級任務(wù)的基礎(chǔ)。移動機(jī)器人路徑規(guī)劃研究方向較多，人們可以從不同的切入點著手對其展開研究。但是，無論從哪一個側(cè)重點進(jìn)行分析研究，移動機(jī)器人路徑規(guī)劃研究方法一般可以歸納為參數(shù)輸入、環(huán)境建模、利用合適算法規(guī)劃路徑、仿真輸出結(jié)果等幾個過程，其技術(shù)路線如圖1所示。

移動機(jī)器人在路徑規(guī)劃的實際應(yīng)用中需要解決兩個主要問題：一是環(huán)境建模;二是路徑搜索生成及處理策略[2]。本文先討論環(huán)境建模方法，然后介紹路徑規(guī)劃算法，為學(xué)習(xí)人員提供一條思路。

1.1 環(huán)境建模

在執(zhí)行路徑規(guī)劃任務(wù)時，移動機(jī)器人首先要獲取即將行駛區(qū)域的環(huán)境地圖。移動機(jī)器人主要依靠機(jī)身上配置的雙目立體視覺、CCD工業(yè)攝像機(jī)、傳感器等通過算法獲得自身所處的位置，并在此基礎(chǔ)上獲取以上傳感器所能夠觀測的一定范圍內(nèi)的地圖信息。環(huán)境地圖的主要創(chuàng)建方法是把移動機(jī)器人所在的相關(guān)環(huán)境信息分解為若干個形態(tài)各異的網(wǎng)格空間，利用多傳感器獲取的障礙物信息進(jìn)行相關(guān)處理，最后依據(jù)某種設(shè)定規(guī)則來處理包含障礙物的網(wǎng)格信息。此時，環(huán)境地圖信息已比較詳盡，移動機(jī)器人可以利用處理好的環(huán)境信息進(jìn)行路徑規(guī)劃。當(dāng)前，環(huán)境地圖的創(chuàng)建方法多種多樣，拓?fù)涞貓D、特征地圖、柵格地圖等是比較常見的地圖創(chuàng)建方法，每種方法各有優(yōu)劣勢，適用于不同的應(yīng)用場景。

1.1.1 拓?fù)涞貓D。拓?fù)涞貓D是一種通過化簡和再調(diào)整，最終保留關(guān)鍵信息的地圖，兩點之間的距離及相對位置也不完全一定和實際的位置及距離對應(yīng)。拓?fù)涞貓D一般適合于規(guī)模較大的環(huán)境，多用圖來進(jìn)行表征。拓?fù)涞貓D占用的存儲空間小，在應(yīng)用于移動機(jī)器人路徑規(guī)劃時，既簡便又高效。不過，拓?fù)涞貓D不能提供準(zhǔn)確的尺度信息，所以其實并不適用于移動機(jī)器人的定位。

1.1.2 特征地圖。特征地圖是通過傳感器采集周圍環(huán)境的特征信息后，對其展開特征信息提取和共性信息挑選，得到簡單幾何特征而創(chuàng)建的地圖。這種表示方法定位準(zhǔn)確，實現(xiàn)起來較為簡單，便于對障礙物信息進(jìn)行特征識別和估計，其模型比較適合于計算機(jī)表示，參數(shù)化特征也和路徑規(guī)劃問題相匹配，但是該方法存在特征提取等預(yù)處理步驟，容易受到傳感器的噪聲干擾，因此不能推廣應(yīng)用在室外較為復(fù)雜的環(huán)境地圖構(gòu)建中。

1.1.3 柵格地圖。柵格地圖是在真實環(huán)境中通過數(shù)字化手段創(chuàng)建的地圖。它將環(huán)境分解成一個個離散的柵格，每個柵格和現(xiàn)實環(huán)境中的一個小區(qū)域?qū)?yīng)，表示環(huán)境區(qū)域是否存在障礙物。每個柵格都標(biāo)有一個編號值，據(jù)此來分辨柵格所表征的環(huán)境區(qū)域的相對位置。環(huán)境信息可以被柵格地圖詳細(xì)描述，這種方法方便創(chuàng)建與維護(hù)。

1.2 常用路徑規(guī)劃算法

路徑規(guī)劃的核心是路徑規(guī)劃算法[3]，路徑規(guī)劃發(fā)展到今天，算法有很多種，比較常見的算法有以下幾種：迪杰斯特拉算法、A*算法、D*算法、人工勢場法、遺傳算法（GA）等。

1.2.1 迪杰斯特拉算法。迪杰斯特拉算法又被稱為Dijkstra算法，是由計算機(jī)專家E W Dijkstra提出的。它適用于有向圖中，能夠從一個頂點搜索到另一個頂點的最優(yōu)路徑。Dijkstra算法的特點是：選取一個節(jié)點作為移動機(jī)器人的起點，并由此起始點逐步對外擴(kuò)展，直至抵達(dá)路徑目標(biāo)點所在的節(jié)點為止。Dijkstra算法作為一種最優(yōu)化算法，它對于各個方向的搜索的可能性都是相等的，最終目的是尋找一個從初始狀態(tài)到目標(biāo)狀態(tài)的最短路徑，所以要遍歷的節(jié)點很多，因此效率偏低。

1.2.2 A*算法。A*算法是一種啟發(fā)式搜索算法（Heuristic Search Algorithm）[4]，它融合了廣度優(yōu)先搜索算法和迪杰斯特拉算法的優(yōu)點，既獲取最優(yōu)的路徑規(guī)劃，又確保了搜索效率。因此，這種方法簡潔快速，而且啟發(fā)式搜索非常具有針對性，只要求獲取搜索事件的部分狀態(tài)空間信息，就能達(dá)到縮小搜索區(qū)域、減小搜索問題復(fù)雜度的目的，所有具有較高的路徑尋找效率。但是，如果A*算法存在多個最小值，其不能保證搜索路徑的最優(yōu)化。

1.2.3 D*算法。D*算法是由Stentz提出的動態(tài)規(guī)劃算法[5]，主要應(yīng)用于面對周圍未知環(huán)境或者存在動態(tài)變化的周圍環(huán)境的場景，移動機(jī)器人在向目標(biāo)位置搜索過程中只計算最短路徑臨近節(jié)點的更新情況。因此，該算法具有比較高的動態(tài)搜索效率，且可以處理任何成本參數(shù)發(fā)生變化的路徑成本優(yōu)化問題。D*算法是動態(tài)情景下的A*算法，但是對于遠(yuǎn)距離的最短路徑上發(fā)生的變化，其計算工作量很大。

1.2.4 人工勢場法。人工勢場法是由Khatib提出的一種虛擬力場法。其基本原理可以這樣描述：首先將移動機(jī)器人假設(shè)成一個點，在一種虛擬的受力場環(huán)境中運動。虛擬力場由引力場和斥力場組成，目標(biāo)位置對移動機(jī)器人產(chǎn)生引力場，這種力隨著移動機(jī)器人與目標(biāo)位置的距離增大而減?。ǚ幢汝P(guān)系）;斥力場由測量環(huán)境中存在的所有障礙物產(chǎn)生的合力組成，這種力隨移動機(jī)器人與障礙物距離的減小而增大（反比關(guān)系）。人工勢場法的勢場函數(shù)顯示，移動機(jī)器人的運動方向取決于引力與斥力之間的矢量合，即勢場函數(shù)下降的方向。這種方法在數(shù)學(xué)描述上結(jié)構(gòu)簡單，對底層的實時控制比較適用，缺點是容易陷入一些局部最優(yōu)解的問題。

1.2.5 遺傳算法。遺傳算法（Genetic Algorithm，GA）是由Holland提出來的。20世紀(jì)60年代末，Holland受達(dá)爾文的自然選擇和遺傳機(jī)制等生物進(jìn)化理論啟發(fā)，研究并發(fā)展了一種隨機(jī)搜索算法，其核心是尋找事件的最優(yōu)解。其基本方法是：利用三個基本算子，即選擇、交叉和變異設(shè)置機(jī)構(gòu)的算法程序，對生物進(jìn)化方向和過程進(jìn)行數(shù)學(xué)方式的描述。該算法不尋求適應(yīng)度函數(shù)是否存在可導(dǎo)或連續(xù)，而只限制其函數(shù)為正。同時，該算法作為并行算法，它的并行計算性能夠完全適用于全局搜索。

2 路徑規(guī)劃技術(shù)的發(fā)展趨勢

隨著科學(xué)技術(shù)的飛速發(fā)展，移動機(jī)器人的應(yīng)用范圍越來越廣泛，任務(wù)越來越復(fù)雜，各行業(yè)對移動機(jī)器人路徑規(guī)劃的能力需求隨之提高，移動機(jī)器人的路徑規(guī)劃應(yīng)用和研究呈現(xiàn)出一系列新的變化。

2.1 多源傳感信息融合技術(shù)

目前，移動機(jī)器人應(yīng)用趨于多元化，單一類型的傳感器已經(jīng)很難滿足對環(huán)境信息的認(rèn)識和理解。隨著各個應(yīng)用場景任務(wù)需求的增多，移動機(jī)器人捕獲環(huán)境信息的感知能力和系統(tǒng)處理能力的要求不斷提高。眾所周知，相比傳統(tǒng)的單一傳感器，多源傳感信息融合技術(shù)的測量精度更準(zhǔn)確，能夠更加全面地評估和描述被測對象與環(huán)境信息，從而使移動機(jī)器人做出正確的決策及判斷。

2.2 多機(jī)器人協(xié)作控制

隨著移動機(jī)器人的應(yīng)用場景越來越多，單一機(jī)器人難以完成一些復(fù)雜的作業(yè)，因此采用多機(jī)器人相互協(xié)作共同完成指定任務(wù)是未來研究的一個方向。伴隨科學(xué)技術(shù)的發(fā)展，工業(yè)、農(nóng)業(yè)、醫(yī)療衛(wèi)生、國防科技等行業(yè)對多機(jī)器人系統(tǒng)的需求越來越高，這種應(yīng)用和研究仍然會繼續(xù)發(fā)展。

2.3 多算法融合路徑規(guī)劃

目前，路徑規(guī)劃算法有人工勢場法、A*算法、D*算法等，任何一個單獨的算法都不足以解決實際應(yīng)用中遇到的所有路徑規(guī)劃問題。新型交叉學(xué)科中容易出現(xiàn)新問題，創(chuàng)造新算法的難度大，而路徑規(guī)劃算法之間的優(yōu)勢互補可以有效提供一種解決問題的新思路[6]。人們可以將多種路徑規(guī)劃算法融合，以實現(xiàn)理想狀態(tài)的路徑規(guī)劃。

3 結(jié)語

路徑規(guī)劃作為移動機(jī)器人導(dǎo)航技術(shù)的重要組成部分，是完成上層任務(wù)的先決條件，同時也是機(jī)器人具備智能化的重要標(biāo)志。本文分析了移動機(jī)器人路徑規(guī)劃方法，詳細(xì)介紹了環(huán)境建模方法和路徑規(guī)劃算法，展望了移動機(jī)器人路徑規(guī)劃技術(shù)的未來發(fā)展趨勢，以期提高移動機(jī)器人路徑規(guī)劃水平。

參考文獻(xiàn)：

[1]蒲興成，李俊杰.基于改進(jìn)粒子群算法的移動機(jī)器人多目標(biāo)點路徑規(guī)劃[J].智能系統(tǒng)學(xué)報，2017（3）：301-309.

[2]郭江，肖宇峰.Bezier曲線與A*算法融合的移動機(jī)器人路徑規(guī)劃[J].微型機(jī)與應(yīng)用，2017（2）：52-59.

[3]趙曉，王錚，基于改進(jìn)A*算法的移動機(jī)器人路徑規(guī)劃[J].機(jī)器人，2018（6）：903-910.

[4]陳若男，文聰聰.改進(jìn)A*算法在機(jī)器人室內(nèi)路徑規(guī)劃中的應(yīng)用[J].計算機(jī)應(yīng)用，2019（4）：1006-1011.

[5]劉軍，馮碩.移動機(jī)器人路徑規(guī)劃有向D*算法[J].浙江大學(xué)學(xué)報（工學(xué)版），2020（2）：291-300.

[6]霍鳳財，遲金.移動機(jī)器人路徑規(guī)劃算法綜述[J].吉林大學(xué)學(xué)報（信息科學(xué)版），2018（6）：639-646.