Hierarchical map building and planning based on graph partitioning
Hierarchical map building and planning based on graph partitioning
复制标题
DOI：
10.1109/robot.2006.1641808
复制
发表时间：
2006-05
期刊：
影响因子：
--
通讯作者：
Z. Zivkovic;B. Bakker;B. Kröse
中科院分区：
文献类型：
--
作者：
Z. Zivkovic;B. Bakker;B. Kröse
移动的机器人定位和导航需要地图-机器人对环境的内部表示。一个常见的问题是，路径规划变得非常低效的大型地图。在本文中，我们解决的问题，分割一个基层地图，以构建一个更高层次的空间表示，可用于更有效的规划。我们将基层地图表示为基于几何和外观的空间表示的图形。然后，我们使用图划分的方法来聚类的基本级别的地图的节点，这样就可以构建一个高级别的地图，这也是一个图。本文提出了一种基于马尔可夫决策过程（MDP）的随机任务分层路径规划方法，并研究了不同簇数对路径规划的影响
Mobile robot localization and navigation requires a map - the robot's internal representation of the environment. A common problem is that path planning becomes very inefficient for large maps. In this paper we address the problem of segmenting a base-level map in order to construct a higher-level representation of the space which can be used for more efficient planning. We represent the base-level map as a graph for both geometric and appearance based space representations. Then we use a graph partitioning method to cluster nodes of the base-level map and in this way construct a high-level map, which is also a graph. We apply a hierarchical path planning method for stochastic tasks based on Markov decision processes (MDPs) and investigate the effect of choosing different numbers of clusters