Multidepot 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 multidrone missions are indications of a high likelihood of in-flight drone collisions. This likelihood can be proactively minimized during path planning. This article proposes two offline collision-avoidance multidrone path-planning algorithms: 1) DETACH and 2) 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)
Pages (from-to)16297-16307
Number of pages11
JournalIEEE Internet of Things Journal
Volume9
Issue number17
DOIs
StatePublished - Sep 1 2022

All Science Journal Classification (ASJC) codes

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

Keywords

  • Collision avoidance
  • drones
  • multidepot vehicle routing problem (MDVRP)
  • optimization
  • path planning
  • unmanned aerial vehicles (UAVs)

Fingerprint

Dive into the research topics of 'Multidepot Drone Path Planning With Collision Avoidance'. Together they form a unique fingerprint.

Cite this