障碍物空间(自由空间)的中轴线(如图2-1(d)所示)。由于Voronoi图的维数比机器人所在的环境维数低,因此Voronoi图用于路径规划搜索时通常搜索空间也较小。Voronoi图上形成的路径长度要长于最短路径长度,故而Voronoi图上路径的最优性较差。但在实际应用中,由于要考虑到机器人运动的安全性,通常沿着Voronoi图运动时具有较宽阔的通道。不过当采用路径长度作为优化目标时,Voronoi图不能完全保证所规划路径的安全性。计算Voronoi图的算法较多,如Aggarwahl[6]给出了一种N个节点环境中,串行计算复杂度为O(Nlog2N)的算法。拓扑地图拓扑地图[7]高度抽象了环境的几何特征描述,采用拓扑节点表示具有相同或相近特征的环境,不同节点间的连接权值表示相应的距离代价(如图2-1(e)所示)。拓扑节点可以人为定义也可以由机器人自主定义,走廊、门、路口常常被选作拓扑节点;拓扑节点间的连接可以用节点间的距离和角度表示,也可以用它们在不同方向上距离的差值表示,还可以直接以坐标形式表示拓扑节点,只是需要附加信息来表示节点间的连通性。拓扑地图表示忽视对物体形态的认知,即不需要通过传感器去感知观测到的具体是何种物体,它要做的是拓扑节点的定义以及根据传感器信息对节点的确认。离散的拓扑地图可以应用与更高层次的决策,例如在较大范围的环境里,在具有较少存储空间的拓扑地图上的规划显然要比直接在几何地图上的规划要简单得多。这样做,对于人类使用者来说也更为熟悉,我们更习惯指使机器人去某个房间而不是叫它去某个坐标位置。尽管拓扑地图表现出种种优越性,但它仍存在其不利的方面。它需要较精确的位置估计,也要求拓扑节点方便被观测到;对拓扑节点的定义是拓扑地图的一大难点,如果传感器本身不稳定或环境动态性较大,将更加困难;规则化的环境常常有很多地方很相近,观测上的相似性将陷入对拓扑节点确认的混淆。
全文预览
