01

　　引言

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

　　圖 1.1 運動規(guī)劃示意圖(圖片來源：http://wiki.ros.org/navigaTIon)

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

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

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

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

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

　　在分析之前需要先補充點概念：運動規(guī)劃、軌跡規(guī)劃和路徑規(guī)劃之間是什么關系?

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

　　式中，(xk, yk)表示地圖坐標系下的路徑點位置。

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

　　式中，(xt, yt)表示地圖坐標系下的t時刻路徑點位置，而(vt, wt)表示t時刻機器人的運動速度。

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

　　<回歸正題>

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

　　圖 2.1 運動規(guī)劃通用模型

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

　　運動規(guī)劃研究歷史長久、算法相當多，除了上述提到的約束多外，當前運動規(guī)劃的研究難點是什么呢?

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

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

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

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

　　諸多學者針對不同應用場景和需求，設計、改進了非常多的運動規(guī)劃算法，筆者將常見的運動規(guī)劃算法主要分為四類：圖規(guī)劃算法、空間采樣算法、曲線插值擬合算法和仿生智能算法。

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

　　2.1   圖規(guī)劃算法

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

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

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

　　(請橫屏看圖)

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

　　2.2   空間采樣算法

　　空間采樣算法按照采樣空間不同，可分為：狀態(tài)空間采樣和運動空間采樣。

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

　　基于運動空間采樣的算法則在速度空間等距采樣，通過評價函數(shù)選擇最佳控制指令，驅(qū)動機器人運動，主要包括CVM類算法及DWA類算法等。

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

　　(請橫屏看圖)

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

　　2.3   曲線插值擬合算法

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

　　圖 2.4 CHOMP規(guī)劃算法

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

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

　　2.4   仿生智能算法

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

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

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

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

　　03

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

　　在表 3-1中，筆者總結(jié)對比了不同類型算法的主要優(yōu)缺點，其應用場景也存在差異。

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

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

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

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

　　表 3 -1 運動規(guī)劃算法優(yōu)缺點對比(點擊或原文查看大圖)

　　備注：相關參考文獻可對照《類車機器人集成感知與規(guī)劃系統(tǒng)設計研究》

　　04

　　結(jié)論與展望

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

　　運動規(guī)劃算法種類繁多，應用場景各不相同，而本文僅從移動機器人視角對部分運動規(guī)劃算法進行了分析概述，只能算是窺探運動規(guī)劃這一領域的冰山一角。

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