在三維曲面上之最短路徑規劃及其應用

Abstract

機械手在多重障礙空間中連續反覆移動執行任務，其移動之時間及距離與產量有關，而時間與距離均為路徑規劃之重要因素，又路徑規劃需考量機械手與工件、機台、夾治具及週邊設備等之避碰問題，但以架構空間顯示障礙區時皆呈不規則狀，欲由不規則之障礙區域內直接規劃避碰之最短路徑著實不易，因此我們以特殊外形之多面體來界定障礙區，來尋找兩點間之最短路徑，設定在多面體上任意兩點間最短路徑之向量係由起點朝終點方向前進，若遇界定障礙區之多面體則先繞行其表面，待通過該多面體後再返回原來向量方向繼續前進，來獲得整體性之合適路徑。通常在多面體上估算最短路徑必須經過大量搜尋、登錄與比對其相關資料而花費甚多之計算量，假如企圖在弧形曲面上直接規劃最短路徑時則需花費更龐大之計算量，因此研究如何降低路徑規劃之計算量與如何整合路徑規劃理論在多面體上及弧形曲面上規劃路徑確有其必要性。 本研究首先將三維曲面上之最短路徑規劃問題分成(一)敞開式與搭接式多面體、(二)封閉式與規則式多面體、(三)可展開成平面之多面體等三種類型來驗證。第一種類型係利用網格規劃法配合迪吉斯托(Dijkstra)法則在敞開式與搭接式多面體上任意兩點間尋找最短之繞行路徑，並達成在平面、斜面、山形多面體與盒形、瓶形、雙球形等多面體之表面上搜尋最短路徑。布魯霍斯(Brute Force)法則主張被最短路徑通過之邊界轉折點其入角度必等於其出角度可應用在第二種類型封閉式或規則式多面體上尋求避碰之最短路徑[6]，並達成在六面體與規則曲面上搜尋最短路徑的目標。以布魯霍斯法則為基礎所發展的平面展開法在第三種類型可被展開成平面之多面體上尋求避碰之最短路徑，再經由座標轉換理論將該路徑轉換至多面體上，本研究並以平面、十二面體、二十面體、圓柱、圓錐、與由圓柱圓錐平面與斜面等所組成之多面體為例示範多面體展開成平面組合用來搜尋最短路徑。 本研究旨在將前述之路徑規劃理論加以延伸及改良並稱為PBBF理論(整合邊界分割法與布魯霍斯法則)直接應用在弧形曲面上規劃最短路徑。PBBF理論旨在解決弧形曲面之路徑規劃問題，成果可應用於包裝纏繞及數值控制之機械加工路徑規劃。在包裝及加工方面，同時考量纏繞線長最短、纏繞線徑與不得重覆纏繞等限制，本研究甭果與方法亦順利且有效地模擬解出多面體做合適的纏繞結果。

關鍵字： 最短路徑，邊界分割法，網格規劃法，弧形曲面，平面展開法，布魯霍斯法則

The shortest path planning has been widely used in 2D path planning problems, such as postman mail delivery problem, AGV route scheduling problem etc. There are several efficacious methodologies discussed in many related papers. The study proposes a novel concept and method to solve not only the 2D shortest path planning but to extend to 3D shortest path planning on a 3D curved surface. The curved surface model defined in this study is a surface model described by many spline curves at the cross section edges. Four categories of the curved surface have been assigned appropriate planning method separately based on their geometry characteristics. Each of the four surface groups is named as follows: (1). Simple patch with or without forbidden zone on it, abbreviated as “SPFZ”. (2). Prism type polyhedron, abbreviated as “PSP”. (3). Plane unfoldable polyhedron, abbreviated as “PUP”. (4). Surface framed by polygons, abbreviated as “SFP”. It’s hard to find a simple way to solve for the shortest path from the starting point to the goal point on the patch for all the four different kinds of surface. Thus, we present the novel method each for the four discussed surface groups. For SPFZ, the study proposes to net the patch including the forbidden zone, then set up the route length table for adjacent grid points and search for the shortest path by using Dijkstra Method. For PSP, the bending segments of the polyhedron are modeled as polynomial equations, then Brute Force method is applied to solve for all the bending points on the shortest path. For PUP, all the plate patches of the polyhedron are unfolded to a plane; the bending points of the shortest path found on the plane will then transformed back to the original coordinates. For SFP, the general type curved surface case, two steps are implemented integratively. First step will be the same as SPFZ model, the following step will be the same as PSP model to reach the shortest path closer to the theoretical length. The study has developed a shortest path planning system bonded with CAD software, named as PBBF. The PBBF system provides a CAD based shortest path planning functions that can be easily applied to 3D route planning task on industry and academic research.

Key words: Shortest Path Planning, Polyhedron, 3D Curved Surface, Brute Force Method