有障礙物之最短路徑問題（Shortest Path problem With Obstacles）在應用上甚廣
，如無人搬運車、工廠內自動化、機械手臂……等。然而在以往文獻的研究，所用
方法不外乎僅找出一條安全的路徑而非最短路徑，不然使是可解出最短路徑，但其所
採用的卻是計算繁度（Computational Complexity）較高的可見點構圖法（Visibili
ty Graph）。因此或為了尋找最短的路徑須耗費較多決策時間，或為了節省決朿時間
而產生不經濟的行進路線皆不是我們所希望的，本論文提出一新的演算法(Algorithm
，以便能對決策時間和行進路線皆可顧慮到。由於可見點構圖法是建立在所有的可能
路徑，但在實際上有很多路徑是多餘的，為了改進此缺點，吾人僅以會影響最短路徑
之障礙物為考慮對象，結果使得計算繁度較可見點構圖法低，而所求出之路徑亦為最
短。
本論文所提出之演算法係針對障礙物為n 個凸多邊形時，而其總預點為N 之最短路徑
問題來討論，整個演算法計算繁度為０（nＮ＋ｎ）， 若以可見點構圖法，則計算
繁度將為0 （Ｎ） [12]。
|