避開K 個凸多面體障礙物的最短路徑

Abstract

最短路徑問題的研究，在現今的機器人學中可幫助機器人自動計算出最佳的移動路徑 。同時，這類問題在計算幾何學中，也有它理論研究的價值。本篇論文便是以理論研 究的觀點來探討這類問題中的一個特例：找出兩點間避開三度空間中ｋ個凸多面體障 礙物的最短路徑。根據Sharir的研究，這種最短路徑經過一個組合邊序列。這個組合 邊序列是由所有被此最短路徑經過的凸多面體，各提供一個邊序列所組合而成，而一 個邊序列是由一連串相鄰凸多面體的邊所組成。假如我們稱被一任意兩點間的最短路 徑經過的邊序列為最短邊序列，在找ｋ個凸多面體事所有最短邊序列後，可以嘗試所 有凸多面體上邊序列的組合，而找到一個組合邊序列是最短路徑經過的組合邊序列。 在找到最短路徑過的組合邊序列後，可用已有的方法來找出真正的最短路徑。Sharir 提出一個方法，並證明在一個凸多面體上最多ｎ的７次方個邊序列屬於最短邊序列， 其中，ｎ為凸多面體的總邊數。Sharir的方法會找出一些非最邊序列的邊序列。因此 我們必須嘗試ｎ的７ｋ 次方種組合邊序列才可找到最短路徑。Mount 曾舉出一個例 子，證明在最壞的情形下，一個凸多面體上至少ｎ的４次方個最短邊序列。在本篇論 文中，我們提出一個方法可一一找出所有最短邊序列，而絕不包含非最短邊序列的邊 序列，所以我們只要嘗試最少種組合邊序列，便可找出最短路徑。Sharir猜測在最壞 的情形下，一個凸多面體上最多有ｎ的４次方個最短序列，而就算這項猜測錯誤，在 實際上我們的方法也會比Sharir的方法快。