能服务机器人环境描述方法：基于拓扑地图的同时定位与地图生成

正如 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 在实际机器人探索、导航中的应用。