A Multi-UAV Router and Scheduler for Executing Spatially Scattered Real-Time Tasks

Recent advancements in computing and communication technologies have led to a surge in Internet of Things (IoT) applications across various domains such as smart cities, industrial automation, healthcare, smart agriculture etc,. These IoT applications often require continuous control, sensing, and actuation, with strict demands on timeliness and reliability. For example, IoT-enabled smart agricultural systems monitor soil conditions and crop health in real-time, allowing for automated irrigation and fertilization based on live data feeds [30]. Similarly, predictive maintenance in industrial IoT (IIoT) leverages real-time data to monitor equipment performance, preventing unexpected breakdowns and optimizing operational efficiency [17]. In traffic management, IoT systems can monitor vehicle flow and congestion, detect road hazards, air quality etc. to perform real-time adjustments in traffic signals for improving road safety and reduce delays [1]. As the number and complexity of these IoT applications continue to grow, there is an increasing need for flexible/scalable computation and communication solutions in order to support the high bandwidth, low-latency processing and connectivity demands.

Traditionally, computation, sensing and communication needs of IoT applications have been met using local on-board facilities. However in recent times, the limited processing facilities available on-board often become overwhelmed as the applications become progressively smarter, distributed, heterogeneous and complex in nature. To address this challenge, IoT systems have sometimes resorted to remote computation on nearby edge servers. Equipped with high bandwidth communication, such edge-based systems can become an attractive alternative mechanism for executing real-time IoT applications in diverse domains like agriculture, transportation, emergency response etc. However in many scenarios, such as remote or rapidly changing environments, fixed edge infrastructure may not be readily available.

To alleviate this problem, mobile edge computing implemented with Unmanned Aerial Vehicles (UAVs), are being envisaged as vital enablers for executing real-time IoT applications, particularly in environments where fixed infrastructure is either unavailable or impractical. Equipped with onboard processing capabilities and sensors, such as cameras, radar, and RFID readers, UAVs can independently handle real-time data acquisition and edge computation. Amodu et al. (2023) emphasize the crucial role of UAVs integrated with mobile edge computing to enable efficient data acquisition, processing, and communication in real-time scenarios [2]. This unique capability allows UAVs to perform end-to-end data collection, processing, and communication, making them indispensable for a wide range of mission-critical applications, particularly in environments where real-time performance is essential. For instance, in precision agriculture, UAVs equipped with multispectral sensors and onboard data processing capabilities monitor vast farmland areas, providing insights on crop health to optimize resource use and increase yields [4]. In search and rescue operations, UAVs equipped with thermal imaging sensors can rapidly scan large regions, providing real-time data on survivor locations [20]. Likewise, in urban environments, UAVs can analyze real-time video feeds to detect traffic congestion, accidents, or hazards, enabling quick interventions to improve traffic flow and safety [16]. By handling both sensing and computation onboard, UAVs eliminate the need for fixed edge servers, functioning as adaptable, autonomous platforms capable of meeting the dynamic demands of modern IoT applications.

The fundamental challenges in efficiently scheduling and routing UAVs for real-time task execution are closely related to classical combinatorial optimization problems, notably the Traveling Salesman Problem (TSP), Vehicle Routing Problem (VRP), and Dial-a-Ride Problem (DARP). To efficiently manage the spatial distribution and time-sensitive execution of UAV tasks, these optimization problems offer valuable modeling insights. One such optimization problem, the Traveling Salesman Problem (TSP), seeks the shortest possible route visiting a set of locations exactly once and returning to the starting point, providing a foundational structure for single-UAV route planning [3]. On the other hand, the Vehicle Routing Problem (VRP) extends TSP by considering multiple vehicles originating from a depot, each serving a subset of locations, thus naturally aligning with multi-UAV deployment scenarios [24]. Further, the Dial-a-Ride Problem (DARP) is a dynamic version of $VRP$ that generalizes VRP by introducing time-window constraints and pairing pickup and delivery points, making it particularly relevant for UAV-based real-time task execution where both timing and capacity constraints are critical [9].

In literature, the VRP and its variations have been widely studied, resulting in rich modeling frameworks and solution strategies that are highly relevant to UAV-based systems. For example, the Capacitated VRP (CVRP) imposes load capacity constraints on vehicles, while the Capacitated Electric Vehicle Routing Problem (CEVRP) incorporates limited driving ranges and non-linear charging behaviors, modeling the operational challenges faced by electric vehicles (EVs) [14, 15]. These VRP variants have seen extensive application in domains such as logistics, supply chain management, public transportation, and more recently, green transportation networks. Major industries including DHL, FedEx, XPO, and JD Logistics deploy VRP-based solutions for optimizing fleet operations under resource and energy constraints. Similarly, DARP has been instrumental in designing and optimizing on-demand ride services, paratransit operations, and dynamic shuttle systems, where tasks (pickups/deliveries) arrive dynamically, and operational schedules must adapt in real time. Importantly, these VRP/DARP modeling concepts extend beyond logistics or transportation and are equally applicable to mobile robotic systems like Unmanned Aerial Vehicles (UAVs), Terrestrial Mobile Robots (TMRs) and Underwater Unmanned Vehicles (UUVs).

Drawing inspiration from these classical optimization problems, this work majorly concentrates on the real-time execution of a given set of spatially dispersed, static, periodic/ aperiodic control tasks using a minimum number of UAVs, by jointly optimizing per-UAV routing, task hovering durations and deadline-constrained task execution. Despite the numerous advantages, UAV-based IoT systems encounter significant challenges in reliably executing tasks within strict real-time deadlines. Efficient deployment and routing strategies are crucial for UAVs to effectively cover large areas or manage numerous spatially distributed tasks. Typically, these strategies are divided into static and dynamic approaches. Many deployments position UAVs at fixed locations within statically defined layouts, such as at the intersection points of logical grids. However, these static methods often lack flexibility to adapt to changes in user demand, task urgency, or environmental conditions [12]. In contrast, dynamic strategies allow UAVs to adjust their positions and routes in real-time to improve coverage, reduce latency, and enhance network reliability [32, 31, 29, 28].

Zhou et al. (2018) proposed an online multi-UAV repositioning methodology to dynamically adjust coverage based on emerging temporary events [32]. Building on this, Zhang and Duan (2019) introduced a fast UAV placement method to enhance wireless coverage and connectivity in areas with limited infrastructure [31]. The work by Zeng et al. (2016) optimized UAV paths to maximize data throughput in mobile relay systems [29]. To further improve communication efficiency, Zeng et al. (2018) designed UAV multicast schemes to minimize transmission time when delivering data to multiple ground users [28].

Recently researchers have also delved towards optimizing combined routing and hovering strategies for UAVs with the objective of enhancing distributed sensing and computation [2, 26, 8, 27]. Yu et al. (2020) developed an approach for using UAVs as mobile edge computing nodes and focused on joint task offloading and resource allocation to optimize energy efficiency and computational load balancing [27]. Yang et al. (2020) and Chen et al. (2024) designed real-time routing algorithms, which also take into account necessary hovering time for the execution of aperiodic real-time tasks using UAVs [26, 8]. The objectives of these works are to maximize the number of tasks that can be completed before their deadlines, and/or minimize energy consumption.

In this work, we consider both periodic as well as aperiodic, real-time tasks that are spatially distributed at fixed locations across a remote isolated region. Applications such as precision agriculture, search and rescue operations, traffic management, etc. are suitable candidates for these types of tasks. Applications such as say, continuous crop health monitoring and controlled fertilizer/ water delivery (in precision agriculture), are usually persistently repeating with specific sampling periodicities. Moreover, the application set may consist of multiple instances of the same type of application; for precision agriculture say, different application instances may be employed to serve distinct agricultural fields at different locations. In any case, the applications being static and periodic, the overall system has a hyperperiodically repeating cyclic nature. Within a hyperperiod, an application executes for a certain number of task instances. For such a scenario, this work considers the employment of a set of UAVs as real-time processing/ sensing resources, and proposes an efficient heuristic called UAV Scheduling and Routing Algorithm for Real-time Tasks - Periodic Arrivals (USRART-P).

Further, adapting this framework for aperiodic task scenarios, we develop two additional heuristic strategies: $𝑼𝑺𝑹𝑨𝑹𝑻\mathbf{-}𝑺𝑨$ for Synchronous Aperiodic Arrivals (common arrival time, distinct deadlines) and $𝑼𝑺𝑹𝑨𝑹𝑻\mathbf{-}𝑨𝑨$ for Asynchronous Aperiodic Arrivals (distinct arrival times and deadlines). $USRART\text{-}SA$ is applicable to scenarios where multiple aperiodic tasks are triggered simultaneously by a single critical event. A representative example of such a scenario can be industrial facility accident management. For instance, in the event of a fire outbreak at a chemical plant at $t=0$, multiple UAV tasks such as toxic gas sensing, pipeline integrity checks, and perimeter thermal scans, may be simultaneously launched to assess the situation. These tasks may have distinct urgency driven deadlines. For example, toxic gas sensing can be considered the most urgent and may have a shorter deadline compared to pipeline integrity check and thermal scan. $USRART\text{-}SA$ is designed to manage such synchronously triggered yet deadline-diverse tasks, ensuring timely and prioritized execution.

Certain aperiodic tasks may have known arrival times within a specified time horizon, enabling higher scheduling flexibility compared to systems with synchronous task arrivals. In such scenarios, $USRART\text{-}AA$ can be usefully applied. An example scenario arises with UAV-based last-mile delivery in smart logistics. In this context, package pickup and drop-off requests are specified with known release times and associated delivery deadlines within the operational horizon. For instance, it may be pre-scheduled that an urgent medical supply delivery task becomes available at time $t=5$, while a food delivery request is set to arrive at $t=12$. Further, medical supply delivery being more urgent may have a shorter relative deadline compared to food delivery. For such an use-case, $USRART\text{-}AA$ can proactively schedule UAV routes, ensuring that each request is served within its deadline while maintaining efficient utilization of the UAV fleet.

All three variations of $USRART$ assume that each member of the set of UAVs starts from the same depot location at the beginning of a time horizon and flies over a subset of the task locations following a designated route, returning back to the depot by the end of that time horizon. During the traversal in its route, a UAV follows an alternating sequence of movement and hovering operations. The movement operation takes a UAV from one task location to another. At each task location, the UAV hovers for a specific time duration during which, it performs sensing and processing for the task. With the aim of minimizing the number of UAVs required, this work proposes an efficient methodology for generating per-UAV routes and deadline-meeting execution schedules for all tasks, aiming to maximize the subset of tasks that can be covered by each route. The major contributions of this work are thus summarized as follows:

• $\mathrm{■}$

  This is possibly the first research work that presents a mechanism for UAV-based execution of a set of geographically distributed, periodic as well as aperiodic real-time applications. We have systematically analyzed the underlying problem structure and represented it in the form of a constraint optimization formulation.

• $\mathrm{■}$

  We have proposed an efficient but low-overhead heuristic approach called “UAV Scheduling and Routing Algorithm for Real-time Tasks ($USRART$)”, for the problem at hand. With the aim of minimizing the number of UAVs, $USRART$ generates routes with deadline-meeting task schedules for each UAV.

• $\mathrm{■}$

  We propose three adaptations of $USRART$ namely, $USRART-P$ for periodic real-time tasks, $USRART-SA$ for synchronously arriving aperiodic tasks and $USRART-AA$ for asynchronous aperiodic tasks with known arrival times.

• $\mathrm{■}$

  We have conducted extensive simulations to rigorously evaluate our algorithms using diverse datasets inspired by plausible real-world scenarios. Our experiments span a wide range of conditions, varying task densities, spatial distributions, task execution times, and UAV speeds. The experimental results show that all variations of USRART consistently deliver appreciable performance across diverse test cases, highlighting their robustness, generic nature, and practical applicability.

The remainder of this paper is organized as follows: Section 2 presents the system model and problem formulation. Section 3 provides a detailed description of the proposed algorithm. Finally, Section 4 discusses the experimental setup and results, demonstrating the effectiveness of our proposed approach.

We consider here, a real-time military surveillance system described as follows. The system requires to surveil seven geographically scattered sites ($lo{c}_1,\mathrm{\dots },lo{c}_7$) within a given region of size 10 km × 10 km, as shown in Fig. 1. Each site is surveilled by a UAV which periodically comes and performs surveillance. This surveillance job is conducted by scanning and collecting information (such as potential enemy movements and/or rescue needs) from the area of the site, with the help of camera-equipped UAVs or via cameras installed at terrestrial locations. In addition, the UAVs may also be equipped with processing power in order to say, perform periodic adjustments of the pan-tilt-zoom settings of the installed cameras, based on received image/video feeds. The activities in a job thus include scanning, data transmission (information collection) and computation. The potential sequence of jobs $⟨T_{i1},T_{i2},\mathrm{\dots }⟩$ associated with a particular site say $lo{c}_i$, constitutes a distinct periodic real-time application $T_i$. The execution time $E_i$ (of $T_i$) depends on the total time required by a UAV to perform all the mentioned activities associated with a job say, $T_{ij}$. This execution time depends on factors such as, area of the site to be scanned, number of installed cameras, size of transmitted data and computation time required to generate control outputs say, new pan-tilt-zoom setpoints. Periodicity of surveillance may depend among other factors on the sensitivity of the site w.r.t surveillance. Thus, high-risk sites which are say, prone to enemy activity, may require to be more frequently surveilled at shorter intervals, compared to others.

Table 1 depicts the execution times, periods, and site locations of all the seven periodic applications considered in the problem. The hyper-period of these applications is $H=30$. The number of jobs of each application within one hyper-period has also been shown in Table 1. The objective of the problem is to deploy the minimum among a set of available UAVs which are homogeneous in terms of their flight speed (here, 30 km/h), processing capability, as well as data collection/transmission rate. All deployed UAVs should start from their designated depot location ($lo{c}_D=(5,5)$) at the beginning of each hyper-period, cover a subset of jobs, and return back to the depot by the end of the hyper-period. Fig.1 shows a solution to this problem scenario using the proposed algorithm $USRART$ (described later). It may observed that $USRART$ requires the deployment of four UAVs to solve this periodic real-time routing cum scheduling problem. The above running example is motivated by the real-world military surveillance operation

The above example is motivated from the requirements of modern day military surveillance (as detailed in [18]) which underscore the critical need for efficient UAV routing and task allocation in remote, high-risk environments.

Unlike periodic tasks, aperiodic applications are modeled as single-instance tasks. The system model considers $l$ aperiodic tasks $I_1\mathrm{\dots }{I}_l$, each arriving at arbitrary times rather than following a periodic pattern. The attributes associated with an aperiodic task has however been kept exactly same as that of a single periodic task instance, discussed above; an aperiodic task $I_j$ is described as $I_j$: $⟨I_j^{aid},I_j^{rt},I_j^d,I_j^e,I_j^{loc},I_j^{trt},I_j^{st},I_j^{ct},I_j^s⟩$. The only difference is that, unlike the periodic model where each job instance carried a distinct job identifier ($I_j^{tid}$) corresponding to its instance in the periodic sequence, the aperiodic model omits this job ID, as each application represents a unique, single-occurrence task. The aperiodic model supports two subclasses of aperiodic arrivals in this work: $USRART-SA$ and $USRART-AA$ as described in the Introduction section. All other assumptions and structural elements of the system model – such as UAV capabilities, depot behavior, and routing formulation – remain consistent with those described for the periodic case.

$USRART$ takes as input a set $T=\{T_1,T_2,\mathrm{\dots },T_n\}$ of n applications. The output of the algorithm is a route set ($RS$), which contains the routes for all deployed UAVs. The algorithm begins with four initialization steps. Line 1 initializes the global list of task instances ($I$) from the input application set ($T$) and computes essential attributes for each task instance $I_j(\in I)$ including, release time ($I_j^{rt}$), deadline ($I_j^d$), execution time ($I_j^e$), and location ($I_j^{loc}$) (Refers Section II, System Model). In Line 3 we initialize a boolean array map[] of size $l=|I|$. An element $\text{map}[j]=1$, indicates that task instance $I_j$ has already been mapped to a UAV route; $\text{map}[j]=0$, if $I_j$ is still unmapped. Line 4 initializes a global array thread[], which threads together the first instances of each application $T_i$ within list $I$. Lines 5-8 initiate an iterative process where UAVs are deployed sequentially until all task instances are assigned. In each iteration, the $URG$ (UAV Route Generator) function is called to compute an efficient route $r_{\alpha }$ based on task constraints, for a new UAV $U_{\alpha }$. The route is then added to the UAV route set $RS$, and the process repeats until all tasks in $I$ are mapped. Example Continued: Following table 1, we generate a set of task instances $I=\{I_1,I_2\mathrm{\dots }{I}_{16}\}$, derived from the given set of seven applications. For each $I_j$, the algorithm computes $I_j^{rt}$, $I_j^d$, $I_j^e$ and $I_j^{loc}$. As example, for $I_5$$(I_{({\varphi }_{1+2})}$; $2^{nd}$ instance $T_{22}$ of $T_2$) we have, $I_j^{rt}$ = 30, $I_j^d$ = 45, $I_j^e$ = 0.5 and $I_j^{loc}$ = (7,2). The array thread[] which holds position indices (within list $I$) of the first instances of each application, gets initialized as thread[] = $⟨1,4,6,7,10,13,14⟩$.

The $𝑼𝑹𝑮$ (UAV Route Generator) function is designed to generate an efficient route for each UAV ($U_{\alpha }$). The algorithm takes two inputs: the UAV identifier $\alpha$ and an array map[] that tracks task instances that have not yet been assigned to any UAV. The output is a route $r_{\alpha }$ which specifies the sequence of task instances assigned to $U_{\alpha }$.

The while loop in Lines 5 to 28 sequentially adds new task instances to UAV $U_{\alpha }$’s route $r_{\alpha }$ as long as the total route time $t_c$ remains less than the hyper-period $H$. At any time during partial route generation, the for loop in Lines 7 to 22 attempts to append the best task instance (whose index in $I$ is stored in $bes{t}_{id}$) among all unmapped instances over all applications, to the current partial route $r_{\alpha }$ = $⟨r_{\alpha 1},r_{\alpha 2},\mathrm{\dots },r_{\alpha k}⟩$. For any given application $T_i$, the while loop in Lines 8 to 22 first attempts to find the earliest instance of $T_i$ that can be feasibly accommodated into $U_{\alpha }$’s route. For an unmapped candidate task instance say $I_j$ to be eligible for inclusion into $r_{\alpha }$ at position $r_{\alpha (k+1)}$, the following conditions must be satisfied. First, the UAV which is at location $I_{r_{\alpha k}}^{loc}$ at time $t_c$ must be able to travel to $I_j$’s position, then either start immediately or wait (Refer eq. 4) until the release of $I_j$ at time $I_j^{rt}$ (Refer eq. 1), and finally be able to complete execution before $I_j^d$ (Refer eq. 2), the deadline of $I_j$. The deadline check is performed as part of the condition in Line 13. The condition in Line 17 is necessary to ensure that the length of route $r_{\alpha }$ remains within the hyper-period duration $H$ after the inclusion of $I_j$. If a candidate instance $I_j$ is deemed to be feasible, its Goodness $G_j$ is computed in Line 21. The value of Goodness which is used to determine the most eligible candidate task instance $I_j$ that should be added to $r_{\alpha }$ at $r_{\alpha (k+1)}$, is computed as:

In the above equation, $S_j$ denotes the tentative relative slack that will remain after completion of execution, if $I_j$ is actually selected for inclusion at $r_{\alpha (k+1)}$. The value of $S_j$ is computed as: $S_j=I_j^s/{\max }_{\forall i\in T}\left(P_i-E_i\right)$, where $I_j^s$ is the actual tentative slack (Refer eq. 6) associated with $I_j$’s inclusion, and ${\max }_{\forall i\in T}\left(P_i-E_i\right)$ denotes the maximum possible slack that may possibly be enjoyed by any task in the system. A lower value of $S_j$ indicates a relatively higher urgency w.r.t inclusion of $I_j$ in $r_{\alpha }$; thus in equation 12, $G_j\propto 1/S_j$.

The value of $To{t}_j$ is computed as: $To{t}_j=(I_j^{st}-I_{r_{\alpha k}}^{ct})/({\max }_{\forall i,j\in T}\left(D(lo{c}_i,lo{c}_j)/s+P_j\right))$, where $(I_j^{st}-I_{r_{\alpha k}}^{ct})$ represents the total travel time and waiting time that must be spent by UAV $U_{\alpha }$, after completion of the last task instance ($I_{r_{\alpha k}}^{ct}$) in its current partial route, and before the start ($I_j^{st}$) of $I_j$’s execution. On the other hand, ${\max }_{\forall i,j\in T}\left(D(lo{c}_i,lo{c}_j)/s+P_j\right)$ represents the maximum travel and waiting time that can possibly be spent by a UAV $U_{\alpha }$ between the completion of execution of a task instance and start of execution of the next instance, in any feasible route $r_{\alpha }$ which does not violate deadlines. It may be noted that for a candidate instance $I_j$, if $To{t}_j$ is relatively higher, it indicates that the UAV wastes relatively more time travelling and waiting than more useful task execution, ultimately resulting in lower resource utilization. Thus, $G_j\propto 1/To{t}_j$.

The parameter ${𝒟}_j$ quantitatively represents the relative density of tasks within a stipulated radius¹¹1$\lambda$: The value of $\gamma$ is an input constant to the problem and remains same for all tasks $\gamma$ around $I_j$’s location. Density ${𝒟}_j$ is formulated as: ${𝒟}_j=(T_{\text{max}}^{\gamma }-T_j^{\gamma })/(T_{\text{max}}^{\gamma }-T_{\text{min}}^{\gamma })$ where, $T_j^{\gamma }$ denotes the number of tasks within radius $\gamma$, around $I_{lo{c}_j}$, while $T_{\text{max}}^{\gamma }$ ($T_{\text{min}}^{\gamma }$) is the maximum (minimum) number of tasks found within radius $\gamma$, across all task locations within the region being considered in the problem. For a candidate instance $I_j$ a relatively higher value of ${𝒟}_j$ indicates a lower density of tasks around $I_j^{loc}$. It may be noted that, if a candidate $I_j$ located in a sparsely dense area is selected for inclusion in $U_{\alpha }$’s route, the likelyhood of higher travel and waiting times in the future route of $r_{\alpha }$, will increase. Thus, $G_j\propto 1/{𝒟}_j$.

In equation 12, $G_j$ has been designed to be inversely proportional to the linear combination of $S_j$, $To{t}_j$ and ${𝒟}_j$. Here, $w_1,w_2,w_3$ are positive quantities; $w_1+w_2+w_3=1$. If $G_j$ is better than the best Goodness seen so far ($bes{t}_G$; Line 21), $bes{t}_{id}$ and $bes{t}_G$ are updated (Line 23). After all instances have been considered, the instance $I_{bes{t}_{id}}$ is added to $r_{\alpha }$ (Line 27), current time and route length are updated (Lines 28 and 29) and $I_{bes{t}_{id}}$ is marked as mapped (Line 30). Finally we consider the case where no new task instances can be feasibly added to the current route $r_{\alpha }=\{r_{\alpha 1},\mathrm{\dots },r_{\alpha k}\}$. In this case, $bes{t}_{id}$ remains null after evaluating all task instances. We set the route length and add the destination dummy instance ${\delta }_{\alpha }$ to route $r_{\alpha }$, in Line 25 and update total route time ($I_{{\delta }_{\alpha }}^{ct}$) in Line 26.

Example Continued: Continuing further with our running example (Refer “An Example System”, Section 2, and “Example Continued”, Section 4.1), Table 2 presents the final UAV routes and execution schedules generated by $USRART-P$ for the scenario described earlier. It may be observed that the solution requires four UAVs $\{U_1,\mathrm{\dots },U_4$}. Out of the 16 task instances in $I$, $U_1$ covers six instances, $U_2$ and $U_3$ covers three instances each, while $U_4$ covers four instances. The table also depicts the relative slack $S_j$, relative total time $To{t}_j$, relative density $D_j$, Goodness $G_j$, start time $I_j^{st}$ and completion time $I_j^{ct}$ for each instance $I_j$. Gantt charts of the final routes and schedules have also been depicted in Fig. 2. We see that as is necessary, total route times for all UAVs is less that $H=30$. A diagramatic representation of the final routes has been shown in Fig. 1.

The aperiodic variant $USRART-AA$ retains the overall structure of $USRART-P$ but introduce key changes to handle possibly distinct but known arrivals as well as deadlines. Feasibility is now checked by ensuring that each task starts no earlier than its arrival time and completes before its deadline. The pseudocode for this scenario is presented in Algorithm 3. A new array, skip${}_{\alpha }{}^{}[]$, tracks tasks that UAV $U_{\alpha }$ cannot feasibly serve, enabling early pruning and improving efficiency. The while-loop is updated: unlike the periodic case where tasks were added while route time $t_c$ stayed below hyper-period $H$, here it continues until all tasks are scheduled or skipped. Also, unlike $USRART-P$ which used a thread[] array to manage multiple task instances, aperiodic tasks are treated as single applications without instances. Further, in cost calculations, the parameter period in relative slack and relative total time terms ($S_j$, $To{t}_j$) is replaced by the task’s deadline to align with aperiodic constraints. The rest, including density formulations and overall cost structure, remains as in $USRART-P$. $USRART-SA$ is identical to $USRART-AA$ except the fact that $USRART-SA$ assumes a common arrival time unlike $USRART-AA$ which handles individual known arrivals.

An exhaustive set of experiments has been performed using carefully designed synthetic datasets to evaluate the performance of $USRART$ in various plausable real-world scenarios that it may encounter in practice. To derive essential real-time task parameters such as periodicities and execution times, we have conducted relevant surveys on real-world UAV application scenarios. For example in precision agriculture, UAVs are utilized for crop health monitoring, pest detection, and irrigation management, which require detailed flight paths over agricultural fields, data capture via sensors, and real-time data analysis. Each task typically takes between 5 to 15 minutes, considering the time required for UAVs to navigate the area, capture necessary data, and transmit it for processing [25]. Similarly, traffic management applications, where UAVs monitor traffic flow, congestion, or accidents, demand high-resolution imaging and density estimation. These tasks usually require 20 to 25 minutes per zone, depending on the area size and urban density [11]. Other significant UAV applications include search and rescue missions, where UAVs navigate disaster zones to locate victims or deliver supplies. These operations typically require around 30 minutes, as the UAVs must cover large areas while coordinating with on-ground teams [10]. In military contexts, UAVs are used for surveillance and reconnaissance, with missions ranging from 15 to 45 minutes, influenced by the complexity of the task and the geographical challenges involved [18]. Additionally, UAVs are increasingly used for environmental monitoring, for tasks like air quality assessment, water resource management, and deforestation analysis, with tasks typically taking 14 to 20 minutes for comprehensive data collection and processing [6]. Based on the above studies we have attempted to construct a data generation framework which should be able to ensure that experimental analysis is applicable to real-world scenarios while being also adaptable for future benchmarking efforts. The common parameters used in the experiments discussed in Section 6.2 below, are described as follows:

• $\mathrm{■}$

  Application locations: Locations are randomly generated using a uniform distribution within a fixed grid size of $10km\times 10km$ for all experiments apart from experiment 3. In experiment 3, we have generated the locations using a normal distribution as discussed later in Section 6.2.

• $\mathrm{■}$

  Application Count: In experiments 2 and 4, we run the heuristics for 50 applications whereas for experiments 1, 3, 5 and 6 we run them for both 50 and 100 applications.

• $\mathrm{■}$

  Application Periods: The period of each application, in the context of the periodic case experiments, is randomly selected uniformly from the range [10 mins, 50 mins], aligned with the application scenarios discussed above.

• $\mathrm{■}$

  Application Deadlines: For experiments 5 and 6, application deadlines are randomly selected within 20 to 180 minutes.

• $\mathrm{■}$

  Application Arrival Times: For experiments 5 and 6 (aperiodic tasks), arrival times are randomly selected within [0, 135] minutes. The range starts from 0 to align with the $USRART\text{-}SA$ case (where all applications arrive at $t=0$), while 135 minutes serves as the upper bound for varied arrival patterns.

• $\mathrm{■}$

  Application execution times: For experiments 1 to 4 (periodic tasks), application execution times are generated from the range [0.5 mins, 2.5 mins] using a normal distribution with mean $\mu =1.5$ mins and standard deviation $\sigma =0.5$ mins. To evaluate the impact of task execution time variation, execution times are progressively increased along the x-axis in steps of 10$\%$ for experiments 1, 2, and 4. For aperiodic task experiments (5 and 6), execution times also follow a normal distribution with $\mu =10$ mins and $\sigma =3$ mins, bounded between 0.5 and 19.5 minutes, with the same 10$\%$ incremental variation applied across both USRART-SA and USRART-AA.

• $\mathrm{■}$

  UAV speed: In Experiments 1,4 and 5 the UAV speed is fixed at 30 km/h (0.5 km/min) to maintain consistency in travel time calculations across different task counts. In Experiments 2,3 and 6, UAV speeds of 0.5 km/min, and 1 km/min are used to analyze the effect of the variation in speed on Average UAV Count.

The following two metrics have been used to evaluate the performance of $USRART$:

• $\mathrm{■}$

  UAV Count: The number of UAVs required to cover all task instances using a given heuristic algorithm, is calculated for each test case.

• $\mathrm{■}$

  Algorithm runtime: The proposed heuristic approaches are evaluated based on the time required to compute the UAV routes and associated task schedules.

To evaluate the performance of all variations of $USRART$ and compare them against baseline heuristic strategies, six experiments have been conducted. All experiments apart from experiment 4 measure the number of UAVs required to generate UAV routes and task schedules, against increase in task execution times, variations in task location density, change in UAV speeds and variation in the number of applications. Experiment 4 on the other hand, depict runtimes of the algorithms as task execution times are varied on the x-axis. The value of each result point in the plots for any of the depicted experiments represents the average over 500 test cases derived from a designated fixed set of parameter values. In order to compute Goodness for $USRART-P$, the parameters $S_j$, $To{t}_j$, and $D_j$ are multiplied with empirically derived weight constants $w_1=0.5$, $w_2=0.2$, and $w_3=0.3$, respectively. Similarly, for $USRAR{T}_{B2}$ in the periodic setting, we use weight constants as $w_1=0.5$ and $w_2=0.5$ whereas in the aperiodic cases, we assign $w_1=0.4$ and $w_2=0.6$.

The methodologies developed in this work are not limited to UAV based systems but can be applied to other autonomous mobile systems operating in similar constrained and dynamic environments. Two representative domains are discussed below:

For obtaining accurate solutions through the proposed framework, a few practical operational constraints may be needed to be considered depending on the specific deployment scenario at hand. A few important operational constraints include:

• $\mathrm{■}$

  Battery Constraints: UAVs have limited battery capacity, and their energy consumption varies based on flight dynamics, hovering time, and onboard computation. Accurate energy modeling is crucial to prevent mission failures due to unexpected depletion. Recent studies have proposed mathematical models to capture these energy dynamics in the context of routing problems  [7].

• $\mathrm{■}$

  Recharging Logistics: Incorporating recharge or battery-swap stations adds further complexity to the scheduling and routing problem. This aspect aligns with the Electric Vehicle Routing Problem (EVRP), where vehicles plan their paths considering limited energy reserves and intermediate recharging stops [19]. Leveraging such ideas will be essential for extended-duration UAV missions.

• $\mathrm{■}$

  Environmental Factors: External environmental conditions, particularly wind and weather variability, significantly impact UAV flight stability, energy usage, and latency. Experimental studies have demonstrated how wind disturbances alter UAV performance [21]. Advanced nonlinear guidance and robust control techniques have also been proposed to ensure safe operation under strong wind conditions [23]. Integrating adaptive and robust planning mechanisms is critical for reliable UAV mission execution in varying environmental settings.