Research Article
Online Dynamic Path Planner for UAVs
@INPROCEEDINGS{10.1007/978-3-031-63992-0_20, author={Manisha Wadhwa and Neelima Gupta and Sanjay Madria}, title={Online Dynamic Path Planner for UAVs}, proceedings={Mobile and Ubiquitous Systems: Computing, Networking and Services. 20th EAI International Conference, MobiQuitous 2023, Melbourne, VIC, Australia, November 14--17, 2023, Proceedings, Part II}, proceedings_a={MOBIQUITOUS PART 2}, year={2024}, month={7}, keywords={Path Planning Knapsack UAV Online}, doi={10.1007/978-3-031-63992-0_20} }- Manisha Wadhwa
Neelima Gupta
Sanjay Madria
Year: 2024
Online Dynamic Path Planner for UAVs
MOBIQUITOUS PART 2
Springer
DOI: 10.1007/978-3-031-63992-0_20
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.
