結合轉折點偵測與Dijkstra演算法在最短路徑搜尋與應用

Combining Corner Detection and Dijkstra Algorithm for Shortest Path Search and Application

蔡樸生(Pu-Sheng Tsai) ； 林盈灝(Ying-Hao Lin) ； 周利蔚(Li-Wei Chou)

《中華技術學院學報》 38期 (2008/06) Pp. 65-83

https://doi.org/10.7095/JCIT.200806.0065

摘要

本文結合影像處理以及路徑規劃的技術建立一條能夠避開障礙物，並且到達目的地之最短路徑。文中分為兩個部分，一是以影像處理為基礎建立環境中的障礙物體分佈模型。在此我們提出邊點序向排列法，將所有物體的邊點座標進行有序排列，除了決定每個邊點之間的鏈結關係外，並且將影像中的物體作個別分類。其次，應用轉折點偵測法比較每個邊點前後向量間的夾角大小來決定多邊形障礙物的頂點座標。第二部分我們提出修正型Dijkstra演算法，以凸邊形障礙物的頂點為網路節點，最短路徑為代價函數，尋找一條連接起始點與終點之避障路徑。首先在每一個障礙物的邊界上加入一個凸邊形的安全防護網，除了防止車輛與障礙物發生碰撞之外，並可保證每一個障礙物都隸屬於凸型集合。其次，藉由直線與凸邊形障礙物之間的幾何關係來決定偵測點是否座落在障礙物範圍內。為了驗證本文架構的可行性，我們以Matlab程式語言的GUI介面完成避障路徑模擬。由結果得知，本文所提的方法在路徑規劃不僅具有可行性，並可獲至良好的效果。

關鍵字

路徑規劃 ； 邊點序向排列法 ； 轉折點偵測法 ； Dijkstra演算法 ； 禁行路徑判別

並列摘要

In this paper, the problem of path planning for autonomous vehicles or mobile robots moving in the exploration of hazardous or complex areas is solved. The purpose is to generate a feasible path connecting the initial and the final posture so that no collisions with obstacles would occur and various constraints are satisfied. First, an obstacle distribution model is established in a modeled-based environment by image processing techniques. As for the obstacle detection, the boundary sequence method arranges boundary coordinates for each object in order. It also determines the link relation of each boundary pixel such that the objects are detected and classified. By adopting the corner detection algorithm, we compare the angles of bordered vector in order to determine the location of corners of each object. Using the corner points of each obstacle object as nodes to create a network map, Dijkstra's algorithm is adopted to search the shortest path and to avoid collisions with the obstacles. In addition, the obstacles are modeled by polygonal sets which include appropriate safety margins. To determine the connectivity between two nodes, geometric detection is evolved to determine the forbidden paths. By using Matlab GUI toolbox, simulation results show that the design of obstacle avoidance trajectory which is based on image detection is applicable and it shows a better result.

並列關鍵字

Motion Planning ； Boundary Sequence Method ； Corner Detection Algorithm ； Dijkstra Algorithm ； forbidden path