基于环境剖分的层次拓扑地图及路径规划

针对基于拓扑地图的移动机器人路径规划问题，提出一种层次拓扑地图及相应的路径规划方法——边界方位法。层次拓扑地图分为剖分层和边界层，剖分层以环境剖分为拓扑节点，边界层以剖分的边界为拓扑节点。边界方位法首先在剖分层生成由剖分构成的路径序列，再将边界层转化为由边界构成的路径序列，最后根据机器人当前位置及边界之间的方位荚系实时生成实际路径。由于定义了边界之间的方位关系，使得机器人能够根据边界序列路径中的下一边界与当前边界的方位关系确定当前的运动方向，从而实现了实际路径的优化。理论分析和仿真实验均表明，该方法在增加少量存储信息的基础上，获得了较好的路径规划效果。

Hierarchical Topological Map Based on Environmental Partition and Path Planning

Aiming at the path planning problem of the moving robot based on topological map,this paper proposed a hierarchical topological map and its path planning algorithm called boundary orientation algorithm.The hierarchical map includes partition level and boundary level.The topological nodes in partition level are partitions of environment while the topological nodes in boundary level are partitions of boundaries.In boundary orientation algorithm,we firstly get the path sequence constructed by partitions generated in partition level and,then,get the path sequence constructed by boundaries in boundary level.Finally,according to the current robot position and orientation relationship between boundaries,the actual path is generated on real time.Because the orientation relationship between boundaries is defined,the robot can decide the current direction of movement according to the orientation relation between current boundary and next boundary,achieving the optimization of the actual path.Theoretical analysis and simulation experiments both show that the method can get a batter effect of path planning with a slight increase of space complexity.