.png){kind=icon}
.png){kind=icon}
Return
Accelerating path planning with vectorization of intersection operations
.png){kind=icon}
PRE
AI
DOI：10.1007/s11370-025-00680-4.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 100x\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\times $$\end{document} faster than Theta*, and on larger, obstacle-rich maps it still delivers roughly a 5x\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\times $$\end{document} 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.
Keywords:
Path planning
Visibility graph
Vectorization
Mobile robots
Accelerating intersection checks
Polygon approximation
Journal
IF:
4.3
Papers:
78
Citations:
1.2K