基于扫描法在线构造拓扑图的路经规划算法

Path Planning Algorithm Based on Topology Map Structured by Sweep Method

该文提出了一种基于扫描法在线构造环境拓扑图的路径规划算法。与传统路图法相比,该算法利用扫描的方法搜索障碍物切点,并构造环境拓扑图,降低了计算复杂度,提高了实用性;利用启发式函数选择适当的离开点进行扩展,并逐步完善拓扑图,避免了一次性构造整个环境拓扑图所带来的不必要的大计算量。通过“沿直线行走”和“绕障碍物行走”这两种行为模式的切换,保证机器人顺利地避开障碍物到达目标位置。该算法的计算复杂度低,易于在线实现,并在仿真中得到了验证。

In this paper, we propose a sweep - based path planning algorithm, in which sweep method is introduced to search obstacle＇s tangent points and structure topology map, independent of the geometric shapes and vertexes of the obstacles. According to the structured partial topology map of the environment and global information, heuristic function is used to select a leaving point for expanding, and update the structured topology map, till a traversable path between starting point and goal is found in the topology map. Two behavioral modes, ＂go straight line＂ and ＂boundary following＂ , guarantee that the robot can achieve the goal safely. The simulation results prove the effectiveness and correctness of this algorithm. In short, this algorithm has lower computational complexity compared with other existing roadmap algorithms, and is easy to realize on - line.