Multi-Depot Drone Path Planning with Collision Avoidance

Kun Shen, Rutuja Shivgan, Jorge Medina, Ziqian Dong, Roberto Rojas-Cessa

Research output: Contribution to journalArticlepeer-review

Abstract

Intersections of flight paths in multi-drone missions are indications of a high likelihood of in-flight drone collisions. This likelihood can be proactively minimized during path planning. This paper proposes two offline collision-avoidance multi-drone path-planning algorithms: DETACH and STEER. Large drone tasks can be divided into smaller ones and carried out by multiple drones. Each drone follows a planned flight path that is optimized to efficiently perform the task. The path planning of the set of drones can then be optimized to complete the task in a short time, with minimum energy expenditure, or with maximum waypoint coverage. Here we focus on maximizing waypoint coverage. Different from existing schemes, our proposed offline path-planning algorithms detect and remove possible in-flight collisions. They are based on a constrained nearest-neighbor search algorithm that aims to cover a large number of waypoints per flight-path. DETACH and STEER perform vector intersection check for flight path analysis, but each at different stages of path planning. We evaluate the waypoint coverage of the proposed algorithms through a novel profit model and compare their performance on a work area with different waypoint densities. Our results show that STEER covers 40% more waypoints and generates 20% more profit than DETACH in high-density waypoint scenarios.

Original languageEnglish (US)
JournalIEEE Internet of Things Journal
DOIs
StateAccepted/In press - 2022

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Information Systems
  • Hardware and Architecture
  • Computer Science Applications
  • Computer Networks and Communications

Keywords

  • Collision avoidance
  • Collision avoidance.
  • Drones
  • Drones
  • Multi-Depot Vehicle Routing Problem
  • Optimization
  • Orbits
  • Path planning
  • Path planning
  • Routing
  • Sensors
  • Task analysis
  • Unmanned Aerial Vehicles

Fingerprint

Dive into the research topics of 'Multi-Depot Drone Path Planning with Collision Avoidance'. Together they form a unique fingerprint.

Cite this