機器人運動規(guī)劃方法綜述（1）

隨著應用場景的日益復雜，機器人對旨在生成無碰撞路徑（軌跡）的自主運動規(guī)劃技術的需求也變得更加迫切。雖然目前已產生了大量適應于不同場景的規(guī)劃算法，但如何妥善地對現有成果進行歸類，并分析不同方法間的優(yōu)劣異同仍是需要深入思考的問題。以此為切入點，首先，闡釋運動規(guī)劃的基本內涵及經典算法的關鍵步驟；其次，針對實時性與解路徑（軌跡）品質間的矛盾，以是否考慮微分約束為標準，有層次地總結了現有的算法加速策略；最后，面向不確定性（即傳感器不確定性、未來狀態(tài)不確定性和環(huán)境不確定性）下的規(guī)劃和智能規(guī)劃提出的新需求，對運動規(guī)劃領域的最新成果和發(fā)展方向進行了評述，以期為后續(xù)研究提供有益的參考。機器人學是研究如何通過計算機控制裝置感知并操縱客觀世界的學科，現今已被應用于各個領域，如行星探索中的移動平臺、空間機械臂、無人機、自動駕駛汽車等（圖1）。設想這樣的場景：一架無人機正在高樓聳立的城市中穿行，未知環(huán)境要求其應利用新接收到的信息不斷修正它的運動；雜亂的障礙物要求其應避免與眾多物體發(fā)生碰撞；傳感器誤差、陣風干擾、模型誤差、控制約束等則要求真實運動與規(guī)劃運動間的誤差應盡量小。因此為了能在充滿未知性和不確定性的真實世界中可靠地完成任務，機器人必須具有自主感知、快速決策、運動規(guī)劃與控制的能力。其中運動規(guī)劃作為上層決策與底層控制的連接模塊，負責將決策序列轉化為控制器可執(zhí)行的參考路徑（軌跡），在機器人研究中占有重要地位。圖1 典型的機器人系統(tǒng)運動規(guī)劃領域早期側重于處理有障礙物的二維或三維世界中的開環(huán)運動規(guī)劃問題，其結果可以是一條無碰路徑，也可以是一條無碰軌跡。前者是幾何意義上的連續(xù)（光滑）曲線，后者則是這一曲線的時間參數化表達。對機器人而言，路徑規(guī)劃（本文稱其為傳統(tǒng)運動規(guī)劃）一般在構型空間（Configuration Space，C-space）內進行，軌跡規(guī)劃（本文稱其為考慮微分約束的開環(huán)運動規(guī)劃）則在狀態(tài)空間（即構型空間或相空間）內進行。但無論構型空間亦或相空間，都是無限不可數的，故開環(huán)運動規(guī)劃的一個中心主題是將連續(xù)空間離散化，進而借助人工智能領域的離散搜索思想，將求解運動規(guī)劃問題視為在高維自由構型空間（,）或自由相空間中的搜索過程。除一般的可行性問題外，滿足某類性能指標最優(yōu)（如時間最優(yōu)、路徑長度最優(yōu)等）的開環(huán)運動規(guī)劃問題亦是學者們的關注焦點。一條最優(yōu)路徑往往可參數化為許多條軌跡，它們的速度時間歷程各不相同，而最優(yōu)軌跡僅是其中一條。不幸的是，計算最優(yōu)路徑（軌跡）的時間復雜度往往較高（甚至對某些問題來講，計算可行路徑就已十分困難），很難滿足機器人實時規(guī)劃的需求，這便促使研究人員不斷開發(fā)新的算法以實現兩者間的平衡。另外，經典控制理論的發(fā)展歷史表明：反饋是應對不確定性的有效手段。但開環(huán)運動規(guī)劃過程常常忽略了這一點，從而容易造成機器人沿規(guī)劃路徑（軌跡）運動時意外碰撞的發(fā)生（圖2）。反饋運動規(guī)劃則通過對不確定性進行建模，并將該模型融入規(guī)劃過程，為機器人的實際運動提供了安全保障。雖然近年關于反饋運動規(guī)劃的研究取得了一系列進展，但鮮有文章對這一主題進行歸納總結。即使有所提煉，包括反饋運動規(guī)劃在內的各類內容也已稍顯陳舊，而且將運動規(guī)劃的研究范圍局限于基于采樣的運動規(guī)劃（Sampling-based Motion Planning，SBMP）算法的做法無疑限制了讀者的視野。圖2 運動規(guī)劃與控制的解耦可能造成意外碰撞根據是否考慮微分約束和反饋，Lavalle的經典專著將運動規(guī)劃問題分為表1中的4 項子課題，本文則不區(qū)分最右側2項，并將其統(tǒng)稱為反饋運動規(guī)劃。進而在這種分類方式的基礎上以單機器人為研究對象，依次總結了現有的傳統(tǒng)運動規(guī)劃、考慮微分約束的開環(huán)運動規(guī)劃和反饋運動規(guī)劃相關算法，形成了類似于“譜”的運動規(guī)劃算法歸類，便于讀者對比分析各種方法間的區(qū)別與聯(lián)系。其中針對解路徑（軌跡）品質與求解效率間存在的矛盾，重點詳述了如何利用已有信息來加速漸近最（近）優(yōu)算法。另外則對不確定性建模方式、動態(tài)環(huán)境中的規(guī)劃、學習算法與運動規(guī)劃算法的融合等先進課題的最新成果進行了總結，以期為后續(xù)研究提供思路。表1 運動規(guī)劃問題分類01  傳統(tǒng)運動規(guī)劃設為映射到的拓撲圖（可參考圖3~圖6），其中為圖中節(jié)點的集合，每個節(jié)點相對應一個構型。為圖中邊的集合，每條邊相對應兩個構型 間的無碰撞路徑。對于所有，定義式中：表示路徑的像；為可以通過）到達的所有構型的集合。解決傳統(tǒng)運動規(guī)劃問題的思路正是用包含可數個節(jié)點的圖結構捕捉的連通信息，并基于此離散結構搜索解路徑。由于 的構建過程顯然受障礙物形狀及其位置分布的影響，故一般可根據是否在中顯式表示障礙物區(qū)域（），將處理傳統(tǒng)運動規(guī)劃問題的算法分為組合運動規(guī)劃（Combina?torial Motion Planning， CMP）算法和基于采樣的運動規(guī)劃算法兩類。1.1 組合運動規(guī)劃基于顯式表示的障礙物，CMP首先構造滿足下列條件：1）可達性（Accessibility）：對于任一，可以簡單高效地計算一條以其為起點，以中任一點為終點的路徑，即，。2）確保連通性（Connectivity-Preserving）：對于起始構型、目標構型及它們在中的連接點、，如果存在一條路徑，使得，，那么也將存在一條路徑，使得的路圖，其或由的胞腔剖分間接生成，如垂直胞腔剖分、圓柱代數剖分等；或通過其他方法直接構造，如可視圖法、廣義維羅尼圖法、輪廓法等。進而利用圖搜索算法如Dijkstra算法、A*算法、ARA*算法、D*Lite算法、AD*算法及Theta*算法等尋找解路徑。后四者都是A*的變體：ARA*通過放松對啟發(fā)式的一致性要求并重復使用先前的搜索信息，可快速產生因子可控的次優(yōu)路徑，具有Anytime特性，適用于計算時間受限的靜態(tài)環(huán)境；D*Lite是一種遞增搜索算法，其先用A*算法從目標頂點反向計算相關節(jié)點的最優(yōu)路徑代價，待環(huán)境發(fā)生改變后，再以此有效信息為基礎進一步調整相關節(jié)點的最優(yōu)路徑代價，適用于含動態(tài)障礙物的場景；AD*則是結合了ARA*和D*Lite的優(yōu)點，既具有Anytime特性，又有遞增特性，真正實現了動態(tài)場景中的實時規(guī)劃。另外由于A*算法找出的解路徑角度往往被網格劃分方式所限制，因而其并非真實地形中的最優(yōu)路徑，Theta*通過解除這一約束，可在相同時間復雜度下得到更高質量的解路徑。條件1）其實保證了內的任一起始、目標構型對（）均可被連接到中，條件2）則保證了在解路徑存在的情況下，搜索總是可以成功。而這正是CMP 完備性的來源，即在有限時間內，算法要么找到一條解路徑，要么正確地報告無解。雖然其幾乎能解決任何運動規(guī)劃問題，而且在一些簡單情形（如二維世界中，為多邊形，機器人僅進行平移運動）下可以高效地得到較好解，但對于大多數具有高維C-space且障礙物數量巨大的問題，較長的運行時間和執(zhí)行困難使此類方法失去了吸引力。1.2 基于采樣的運動規(guī)劃與CMP不同，SBMP通過碰撞檢測模塊來避免顯式構建，并且利用可數的采樣點集或采樣序列及滿足一定條件的連接方式近似捕捉無限不可數的Cfree的連通特性。盡管其永遠不可能知曉的精確形狀，但卻節(jié)省了大量計算時間，是一種行之有效的折中方式，可用于高維空間中的運動規(guī)劃。不過與此同時也犧牲了算法的完備性，并代之以更弱的概念：使用隨機采樣方法的運動規(guī)劃算法是概率完備（Probabilistically Complete）的，使用確定性采樣方法的運動規(guī)劃算法是分辨率完備（Resolution Complete）的。為滿足弱完備性要求：①中的采樣序列必須稠密；②算法的搜索過程應具備“系統(tǒng)性”。更多關于 SBMP產生的歷史原因和早期發(fā)展過程可參考Lindemann和Lavalle的綜述文章。對于給定數個起始-目標構型對的多疑問（Multiple-Query）運動規(guī)劃問題，如果環(huán)境結構不發(fā)生改變，則非常有必要花費時間對模型進行預計算以生成路圖，從而提高后續(xù)搜索效率。概率路圖法（Probabilistic Roadmap，PRM）是其中的典型代表，它最初是為應對高自由度運動規(guī)劃問題而發(fā)展的，算法流程如圖3所示。PRM構建的路圖可看作是對CMP所導出路圖的一種近似，因此也常被與CMP共同歸入基于圖搜索的運動規(guī)劃算法中。Kavraki等通過對簡化的PRM（Simplified PRM，s-PRM）進行分析，建立了算法失敗概率與路徑長度、路徑和障礙物間距、采樣點數量之間的函數關系，其中隨的增加而線性增加，隨的增加而指數減小到0，從而證明了PRM的概率完備性。但由于路徑特性很難提前得知，故該完備性分析方法不易使用。另一分析方法則借助ε-goodness、β-lookout和（ε，α，β）-expansive的概念，證明算法失敗概率為圖3 PRM算法流程式中：為正常量。從式（2）不僅能得出與的指數關系，而且可以發(fā)現如果暗含可視特性的越大，那么完成求解所需的采樣點就越少，算法運行時間就越短。因為引起可視特性下降的狹窄通道不可能偶然出現，故實際中遇到的許多都具有良好的可視特性，即相應的較大。另外可視特性是用體積比率定義的，而不直接依賴于C-space維數，這便解釋了為什么當維數在一定范圍內增加時，PRM仍能較好地運行。