Path planning algorithm based on topologyMap structured by scanning method

In this paper, we propose a scan-based path planning algorithm, in which scanning method is introduced to search obstacle's tangent and structure topology map on-line, independent of the geometric shapes and vertexes' information of the obstacles. According to the structured partial topology map of the environment and the global information, heuristic function is used to select tangent point to expand, while update and complement 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", are included, and switch between them guarantees that the robot can achieve the goal safely. While a direction selection method is used to minimize scanning scope and improve efficiency. The simulation results prove the effectiveness and correctness of this algorithm. In short, this algorithm has lower computational complexity compared with other existed roadmap algorithms, is feasible for obstacle with arbitrary shape, and easy to realize on-line.