<p>Traditional path planning algorithms face notable limitations: the graph search-based A* algorithm suffers from excessive turning points and low search efficiency, while the boundary-following Bug0 algorithm, though capable of rapid obstacle avoidance, struggles with concave regions, infeasible areas, and high path redundancy. To address these issues, this study proposes a global path planning algorithm that leverages obstacle boundary point sequences for rapid obstacle circumvention. First, by integrating the node expansion mechanism of the A* algorithm with a ray model to optimize search direction, redundant node traversal is significantly reduced. Second, fusion with the Floyd optimization algorithm enhances the smoothness and stability of the global path. Subsequently, during path planning, the obstacle boundary-following strategy of Bug0 is adopted but improved by dynamically generating boundary point sequences instead of unidirectional traversal, thereby eliminating local loops. A novel boundary-following algorithm, bypass barriers through borders, is proposed to efficiently handle path planning in concave and infeasible regions. Experimental results across diverse environments demonstrate that the proposed algorithm outperforms both A* and Bug0, achieving an 80% reduction in computation time, smoother and shorter paths, and superior performance in concave and infeasible regions where traditional algorithms typically fail.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An improved global path planning algorithm for fast obstacle bypassing using boundary point sequences

  • Songming Jiao,
  • Zhi Li,
  • Zemin Wang,
  • Zhenzhen Li,
  • Jincheng Zhou

摘要

Traditional path planning algorithms face notable limitations: the graph search-based A* algorithm suffers from excessive turning points and low search efficiency, while the boundary-following Bug0 algorithm, though capable of rapid obstacle avoidance, struggles with concave regions, infeasible areas, and high path redundancy. To address these issues, this study proposes a global path planning algorithm that leverages obstacle boundary point sequences for rapid obstacle circumvention. First, by integrating the node expansion mechanism of the A* algorithm with a ray model to optimize search direction, redundant node traversal is significantly reduced. Second, fusion with the Floyd optimization algorithm enhances the smoothness and stability of the global path. Subsequently, during path planning, the obstacle boundary-following strategy of Bug0 is adopted but improved by dynamically generating boundary point sequences instead of unidirectional traversal, thereby eliminating local loops. A novel boundary-following algorithm, bypass barriers through borders, is proposed to efficiently handle path planning in concave and infeasible regions. Experimental results across diverse environments demonstrate that the proposed algorithm outperforms both A* and Bug0, achieving an 80% reduction in computation time, smoother and shorter paths, and superior performance in concave and infeasible regions where traditional algorithms typically fail.