拓撲地圖

節點是指不同通道之間交叉區域的幾何中心或只有一個出口的區域的幾何中心 ,比如門口、拐角或房間與走廊的盡頭等,同時稱該區域為節點區域.

一類節點 :只存在一個無碰扇區的節點

二類節點 :存在兩個無碰扇區的節點

三類節點 :存在 3個或 3個以上無碰扇區的節點

拓撲地圖：把室內環境表示為帶結點和相關連接線的拓撲結構圖，其中結點表示環境中的重要位置點（拐角、門、電梯、樓梯等），邊表示節點間的連接關係，如走廊等。 ^[1] 

柵格地圖：把環境劃分成一系列柵格，其中每一柵格給定一個可能值，表示該柵格被佔據的概率。

直接表徵法：省去了特徵或柵格表示這一中間環節，直接用傳感器讀取的數據來構造機器人的位姿空間。每種方法各有自己的特點和適用範圍，其中特徵地圖和柵格地圖應用最普遍。

利用BCM 在線生成拓撲地圖(Construc-ting the topolog ical m ap on line w ith BCM )：

BCM 採用分層結構把環境分為若干扇區,利用最大化目標函數的扇區產生滿足物理限制和環境約束的線速度和角速度.與其他常用的反應式導航方法如人工勢場法、矢量場矩形法以及巷道—曲率法相比,BCM能夠實現更加可靠、快速和平滑的導航而且不容易陷入局部陷阱。扇區分為阻塞扇區和無碰扇區,其中阻塞扇區與環境中的某一障礙物相關聯 ,而無碰扇區中則不包含任何障礙物

基於散點建立數字地面模型，常採用在d維的歐幾里得空間Ed中構造Delaunay三角形網的通用算法-逐點插入算法，具體算法過程如下:

1、遍歷所有散點，求出點集的包容盒，得到作為點集凸殼的初始三角形並放入三角形鏈表。

2、將點集中的散點依次插入，在三角形鏈表中找出其外接圓包含插入點的三角形(稱為該點的影響三角形)，刪除影響三角形的公共邊，將插入點同影響三角形的全部頂點連接起來，從而完成一個點在Delaunay三角形鏈表中的插入。

3、根據優化準則對局部新形成的三角形進行優化(如互換對角線等)。將形成的三角形放入Delaunay三角形鏈表。

4、循環執行上述第2步，直到所有散點插入完畢。 ^[2] 

第一,對於環境的拓撲,尚沒有形成統一的定義.例如 Kuipers和 Th run分別採用不同的方式表示拓撲節點和弧.這導致在實際應用中機器人難以對環境的拓撲地圖進行創建.

第二 ,拓撲地圖的在線創建. Zwynsvoo rde提出了一種拓撲地圖在線創建方法 ———V orono i圖法,該方法無法應用於任意形狀的空間並且需要很長的計算時間.而其他大部分方法在本質上是離線的.

第三 ,機器人在拓撲地圖中的定位.傳統的拓撲地圖利用人工路標進行定位.在未知環境中 ,機器人必須提取容易區分的特徵作為路標.常用的方法有線段檢測、角點檢測等. Lowe等人提出了一種比例不變特徵變換 (Sca le Invariant Fea ture T rans-fo rm ,SIFT). 該特徵對圖像的縮放、視角、光強等變化具有較好的不變性 ,已經在地圖創建中開始應用. ^[3]