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

• 作 者: 种 陈阳舟 崔平远 居鹤华
• 机 构: 北京工业大学电控学院,北京工业大学电控学院,北京工业大学电控学院,北京工业大学电控学院 北京100022,北京100022,北京100022,北京100022
• 出 处: 计算机仿真
• 发表日期: 2006年04期
• 关键词: 移动机器人 障碍物 路径规划 直线行走 扫描法 算法 构造环境 路径规划算法 拓扑图 启发式函数

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

This paper presents a path planning algorithm based on scanning method to construct environment topology graphically. Compared with the traditional road map method, this algorithm uses the scanning method to search the obstacle cut-point and constructs the environment topology map, which reduces the computational complexity and improves the practicability. The heuristic function is used to select the appropriate exit point for expansion and gradually Improve the topology, avoiding the one-time construction of the entire environment topology caused by unnecessary large amount of calculation. Switching between “walking along a straight line” and “walking around an obstacle” ensures that the robot smoothly avoids the obstacle to reach the target position. The algorithm has low computational complexity, is easy to implement online and has been verified in simulation.