Scholarlink

<p>Path planning in environments with obstacles is addressed through the construction of visibility graphs, known for high accuracy but computationally expensive edge intersection checks. A fully vectorized approach is proposed, in which all candidate visibility edges are processed against all obstacle edges simultaneously, reducing computation time. Polygonal contours are simplified, which decreases the number of vertices without affecting path optimality, thus further accelerating graph construction. Performance improvements are demonstrated through experiments, showing a substantial reduction in graph construction time compared to traditional and partially vectorized methods. Integration with various polygon extraction techniques is explored, and comparisons are made with other path-finding algorithms. In particular, comparisons are made with Theta*, A* and PRM, as well as with modern sampling-based methods such as RRT*, BIT*, FMT*, and Lazy&#xa0;Theta*. Global path optimality is preserved while achieving competitive or superior construction times. Visibility graphs enable replanning by updating only the necessary edges without reconstructing the entire graph. The graph’s sparse structure combined with optimized vectorized construction enables high-speed path planning. Paths were successfully and quickly found on large maps with a large number of obstacles for various navigation tasks of mobile robots. Overall, on small maps the vectorized visibility graph construction is up to 100<InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\times \)</EquationSource> <EquationSource Format="MATHML"><math> <mo>×</mo> </math></EquationSource> </InlineEquation> faster than Theta*, and on larger, obstacle-rich maps it still delivers roughly a 5<InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\times \)</EquationSource> <EquationSource Format="MATHML"><math> <mo>×</mo> </math></EquationSource> </InlineEquation> speedup. It also outperforms PRM, as increasing PRM’s sampling density to approach optimal paths leads to a rapid growth in computational cost. Similar trends were observed when compared with other sampling-based planners such as RRT*, BIT*, and FMT*. These results confirm the suitability of the vectorized visibility graph approach for high-performance mobile robot navigation.</p>

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

Accelerating path planning with vectorization of intersection operations

  • 期刊论文

  • 发表日期：

    2026年1月29日

查看全文
  • Kirill Kasmynin,
  • Konstantin Mironov,
  • Aleksandr Panov

摘要

Path planning in environments with obstacles is addressed through the construction of visibility graphs, known for high accuracy but computationally expensive edge intersection checks. A fully vectorized approach is proposed, in which all candidate visibility edges are processed against all obstacle edges simultaneously, reducing computation time. Polygonal contours are simplified, which decreases the number of vertices without affecting path optimality, thus further accelerating graph construction. Performance improvements are demonstrated through experiments, showing a substantial reduction in graph construction time compared to traditional and partially vectorized methods. Integration with various polygon extraction techniques is explored, and comparisons are made with other path-finding algorithms. In particular, comparisons are made with Theta*, A* and PRM, as well as with modern sampling-based methods such as RRT*, BIT*, FMT*, and Lazy Theta*. Global path optimality is preserved while achieving competitive or superior construction times. Visibility graphs enable replanning by updating only the necessary edges without reconstructing the entire graph. The graph’s sparse structure combined with optimized vectorized construction enables high-speed path planning. Paths were successfully and quickly found on large maps with a large number of obstacles for various navigation tasks of mobile robots. Overall, on small maps the vectorized visibility graph construction is up to 100 \(\times \) × faster than Theta*, and on larger, obstacle-rich maps it still delivers roughly a 5 \(\times \) × speedup. It also outperforms PRM, as increasing PRM’s sampling density to approach optimal paths leads to a rapid growth in computational cost. Similar trends were observed when compared with other sampling-based planners such as RRT*, BIT*, and FMT*. These results confirm the suitability of the vectorized visibility graph approach for high-performance mobile robot navigation.