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