正如 FastSLAM 廣泛應(yīng)用于柵格地圖一樣，Howie提出了一種基于拓?fù)涞貓D的同時(shí)定 位與地圖生成算法75]。該方法建立在廣義 Voronoi圖(Generalized Voronoi Graph,GVG) 的基礎(chǔ)之上。圖1.59給出了基于拓?fù)涞貓D的同時(shí)定位與地圖生成方法創(chuàng)建的GVG 拓?fù)涞貓D。圖中線的交點(diǎn)為拓?fù)涔?jié)點(diǎn)，代表特定地點(diǎn)。節(jié)點(diǎn)之間的連線代表連通的路徑。

考慮平面上的一組點(diǎn)P, 對(duì)于P 上任意一點(diǎn)p, 定義離p; 點(diǎn)較近而與其他點(diǎn)較遠(yuǎn)的區(qū) 域?yàn)榕cp; 相關(guān)的Voronoi區(qū)域，表示為V 。這樣平面上的所有點(diǎn)都必定屬于某一區(qū)域。兩 個(gè) Voronoi區(qū)域V 和 V 邊界線上的所有點(diǎn)到p 和p,的距離相等并且小于到其他任何點(diǎn)的 距離，定義這條邊界線為Voronoi 邊，表示為E, 。Voronoi 邊或者延伸到無(wú)限遠(yuǎn)處，或者與 其他的Voronoi邊相交，交點(diǎn)到平面上三點(diǎn)P:\p 和p₆ 的距離相等且小于到其他任何點(diǎn)的 距離，則稱該交點(diǎn)為Voronoi 節(jié)點(diǎn)，表示為N, 并把與若干點(diǎn)集相對(duì)應(yīng)的Voronoi 節(jié)點(diǎn)和 Voronoi邊集合稱為Voronoi圖。

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

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

根據(jù)所知的文獻(xiàn)，GVG是目前W一一種可以在線創(chuàng)建的拓?fù)涞貓D，但是該方法仍然 有其不足之處：先，GVG 本身是一種道路地圖，GVG 節(jié)點(diǎn)可以認(rèn)為是不同通道的集結(jié) 點(diǎn)，在大規(guī)模未知環(huán)境中，可能存在許多特征相似的節(jié)點(diǎn)，給地圖創(chuàng)建或機(jī)器人定位時(shí)的 數(shù)據(jù)關(guān)聯(lián)帶來(lái)了很大的困難。這一不足比FastSLAM 有所改善，但仍然不能滿足機(jī)器人 在大規(guī)模復(fù)雜環(huán)境下的導(dǎo)航和探索要求。其次，GVG 對(duì)于環(huán)境的局部改變比較敏感，增加一個(gè)障礙物可能導(dǎo)致若干節(jié)點(diǎn)的產(chǎn)生，因此GVG 不適合應(yīng)用于動(dòng)態(tài)環(huán)境，這一點(diǎn)妨礙 了 GVG 在實(shí)際機(jī)器人探索、導(dǎo)航中的應(yīng)用。