利用位能場模型作路徑規劃及物體形狀比對

Abstract

本博士論文乃利用位能場模型來呈現自由空間的方法，探討位能場於不同問題的應用。我們提出數個以位能場模型為基礎的演算法來協助解決（1）機器人路徑規劃與（2）物體形狀比對的問題。在這些演算法中，其共同的主要概念是將物體及自由空間的邊界帶相同之電性後，靜止的自由空間會有位能場形成，且自由空間對物體產生推斥力，再將作用於物體上的推斥力作為物體移動的推力與轉動的轉矩，使物體降低在自由空間中位能與自由空間達成最佳的形狀比對，物體的形式可以是剛體或是連結物。最佳的形狀比對可藉由調整物體的位置、姿態來降低位能而達成。 在機械手臂路徑規劃研究中，我們探討了利用牛頓位能場應用於二維路徑規劃問題的可行性。在研究中，我們將機械手臂及自由空間的邊界以均勻或不均勻的帶電後，如同於電學中的定義，可計算得知機械手臂在工作空間中所受的斥力與轉矩，藉由這些斥力與轉矩來調整手臂於自由空間之組態使其位能降低。透過尋找這一連串的組態後，一條避碰的路徑即可由這些一系列組態來構成。我們也將上述演算法推廣到三維工作空間，亦即將原來牛頓位能場模型用三維廣義位能場[1] 來取代。 在 [1] 中提到，牛頓位能場模型在三維空間之中會造成物體撞入障礙物中，並不能達到避碰的要求。因而，我們採用廣義位能場模型來達成避碰。相對於機械手臂的基點是固定的，連結型機器人因有可移動的基點所以在路經規劃上有較高的自由度。在本論文中，我們亦發展了相對應之路徑規劃演算法。 另外，透過相同的廣義位能場模型的建立，我們亦提出一三維物體形狀比對的演算法。在 [2] 中，廣義位能場模型被用來做單一剛體在一靜態空間的路徑規劃；事實上，在路徑規劃的過程中，降低剛體於靜態空間位能的作法可視為某種程度的剛體與自由空間的形狀比對。在路徑規劃演算法中，剛體位置會沿著路徑改變、但大小不變；然而，在形狀比對中，比對物體的位置變化不大，但其大小卻會隨之增 長。當比對物體增大後，如能調整其位置及姿態以降低位能，則可獲得一個較好的比對形狀。此外，由於三維物體資料經常為點資訊（如range data），資料量大且不易解讀，以位能場為基礎之形狀比對演算法可直接使用物體的點資訊作比對，可省去費時的物體點資訊前處理。由實驗結果得知，所提出的演算法在物體之路徑規劃與形狀比對均有不錯之成果，而後者對於部分遮蔽的物體亦可適用。

In this thesis, along the general direction of free space modeling using potential models, various applications of potential models are investigated. Variant potential-based algorithms are proposed to solve (1) path planning and (2) shape matching problems. The common idea of these algorithms is to use the repulsion exerted on an object, in forms of repulsive force and torque, from free space boundaries to achieve the best shape match between them. The object can be rigid or articulated, and the best match in shape is accomplished by adjusting object configuration, i.e., location and orientation, to minimize the potential fields among them. In the path planning algorithm of manipulators, the bewtonian potential is used to represent manipulators and obstacles with charged boundaries in a 2-D workspace. The approach computes, similar to that done in electrostatics, repulsive force and torque between charged objects in the workspace. A collision-free path of a manipulator will then be obtained by locally adjusting the manipulator configuration to search for minimum potential configurations using these force and torque. The proposed approach is efficient because these potential gradients are analytically tractable. The above potential-based path planning approach for manipulators is extended to three dimensions using the generalized potential model [1] instead of Newtonian potential. In [1], it is shown that the Newtonian potential, being harmonic in the 3-D space, can not prevent a charged point object from running into another object whose surface is uniformly charged. While the base of a manipulator is fixed, an articulated robot has higher DOF due to its moving base. A modified path planning algorithm based on the same generalized potential model is also proposed for articulated robots with moving bases in this thesis. In addition, the repulsion between an input object and a shape template is also utilized in the shape matching approach proposed in this thesis. In [2], it proposed a potential-based path planner for a single rigid robot among stationary and rigid obstacles in 3-D workspace. Indeed, the minimization of potential between robots and obstacles is a shape matching procedure of a robot within a free space in some respects. While a rigid robot moves along a path in a free space without changing its size in path planning, the object stays about the same location inside the shape template with growing size in shape matching. According to the proposed approach, a better match in shape between the template object and the input object can be obtained if the input object translates and reorients itself to reduce the potential while growing in size. Since objects are usually represented by mass and unstructured row data, e.g., range data, existed shape matching algorithms may have a preprocessing procedure to extract features from row data of objects. However, the proposed potential-based algorithm can directly perform the matching with range data of objects without preprocessing procedures. Simulation results show that the proposed algorithms work well for both path planning and shape matching applications. The latter is also practicable to objects with incomplete surface descriptions, e.g., due to a partial view.