A Parallel Algorithm for UAV Flight Route Planning on GPU

Date

2011-12-01

Author

Sanci, Seckin
İşler, Veysi

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

160
views

0
downloads

Aerial surveillance missions require a geographical region known as the area of interest to be inspected. The route that the aerial reconnaissance vehicle will follow is known as the flight route. Flight route planning operation has to be done before the actual mission is executed. A flight route may consist of hundreds of pre-defined geographical positions called waypoints. The optimal flight route planning manages to find a tour passing through all of the waypoints by covering the minimum possible distance. Due to the combinatorial nature of the problem it is impractical to devise a solution using brute force approaches. This study presents an approach to find a near-optimal solution to the flight route planning problem. The proposed approach is based on converting the problem into Traveling Salesman Problem which is solved using Genetic Algorithms on Graphical Processing Unit (GPU). The parallel genetic algorithm devised for GPUs has been compared to the alternative algorithms and found to be promising in terms of speed-up. We also present a thorough analysis of the implemented algorithm for several cases using different parameter values.

Subject Keywords

Theoretical Computer Science, Software, Information Systems

URI

https://hdl.handle.net/11511/52328

Journal

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING

DOI

https://doi.org/10.1007/s10766-011-0171-8

Collections

Graduate School of Natural and Applied Sciences, Article

Suggestions

OpenMETU
Core

A parallel algorithm for flight route planning on gpu using cuda Sancı, Seçkin; İşler, Veysi; Department of Computer Engineering (2010) Aerial surveillance missions require a geographical region known as the area of interest to be inspected. The route that the aerial reconnaissance vehicle will follow is known as the flight route. Flight route planning operation has to be done before the actual mission is executed. A flight route may consist of hundreds of pre-defined geographical positions called waypoints. The optimal flight route planning manages to find a tour passing through all of the waypoints by covering the minimum possible distanc...
Solving the area coverage problem with UAVs: A vehicle routing with time windows variation Semiz, Fatih; Polat, Faruk (Elsevier BV, 2020-4) In real life, providing security for a set of large areas by covering the area with Unmanned Aerial Vehicles (UAVs) is a difficult problem that consist of multiple objectives. These difficulties are even greater if the area coverage must continue throughout a specific time window. We address this by considering a Vehicle Routing Problem with Time Windows (VRPTW) variation in which capacity of agents is one and each customer (target area) must be supplied with more than one vehicles simultaneously without v...
An exact and a heuristic approach for the transportation-p-facility location problem Das, Soumen Kumar; Roy, Sankar Kumar; Weber, Gerhard Wilhelm (Springer Science and Business Media LLC, 2020-01-30) The delineation of the transportation network is a strategic issue for all over the place. The problem of locating new facilities among several existing facilities and minimizing the total transportation cost are the main topics of the location network system. This paper addresses the transportation-p-facility location problem (T-p-FLP) which makes a connection between the facility location problem and the transportation problem, where p corresponds to the number of facilities. The T-p-FLP is a generalizati...
A simulation study of ad hoc networking of UAVs with opportunistic resource utilization networks Lilien, Leszek T.; BEN OTHMANE, Lotfi; Angın, Pelin; DECARLO, Andrew; Salih, Raed M.; BHARGAVA, Bharat (Elsevier BV, 2014-02-01) Specialized ad hoc networks of unmanned aerial vehicles (UAVs) have been playing increasingly important roles in applications for homeland defense and security. Common resource virtualization techniques are mainly designed for stable networks; they fall short in providing optimal performance in more dynamic networks such as mobile ad hoc networks (MANETs)-due to their highly dynamic and unstable nature. We propose application of Opportunistic Resource Utilization Networks (Oppnets), a novel type of MANETs, ...
A flexible reference point-based multi-objective evolutionary algorithm: An application to the UAV route planning problem DAŞDEMİR, ERDİ; Köksalan, Mustafa Murat; TEZCANER ÖZTÜRK, DİCLEHAN (Elsevier BV, 2020-02-01) We study the multi-objective route planning problem of an unmanned air vehicle (UAV) moving in a continuous terrain. In this problem, the UAV starts from a base, visits all targets and returns to the base in a continuous terrain that is monitored by radars. We consider two objectives: minimizing total distance and minimizing radar detection threat. This problem has infinitely many Pareto-optimal points and generating all those points is not possible. We develop a general preference-based multi-objective evo...

Citation Formats

S. Sanci and V. İşler, “A Parallel Algorithm for UAV Flight Route Planning on GPU,” INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING, pp. 809–837, 2011, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/52328.