在未知環境中機器人之地形模式探知及其修正和導航

Abstract

本論文探討有關機器人於未知環境中，規劃避碰路徑的方法。 本文之第 一部份將討論漸近式地形模式的探知。 經由在佈滿多邊形障礙物的未知 環境中有系統的運動規劃， 一個配有感測器的機器人將顯示能夠漸進地 建立整個地形模式，這個模式將以可視圖、可視窗來描述。 這種模式將 逐塊區域地建立起來， 且這些已開發的區域彼此間不重疊，如此所求地 域環境將由一群互不重疊的星狀多邊形拼湊而成， 且其相鄰關係可以星 狀多邊形相鄰圖來表示。 這種漸近式的開發程序，包含兩項基本工作： (1) 區域開發， (2) 合併開發。 有用的定理將為此二工作推導，且這些 工作的演算法也將可得到。 本文也提出兩種規劃機器人在未知地域環境 中運動的策略建議，並作比較； 這兩種策略就是在星狀多邊形相鄰圖中 分別作深度優先和寬度優先搜尋以決定如何開發整個未知環境。第二部份 將提出基本演算法來修訂地形模式因障礙物之刪除、 插入或其他情形所 產生的改變。 透過可視圖和可視窗對地形模式的描述，有關地形環境的 改變，只需要部份修訂即可。 同時也避免了現存大部份方法的缺點 ---- 全部重新建立。 針對環境中障礙物的刪除和插入，一套有系統的修 訂步驟也將在本文發展出來。第三部份則在佈滿多邊形障礙物的未知環境 中， 駕馭配有感測器的機器人有系統地運動，使其可漸近地建立一種圖 來規劃避碰路徑。 而一個良好的避碰路徑可使機器人從起始點移往目的 地。 對機器人而言，當開發未知環境時， 部份的地形資訊是以星狀多邊 形的方式取得，為了開發其他未開發區域， 它必須規劃一條避碰路徑以 便移出目前所在的星狀多邊形到另一個，這將產生一組星狀多邊形的組合 。 機器人利用擴張空間方法的輔助將可規劃避碰路徑來穿越所有遇到的 星狀多邊形直到獲得整個地形環境的資訊或機器人已到達目的地為止。本 文中援用了許多例子來闡述主要的觀念。 對於所提的演算法的績效也將 加以評估，並和其他現存方法作比較。 This dissertation is concerned with approaches to planning collsion-free paths in unknown environment for a mobile robot. In the first part, the problem of incremental terrain acquisition is addressed. Through a systematic planning of movements in an unknown terrain filled with polygonal obstacles, a sensor- based robot is shown to be able to incrementally build the entire terrain model; the model will be described in terms of visibility graph and visibility window. The terrain model is built area by area without any overlapping between explored areas. As a consequence, the terrain is obtained as a tessellation of disjoint star polygons. And the adjacency relations between star polygons are represented by a star polygon adjacency graph (SPAG graph). The incremental exploration process consists of two basic tasks: local exploration and exploration merging. Useful lemmas are derived for these two tasks and, then, the algorithms for the tasks are given. Two strategies for planning robot movements in the unknown terrain environment are suggested and compared. They are the depth-first search and the breadth-first search applied to the SPAG graph. In the second part, the basic algorithms are provided for updating the terrain data model due to obstacle deletion, insertion or other combined effects. Through a data representation in terms of visibility graph and visibility window, only the portion of terrain model that is affected by obstacle change is updated. It avoids reconstructing the terrain model all over again as required in most of existing methods. Systematic steps for terrain updating in the cases of obstacle deletion and obstacle insertion are developed.