Abstract

The rapid proliferation of Unmanned Aerial Vehicles (UAVs) in safety–critical and time-sensitive applications such as disaster management, battlefield reconnaissance, urban surveillance and infrastructure inspection demands online path planning strategies. A fundamental requirement in such missions is generating flight paths that pass through some pre-specified waypoints while servicing dynamically requested spatio-temporal task points arriving randomly such as capturing aerial imagery. Existing UAV path planning approaches, including A* and its variants, meta-heuristic algorithms, and dynamic programming, find the shortest distance path from source to destination, but they are predominantly offline and assume complete prior environmental knowledge, thus, incur significantly higher computational cost to process the entire problem space before producing a solution. Consequently, they are ill-suited for dynamic real-world scenarios where tasks arrive unpredictably, and environmental conditions continuously evolve. In addition, the shortest distance does not always mean the fastest or safest route due to congestion or other environmental conditions, such as wind speed. This paper addresses this critical gap by presenting the first completely online, reward-maximizing UAV path planning framework that simultaneously handles dynamically arriving task requests, pre-assigned waypoints, and on-the-go environmental uncertainty without requiring complete prior knowledge or periodic re-optimization. This work presents a greedy Online Dynamic Path Planning algorithm (ODP) modeled as a multiple choice knapsack problem where-the task have rewards earned on completing while satisfying the waypoints with a limit on the total traverse time. Next, we extend ODP to Multidimensional Online Dynamic Path Planning Algorithm (MODP) that is both time bound and distance bound greedy online dynamic path planning algorithm. We model the problem as Online Multiple choice Multidimensional Knapsack Problem where the task points with lower accessibility of task points have higher rewards associated. We analyze the efficiency of ODP (an online approach), and compare its performance empirically with that of the optimal offline (Brute Force) algorithm. It was found that ODP provides a competitive ratio cr(alg)2

Department(s)

Computer Science

Publication Status

Full Text Access

Keywords and Phrases

Multidimensional knapsack; Online algorithm; Path planning; UAV

International Standard Serial Number (ISSN)

0921-8890

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2026 Elsevier, All rights reserved.

Publication Date

01 Oct 2026

Download

Full Text Link

Share

 
COinS