Global Path Planning for UAVs Using a Simplified Visibility Graph with Obstacle Merging
Do Dang Khoa, Tran Van Minh Hieu · 2025
Efficient path planning is essential for Unmanned Aerial Vehicles (UAVs) to navigate complex environments while avoiding obstacles. This paper presents a novel global path planning algorithm that integrates a simplified visibility graph (VG) method with the Dijkstra algorithm to enhance computational efficiency and adaptability. Unlike traditional polygon-based approaches, the proposed method models obstacles as rectangles with safety buffer, reducing graph node complexity. The algorithm optimizes the graph by considering only obstacles intersected by the M-Line connecting start and goal points, minimizing unnecessary computations. A smart obstacle merging strategy ensures path existence by addressing narrow gaps between adjacent obstacles and accounting for UAV size and sensor noise-induced position errors. Simulation results show that the proposed method outperforms the traditional VG approaches as well as another popular global path planning algorithm, the Rapidly exploring Random Tree Connect (RRT-Connect), achieving shorter paths and faster computation time. These advantages make the proposed algorithm well-suited for real-time UAV navigation in obstaclerich environments.