Multiunmanned Aerial Vehicle Path Planner on Graphics Processing Unit
- 27 July 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Canadian Journal of Electrical and Computer Engineering
- Vol. 44 (3) , 364-375
Abstract
Using multiple unmanned aerial vehicles (UAVs) improves the efficiency of reconnaissance, surveillance, and search and rescue missions. This article presents a path-planning software for a team of UAVs utilizing graphics processing units (GPUs). The UAVs are tasked to visit multiple points of interest (POIs) in a 3-D environment, and the software finds an optimized solution that assigns the POIs to the UAVs, selects the order in which the POIs are visited, and calculates the paths between the POIs. The software uses a multistep approach using a single-source-shortest-path algorithm to find the optimal paths between all combinations of POIs followed by a genetic algorithm to solve the multitraveling salesperson problem. The algorithm can minimize distance, time, or energy consumption depending on the setting selected by the user. The proposed GPU implementation is tested on eight different maps from around the world and executes in just 0.6 s, a 48.3x speedup compared to a sequential execution on CPU. This performance improvement is a real asset in a mission-changing environment.Keywords
Funding Information
- Canadian Defence Academy
- Directorate of Technical Airworthiness and Engineering Support
This publication has 31 references indexed in Scilit:
- Energy-Aware Spiral Coverage Path Planning for UAV Photogrammetric ApplicationsIEEE Robotics and Automation Letters, 2018
- Fast Genetic Algorithm Path Planner for Fixed-Wing Military UAV Using GPUIEEE Transactions on Aerospace and Electronic Systems, 2018
- Node, Edge, Arc Routing and Turn Penalties: Multiple Problems—One Neighborhood ExtensionOperations Research, 2017
- Multi-UAV Path Planning with Parallel Genetic Algorithms on CUDA Architecture2016
- Coverage Path Planning for UAVs Photogrammetry with Energy and Resolution ConstraintsJournal of Intelligent & Robotic Systems, 2016
- PARALLEL HYBRID METAHEURISTIC ON SHARED MEMORY SYSTEM FOR REAL-TIME UAV PATH PLANNINGInternational Journal of Computational Intelligence and Applications, 2014
- A Scalable Work-Efficient and Depth-Optimal Parallel Scan for the GPGPU EnvironmentIEEE Transactions on Parallel and Distributed Systems, 2012
- Comparison of Parallel Genetic Algorithm and Particle Swarm Optimization for Real-Time UAV Path PlanningIEEE Transactions on Industrial Informatics, 2012
- FPGA Implementation of an Evolutionary Algorithm for Autonomous Unmanned Aerial Vehicle On-Board Path PlanningIEEE Transactions on Evolutionary Computation, 2012
- The Shuttle Radar Topography MissionReviews of Geophysics, 2007