Abstract
Autonomous drone navigation in complex, cluttered environments requires path-planning algorithms that are both mathematically optimal and computationally efficient. This paper presents AutoDrone, a system that utilizes visibility graphs and a rotating sweep-line heuristic to determine the shortest Euclidean path between two points. By enabling any-angle movement and decoupling computational complexity from grid resolution, AutoDrone offers a scalable solution for real-time navigation in urban or disaster-stricken areas.
Introduction
Efficiently navigating a drone through urban landscapes is a significant challenge due to the presence of numerous obstacles like buildings and trees. Traditional grid-based pathfinding methods often result in suboptimal, jagged paths that increase travel distance and energy consumption. While visibility graphs provide the true shortest path, their $O(N^2)$ construction complexity is often prohibitive for onboard processing. AutoDrone addresses these issues through optimized geometric algorithms.
Methods
The AutoDrone system processes environmental data through four primary stages:
- Perception and Mapping: High-altitude sensors create a 2D binary map identifying obstacles.
- Obstacle Graph Formation ($G_O$): The system identifies obstacle corners and filters out interior vertices that do not contribute to the shortest path.
- Visibility Graph Optimization ($G_V$): A rotating sweep-line algorithm is used to efficiently determine line-of-sight between vertices, significantly reducing the number of visibility checks.
- Pathfinding: Dijkstra’s Algorithm is applied to the resulting graph to find the global shortest path.
Key Insights and Performance
A major contribution of this work is the discovery of complexity decoupling. Empirical results show that execution time is primarily driven by the number of obstacles rather than the grid resolution. This allows for high-fidelity mapping without a linear increase in path-planning latency.
Additionally, the "tight string" approach ensures that the path grazes obstacle corners, minimizing the number of angular maneuvers. This reduction in turns is critical for battery conservation and mechanical longevity in autonomous flight.
Results and Scalability
The algorithm was tested on various synthetic maps:
- Medium-scale: A $30 \times 20$ grid with 200 obstacles yielded an optimal path of 38.05 units.
- Large-scale: A $100 \times 150$ grid with 7,000 obstacles was successfully navigated with a path length of 195.39 units. The sweep-line approach consistently kept the list of "critical edges" manageable, ensuring fast graph construction even in dense environments.
Conclusion
AutoDrone demonstrates a robust method for finding the shortest obstacle-free path for autonomous drones. By optimizing the visibility graph construction, the system achieves scalability and efficiency suitable for real-world applications. Future research will focus on dynamic obstacle avoidance and full 3D path integration.
Summary updated