Non-Euclidean Motion Planning with Graphs of Geodesically-Convex Sets

作者: Thomas Cohn, Mark Petersen, Max Simchowitz, Russ Tedrake · RSS 2023

授權條款

• 開放取用
• 論文: CC BY 4.0

以下內容皆依據論文全文，依其 CC BY 4.0 授權條款使用；圖表已標示作者。

一句話摘要

把會環繞的關節空間（移動底座、連續關節）視為平坦流形，讓 GCS 最短路徑規劃器仍能給出全域最佳且無碰撞的路徑。

為何重要

移動機械手臂以及底座關節沒有角度限制的手臂，如今可以使用一種規劃器：它能證明軌跡上的每一點都不會碰撞，而且在精確求解時，於經認證的自由空間內為最佳。論文也證明正曲率（例如 SO(3) 球形關節或自由漂浮的物體）會破壞凸性，這劃出了此方法無法涵蓋的範圍。

問題

Marcucci 等人的 GCS 規劃器將自由組態空間分解為凸集合，藉此找出無碰撞、全域最佳的路徑，但僅適用於歐氏組態空間。能完整轉動 360° 的移動底座或連續旋轉關節會環繞回來，因此其組態空間並非歐氏空間。加入人為的關節限制，或把角度當成無界實數，不是讓最佳解變得不可行，就是需要事先知道答案並複製許多集合。

提出的方法

作者將組態空間建模為黎曼流形，並定義測地凸集合圖（Graph of Geodesically-Convex Sets，GGCS），證明它保有一般 GCS 的各項保證。對於平坦（零曲率）流形，涵蓋任何由 1-DoF 關節加上 SE(2) 底座構成的機器人，每個集合都透過一個局部等距座標圖映射到歐氏空間，問題便化約為具有仿射轉移約束的標準混合整數凸 GCS 問題。區域以 IRIS 擴展，並依各關節以凸性半徑加以限制；具連續性約束的分段 Bézier 軌跡也能沿用。

關鍵見解

• SE(2)、所有 1 維流形，以及平坦流形的乘積都是平坦的，因此由單自由度關節與移動底座組成的機器人適用此方法；3-DoF 球形關節則不適用
• 依各關節以凸性半徑限制每個 IRIS 區域，可保證該區域映射回流形時仍維持測地凸
• 在具有全域對齊座標的平坦空間上，轉移映射是仿射的，因此端點匹配與導數連續的約束仍維持凸性
• 即使只有一個正曲率點，也會讓黎曼距離函數在該點的每個鄰域內都是非凸的（定理 5）

主要結果

• 環面上的點機器人：0.79 s 求得最佳的環繞路徑；具連續關節的 5 關節平面手臂：規劃耗時 5.36 s 與 4.63 s，其中一條讓中間關節轉動超過 360°
• 平面手臂：鬆弛後取整的路徑長度為 7.749 與 8.448，分支定界的最佳值則為 7.274 與 8.008
• 具連續底座關節的 KUKA iiwa（模擬）：使用 18 個凸區域完成 14 個馬克杯分類動作，每個動作平均 25.75 s（範圍 4.63–50.30 s）
• PR2（模擬，15 維組態空間），7 個貨架取物任務：GGCS 路徑在每種情況下都無碰撞，例如 1M→4M 長度為 3.875，PRM 則為 14.554；Drake-Trajopt 與 PRM+Trajopt 有時給出較短的路徑，但那些路徑有輕微碰撞
• PR2 線上規劃方面，GGCS-Planner 耗時 25.51–66.15 s，PRM 為 0.49–0.54 s，Drake-Trajopt 為 2.26–15.23 s，PRM+Trajopt 為 11.61–40.10 s
• PR2 離線準備：一個 IRIS 區域平均耗時 30.20 s（8.56–75.42 s），所有區域平行計算共 156.63 s；建立 100,000 個樣本的 PRM 耗時 124.39 s

限制

• 作者表示此方法無法處理非凸的成本與約束，例如非線性動力學與封閉運動鏈，也無法處理球形關節
• SO(3) 等正曲率空間被排除在外，因為可以證明距離函數在其上是非凸的
• 最佳性只在區域所涵蓋的「經認證」自由空間內成立；效能在很大程度上取決於區域的選擇，而 PR2 的部分中間區域是手動加入的
• PR2 的線上規劃時間（25.51–66.15 s）高於所有比較的基準方法
• 所有機器人結果均來自模擬；作者將具隱式運動學約束的雙臂規劃，以及穿越接觸的規劃列為未來工作

對領域的影響

入圍 RSS 2023 最佳論文獎決選，被引用 44 次。作者在一個成果網站上公開了每條軌跡的互動式紀錄。

摘要

為高維度系統計算最佳且無碰撞的軌跡是一個具挑戰性的問題。以取樣為基礎的規劃器難以應付高維度，而軌跡最佳化器則可能因最佳化地形中固有的非凸性而陷入局部極小值。以混合整數規劃涵蓋這些非凸性並求得全域最佳軌跡的做法，近來展現出極大的潛力，部分原因在於緊緻的凸鬆弛，以及能大幅縮短執行時間的高效率近似策略。這些方法以往僅限於歐氏組態空間，因而無法用於移動底座或連續旋轉關節。本文將組態空間建模為黎曼流形來處理這類情境，並針對零曲率的情況，描述一套將問題化約為混合整數凸最佳化問題的程序。我們在多種機器人平台上展示成果，包括為 PR2 雙臂移動機械手臂產生高效率的無碰撞軌跡。

連結

• arXiv 2305.06341: https://arxiv.org/abs/2305.06341
• DOI 10.1177/02783649241302419: https://doi.org/10.1177/02783649241302419
• PDF: https://arxiv.org/pdf/2305.06341v1
• 專案頁面: https://ggcs-anonymous-submission.github.io/