拓撲地圖(topological map )是指地圖學中一種統計地圖,一種保持點與線相對位置關係正確而不一定保持圖形形狀與面積、距離、方向正確的抽象地圖。
基本介紹
概念解釋,節點,節點分類,繪圖特點,繪圖方法,BCM法,Voronoi法,發展現狀,
概念解釋
節點
節點是指不同通道之間交叉區域的幾何中心或只有一個出口的區域的幾何中心 ,比如門口、拐角或房間與走廊的盡頭等,同時稱該區域為節點區域.
節點分類
一類節點 :只存在一個無碰扇區的節點
二類節點 :存在兩個無碰扇區的節點
三類節點 :存在 3個或 3個以上無碰扇區的節點
繪圖特點
拓撲地圖:把室內環境表示為帶結點和相關連線線的拓撲結構圖,其中結點表示環境中的重要位置點(拐角、門、電梯、樓梯等),邊表示節點間的連線關係,如走廊等。
直接表征法:省去了特徵或柵格表示這一中間環節,直接用感測器讀取的數據來構造機器人的位姿空間。每種方法各有自己的特點和適用範圍,其中特徵地圖和柵格地圖套用最普遍。
繪圖方法
BCM法
利用BCM 線上生成拓撲地圖(Construc-ting the topolog ical m ap on line w ith BCM ):
BCM 採用分層結構把環境分為若干扇區,利用最大化目標函式的扇區產生滿足物理限制和環境約束的線速度和角速度.與其他常用的反應式導航方法如人工勢場法、矢量場矩形法以及巷道—曲率法相比,BCM能夠實現更加可靠、快速和平滑的導航而且不容易陷入局部陷阱。扇區分為阻塞扇區和無碰扇區,其中阻塞扇區與環境中的某一障礙物相關聯 ,而無碰扇區中則不包含任何障礙物
Voronoi法
基於散點建立數字地面模型,常採用在d維的歐幾里得空間Ed中構造Delaunay三角形網的通用算法-逐點插入算法,具體算法過程如下:
1、遍歷所有散點,求出點集的包容盒,得到作為點集凸殼的初始三角形並放入三角形鍊表。
2、將點集中的散點依次插入,在三角形鍊表中找出其外接圓包含插入點的三角形(稱為該點的影響三角形),刪除影響三角形的公共邊,將插入點同影響三角形的全部頂點連線起來,從而完成一個點在Delaunay三角形鍊表中的插入。
3、根據最佳化準則對局部新形成的三角形進行最佳化(如互換對角線等)。將形成的三角形放入Delaunay三角形鍊表。
4、循環執行上述第2步,直到所有散點插入完畢。
發展現狀
第一,對於環境的拓撲,尚沒有形成統一的定義.例如 Kuipers和 Th run分別採用不同的方式表示拓撲節點和弧.這導致在實際套用中機器人難以對環境的拓撲地圖進行創建.
第二 ,拓撲地圖的線上創建. Zwynsvoo rde提出了一種拓撲地圖線上創建方法 ———V orono i圖法,該方法無法套用於任意形狀的空間並且需要很長的計算時間.而其他大部分方法在本質上是離線的.
第三 ,機器人在拓撲地圖中的定位.傳統的拓撲地圖利用人工路標進行定位.在未知環境中 ,機器人必須提取容易區分的特徵作為路標.目前常用的方法有線段檢測、角點檢測等. Lowe等人提出了一種比例不變特徵變換 (Sca le Invariant Fea ture T rans-fo rm ,SIFT). 該特徵對圖像的縮放、視角、光強等變化具有較好的不變性 ,已經在地圖創建中開始套用.