摘要：運動規劃是移動機器人自主導航系統中的重要模塊之一，相關算法研究成果層出不同窮，本文根據規劃算法特性，劃分為圖規劃算法、空間采樣算法、曲線插值擬合算法和仿生智能算法四個子類，并從移動機器人運動的角度對部分經典研究成果進行分析和總結。

01

引言

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

圖 1.1 運動規劃示意圖（圖片來源：http://wiki.ros.org/navigation）

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

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

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

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

02規劃算法研究分析

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

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

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

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

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

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

<回歸正題>

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

圖 2.1 運動規劃通用模型

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

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

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

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

2）路徑-速度循環迭代優化：先生成無碰撞路徑（靜態避障），再基于該路徑生成穩定好的無碰撞速度曲線（動態避障），并通過循環迭代優化算法生成最佳軌跡曲線，該方法降低優化維度，提升了優化效率。?

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

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

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

2.1 ? 圖規劃算法

圖規劃算法多數將環境模型離散化表達，如柵格圖等，其離散節點描述相應狀態，建立節點間聯系，并求解最優路徑。?

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

具體相關分析可閱讀《機器人圖規劃算法研究現狀簡述》。

（請橫屏看圖）

圖 2.2 圖規劃算法發展路線概況

2.2 ? 空間采樣算法

空間采樣算法按照采樣空間不同，可分為：狀態空間采樣和運動空間采樣。?

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

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

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

（請橫屏看圖）

圖 2.3 空間采樣算法發展路線概況

2.3 ? 曲線插值擬合算法

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

圖 2.4 CHOMP規劃算法

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

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

2.4 ? 仿生智能算法

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

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

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

圖 2.5 路徑規劃模糊系統架構

03

規劃算法特性討論 ? ?

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

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

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

多數仿生智能算法處理動態環境下的規劃問題時存在實時性、收斂性均不穩定等問題，實際應用較少。?

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

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

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

04

結論與展望

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

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

后續會逐漸深入討論分析一些經典的算法。

編輯：黃飛

?