Online Dynamic Path Planner for Uavs
Abstract
Unmanned Aerial Vehicles (UAVs) flight path generation that passes through specified waypoints while satisfying spatio-temporal task points (delivering goods or taking aerial pictures) is an important application in battlefield and disaster management among others. Most of the previous work on UAV path planning has been on finding a shortest distance path from source to destination. However, the shortest distance does not always mean fastest route due to congestion or other environmental conditions such as rain, storm, wind etc, passing by aerial objects and no fly zone that may affect the speed/direction of the UAV. Moreover most of these approaches are offline (using A* type algorithms) and hence cannot respond to the dynamically changing environmental conditions when the number of dynamic task points increases. In this paper, we present a greedy Online Dynamic Path Planning algorithm (ODP) considering the dynamically changing requests of tasks, and the environmental conditions. We model the problem as an online multiple choice knapsack problem where-the task points have rewards (earned on completing tasks on the path) and the aim is to maximise the sum of reward points earned on completing the tasks on the path while satisfying the way points with a limit on the total traverse time. To analyze the efficiency of ODP (an online approach), we compare its performance empirically with that of the optimal offline (brute force) algorithm. It was found that ODP provides a competitive ratio (competitive ratio is defined as the ratio of performance of an online algorithm to that of the optimal offline algorithm in the context of algorithm analysis) of 0.8 indicating a near-optimal performance. That is, ODP returns a path that obtains about 80% of the optimal rewards.
Recommended Citation
M. Wadhwa et al., "Online Dynamic Path Planner for Uavs," Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST, vol. 594 LNICST, pp. 294 - 315, Springer, Jan 2024.
The definitive version is available at https://doi.org/10.1007/978-3-031-63992-0_20
Department(s)
Computer Science
Keywords and Phrases
Knapsack; Online; Path Planning; UAV
International Standard Book Number (ISBN)
978-303163991-3
International Standard Serial Number (ISSN)
1867-822X; 1867-8211
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2024 Springer, All rights reserved.
Publication Date
01 Jan 2024
