能服務機器人環境描述方法：基于拓撲地圖的同時定位與地圖生成

正如 FastSLAM 廣泛應用于柵格地圖一樣，Howie提出了一種基于拓撲地圖的同時定 位與地圖生成算法75]。該方法建立在廣義 Voronoi圖(Generalized Voronoi Graph,GVG) 的基礎之上。圖1.59給出了基于拓撲地圖的同時定位與地圖生成方法創建的GVG 拓撲地圖。圖中線的交點為拓撲節點，代表特定地點。節點之間的連線代表連通的路徑。

考慮平面上的一組點P, 對于P 上任意一點p, 定義離p; 點較近而與其他點較遠的區 域為與p; 相關的Voronoi區域，表示為V 。這樣平面上的所有點都必定屬于某一區域。兩 個 Voronoi區域V 和 V 邊界線上的所有點到p 和p,的距離相等并且小于到其他任何點的 距離，定義這條邊界線為Voronoi 邊，表示為E, 。Voronoi 邊或者延伸到無限遠處，或者與 其他的Voronoi邊相交，交點到平面上三點P:\p 和p₆ 的距離相等且小于到其他任何點的 距離，則稱該交點為Voronoi 節點，表示為N, 并把與若干點集相對應的Voronoi 節點和 Voronoi邊集合稱為Voronoi圖。

點集P 的 Delaunay 三角剖分是指對于每一個 Voronoi節點N, 總存在一個三角形T, T 的D點分別為P:、P;和Ph, 并且三角形T 的三個邊分別被E 、Eμ 和 E 中分。所以過Pi、 P;和ph三點的外接圓以節點N; 為圓心，并且不包含平面上的所有其他點。Delaunay 三角 剖分具有很多優良的品質，比如，三角剖分的結果不受點集旋轉和平移操作的影響，并且 小區域點的變化不會引起在整個Voronoi圖上的傳播，只會對局部的區域造成影響。

根據Z短距離的定義不同，可以把Voronoi圖分為很多種，比如GVG按照到物體而非 到點的Z短距離劃分Voronoi圖，可以視為單純依靠傳感器信息就能夠跟蹤的嵌入式道路 地圖(Road map)。所 以 ，GVG 非常適合于拓撲地圖的在線創建。

根據所知的文獻，GVG是目前W一一種可以在線創建的拓撲地圖，但是該方法仍然 有其不足之處：先，GVG 本身是一種道路地圖，GVG 節點可以認為是不同通道的集結 點，在大規模未知環境中，可能存在許多特征相似的節點，給地圖創建或機器人定位時的 數據關聯帶來了很大的困難。這一不足比FastSLAM 有所改善，但仍然不能滿足機器人 在大規模復雜環境下的導航和探索要求。其次，GVG 對于環境的局部改變比較敏感，增加一個障礙物可能導致若干節點的產生，因此GVG 不適合應用于動態環境，這一點妨礙 了 GVG 在實際機器人探索、導航中的應用。