摘要：運(yùn)動(dòng)規(guī)劃是移動(dòng)機(jī)器人自主導(dǎo)航系統(tǒng)中的重要模塊之一，相關(guān)算法研究成果層出不同窮，本文根據(jù)規(guī)劃算法特性，劃分為圖規(guī)劃算法、空間采樣算法、曲線插值擬合算法和仿生智能算法四個(gè)子類(lèi)，并從移動(dòng)機(jī)器人運(yùn)動(dòng)的角度對(duì)部分經(jīng)典研究成果進(jìn)行分析和總結(jié)。

01

引言

移動(dòng)機(jī)器人運(yùn)動(dòng)行為是由自主導(dǎo)航系統(tǒng)決定的，自主導(dǎo)航系統(tǒng)主要包含感知、規(guī)劃、控制與定位四個(gè)模塊，感知模塊是連接機(jī)器人與環(huán)境的橋梁，其作用是“閱讀、提取”環(huán)境內(nèi)容；規(guī)劃模塊是連接感知與控制的橋梁，其作用是“分析、理解”環(huán)境內(nèi)容，根據(jù)用戶目標(biāo)及需求輸出可執(zhí)行控制命令，因此感知、規(guī)劃模塊是決定導(dǎo)航系統(tǒng)智能程度的關(guān)鍵。

圖 1.1 運(yùn)動(dòng)規(guī)劃示意圖（圖片來(lái)源：http://wiki.ros.org/navigation）

運(yùn)動(dòng)規(guī)劃一直是機(jī)器人領(lǐng)域非常經(jīng)典的研究熱點(diǎn)之一，諸多學(xué)者和研究機(jī)構(gòu)針對(duì)運(yùn)動(dòng)規(guī)劃中的科學(xué)問(wèn)題進(jìn)行了深入研究。運(yùn)動(dòng)規(guī)劃算法針對(duì)不同的應(yīng)用場(chǎng)景有著不同的研究側(cè)重點(diǎn)，比如游戲領(lǐng)域，游戲任務(wù)從A點(diǎn)運(yùn)動(dòng)到B點(diǎn)的運(yùn)動(dòng)規(guī)劃需求是計(jì)算消耗內(nèi)存小、計(jì)算實(shí)時(shí)性好，路徑質(zhì)量要求可能需要太高；而在全局規(guī)劃領(lǐng)域，如百度地圖等應(yīng)用，則側(cè)重研究如何快速找到一條從起點(diǎn)到終點(diǎn)的可行的路徑，并不會(huì)關(guān)注整條路徑的細(xì)節(jié)問(wèn)題；而在機(jī)器人運(yùn)動(dòng)過(guò)程中，就需要側(cè)重關(guān)注軌跡曲線的質(zhì)量。?

細(xì)心讀者可能發(fā)現(xiàn)了，這里的規(guī)劃都是依賴于地圖的，路徑是依托于地圖的，不同的地圖使用的規(guī)劃算法是有區(qū)別的，這可以在《機(jī)器人環(huán)境感知研究現(xiàn)狀簡(jiǎn)述》中獲知不同類(lèi)型的地圖及其對(duì)應(yīng)的特點(diǎn)、適用場(chǎng)景。?

此外，路徑規(guī)劃中也包含路徑搜索這塊方向，路徑搜索不僅僅是用于搜索路徑，還可以用于搜索目標(biāo)，比如藥物結(jié)構(gòu)的搜索，采用智能算法，給定初始條件和篩選條件，讓算法在指定區(qū)域搜索藥物分子結(jié)構(gòu)。?

為提升機(jī)器人在不同場(chǎng)景下的自主運(yùn)動(dòng)能力，適用于不同環(huán)境的運(yùn)動(dòng)規(guī)劃算法層出不窮，本文將根據(jù)算法原理分類(lèi)、研究時(shí)間排序，整理概述該研究領(lǐng)域的進(jìn)展及成果。

02規(guī)劃算法研究分析

在分析之前需要先補(bǔ)充點(diǎn)概念：運(yùn)動(dòng)規(guī)劃、軌跡規(guī)劃和路徑規(guī)劃之間是什么關(guān)系？?

路徑規(guī)劃指的是在地圖上生成一條連接起點(diǎn)和終點(diǎn)的路徑曲線，該路徑曲線不會(huì)與地圖中的障礙物相交，且均在可行區(qū)域，路徑曲線Path可以用離散的點(diǎn)序列表示：

式中，(xk,?yk)表示地圖坐標(biāo)系下的路徑點(diǎn)位置。?

軌跡規(guī)劃顧名思義就是在地圖上生成一條連接起點(diǎn)和終點(diǎn)的軌跡曲線，而軌跡曲線是路徑曲線和速度曲線相耦合的復(fù)合曲線，換句話說(shuō)，就是軌跡曲線Traj包含了位置、速度和時(shí)間等信息，離散化后可表示為：

式中，(xt, yt)表示地圖坐標(biāo)系下的t時(shí)刻路徑點(diǎn)位置，而(vt, wt)表示t時(shí)刻機(jī)器人的運(yùn)動(dòng)速度。?

運(yùn)動(dòng)規(guī)劃狹義上和軌跡規(guī)劃的概念非常接近，區(qū)別在于不同的機(jī)器人的運(yùn)動(dòng)學(xué)/動(dòng)力學(xué)模型是不一樣的，比如多軸機(jī)械臂、移動(dòng)機(jī)器人等，運(yùn)動(dòng)規(guī)劃需要做的事情是需要先規(guī)劃出上述軌跡曲線，接著結(jié)合動(dòng)力學(xué)模型，將軌跡曲線轉(zhuǎn)化為每個(gè)電機(jī)的運(yùn)動(dòng)控制曲線，控制電機(jī)沿著該控制曲線運(yùn)動(dòng)，以實(shí)現(xiàn)機(jī)器人沿著規(guī)劃的目標(biāo)軌跡曲線運(yùn)動(dòng)。?

<回歸正題>

如圖 2.1所示，運(yùn)動(dòng)規(guī)劃的研究主要是對(duì)多目標(biāo)多變量多約束耦合的規(guī)劃模型優(yōu)化求解，目標(biāo)需求非常多，包括模型硬約束，如軌跡曲線需要滿足機(jī)器人運(yùn)動(dòng)學(xué)和動(dòng)力學(xué)模型約束，同時(shí)還需要滿足避障約束，也就是說(shuō)該軌跡曲線的最基礎(chǔ)要求就是機(jī)器人實(shí)際上能夠跟隨運(yùn)動(dòng)且不會(huì)發(fā)生碰撞；而規(guī)劃需求軟約束則包實(shí)時(shí)性好、動(dòng)態(tài)適應(yīng)性好、計(jì)算成本低等，這些約束根據(jù)不同的應(yīng)用場(chǎng)景是不一樣的，用戶體驗(yàn)也是存在差異的，故而稱為軟約束。?

圖 2.1 運(yùn)動(dòng)規(guī)劃通用模型

此外，對(duì)于具有非完整約束的移動(dòng)機(jī)器人而言（見(jiàn)《兩輪差速驅(qū)動(dòng)機(jī)器人運(yùn)動(dòng)模型及應(yīng)用分析》），在分布有障礙物的環(huán)境中求解最優(yōu)路徑是NP-hard問(wèn)題，即對(duì)于任意場(chǎng)景無(wú)法保證在多項(xiàng)式時(shí)間內(nèi)求得最優(yōu)解，因此大部分規(guī)劃算法追求次優(yōu)解或局部最優(yōu)。?

運(yùn)動(dòng)規(guī)劃研究歷史長(zhǎng)久、算法相當(dāng)多，除了上述提到的約束多外，當(dāng)前運(yùn)動(dòng)規(guī)劃的研究難點(diǎn)是什么呢？?

筆者認(rèn)為難點(diǎn)之一是如何處理存在耦合關(guān)系的路徑與速度曲線的優(yōu)化問(wèn)題，常用方式有三種：?

1）路徑-速度完全脫離處理：僅單純生成平滑路徑，再使用曲線跟蹤算法控制機(jī)器人運(yùn)動(dòng)，該方法動(dòng)態(tài)避障性能偏弱。?

2）路徑-速度循環(huán)迭代優(yōu)化：先生成無(wú)碰撞路徑（靜態(tài)避障），再基于該路徑生成穩(wěn)定好的無(wú)碰撞速度曲線（動(dòng)態(tài)避障），并通過(guò)循環(huán)迭代優(yōu)化算法生成最佳軌跡曲線，該方法降低優(yōu)化維度，提升了優(yōu)化效率。?

3）路徑-速度“捆綁”優(yōu)化：綜合考慮所有的約束關(guān)系及優(yōu)化目標(biāo)，生成最優(yōu)軌跡曲線，該方法生成的軌跡效果很好，但存在優(yōu)化模型構(gòu)造難度大、優(yōu)化效率不高等問(wèn)題。?

諸多學(xué)者針對(duì)不同應(yīng)用場(chǎng)景和需求，設(shè)計(jì)、改進(jìn)了非常多的運(yùn)動(dòng)規(guī)劃算法，筆者將常見(jiàn)的運(yùn)動(dòng)規(guī)劃算法主要分為四類(lèi)：圖規(guī)劃算法、空間采樣算法、曲線插值擬合算法和仿生智能算法。?

接下來(lái)，筆者將從逐一介紹這四個(gè)子類(lèi)規(guī)劃算法的概況。

2.1 ? 圖規(guī)劃算法

圖規(guī)劃算法多數(shù)將環(huán)境模型離散化表達(dá)，如柵格圖等，其離散節(jié)點(diǎn)描述相應(yīng)狀態(tài)，建立節(jié)點(diǎn)間聯(lián)系，并求解最優(yōu)路徑。?

如圖 2.2所示，圖規(guī)劃算法根據(jù)路徑生成方式的不同分為三類(lèi)，其中以圖搜索算法為主，以及BUG算法和勢(shì)場(chǎng)力算法。?

具體相關(guān)分析可閱讀《機(jī)器人圖規(guī)劃算法研究現(xiàn)狀簡(jiǎn)述》。

（請(qǐng)橫屏看圖）

圖 2.2 圖規(guī)劃算法發(fā)展路線概況

2.2 ? 空間采樣算法

空間采樣算法按照采樣空間不同，可分為：狀態(tài)空間采樣和運(yùn)動(dòng)空間采樣。?

如圖 2.3所示，基于狀態(tài)空間采樣的算法能夠在大面積、高緯度的空間中快速生成路徑，包括RRT和PRM類(lèi)算法等，具有概率完備性，其主要步驟包括隨機(jī)采樣、度量連接、碰撞檢測(cè)和路徑查詢。?

基于運(yùn)動(dòng)空間采樣的算法則在速度空間等距采樣，通過(guò)評(píng)價(jià)函數(shù)選擇最佳控制指令，驅(qū)動(dòng)機(jī)器人運(yùn)動(dòng)，主要包括CVM類(lèi)算法及DWA類(lèi)算法等。?

具體相關(guān)分析可閱讀《機(jī)器人空間采樣算法研究現(xiàn)狀簡(jiǎn)述》。

（請(qǐng)橫屏看圖）

圖 2.3 空間采樣算法發(fā)展路線概況

2.3 ? 曲線插值擬合算法

上述大部分《圖規(guī)劃算法》和《空間采樣算法》生成的路徑存在折點(diǎn)、急彎等曲率不連續(xù)的情況，影響了機(jī)器人運(yùn)動(dòng)平穩(wěn)性，因此需要綜合考慮模型硬約束與實(shí)際規(guī)劃軟需求，以提升路徑平滑度。

圖 2.4 CHOMP規(guī)劃算法

如圖 2.4所示，曲線插值擬合算法在曲線平滑控制及優(yōu)化方面有顯著的優(yōu)勢(shì)，按照曲線生成方式及其種類(lèi)可分為：基于插值的規(guī)劃算法、基于特殊曲線的規(guī)劃算法及基于優(yōu)化的規(guī)劃算法三類(lèi)，該類(lèi)算法在自動(dòng)駕駛等領(lǐng)域有著廣泛的應(yīng)用。?

具體相關(guān)分析可閱讀《機(jī)器人曲線插值擬合算法研究現(xiàn)狀簡(jiǎn)述》。

2.4 ? 仿生智能算法

針對(duì)機(jī)器人運(yùn)動(dòng)規(guī)劃問(wèn)題，除上述基于經(jīng)典模型的規(guī)劃算法外（《圖規(guī)劃算法》、《空間采樣算法》和《曲線插值擬合算法》），還有神經(jīng)網(wǎng)絡(luò)、模糊邏輯及基于自然靈感的算法（遺傳算法、粒子群算法、蟻群算法等），并逐漸成為研究熱點(diǎn)。?

如圖 2.5所示，與經(jīng)典算法相比，智能算法能夠較好適應(yīng)復(fù)雜動(dòng)態(tài)環(huán)境中的不確定、不完整的信息，但需要前期學(xué)習(xí)階段和較高計(jì)算成本，適用于大型機(jī)器人，如無(wú)人車(chē)等。?

具體相關(guān)分析可閱讀《機(jī)器人智能仿生路徑規(guī)劃算法研究現(xiàn)狀簡(jiǎn)述》。

圖 2.5 路徑規(guī)劃模糊系統(tǒng)架構(gòu)

03

規(guī)劃算法特性討論 ? ?

在表 3-1中，筆者總結(jié)對(duì)比了不同類(lèi)型算法的主要優(yōu)缺點(diǎn)，其應(yīng)用場(chǎng)景也存在差異。?

圖規(guī)劃算法與空間采樣算法已經(jīng)能夠在諸多場(chǎng)景下的規(guī)劃生成一條無(wú)碰撞路徑，實(shí)時(shí)性和動(dòng)態(tài)適應(yīng)性逐漸提升，但多數(shù)算法仍存在路徑質(zhì)量差、未考慮動(dòng)力學(xué)約束等問(wèn)題。?

而曲線插值擬合算法正好與之配合，能夠容易生成連續(xù)性好的軌跡曲線。?

多數(shù)仿生智能算法處理動(dòng)態(tài)環(huán)境下的規(guī)劃問(wèn)題時(shí)存在實(shí)時(shí)性、收斂性均不穩(wěn)定等問(wèn)題，實(shí)際應(yīng)用較少。?

從目前研究思路來(lái)看，多是先采用圖規(guī)劃算法、空間采樣算法生成全局路徑或初始路徑，再使用曲線插值擬合算法，綜合考慮系統(tǒng)軟硬約束，優(yōu)化生成質(zhì)量好的軌跡。

表 3 -1 運(yùn)動(dòng)規(guī)劃算法優(yōu)缺點(diǎn)對(duì)比(點(diǎn)擊或原文查看大圖)

備注：相關(guān)參考文獻(xiàn)可對(duì)照《類(lèi)車(chē)機(jī)器人集成感知與規(guī)劃系統(tǒng)設(shè)計(jì)研究》

04

結(jié)論與展望

本文根據(jù)規(guī)劃算法特點(diǎn)將常見(jiàn)規(guī)劃算法劃分為四類(lèi)，并從實(shí)時(shí)性、計(jì)算成本、模型復(fù)雜度、環(huán)境適應(yīng)能力、路徑曲線質(zhì)量、軌跡長(zhǎng)度等方面綜合對(duì)比分析了上述四個(gè)子類(lèi)規(guī)劃算法。?

運(yùn)動(dòng)規(guī)劃算法種類(lèi)繁多，應(yīng)用場(chǎng)景各不相同，而本文僅從移動(dòng)機(jī)器人視角對(duì)部分運(yùn)動(dòng)規(guī)劃算法進(jìn)行了分析概述，只能算是窺探運(yùn)動(dòng)規(guī)劃這一領(lǐng)域的冰山一角。?

后續(xù)會(huì)逐漸深入討論分析一些經(jīng)典的算法。

編輯：黃飛

?