Abstract
本篇論文的主要內容, 是在於提供一個有關於路徑規劃的計算機演算法則。這個演算法則是藉由形態學(mathematical morphology) 的基本運算來處理二個圓形物體在二度空間運動時, 如何能彼此不互相碰撞而到達各自的目的地。在本篇論文里, 二度空間中障礙物的形狀可以是任意而不受限制的, 演算法則中, 我們采用形態學上的一些運算來計算移動物體的自由活動空間。利用組態空間(configuration space) 的觀念, 我們將這二個圓形物體可以自由移動的空間點, 以狀態空間(state space) 的形式表示。然而這個狀態空間卻是一個四度空間的集合, 這不但造成龐大的資料量, 而且計算速度也會因此緩慢許多。基於以上二點理由, 我們嘗試只利用這個四度空間集合的邊界點, 另外建立成一個二度空間的子集合, 我們稱之為平移映射圖。換言之, 我們只考慮那些沿著障礙物的自由空間點, 使得二個圓盤, 儘量沿著障礙物運動, 若我們將二個圓形物體的起始點及終點分別用平移映射圖上的二個點表示, 從平移映射圖的觀點來看, 我們將會發現二個圓形物體在二度空間運動的問題, 可以看成是平移映射圖上的二點是否屬於同一個連接集合的問題。為了解釋這個觀念, 我們提出一個充分必要條件來說明二個圓形物體, 若且唯若存在某一條路徑可以允許它們到達各自的目的地, 則在平移映射圖里, 我們必然可以找到一條連續曲線連接這二個分別代表起始和目的地的二極點, 最后, 我們列舉了一些例子, 以圖片來說明這個事實。