馬帥 王子銘

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

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

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

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

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

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

1.1 環(huán)境建模

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

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

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