利用位能場模型實作三維多節物體之路徑規劃

Abstract

路徑規劃問題，是在工作空間中為物體找一條無碰撞（collision-free）的路徑。這類型的三維空間的路徑規劃已經被證明為PSPACE-hard的問題，且任何一個路徑規劃的完全演算法（complete algorithm）所需的時間複雜度，會隨著物體的自由度（degree of freedom,或簡稱為 DOF）的增加而快速的成長。本論文提出一個以三維空間位能場模型為基礎的路徑規劃演算法，位能場模型適用於封閉狹窄空間中的局部避碰路徑規劃，不同於一般狀態空間( Configuration Space)的演算法，位能場模型可以直接在工作空間( Work Space )尋找路徑。相較於組態空間的方法，位能場模型的方法不需要花費大量資源建構組態空間，搜尋的效率也比較好。由實驗證明，在連結物體的自由度很高的情況下，我們的演算法也能在短時間內將路徑計算出來。