AutoDrone: Shortest Optimized Obstacle-Free Path Planning for Autonomous Drones

Prithwish Jana, Debasish JanaarXiv 2021 · arXiv

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:

  1. Perception and Mapping: High-altitude sensors create a 2D binary map identifying obstacles.
  2. Obstacle Graph Formation ($G_O$): The system identifies obstacle corners and filters out interior vertices that do not contribute to the shortest path.
  3. 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.
  4. Pathfinding: Dijkstra’s Algorithm is applied to the resulting graph to find the global shortest path.
Figure 1: A sample 2D grid environment showing obstacles (gray) and the start/end navigation points (blue).

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.

Figure 5: Execution time remains nearly constant as grid size increases for a fixed number of obstacles, highlighting the algorithm's efficiency.

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

Abstract

With technological advancement, drone has emerged as unmanned aerial vehicle that can be controlled by humans to fly or reach a destination. This may be autonomous as well, where the drone itself is intelligent enough to find a shortest obstacle-free path to reach the destination from a designated source. Be it a planned smart city or even a wreckage site affected by natural calamity, we may imagine the buildings, any surface-erected structure or other blockage as obstacles for the drone to fly in a straight line-of-sight path. To address such path-planning of drones, the bird's eye-view of the whole landscape is first transformed to a graph of grid-cells, where some are occupied to indicate the obstacles and some are free to indicate the free path. We propose a method to find out the shortest obstacle-free path in the coordinate system guided by GPS. The autonomous drone (AutoDrone) will thus be able to move from one place to another along the shortest path, without colliding into hindrances, while traveling in a two-dimensional space. Heuristics to extend this to long journeys and 3D space are also elaborated. Our approach can be especially beneficial in rescue operations and fast delivery or pick-up in an energy-efficient way, where our algorithm will help in finding out the shortest path and angle along which it should fly. Experiments are done on different scenarios of map layouts and obstacle positions to understand the shortest feasible route, computed by the autonomous drone.
BibTeX
@misc{jana2021autodrone,
  author = {Prithwish Jana and Debasish Jana},
  title = {{AutoDrone: Shortest Optimized Obstacle-Free Path Planning for Autonomous Drones}},
  year = {2021},
  eprint = {2111.00200},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2111.00200},
}
Figure