Flying over The Uncertain Nature (FORTUNE): Intelligent and Humanistic 3D Path Planning for Low-Altitude Collaboration

1

Flying over The Uncertain Nature (FORTUNE): Intelligent and Humanistic 3D Path Planning for Low-Altitude Collaboration

arXiv:2608.03408v1 [cs.RO] 4 Aug 2026

Minghui Liwang, Senior Member, IEEE, Wenhan Jia, Xinlei Yi, Senior Member, IEEE, Wenbo Zhu, Yuhan Su, Xianbin Wang, Fellow, IEEE

Abstract—The proliferation of low-altitude intelligent agents is driving an increasing demand for timely and socially responsible collaborative sensing in dynamic urban environments. Nevertheless, jointly handling heterogeneous spatio-temporal sensing demands, real-time environmental uncertainty, and human-centered operational constraints within a unified multi-UAV optimization framework remains highly challenging. In this paper, we investigate three-dimensional (3D) multi-uncrewed aerial vehicle (UAV) path planning and joint task assignment for low-altitude collaboration under heterogeneous spatio-temporal uncertainty of ground points of interest (PoIs). Unlike existing studies that assume static and fully known PoIs, we formulate a unified model that simultaneously captures persistent (Type-I), temporally predictable (Type-II), and emergent unpredictable (Type-III) demands. Furthermore, following the principle of low-altitude for good, we explicitly model altitude-dependent societal and environmental costs, including noise exposure and public safety risks, thereby jointly optimizing sensing effectiveness and socially compliant UAV operations. To solve the resulting large-scale mixed-integer nonlinear optimization problem, we propose FORTUNE, a hierarchical offline-online cooperative framework. Offline, a Transformer-based predictor forecasts the activation windows of Type-II PoIs, while an enhanced sparrow search algorithm (ES2 A), empowered by priority-aware decoding and danger-aware evolution, proactively generates globally coordinated flight plans. Online, a lightweight trajectory refinement module efficiently accommodates newly emerging TypeIII PoIs while preserving global mission coherence. Extensive experiments on real-world traffic datasets and synthetic scenarios demonstrate that FORTUNE consistently outperforms state-ofthe-art benchmarks, validating its effectiveness, scalability, and practical applicability to dynamic low-altitude systems. Index Terms—Low-altitude economy, Multi-UAV collaboration, Socially-compliant, 3D path planning, Transformer

I. I NTRODUCTION RIVEN by their flexibility and affordability of low-altitude platforms, rapid advances in sensing/communication/computing have accelerated the deployment of uncrewed aerial vehicles (UAV)-enabled applications in urban monitoring, environmental surveillance, and intelligent transportation [1]–[3]. As a representative paradigm, low-altitude collaborative sensing leverages multiple UAVs to serve timely and large-scale perception for missions such as crowd flow observation and abnormal event detection (e.g., sudden gatherings, traffic accidents, and emergency incidents) [4]–[7]. Meanwhile, the commercial expansion of the UAV industry, projected to surpass $48.5 billion by 2029 [8], [9], further highlights its transformative potential in supporting next-generation intelligent systems. Nevertheless, practical multi-UAV collaboration faces fundamental challenges: ground points of interest (PoIs) are inherently dynamic and time-varying, with hotspots forming, shifting, and dissipating over short time scales (e.g., crowds relocating

D

M. Liwang (minghuiliwang@tongji.edu.cn), W. Jia (hxjiawh@gmail.com), X. Yi (xinleiyi@tongji.edu.cn), W. Zhu (wbzhu@tongji.edu.cn) are with the Department of Control Science and Engineering, Shanghai Institute of Intelligent Scienceleiy Technology, Tongji University, Shanghai, China. X. Wang (xianbin.wang@uwo.ca) is with the Department of Electrical and Computer Engineering, Western University, Canada.

across venues). Most existing studies oversimplify this reality by assuming PoIs are known a priori and static, or by merely adopting age-of-information (AoI) as a surrogate for data timeliness [1], [10], thereby limiting their applicability in realworld deployments. Meanwhile, the increasing density of lowaltitude UAV operations also raises societal and operational concerns, including public anxiety over potential crashes and noise disturbance. A. Motivations in Form of Q&A The above observations suggest that the challenge of lowaltitude collaborative sensing is not merely algorithmic, but structural: it concerns how dynamic task patterns should be abstracted, how anticipation and real-time adaptation should be reconciled, and how operational effectiveness should be balanced with humanistic impact within a unified optimization framework. Addressing these issues requires moving beyond incremental refinements of existing models toward a more principled formulation. Accordingly, answering the following research questions (RQs) forms our fundamental motivation. • RQ1: How can multi-UAV systems fundamentally characterize and handle heterogeneous, time-evolving sensing demands, instead of relying on the oversimplified assumption of static and known PoIs? Existing studies typically assume that sensing targets are fixed and known a priori, which substantially simplifies trajectory planning but departs from real-world lowaltitude scenarios where sensing demands exhibit heterogeneous spatio-temporal dynamics. To overcome this limitation, we adopt a structured view of task dynamics that distinguishes different levels of predictability and persistence in ground sensing demands, i.e., PoIs are classified into three types. This abstraction enables proactive planning over stable and partially predictable components while explicitly acknowledging intrinsic uncertainty, thereby bridging the gap between idealized static models and realistic dynamic environments. • RQ2: How can environmental and societal impact be rigorously embedded into 3D multi-UAV path optimization, so that sensing effectiveness and public acceptability are jointly considered rather than treated as secondary constraints? Low-altitude UAV operations inherently introduce trade-offs between sensing quality and societal impact, particularly due to altitude-dependent effects. For example, flying at low altitudes may inevitably generate noise, induce public anxiety over potential crashes, and raise privacy concerns regarding terrestrial environments, thereby disturbing both humans and wildlife on the ground. As this paper advocates the concept of “lowaltitude for good (LA4Good)”, it is essential to explicitly account for socially-compliant and environmental implications of low-altitude UAV deployments. Rather than treating these factors as external constraints, we integrate them directly into our optimization goal. By modeling a certain penalty, the resulting framework achieves a principled balance between task effectiveness and socially responsible operation. • RQ3: How can proactive planning and reactive adaptation be unified in multi-UAV 3D path design, such that predictable

2

Add & Norm Feed Forward

Linear Add & Norm Feed Forward Add & Norm Multi-Head Attention Add & Norm Masked Multi-Head Attention

Inputs (Historical PoI Data）

Type-I PoI

UAVs

Type-II PoI

Pre-planned path

Type-III PoI

Adjustive path

Obstacle

Active time window

Output Embedding Outputs (shifted right)

PoI I

…

…

𝑬𝑺𝟐 𝑨 Global Search

PoI II-B

PoI II

Threshold

…

…

PoI II-C …

A B C

D

t=2

Levy Flight Update

Fitness Heuristic Decoder Height and Avoidance: Joint 3D AvoidanceAltitude Decision Speed: Adaptive Selection

Initialization

Pre-planned paths

Feasible Task Set Construction

Module C: Online path adjustment when facing active Type-III PoIs

Threshold …

PoI II-D Threshold

…

…

Estimated active Time windows for each Type-II PoIs

… t=1

Module B: Evolutionary heuristic for pre-path planning over Type-I and Type-II PoIs

…

Input Embedding

Observation value

Positional Encoding

Positional Encoding

PoI II-A Threshold

…

Add & Norm Multi-Head Attention

Observation value

场景 地图之类的

Softmax

Observation value

…

Observation value

Timeline

Module A: Service demand prediction for Type-II PoIs empowered by Transformer

t=3

t=4

t

Net-BenefitGuided Greedy Allocation

Fig. 1: Schematic of FORTUNE, a 3D multi-UAV path planning framework over dynamic and uncertain PoIs, with three modules integrated solutions.

task patterns are efficiently exploited without sacrificing re- PoIs as static entities with a priori known locations. This sponsiveness to unexpected events? A fundamental tension in assumption often falls short of reality, as real-world networks dynamic collaborative sensing lies between long-term efficiency exhibit complex spatio-temporal dynamics. While Li et al. [10] and short-term responsiveness. Purely reactive strategies lead explored multi-task-oriented UAV crowdsensing with diverse to myopic decisions, whereas fully preplanned strategies fail AoI requirements and introduced a “valid task handling index”, under unforeseen events. We address this tension by developing their work approaches the problem from a fundamentally a planning paradigm that integrates anticipative path generation different perspective with us. Unlike these studies, we concern with globally consistent online refinement. By preserving dynamic and uncertain PoIs, where the varying activation awareness of the overall mission state during adjustments, the windows of them lead to sensing tasks with disparate timing framework enables rapid adaptation to emergent events while and locations. maintaining system-level coordination and efficiency. • View 2. Way to optimize UAV paths. Path planning involves complex spatio-temporal coupling where current decisions propagate through the temporal horizon, leading to exponential B. Literature Review complexity. Given the computational intractability of convenWe review existing related literature from various perspec- tional integer programming in high-dimensional multi-agent systems, research has shifted toward RL-based approaches, tives, further highlighting our key differences and novelty. • View 1. Static/known PoIs vs. uncertain PoIs over spatio- heuristic-driven methods, and hybrid ideas that integrate temporal evolution. Most existing studies regarding UAV- different methodologies. The rapid advancement of artificial intelligence (AI) has assisted data collection focus on known or fixed PoIs, which are typically modeled with predetermined parameters such as enabled an effective integration of deep neural networks with quantity, location, and active time windows. For instance, He RL, which are widely adopted path planning problems [11], et al. [11] implemented a two-timescale trajectory planning [13]–[16], [18]–[20]. For example, Yu et al. [20] studied scheme within a leader-follower control framework for known multi-UAV 3D trajectory planning strategy using multi-agent hotspot areas. Guo et al. [12] investigated hierarchical incentive deep reinforcement learning (MADRL), by employing multimechanisms for UAV-assisted crowdsensing while optimizing agent proximal policy optimization (MAPPO). Deng et al. data freshness within a fixed set of subregions. Similarly, [18] proposed a decentralized MADRL framework with multiYuan et al. [13] integrated transfer learning with reinforcement level state representations, facilitating personalized training and learning (RL) to solve 3D trajectory planning problems for better exploitation of environmental information. Gao et al. known ground user hotspots. Ye et al. [14] explored air-ground [19] applied multi-agent deep deterministic policy gradient cooperative crowdsensing by optimizing the AoI metric, where (MADDPG) to jointly optimize task allocation and trajectory vehicles dispatch UAVs from multiple stops to collect data from planning. Despite the efficacy in navigating dynamic envispecific PoIs, with multi-agent curriculum learning (MACL). ronments, its practical deployment remains constrained by Furthermore, Wang et al. [15] focused on urban data collection suboptimal sample efficiency, stochastic training instability, to maintain AoI within specified thresholds across diverse but and fragile scalability. Existing literature predominantly focuses known PoIs. Hou et al. [16] proposed a hierarchical optimization on restricted coordination scenarios, typically involving fewer framework for multi-UAV collaboration to jointly address than 10 agents (usually around 4), whereas scaling to denser trajectory planning, energy management, and load balancing, swarms triggers an exponential explosion of the joint statewhere each sensing task is tied to a specific target in a designated action space. This frequently precipitates gradient divergence area. Li et al. [17] studied air-ground collaborative sensing and computational collapse during policy optimization. where UAVs are guided along informative trajectories to reach To circumvent the above bottlenecks, a large body of research target positions rapidly. has pivoted toward heuristic-based frameworks. Although Although these works contribute significantly to UAV path rooted in classical optimization principles, they exhibit superior planning and data freshness (e.g., via AoI), they largely treat architectural scalability, computational parsimony, and structural

3

robustness, rendering them more viable for high-density, largescale systems. Wang et al. [21] presented a multi-vehicle path planning method based on multi-group cooperative particle swarm optimization (PSO), handling diverse intersections and traffic conditions. He et al. [22] investigated adaptive heuristic with collaborative search to for multi-UAV inspection path planning. Liu et al. [23] considered UAV energy, mapping efficiency, and target structure coverage while respecting hardware constraints, with two-stage heuristic designed for trajectory planning. While heuristic methods enhance computational tractability in large-scale problems, their efficacy often hinges on idealized assumptions. Specifically, most existing models enforce a singleton visit constraint and assume stationary PoI distributions with deterministic activation windows. To tackle complex problems such as highly coupled and non-convex mixed-integer optimizations, research focus begins turning to hybrid solution design with multiple stages. For example, Yuan et al. [24] divide the problem into three stages, namely, clustering, trajectory planning, and resource allocation with algorithms designed respectively. Pan et al. [25] combined genetic algorithm (GA) and MADRL, to achieve the distributed multi-UAV 3D trajectory planning collaborative optimization. Guo et al. [26] decomposed the main problem into tow sub-ones, while designing zero-forcing algorithm and successive convex approximation, respectively, to support UAV-assisted sensing and communication. Although these hybrid methodologies empowered solution design, dynamic and uncertain tasks (i.e., uncertain PoIs) are somehow overlooked. From a novel perspective, we propose a multi-module framework integrating prediction-enhanced PoI active time window estimation, UAV path pre-planning, and greedy online adjustment, enabling an effective solution to the complex problem. • View 3. Obstacle avoidance vs. socially compliant navigation. Existing UAV trajectory planning methods primarily formulate surrounding environments as physical obstacles, focusing on collision avoidance, energy efficiency, and mission completion while paying limited attention to human-centered social considerations [20], [25], [27]. However, as UAVs are increasingly deployed in low-altitude urban environments, socially compliant flight behavior has become equally important. Unlike conventional obstacle avoidance, UAVs inevitably share airspace with nearby pedestrians and residents. Flying at low altitudes or in close proximity to people may violate personal space, reduce perceived safety, and induce psychological discomfort, while rotor noise further degrades human comfort and environmental acceptability. These human-aware considerations have been extensively investigated in socially aware robot navigation and human-robot interaction, where factors such as proxemics, perceived safety, and social norms are explicitly incorporated into motion planning [28], [29]. Nevertheless, such socially compliant principles remain largely overlooked in existing UAV path planning frameworks. To bridge this gap, we explicitly incorporate a human-aware social cost into trajectory optimization, enabling UAVs to adapt their flight altitude and path according to the surrounding crowd distribution, thereby jointly optimizing sensing performance and social acceptability in accordance with LA4Good paradigm. C. Spotlight and Contribution Recall the above efforts and challenges, we propose FORTUNE, abbreviated from “Flying OveR The Uncertain NaturE”, an intelligent and humanistic engine for efficient multi-UAV collaboration, over dynamic and heterogeneous PoIs. Main contributions are summarized below.

TABLE I: Summary of related literature Attributes Related Study

Path 2D

[11] [12] [13], [20] [14] [15] [10], [17] [25] [18] [21], [22] [23] [24] FORTUNE

3D

✓ ✓ ✓ ✓ ✓ ✓

PoI/UE Static Dynamic Known

Social Factor

✓ ✓ ✓ ✓ ✓

AoI

✓ ✓ ✓ ✓

✓ ✓ ✓ ✓ ✓ ✓

✓ ✓ ✓ ✓ ✓ ✓

✓

✓ ✓

Solution

RL Contract RL MACL RL RL Hybrid RL Heuristic Hybrid Hybrid Hybrid

• We are interested in a novel 3D multi-UAV path planning and task scheduling problem for low-altitude collaborative sensing characterized by static obstacles and dynamic as well as uncertain PoIs. Specifically, we model PoIs into three heterogeneous types (Type-I, Type-II and Type-III) to capture diverse spatio-temporal characteristics, thereby moving beyond conventional static and homogeneous assumptions. Furthermore, in line with the LA4Good principle, we explicitly incorporate altitude-induced societal and environmental impacts, such as noise disturbance and perceived safety risk, into the objective function as penalty terms. Together, we formulate a practically meaningful yet mathematically challenging optimization problem that reflects the intrinsic trade-offs between sensing efficiency and socially responsible operation. • To tackle the optimization with NP hardness, we propose FORTUNE, which establishes a hierarchical offline-online cooperative framework that decomposes it into one regression problem and two path optimization problems, integrating intelligent prediction (Module A), pre-planning (Module B), and online adjustment (Module C). In the offline stage, a Transformer-based module predicts the active time windows of Type-II PoIs, enabling anticipatory trajectory pre-planning for Type-I and -II PoIs via a dynamic evolutionary optimization scheme under practical constraints such as collision avoidance. In the online stage, when Type-III PoIs emerge, a time-efficient greedy adjustment module refines UAV trajectories in real time to enhance the overall objective. Collectively, these modules establish a prediction-aware and adaptively refined solution framework that balances proactive efficiency with real-time responsiveness under dynamic and uncertain sensing environments. • We conduct comprehensive experiments on both real-world and numerical datasets, to verify our performance across diverse parameters. Experiments have shown good effectiveness as comparing to multi-dimension benchmark methods. II. C ORE M ODELING To describe spatial-temporal dynamism, the whole time horizon is discretized by set T = {1, . . . , 𝑡, . . . , |T|}, while Δ𝑡 denotes the duration of each timeslot. A. Modeling of PoIs In real-world networks, PoIs can either be known, or dynamic and uncertain, on factors such as geographical location, significance, and data volume required for collection. In our modeling, different types of PoIs are considered to capture diverse data needs. For notational simplicity, we use 𝑖 as the index of PoIs across all types.

4

• Type-I PoI. Type-I PoIs are defined as spatially fixed sensing is generated once 𝑜 𝑖(II) exceeds a predefined threshold. For targets with persistent validity over the entire mission horizon. instance, in intelligent transportation systems, traffic flow Their sensing demands are temporally invariant and remain intensity can serve as the observation value of an intersection. active regardless of external dynamics or contextual variations. High traffic volumes may induce sensing demands for traffic Typical instances include permanent infrastructure inspection monitoring, incident detection, and emission assessment, thereby points, long-term environmental monitoring sites, and predefined motivating UAV-assisted data collection. Such activation events land-use survey locations. The deterministic nature of their can be autonomously identified through real-time observations spatial distribution and sensing requirements enables efficient collected and processed by edge intelligence infrastructures, scheduling and proactive path optimization for UAV operations. including roadside units (RSUs) and edge servers. Accordingly, (I) In our modeling, let P (I) = {𝑝 1(I) , . . . , 𝑝 𝑖(I) , . . . , 𝑝 |P| } be the set when 𝑜𝑖(II) exceeds a pre-determined threshold 𝑜 (∗) , we consider (II) (II) of type-I PoIs, where each 𝑝 𝑖(I) ∈ P (I) is assumed to carry a 𝑝 𝑖 to be activated, whereas it becomes inactive once 𝑜𝑖 (∗) long-lasting task opening for data collection across the whole falls below 𝑜 . Apparently, this enables capturing the active time domain (namely, this PoI type always has data collection time windows of different PoIs. needs). In particular, each 𝑝 𝑖(I) can be represented by a tuple • Type-III PoI. Type-III PoIs are characterized by both spatial    and temporal uncertainty. These PoIs emerge unexpectedly (I) (I) (I) (I) (I) (I) (I) l𝑖 , 𝑑𝑖 , 𝑟 𝑖 , with l𝑖 = 𝑥 𝑖 , 𝑦 𝑖 , ℎ𝑖 denoting the 3Din response to sudden events, with no prior knowledge of space coordinate of 𝑝 𝑖(I) ; while 𝑑𝑖(I) and 𝑟 𝑖(I) represent the data their location, timing, or sensing requirements. Despite their volume required by the task of 𝑝 𝑖(I) , as well as the overall unpredictability, they often represent critical or high-priority scenarios that demand immediate attention and rapid deployment. reward that the UAVs who have contributed to 𝑝 𝑖(I) can get, Examples involve unexpected traffic accidents on highways, after completing its task. crowd congestion incidents in public spaces, or emergency • Type-II PoI. Type-II PoIs are spatially fixed sensing targets situations in large outdoor gatherings. Due to their dynamic whose demands exhibit predictable temporal dynamics. Their and urgent nature, these PoIs require highly adaptive, leveraging sensing requirements are activated only during specific time winreal-time task updates and on-demand UAV redirection to dows that recur according to underlying human behavioral patensure timely and effective responses. Accordingly, at the terns or environmental processes. Typical examples include rushbeginning of each timeslot 𝑡, we let the set of type-III PoIs hour traffic monitoring at major intersections and air-quality (III,𝑡 ) = {𝑝 (III,𝑡 ) , . . . , 𝑝 (III,𝑡 ) , . . . }, with each PoI associated 𝑖 1 sensing near heavily traveled roads during commuting periods. be P More importantly, the number of elements in P (III,𝑡 ) , The temporal predictability of these demands allows UAVs to with a task.(III,𝑡 ) |, can not be aware in advance (before 𝑡), due to perform proactive mission planning through time-aware task namely, |P the unpredictability and randomness of this type1 . Apparently, assignment and path optimization. Accordingly, we involve a set o n for each type-III PoI with starting time (II)  𝑡, we record  it as of type-II PoIs denoted by P (II) = 𝑝 1(II) , . . . , 𝑝 𝑖(II) , . . . , 𝑝 |P (II) | ,   𝑝 𝑖(III,𝑡 ) ∈ P (III,𝑡 ) and describe it by a tuple l𝑖(III,𝑡 ) , τ𝑖(III,𝑡 ) , where where each 𝑝 𝑖(II) ∈ P (II) is represented by a tuple 𝒍 𝑖(II) , 𝜏𝑖(II) . (III,𝑡 )  (III,𝑡 ) (III,𝑡 ) (III,𝑡 )    l𝑖 = 𝑥𝑖 , 𝑦𝑖 , ℎ𝑖 denotes the 3D spatial coordinh i o Specifically, l𝑖(II) = 𝑥𝑖(II) , 𝑦 𝑖(II) , ℎ𝑖(II) denotes the 3D spatial (III,𝑡 ) (III,𝑡 ) nate of 𝑝 𝑖 . Moreover, τ𝑖 = 𝑡, t𝑖(−,𝑡 ) , 𝑑𝑖(III,𝑡 ) , 𝑟 𝑖(III,𝑡 ) (II) h i coordinate of 𝑝 𝑖 . Recall the features of type-II PoIs, they may (−,𝑡 ) , appear multiple times throughout the entire time horizon, and collects the information of its active time window 𝑡, t𝑖 each appearance may last for several timeslots, just like stars the corresponding data requirement 𝑑 (III,𝑡 ) , and reward 𝑟 (III,𝑡 ) 𝑖 𝑖 shining on the map (e.g., a traffic intersection may have data that can be paid to UAVs upon successful task completion. collection requirement during rush hour, while remaining idle for the rest of the day). For ease of understanding, when a PoI has data demands, we say that it is active during the correspondB. Modeling of UAVs n o ing timeslot. Regarding the above, 𝜏𝑖(II) = 𝜏˜𝑖(𝑎) 0 ≤ 𝑎 ≤ 𝐴𝑖 is =  Our model involves UAVs collected by U 𝑢 1 , . . . , 𝑢 𝑚 , . . . , 𝑢 |U| , each equipped with advanced utilized to record the information of 𝑝 𝑖(II) across the whole time horizon, where 𝜏˜𝑖(𝑎) denotes an event corresponding sensors and onboard processors to assist data collection. All UAVs depart from n their designated startingo to the 𝑎-th appearance of PoI 𝑝 𝑖(II) , and 𝐴𝑖 indicates the (start) locations I (start) = i1(start) , . . . , i𝑚(start) , . . . , i |U| total number of occurrences of 𝑝 𝑖(II) on the considered map travel n to their corresponding destinations o over the entire time horizon. To further capture the duration and (end) (end) (end) (end) (II) (𝑎) (II) = i1 , . . . , i𝑚 , . . . , i |U| . In particular, of 𝑝 𝑖 n hbeing active, iwe define each ∈ 𝜏𝑖 asi I o event 𝜏˜h𝑖 (𝑎) (+,𝑎) (−,𝑎) (II,𝑎) (II,𝑎) (+,𝑎) (−,𝑎) each UAV 𝑢 ∈ U can be described by oa n 𝑚 𝜏˜𝑖 = t𝑖 , t𝑖 , 𝑑𝑖 , 𝑟𝑖 , where t𝑖 , t𝑖 (uav,+) (uav,−) (uav,𝑡 ) (hov) (move,𝑣) (+) tuple 𝒍 , 𝒍 , 𝑑𝑚 , 𝑒𝑚 , 𝑒𝑚 , 𝑒𝑚 , 𝑚 𝑚   forms an active time window, with t𝑖(+,𝑎) ∈ T and t𝑖(−,𝑎) ∈ T (uav,+) (uav,+) (uav,+) (uav,+) = 𝑥𝑚 , 𝑦𝑚 , ℎ𝑚 and describing the  starting and  closing timeslots of the 𝑎-th where 𝒍 𝑚   (+,𝑎) (−,𝑎) (−,𝑎) (+,𝑎+1) appearance t𝑖 ≤ t𝑖 , and satisfying t𝑖 < t𝑖 . 𝒍 (uav,−) = 𝑥 (uav,−) , 𝑦 (uav,−) , ℎ (uav,−) denote the three𝑚 𝑚 𝑚 𝑚 Besides, assuming that a task arises along with each active dimensional coordinates of the take-off location and destination (II,𝑎) (II,𝑎) event, we use 𝑑𝑖 and 𝑟 𝑖 to indicate the corresponding of UAV 𝑢 𝑚 , respectively. To ensure the security and privacy of data requirement and reward, respectively. data collection (e.g., preventing sensitive PoIs from close-range To model the emergence of Type-II PoIs, we define an 1We make a reasonable assumption that the appearance timeslot of a Type-III observation value 𝑜𝑖(II) that measures the potential information PoI is uncertain; however, once it emerges, its duration is supposed to be gain associated with a sensing target. The observation value known. Therefore, upon its occurrence, we are able to capture its active time acts as a trigger signal for PoI activation: a sensing demand window.

5

  (uav,𝑡 ) (uav,𝑡 ) (uav,𝑡 ) (uav,𝑡 ) reconnaissance by UAVs), each UAV is required to maintain each timeslot, we use l𝑚 = 𝑥𝑚 , 𝑦𝑚 , ℎ𝑚 a flight altitude no lower than the minimum safety altitude (xy,𝑡 ) to denote the coordinate of 𝑢 𝑚 at timeslot 𝑡, and 𝑣 𝑚 , (uav,min) specified for the corresponding PoIs, denoted by ℎ 𝑚 (h,𝑡 ) 𝑣 show the horizontal and vertical moving velocities of (uav,𝑡 ) when performing sensing tasks. Moreover, 𝑑 𝑚 represents 𝑢𝑚 , respectively. Apparently, the acceleration of each UAV 𝑚 the data sensing capability of UAV 𝑢 𝑚 during each timeslot should not exceed a threshold due to hardware limitations, for (e.g., measured in Mbits/Δ𝑡). Moreover, during 𝑡, UAV 𝑢 𝑚 (xy,𝑡+1) (xy,𝑡 ) (h,𝑡+1) (h,𝑡 ) − 𝑣𝑚 ≤ 𝑣 (xy,max) , 𝑣 𝑚 − 𝑣𝑚 ≤ can take one of two actions, namely hovering and flying. example, 𝑣 𝑚 (h,max) (xy,max) (h,max) (hov) , where 𝑣 and 𝑣 are the maximum Accordingly, 𝑒 𝑚 denotes the unit energy consumption 𝑣 (mov, 𝑣) ˜ for hovering, while 𝑒 𝑚 represents the unit energy horizontal and vertical accelerations. Therefore, the flying Δ𝑡 of each UAV can also be constrained consumption when flying at velocity2 𝑣˜ . Due to the typically distance within (uav,𝑡+1) (uav,𝑡 ) such that l − l𝑚 ≤ 𝑙 (max) , where 𝑙 (max) is 𝑚 limited endurance of UAVs, we assume that each UAV is (+) the maximum flying distance in a certain period of time. initially equipped with an energy budget 𝑒 𝑚 at take-off3 . Accordingly, the trajectory of UAV 𝑢 𝑚 can be odefined by n Also, each UAV should complete its planned flight from (uav,1) (uav,2) (uav,𝑡 ) (uav, |𝑇 | ) , l𝑚 , . . . , l𝑚 , . . . , l𝑚 . the designated starting location to the corresponding destina- L𝑚 = l𝑚 tion before depleting its available   energy. We further define (uav,𝑡 ) (uav) (uav,𝑡 ) 𝑞𝑚 = 𝑓 (qua) 𝜌 𝑚 , ℎ𝑚 to denote the data quality C. Analysis on Task Completion and Reward achieved by UAV 𝑢 𝑚 at timeslot 𝑡, where 𝑓 (qua) (·) is a quality Way to evaluate the completion of a task. To better describe the evaluation function depending on two key factors. Specifically, assignment between UAVs and different types of PoIs across (uav) (i) 𝜌 𝑚 represents the inherent sensing capability of UAV 𝑢 𝑚 various timeslots, we use binary indicator 𝛼 to show whether (e.g., being equipped with high-definition wide-angle cameras a UAV is assigned to the task of a corresponding PoI. The or high-accuracy air pollution sensing modules), which enables answer is yes when 𝛼 = 1; while 𝛼 = 0, otherwise. In addition, (uav,𝑡 ) higher-quality data acquisition; and (ii) ℎ 𝑚 denotes the another binary variable 𝛽 is introduced to indicate whether the flight altitude of UAV 𝑢 𝑚 at timeslot 𝑡, for which an important UAV’s flight path covers the location of the corresponding PoI, trade-off arises from the following two aspects. ensuring the spatial feasibility of the assigned task. Specifically, (uav) (uav,𝑡 ) ) • How 𝜌 𝑚 impacts 𝑞 𝑚 : Hardware platforms with the UAV task can be executed only when the PoI lies within superior performance typically enable the collection of higher- the UAV’s flight path and the PoI has been assigned to this diverse PoI types may have quality data, for instance, producing clearer video of the UAV (i.e., 𝛼𝛽 = 1). Due to that different active time windows5 , they have different modeling assigned PoI regarding 𝛼 and 𝛽, and thus the description of task completion (uav,𝑡 ) (uav,𝑡 ) • How ℎ 𝑚 impacts 𝑞 𝑚 : Subject to the minimum safety can also be different. altitude constraint, a lower flight altitude generally enables • For type-I PoIs. We first define 𝛼 (I,𝑡 ) = 1 to indicate that the 𝑖,𝑚 a UAV to acquire higher-quality multi-modal sensing data, (I) task of type-I PoI 𝑝 is assigned to UAV 𝑢 𝑚 at timeslot 𝑡. 𝑖 including images with finer spatial resolution and audio signals (I,𝑡 ) with improved clarity. Nevertheless, operating at lower altitudes Correspondingly, 𝛽𝑖,𝑚 can be given by (I,𝑡 ) (uav,𝑡 )  may significantly increase the risk of collision with surrounding  1, if 𝛼𝑖,𝑚 = 1, 𝑥 𝑚 = 𝑥𝑖(I) ,    obstacles4 . Conversely, detouring to avoid such obstacles often (I,𝑡 ) (uav,𝑡 ) (uav,𝑡 ) 𝛽𝑖,𝑚 = (1) 𝑦𝑚 = 𝑦 𝑖(I) , ℎ 𝑚 > ℎ𝑖(I) , results in longer travel distances and, consequently, substantially    0, otherwise, higher energy consumption. More critically, as this paper  advocates the concept of “Low-Altitude for Good” (LA4Good), which indicates that the trajectory of 𝑢 𝑚 should also be it is essential to account for social compliant and environmental appropriate for this task to be accomplished. Since the task implications of low-altitude UAV operations. Specifically, flying regarding each PoI should be completed (i.e., the collected at low altitudes may inevitably generate noise, induce panic over data must reach the required data volume of the task) in order potential UAV crashes, and raise privacy concerns regarding to earn the corresponding reward, for type-I PoI, we use 𝑑ˆ𝑖(I) terrestrial environments, thereby disturbing humans and wildlife to represent the overall received data volume of 𝑝 (I) over the on the ground. Such disturbances can, in turn, diminish the entire time domain, and it can be calculated by: 𝑖 rewards or utilities associated with certain PoIs, which will be |T| ∑︁ |U| ∑︁ (I,𝑡 ) (uav,𝑡 ) formally modeled and discussed in Sec. II-D. 𝑑ˆ𝑖(I) = 𝛽𝑖,𝑚 𝑑𝑚 . (2) To describe the location of UAV 𝑢 𝑚 at the beginning of 𝑡=1 𝑚=1 2 To simplify the problem, we neglect the energy consumption caused by

acceleration and consider only the energy associated with maintaining different constant flight speeds. This approximation reduces the modeling complexity while still capturing the key impact of speed on energy usage. 3 Since our goal is to investigate dynamic task scheduling and trajectory coordination rather than wireless resource management, the communication process is abstracted from the optimization. Specifically, once a PoI is sensed, the generated data are assumed to be streamed to the nearest AP during subsequent flight whenever connectivity is available. Such an abstraction is consistent with cellular-connected UAV networks, where communication and mobility are naturally pipelined, allowing data uploading to overlap with flight instead of introducing additional mission delay [30]. As a result, the mission completion time in our model is dominated by the physical sensing process and UAV mobility, while communication latency is assumed to be non-blocking. 4 Obviously, note that UAV is not allowed to arbitrarily minimize its altitude; it should satisfy the PoI-specific minimum altitude constraint, and only above this threshold can it adjust its altitude selection.

Accordingly, we denote 𝑐 𝑖(I) as the indicator of whether the task of 𝑝 𝑖(I) has been completed, given by: ( 1, 𝑑ˆ𝑖(I) ≥ 𝑑𝑖(I) , (I) 𝑐𝑖 = (3) 0, otherwise. Apparently, 𝑐 𝑖(I) = 1 means that the task has been completed. (II,𝑎,𝑡 ) (II,𝑎,𝑡 ) • For type-II PoIs. Then, the modeling of 𝛼𝑖,𝑚 and 𝛽𝑖,𝑚 for type-II PoIs has a slight difference compared to that of the 5 To facilitate analysis, to determine whether the UAV has arrived at the location of the PoI (i.e., whether the PoI lies on the UAV’s flight trajectory), we assume that the PoI and the UAV share the same horizontal coordinate at time 𝑡. However, in real-world scenarios, certain deviations inevitably exist. This simplification is adopted for the purpose of mathematical modeling in this paper.

6

other types, for which we update their definitions by introducing (II,𝑎,𝑡 ) an integer 𝑎, with 1 ≤ 𝑎 ≤ 𝐴𝑖 . Thus, we have 𝛼𝑖,𝑚 = 1 indicating that the task associated with the 𝑎th appearance of type-II PoI 𝑝 𝑖(II) is assigned to UAV 𝑢 𝑚 at timeslot 𝑡; while (II,𝑎,𝑡 ) (II,𝑎,𝑡 ) 𝛼𝑖,𝑚 = 0, otherwise. Accordingly, 𝛽𝑖,𝑚 can be given by (II,𝑎,𝑡 ) (uav,𝑡 ) (II) (uav,𝑡 ) (II)  = 1, 𝑥 𝑚  1, if 𝛼𝑖,𝑚  h = 𝑥𝑖 , 𝑦 𝑚 i = 𝑦 𝑖 ,   (II,𝑎,𝑡 ) (uav,𝑡 ) 𝛽𝑖,𝑚 = ℎ𝑚 > ℎ𝑖(II) , 𝑡 ∈ t𝑖(+,𝑎) , t𝑖(−,𝑎) ,    0, otherwise,  (4) meaning that the UAV should arrive at the mapped PoI within its active time window. Similar to previous discussions, for the 𝑎-th task (the 𝑎-th appearance) of 𝑝 𝑖(II) , we have |T| ∑︁ |U| ∑︁ (II,𝑎,𝑡 ) (uav,𝑡 ) 𝑑ˆ𝑖(II,𝑎) = 𝛽𝑖,𝑚 𝑑𝑚 , (5)

data quality. • Reward of type-II PoIs. Similar to type-I PoIs, we write the reward of task of type-II PoI for its 𝑎-th appearance as: |T| ∑︁ |U| ∑︁ (II,𝑎,𝑡 ) (uav,𝑡 ) 𝑟 𝑖(II,𝑎) = 𝑐 𝑖(II,𝑎) 𝑟˜𝑖(II) + 𝑐 𝑖(II,𝑎) Δ𝑟˜ 𝛽𝑖,𝑚 𝑞𝑚 , | {z } 𝑡=1 𝑚=1 {z } RoTC of Type II PoI | EoDC of Type II PoI

(11) • Reward of type-III PoIs. Similarly, the reward of a type-III PoI emerging at timeslot 𝑡 is defined by |T| ∑︁ |U| ∑︁ (III,𝑡 ,𝑡 ′ ) (uav,𝑡 ′ ) 𝑟 𝑖(III,𝑡 ) = 𝑐 𝑖(III,𝑡 ) 𝑟˜𝑖(III) + 𝑐 𝑖(III,𝑡 ) Δ𝑟˜ 𝛽𝑖,𝑚 𝑞𝑚 , | {z } 𝑡 ′ =1 𝑚=1 {z } RoTC of Type III PoI | EoDC of Type III PoI

(12)

𝑡=1 𝑚=1

and

(

D. Modeling of Environmental and Societal Impacts Brought by UAVs In our modeling, we provide a novel perspective on LA4Good, by explicitly evaluating the potential impacts of low-altitude (III,𝑡 ,𝑡 ′ ) (III,𝑡 ,𝑡 ′ ) • For type-III PoIs. For 𝛼𝑖,𝑚 and 𝛽𝑖,𝑚 of type-III PoIs, intelligent agents on public safety and the surrounding enviwe update their definitions by reinterpreting 𝑡 as the start time ronment. In particular, we characterize the negative effects (i.e., activation time) of a type-III PoI, and introducing 𝑡 ′ as (uav,𝑡 ) ′) associated with UAV flight altitude ℎ 𝑚 , which become (III,𝑡 ,𝑡 the timeslot index with 𝑡 ≤ 𝑡 ′ . Thus, 𝛼𝑖,𝑚 = 1 indicates increasingly significant as UAVs operate at lower heights. For that UAV 𝑢 𝑚 is scheduled to perform the task of 𝑝 𝑖(III,𝑡 ) during example, low-altitude flights may generate substantial noise, (III,𝑡 ,𝑡 ′ ) increase the perceived risk of crashes, and disturb local wildlife, timeslot 𝑡 ′ . Based on this, 𝛽𝑖,𝑚 is calculated by especially birds, thereby leading to ecological disruptions as   1,  well as raising public safety and environmental concerns. Thus,  ′ ′ ′    (III,𝑡 ,𝑡 ) (uav,𝑡 ) (uav,𝑡 )  = 1, 𝑥 𝑚 = h𝑥𝑖(III,𝑡 ) , 𝑦 𝑚 = 𝑦 𝑖(III,𝑡 ) , we define the ecological penalty function as 𝑓 (eco,𝑡 ) ℎ (uav,𝑡 ) ,  if 𝛼𝑖,𝑚  (III,𝑡 ,𝑡 ′ ) i 𝑚 𝛽𝑖,𝑚 = (uav,𝑡 ′ )  ℎ𝑚 > ℎ𝑖(III,𝑡 ) , 𝑡 ′ ∈ 𝑡, t𝑖(−,𝑡 ) ,  which reflects the penalty to the ecology incurred by the altitude    of UAVs during timeslot 𝑡. This function is an inverse function  0, otherwise,  (uav,𝑡 ) : the lower the UAV flies, the greater the negative (7) of ℎ 𝑚 (III,𝑡 ,𝑡 ′ ) impact it imposes on the ground environment (e.g., pedestrians In other words, 𝛽𝑖,𝑚 = 1 shows that the UAV can arrive and vehicles) as well as the low-altitude ecosystem (e.g., birds). at the location of a type-III PoI that emerged at time 𝑡 and is (III,𝑡 ,𝑡 ′ ) still active at 𝑡 ′ , when 𝛼𝑖,𝑚 = 1. Besides, for the task being The form of this function can vary in many ways. For example, it can be modeled by a sigmoid function: active at the beginning of timeslot 𝑡, we have |U|   ∑︁ |T| ∑︁ |U| 𝜀 ∑︁ (uav,𝑡 ) (eco,𝑡 ) ′ ′  , 𝑓 ℎ𝑚 = (13) (III,𝑡 ,𝑡 ) (uav,𝑡 ) (uav,𝑡 ) 𝑑ˆ𝑖(III,𝑡 ) = 𝛽𝑖,𝑚 𝑑𝑚 , (8) (×) 𝜆 ℎ𝑚 −ℎ (0) 𝑚=1 1 + 𝑒 ′ 𝑡 =1 𝑚=1 where 𝜀 is the coefficient of penalty, while ℎ (0) is interpreted and ( (III,𝑡 ) (III,𝑡 ) as a critical altitude: below it, the UAV has a strong negative ˆ 1, 𝑑𝑖 ≥ 𝑑𝑖 , 𝑐 𝑖(III,𝑡 ) = (9) effect; above it, the impact becomes progressively smaller. 0, otherwise. 𝑐 𝑖(II,𝑎) =

1, 0,

𝑑ˆ𝑖(II,𝑎) ≥ 𝑑𝑖(II,𝑎) , otherwise.

(6)

• Way to calculate the reward offered by different types of PoIs. E. Modeling of UAV Collision Risks (Including Obstacles and Note that for different PoI types, their rewards, i.e., 𝑟 𝑖(I) , 𝑟 𝑖(II,𝑎) , Mid-Air Collisions) and 𝑟 𝑖(III,𝑡 ) , actually depend on two key factors: (i) the reward of While excessively low UAV flight altitudes may cause task completion (RoTC) in time, e.g., reflected by 𝑐 𝑖(I) , 𝑐 𝑖(II,𝑎) , negative impacts, this paper promotes the broader vision of 𝑐 𝑖(III,𝑡 ) ; and (ii) the reward of data quality (RoDQ), where higher LA4Good by also addressing two critical dimensions of risk quality can definitely bring increasing reward. Note that if a management: (i) strict control over UAV-obstacle collisions and task associated with a PoI has not been completed, we have (ii) soft control over mid-air collisions. In the following, we its reward equals to zero. we calculate the reward of different offer details regarding these two aspects. • Strict control over UAV-obstacle collisions. Given the intypes of PoIs as following: evitable presence of obstacles such as tall buildings, especially • Reward of type-I PoIs. Correspondingly, for a type-I PoI, we in urban environments, this paper enforces a strict constraint (I) have its reward 𝑟 𝑖 calculated by: to prevent UAVs from colliding with them during flight or |T| ∑︁ |U| ∑︁ task execution. Let B = {𝑏 1 , . . . , 𝑏 𝑛 , . . . , 𝑏 |B| } be the set of  (I) (I) (I) (I) (I,𝑡 ) (uav,𝑡 ) 𝑟𝑖 = 𝑐 𝑖 𝑟˜𝑖 + 𝑐 𝑖 Δ𝑟˜ 𝛽𝑖,𝑚 𝑞 𝑚 , (10) (obs) (obs) obstacles, where 𝑏 is represented by a tuple l , 𝑐 . 𝑛 𝑛 𝑛 | {z } 𝑡=1 𝑚=1   | {z } (obs) (obs) (obs) (obs) RoTC of Type I PoI In particular, l𝑛 = 𝑥𝑛 , 𝑦 𝑛 , ℎ𝑛 denotes the 3D RoDQ of Type I PoI

where Δ𝑟˜ indicates the marginal gain in reward with respect to

coordinate of obstacle 𝑏 𝑛 , while 𝑐 𝑛(obs) represents the cost

7

   0, 

𝜃 𝑖(I,𝑡 ) = 

Í |U| (I,𝑡 ) if 𝑚=1 𝛽 ≤ 𝑠 (max) , Í |U| 𝑖,𝑚 (I,𝑡 ) if 𝑚=1 𝛽𝑖,𝑚 > 𝑠 (max) ,

2   − 1, |U| (I,𝑡 )  −𝜆 (num) Í𝑚=1 𝛽 −𝑠 (max) 𝑖,𝑚  1+𝑒 Í |U| (II,𝑎,𝑡 )  0,  if 𝑚=1 𝛽 ≤ 𝑠 (max) ,   (II,𝑎,𝑡 ) Í |U| 𝑖,𝑚 (II,𝑎,𝑡 ) 2 𝜃𝑖 =   − 1, if 𝑚=1 𝛽𝑖,𝑚 > 𝑠 (max) ,  |U| (II,𝑎,𝑡 )  −𝜆 (num) Í𝑚=1 𝛽 −𝑠 (max) 𝑖,𝑚  1+𝑒 Í |U| (III,𝑡 ,𝑡 ′ )  0,  if 𝑚=1 𝛽 ≤ 𝑠 (max) ,   (III,𝑡 ,𝑡 ′ ) ′) Í |U| 𝑖,𝑚 (III,𝑡 ,𝑡 2 𝜃𝑖 =   − 1, if 𝑚=1 𝛽𝑖,𝑚 > 𝑠 (max) .  |U| (III,𝑡,𝑡 ′ )  −𝜆 (num) Í𝑚=1 𝛽 −𝑠 (max) 𝑖,𝑚  1+𝑒

(14)

(15)

(16)

of detour (e.g., the length of the additional route that needs Then, the overall negative impacts across the whole time to be taken) when a UAV passes by 𝑏 𝑛 . When an obstacle domain can be calculated by: |T| is encountered along the UAV’s trajectory, we enforce strict   ∑︁ (uav,𝑡 ) control by providing two possible options: (i) the UAV adjusts its R (−) = 𝑓 (eco,𝑡 ) ℎ 𝑚 , (18) altitude to overfly the obstacle (and correspondingly consumes 𝑡=1 energy), or (ii) it performs a lateral detour to circumvent the Accordingly, combining these two, we have the net reward obstacle, which may result in additional travel costs. computed by: • Soft control over mid-air collisions. The potential for UAV-toR (net) = R (+) − R (−) . (19) UAV collisions increases as more UAVs operate simultaneously within the same region (e.g., location of a PoI). However, such Accordingly, the optimization problem of our interest is defined collisions are not always inevitable. In our modeling, we adopt as the following P P : argmax R (net) (20) a soft manner to manage this: instead of directly limiting the α, {L𝑚 }𝑢𝑚 ∈U number of UAVs, we constrain the probabilistic risk of collision, s.t. which increases with UAV density. This allows for flexibility |T| ∑︁ (𝑡 ) (+) in UAV deployment while maintaining safety-aware operation. (C1): 𝑒𝑚 ≤ 𝑒𝑚 , ∀ 𝑢𝑚 ∈ U For type-I PoI 𝑝 𝑖(I) ∈ P (I) , type-II PoI 𝑝 𝑖(II) ∈ P (II) , and type𝑡=1 III PoI 𝑝 𝑖(III,𝑡 ) ∈ P (III,𝑡 ) , the number of UAVs that may gather (C2): 𝜃 (I,𝑡 ) ≤ 𝜃 max , 𝜃 (II,𝑎,𝑡 ) ≤ 𝜃 max , 𝜃 (III,𝑡 ,𝑡 ′ ) ≤ 𝜃 max 𝑖 𝑖 𝑖 at the corresponding location during timeslot 𝑡 (or 𝑡 ′ for type(uav,+) start (uav,−) end Í |U| (I,𝑡 ) Í |U| (II,𝑎,𝑡 ) (C3): l = I , l = I (with III PoI) can be calculated by 𝑚=1 𝛽𝑖,𝑚 , 𝑚=1 𝛽𝑖,𝑚 Í |U| (III,𝑡 ,𝑡 ′ ) (uav,𝑡 ) ≠ l𝑛(obs) , ∀𝑏 𝑛 ∈ B 1 ≤ 𝑎 ≤ 𝐴𝑖 ), and 𝑚=1 𝛽𝑖,𝑚 , respectively. To ensure a safe (C4): l low-altitude operating environment, a reference metric is intro- (C5): 𝑣 (xy,𝑡+1) − 𝑣 (xy,𝑡 ) ≤ 𝑣 (xy,max) , 𝑣 (h,𝑡+1) − 𝑣 (h,𝑡 ) ≤ 𝑣 (h,max) , 𝑚 𝑚 𝑚 𝑚 duced to control UAV density, representing the recommended (I,𝑡 ) (II,𝑎,𝑡 ) (III,𝑡 ,𝑡 ′ ) maximum number of UAVs that can simultaneously occupy where α denotes the profile of all 𝛼𝑖,𝑚 , 𝛼𝑖,𝑚 and 𝛼𝑖,𝑚 , a given location, denoted as 𝑠 (max) . Based on the above, the and {L𝑚 }𝑢𝑚 ∈U collects all the paths cross UAVs. Particularly, in risk of UAV collision at a certain timeslot regarding different P, constraint (C1) limits the energy available to each UAV, while (𝑡 ) (hov) PoIs can be modeled using a shifted-and-normalized sigmoid Í |T| 𝑒 𝑚 depens on factors such as 𝑒 𝑚 , 𝑒 (mov,ṽ) . Constraint 𝑡=1 function to keep the risk value within the interval [0, 1], given (C2) constrains the collision risk among UAVs, while (C3) as formulas (14)-(16). ensures that each UAV departs from its origin and lands at the designated destination to accomplish the assigned task, and (C4) enforces obstacle avoidance. Moreover, (C5) bounds III. 3D M ULTI -UAV PATH P LANNING AND TASK the horizontal and vertical accelerations within the maximum S CHEDULING OVER D IVERSE P O I S WITH allowable limits. In particular, problem P involves tightly S OCIALLY-C OMPLIANT C ONCERNS coupled decision variables. Specifically, the binary assignment variable determines the task-UAV matching, while the path A. Problem Description variable characterizes the continuous spatial-temporal flight Our primary goal is to optimize 3D paths of multiple UAVs path of each UAV, including geographical coordinates and coupled with task scheduling over heterogeneous PoIs, in altitude profiles. Notably, the path is not uniquely determined environments with dynamic and uncertain nature. To achieve by the assignment decision, as it should be jointly optimized to this, the designed optimization process aims to maximize enhance task completion quality, mitigate ground impact, and the net reward derived from UAV services, which strives accommodate flight behaviors such as hovering. Consequently, to achieve a well-balanced trade-off between service quality the problem entails the coupling of discrete assignment variables and the mitigation of potential negative impacts that low- and high-dimensional continuous trajectory variables, leading altitude intelligent agents may have on human populations and to a large-scale mixed-integer optimization problem. surrounding ecosystems, while simultaneously incorporating multi-dimensional risk control. Recall our previous discussions, we first write the positive reward that UAVs can obtain for B. Problem Transformation and Solution Design serving diverse PoI types as: (I) (II) (III,𝑡 ) | To tackle the resulting complexity, we decompose the problem |P |P |T| |P∑︁ 𝐴𝑖 ∑︁| ∑︁| ∑︁ ∑︁ (I) (II,𝑎) (III,𝑡 ) (+) into two sequential stages, embedded with three sub-problems R = 𝑟𝑖 + 𝑟𝑖 + 𝑟𝑖 , (17) detailed below: (i) Offline planning stage (before 𝑡 = 1): During 𝑖=1 𝑖=1 𝑎=1 𝑡=1 𝑖=1

8

this time, we first estimate the future service demands of type- with residual connections and normalization. II PoIs by solving a regression problem, with a TransformerAfter several stacked Transformer layers, a linear prediction based forecasting module (Module A) developed. Based on head maps the learned temporal representation into the future these predictions, we further formulate an offline optimization observation sequence:   (pred) −1) problem, employing a carefully designed evolutionary heuristic ô𝑖(II,𝑡:𝑡+𝐿 = 𝐹Θ X𝑖(in,𝑡 ) , (26) to pre-plan efficient UAV paths over type-I and type-II PoIs, with the aim to maximize the expected net reward (Module B, only where 𝐹Θ (·) denotes Transformer predictor parameterized by (pred) is the prediction horizon. Apparently, the model associated with these two PoI types). Such a design is motivated Θ, and 𝐿 can be trained by minimizing the prediction error. Then, the by the fact that the information of type-III PoIs is unavailable predicted observation values are used to infer the activation until they actually emerge in the operational area. (ii) Online adaptation stage (from 𝑡 = 1): In this stage, UAVs initially states of Type-II PoIs (Type-II PoI is regarded as active at follow the pre-determined paths obtained in the former stage. timeslot 𝑡 if its predicted observation value satisfies 𝑜ˆ𝑖(II,𝑡 ) ≥ Once any type-III PoI becomes active, we dynamically adjust 𝑜 (∗) ). The consecutive active timeslots are further treated as the the current paths by solving an online optimization problem, predicted active windows of PoIs, while, together with Type-I for which we investigate a greedy-empowered yet time-efficient PoIs that remain valid over the whole time horizon, announcing refinement strategy (Module C), so as to promptly adapt to the the service demand for Module B. newly revealed information and further improve the achieved net 2) Module B: Offline 3D path pre-planning via ES2 A: reward. This hybrid two-stage framework effectively balances Thanks to Module A predictor, Module B aims to perform planning optimality and decision-making efficiency, enabling offline path pre-planning for Type-I and Type-II PoIs by designfast responses to unexpected events while preserving high- ing three sub-modules (abbreviated as SubM for simplicity). quality solutions under practical computational constraints. In However, directly optimizing task assignments and 3D paths the following, we delve into details associated with the three for multiple UAVs is still computationally expensive, since both modules, forming our FORTUNE. discrete scheduling decisions and continuous position variables 1) Module A: Transformer-based service demand prediction are involved. To this end, we design an enhanced sparrow search 2 for Type-II PoIs (Stage 1): Type-II PoIs are spatially fixed but algorithm (ES A), where each individual searches over the task temporally dynamic, with demands confined to specific time priority space rather than directly encoding UAV waypoints. windows. Before take-off, Module A designs a Transformer- • SubM B.1: priority-driven encoding and tent chaotic based predictor to estimate their demand evolution and maps mapping-based population initialization. One key challenge in the forecasts to active intervals, which are then fed into offline multi-UAV path planning is achieving swarm-level coordination path pre-planning. Accordingly, for a Type-II PoI 𝑝 𝑖(II) , we use while preserving individual autonomy. Conventional coordinateits historical observation values as the input of the prediction based representations lead to rapidly growing search dimensions model. Let 𝑡 be the current timeslot and 𝐿 (his) denote the length with increasing UAVs and waypoints, causing a combinatorial explosion and the curse of dimensionality, which severely of the historical observation window, the input sequence is h i⊤ hampers convergence. To address this, we develop a task(in,𝑡 ) (𝑡 −𝐿 (his) ) (𝑡 −𝐿 (his) +1) (𝑡 −1) 𝐿 (his) ×𝑑 (model) X𝑖 = x𝑖 , x𝑖 , . . . , x𝑖 ∈R , priority-based real-valued encoding strategy, searching the (21) global task execution order rather than directly optimizing where x𝑖( 𝜏 ) denotes the normalized observation feature of 𝑝 𝑖(II) path coordinates (by optimizing task response order, swarm at timeslot 𝜏 ∈ {𝑡 − 𝐿 (his) , ..., 𝑡 − 1} , e.g., traffic-flow intensity, coordination is implicitly achieved). Moreover, Tent mapping is incorporated to initialize the population, thereby improving and 𝑑model is the feature embedding dimension. while mitigating premature convergence to Since the Transformer does not rely on recurrent structures, population diversity (off) local optima. Let T = {𝜙1 , 𝜙2 , . . . , 𝜙 𝑠 , . . . , 𝜙 𝑁 (task) } denote positional information is added to preserve the temporal order of the offline task set (with 𝑁 (task) tasks), consisting of all Type-I the sequence. Specifically, for the 𝑜-th position, the sinusoidal and predicted Type-II tasks. Also, we denote 𝑔 as the generation positional encoding can be given by   index. In our ES2 A, key definition are detailed by follows. 𝑜 , (22) Definition 1 (Population): A population in ES2 A denotes a set E𝑜,2 𝑗 = sin 2 𝑗/𝑑model 10000   of candidate individuals, given by n o 𝑜 (𝑔) (𝑔) (𝑔) (𝑔) (𝑔) E𝑜,2 𝑗+1 = cos , (23) X = x , x , . . . , x , . . . , x , (27) 2 𝑗/𝑑 𝑜 model 1 2 10000 𝑁 (p) (𝑔) (p) is the population size and x𝑜 denotes the 𝑜-th where 𝑗 denotes the dimension index. Then, the embedded where 𝑁 individual at generation 𝑔. input can be obtained by (𝑔) Z𝑖(0,𝑡 ) = X𝑖(in,𝑡 ) + E. (24) Definition 2 (Individual): An individual x𝑜 denotes a swarmsolution) and Based on the embedded sequence, the designed Transformer level path set (i.e., a candidate task-scheduling 2 A, with search serves as the basic optimization unit in ES encoder extracts temporal correlations through multi-head selfattention. In each attention head, the input is linearly projected conducted at both individual and population levels. Each into the query, key, and value matrices, denoted by Q, K, and individual is uniquely mapped to a priority vector, establishing a one-to-one correspondence. Rather than directly encoding UAV V, respectively. The scaled dot-product is  attention  ⊤ paths, an individual encodes task priorities, determining the QK A(Q, K, V) = softmax √ V, (25) global execution order, while specific UAV paths are generated 𝑑𝑘 by a decoder. where 𝑑 𝑘 denotes the dimension of key vector. By performing Definition 3 (Priority vector and priority weight): Priority attention in multiple representation subspaces, the model vector determines the task execution order of the correspondcan capture both local fluctuations and long-range temporal (𝑔) ing individual. For x𝑜 , its priority vector is defined as i dependencies of service demands. The outputs of different heads h (𝑔) (𝑔) (𝑔) (𝑔) (𝑔) , . . . , 𝑥 𝑥 , 𝑥 , . . . , 𝑥 , where 𝑥 𝑜,𝑠 ∈ [0, 1] is the are concatenated and further processed by feed-forward layers 𝑜,𝑠 𝑜,1 𝑜,2 𝑜, 𝑁 (task)

9

(𝑔)

(𝑔)

priority weight of task 𝜙 𝑠 in individual x𝑜 . A larger 𝑥 𝑜,𝑠 point is selected, making the additional vertical climbing implies higher priority for task 𝜙 𝑠 , leading to earlier considerenergy consumption equal to zero, and to minimize the ation during decoding. For each individual, tasks are ranked ecological penalty on this basis. by descending priority weights to form a global execution • Physical lower-bound altitude ℎ (limit) : ℎ (limit) = ℎ (obs) + sequence for decoding. This approach converts the original 𝛿 (safe) , where 𝛿 (safe) denotes the safety margin for verdiscrete scheduling problem into a continuous optimization in tical flight. In general, this corresponds to the minimum the priority space. climbing range that does not require horizontal detouring. • Ecological escape altitude ℎ (eco) : For the continuous In standard S2 A, the initial population is usually generated ecological penalty function 𝑓 (eco) (ℎ) (see (13)), ℎ (eco) by pseudo-random numbers. However, when 𝑁 (task) is large, is selected such that 𝑓 (eco) (ℎ (eco) ) = 𝜘eco , meaning that random initialization may lead to clustered individuals and flying at ℎ (eco) can have slight ecological penalty. This insufficient diversity. To enhance the coverage of the initial may trade increased climbing energy consumption for an search space, Tent chaotic mapping is adopted to initialize the extremely low ecological penalty. population X (0) , as given by  • Ecological critical altitude ℎ (mid) : ℎ (mid) is selected for 2𝑧 𝑘 , 0 ≤ 𝑧 𝑘 < 0.5, 𝑧 𝑘+1 = (28) 𝑓 (eco) (ℎ (mid) ) = 𝜘mid , i.e., the inflection-point altitude of 2(1 − 𝑧 𝑘 ), 0.5 ≤ 𝑧 𝑘 ≤ 1. sigmoid function. Detouring at this altitude is comprowhere 𝑧 𝑘 ∈ [0, 1] denotes the chaotic variable generated at the mise, avoiding high-altitude climbing while keeping the 𝑘-th iteration during random number generation. The generated ecological impact within an acceptable range. (0) chaotic sequence is used to assign the priority weights 𝑥 𝑜,𝑠 for For each of the above, obstacle detection is performed along all individuals in X (0) . Benefiting from its uniform distribution property, it helps generate diverse task-priority patterns at the corresponding flight route. When obstacles are present, the the beginning of the search, thereby improving the global Manhattan detour distance 𝐷 (mht) is estimated accordingly; otherwise, the UAV directly flies from 𝑝 𝑖 to 𝑝 𝑖 ′ along the straight exploration capability of ES2 A. • SubM B.2: Hierarchical heuristic decoding and evaluation. line. Accordingly, the horizontal detour energy is calculated Due to the strict task active time-window and energy constraints as 𝑐 (obs,lvl) (ℎ). Meanwhile, based on the altitude difference of UAVs, a priority sequence cannot be directly converted between ℎ and ℎ𝑖 , the vertical climbing or descending energy into executable UAV path. Therefore, we design a hierarchical is calculated as 𝑐 (obs,vtl) (ℎ). Thus, the obstacle-related cost is heuristic decoder to translate each priority-encoded individual given by 𝑐 (obs) (ℎ) = 𝑐 (obs,lvl) (ℎ) + 𝑐 (obs,vtl) (ℎ). Then, the total into feasible paths. The decoder contains three serially coupled altitude cost is evaluated by combining ecological penalty and decision strategies, namely, joint obstacle avoidance and flight- obstacle-related cost: 𝐽 (alt) (ℎ) = 𝑓 (eco) (ℎ) + 𝑐 (obs) (ℎ). Finally, altitude decision, collection-altitude decision, and adaptive the optimal flight altitude for this segment is selected as discrete speed selection. ℎ∗ = arg min 𝐽 (alt) (ℎ). (30) ℎ∈ H Strategy 1: Joint obstacle avoidance and flight-altitude decision. When UAV 𝑢 𝑚 flies from PoI 𝑝 𝑖 to PoI 𝑝 𝑖 ′ , it needs to determine Strategy 2: Optimal data-collection altitude decision. After a proper flight altitude6 . Recall discussions in Sec. II, the flight UAV 𝑢 𝑚 arrives at 𝑝 𝑖 ′ , it further needs to determine the optimal altitude is affected by the ecological penalty related to low- altitude for data collection. Different from the flight-altitude, decision should additionally consider altitude operation and the obstacle-avoidance cost caused by the collection-altitude (uav,𝑡 ) the data quality 𝑞 , since lower altitude may improve the 𝑚 vertical climbing or horizontal detouring. Thus, consider a sensing quality while also increasing the ecological penalty flight segment from (𝑥𝑖 , 𝑦 𝑖 , ℎ𝑖 ) to (𝑥𝑖 ′ , 𝑦 𝑖 ′ , ℎ𝑖 ′ ), we first check and altitude-changing cost. Therefore, we apply a grid search the obstacles intersecting the straight line between two PoIs (path) over the interval. Specifically, during data collection, the UAV in the horizontal plane, and collect them into the set b𝑖,𝑖 ′ , searches the altitude interval (ℎ𝑖(uav,min) , ℎ (eco) ) with a step ′ (path) (obs) and let ℎ𝑖,𝑖 ′ denote the maximum obstacle altitude in b𝑖,𝑖 ′ . size of 𝑙 (search) . For each candidate altitude, the decoder The optimal flight altitude can be obtained by (29). calculates the corresponding ecological penalty, additional 𝑡ˆ𝑝𝑖 ′ ∑︁ ∑︁ © ª energy consumption, and data collection quality. The collection (uav,𝑡 )∗ (uav, 𝜏 ) ℎ𝑚 = arg min ­­ 𝛾1 𝑓 (eco, 𝜏 ) (ℎ 𝑚 ) + 𝛾2 𝑐 𝑛(obs) ®® altitude is then selected by maximizing the difference between ℎ (path) service quality and the sum of the ecological penalty and 𝜏=𝑡ˆ b𝑖,𝑖 ′ ¬ « 𝑝𝑖 (29) additional energy consumption. Through the above stepwise grid Here, ℎ ∈ [ℎmin , ℎmax ], 𝑡ˆ𝑝𝑖 denotes the time when UAV 𝑢 𝑚 search, the decoder reduces computational complexity while finishes data collection at 𝑝 𝑖 , and 𝑡ˆ𝑝𝑖′ represents the time when jointly considering obstacle avoidance, ecological impact, and it arrives at 𝑝 𝑖 ′ ; 𝛾1 and 𝛾2 are weighting coefficient. Since data-collection quality. Algorithms related to the former two (29) contains nonlinear terms and the feasible altitude space strategies are presented in Alg. 1 (see Appendix). is bounded, we design joint 3D avoidance-altitude decision, Strategy 3: Adaptive discrete speed selection. After determining transforming the path planning process into a multi-cost trade- the flight and collection altitudes, the decoder plans the off over a discrete set of representative altitude strategies, to flying speed toward the target task. For analytical simplicity, speed is discretized into several candidate levels: V = balance energy consumption, time cost, and ecological impact. the  (slow) 𝑣 , 𝑣 (mid) , 𝑣 (fast) . For the flight segment from PoI 𝑝 𝑖 to Then, four representative candidate altitudes are considered (arr,𝑣) (since they work for all pairs of 𝑝 𝑖 and 𝑝 𝑖 ′ , we omit 𝑖 and 𝑖 ′ 𝑝 𝑖 ′ , let 𝑑𝑖,𝑖 ′ denote the segment distance and t𝑚 denote the for simplicity): arrival time of UAV 𝑢 𝑚 when flying with speed 𝑣. Moreover, • Current-or-target altitude ℎ (ct) : ℎ (ct) = max(ℎ𝑖 , ℎ𝑖 ′ ). The t𝑖(start) and t𝑖(end) denote the start time and deadline of task maximum altitude between the current point and the target related PoI 𝑝 𝑖 , respectively. The decoder allows the UAV to arrive slightly later than the task start time, since the reduced 6 Note that here we use 𝑝 and 𝑝 ′ to denote PoIs while do not care their 𝑖 𝑖 types, since Module B only preplans the paths for the former two types of collected data can be compensated by other cooperative UAVs. PoIs. However, arriving after the deadline is meaningless. Thus, the

10

time-violation cost is designed as   0,      (arr,𝑣) (time) − t𝑖(start) , 𝐶𝑚,𝑖,𝑖 ′ = 𝜔 t𝑚 ′    +∞, 

t t t

t

(arr,𝑣) ≤ 𝑖(start) , ′ 𝑚 (start) (arr,𝑣) < 𝑡𝑚 < 𝑖′ (arr,𝑣) (end) ≥ 𝑖′ , 𝑚

t

t𝑖(end) , ′

(31) where 𝜔 is the timeout penalty coefficient. The energy cost considers both the flying energy and the hovering energy caused by early arrival, given by   (energy) (mov,𝑣) 𝑑 𝑖,𝑖 ′ (hov) (arr,𝑣) 𝐶𝑚,𝑖,𝑖 ′ = 𝑒 𝑚 + 𝑒𝑚 max t𝑖(start) − t𝑚 ,0 . ′ 𝑣 (32) Accordingly, the speed cost function is defined as (energy) (time) 𝐽𝑚,𝑖,𝑖 ′ (𝑣) = 𝐶𝑚,𝑖,𝑖 ′ + 𝐶𝑚,𝑖,𝑖 (33) ′ . The decoder traverses all candidate speeds in V and selects the one with the minimum cost: 𝑣 ∗ = arg min 𝐽 (𝑣). (34)

relationship between 𝑟 and the warning threshold 𝑆 (st) , the priority vector is updated by    𝑔+1 (𝑔)    x · exp − , 𝑟 < 𝑆 (st) , 𝑜 (𝑔+1) x𝑜 = (36) 𝐺 (max)   x (𝑔) + 𝜀z, (st) , 𝑟 ≥ 𝑆  𝑜 where 𝐺 (max) denotes the maximum number of generations, z ∼ N (0, I) is a standard Gaussian random vector, and 𝜀 is the perturbation amplitude coefficient. When 𝑟 < 𝑆 (st) , the discoverer performs local search with a progressively shrinking search range. Otherwise, random perturbations are applied to the priority vector to preserve population diversity and prevent premature convergence.

(ii) Joiner update. Joiners perform auxiliary search and structural adjustments, refining task priorities through multi-scale perturbations around the current global best. This jointly exploits local structure and explores globally in the high-dimensional priority 𝑣∈V With sufficient remaining time, the decoder selects the most space. At generation 𝑔, joiners are split into two subgroups by energy-efficient cruising speed since no time penalty is incurred. fitness ranking. The update rule is defined as   As the deadline tightens, it favors higher speeds to reduce time 1  (𝑔) (best,𝑔)   x + 𝜼− ⊙ x𝑜 − x (best,𝑔) , 𝑜 ≤ 𝜏 (f) , (𝑔+1) violation penalties. x𝑜 = 2  (best,𝑔) After the above three strategies are completed, the decoder  + 𝜁L(D), 𝑜 > 𝜏 (f) . x evaluates the execution cost of each feasible UAV for the current (37) (f) (p) task. Specifically, for each task in the priority sequence, the (f) = (1+𝜌 ) 𝑁 where 𝜏 denotes the adaptive threshold, 2 decoder reads the current fleet state D W (𝑡) = {(l𝑚 , t𝑚 , 𝐸 𝑚 ) | 𝑢 𝑚 ∈ U} , (35) 𝜼 ∼ U(0, 1) is a random vector, ⊙ denotes the elementwise product, 𝜁 is the Levy step-size scaling coefficient, and where l𝑚 , t𝑚 , and 𝐸 𝑚 denote current location, available service D = 𝑁 (task) is the dimension of the priority vector. Moreover, time, and remaining energy of UAV 𝑢 𝑚 , respectively. For each L(D) denotes a D-dimensional Levy-flight random vector UAV satisfying the altitude, time-window, energy, and collision generated by the Mantegna algorithm, whose components constraints, the decoder determines its flight altitude, collection follow a heavy-tailed Lévy distribution [31]. Joiners are altitude, and speed, and then generates a feasible flight path stratified by fitness: high-fitness individuals perform small-scale from its current location to the task location (see procedure of perturbations around the global best to refine local solutions, Strategy 3 in Alg. 2, Appendix). while low-fitness individuals undergo large-scale Lévy-flight The task execution cost combines energy consumption and perturbations that reshape task priorities and expand the search ecological penalties along the generated path. UAVs with space. This differential strategy balances local exploitation and finite costs are ranked to form a candidate list. The decoder global exploration, preventing population over-concentration at sequentially selects UAVs to satisfy the task’s data requirement, a single scale. Thus, ES2 A maintains cross-region exploratory assigning it to a single UAV if sufficient, or cooperatively to capacity throughout iterations, structurally alleviating premature multiple UAVs otherwise. UAV states, remaining energy, and convergence (see Alg. 3, Appendix). paths are updated after each assignment. The decoded paths are then evaluated by net reward given in (19), which defines Strategy 2: Danger-aware mechanism and elite perturbation. the individual’s fitness. • SubM B.3: Adaptive evolution integrated with Lévy-flight. Although the discoverer–joiner update can balance exploitation Strategy 1: Basic evolutionary update of the Lévy-flight-based and exploration to some extent, it may still suffer from adaptive evolutionary. After the hierarchical heuristic decoding two issues: (i) premature convergence caused by population and fitness evaluation (base on (19)), ES2 A enters evolutionary homogenization and (ii) search stagnation caused by the longupdate. At the beginning of each generation, all individuals7 term non-improvement of the global best individual. This is are ranked in descending order according to their fitness values mainly due to the highly nonlinear mapping between the priority (𝑔) 𝐹 (x𝑜 ) obtained through the decoding and evaluation process vector x𝑜 and the fitness value 𝐹 (x𝑜 ) induced by the heuristic in SubM B.2, and the historical global best priority vector decoder, together with the fragmented and multi-modal nature is updated as x (best,𝑔) . Then, according to the predefined of the feasible region. Consequently, individuals may rapidly discoverer ratio 𝜌 f ∈ (0, 1), the top ⌊𝜌 f 𝑁 (p) ⌋ individuals are converge to similar priority structures, leading to reduced selected as discoverers, while the remaining ones are regarded diversity and weakened capability to escape local optima. as joiners. To alleviate this, we introduce a danger-aware mechanism (i) Discoverer update. Discoverers represent the individuals with relatively high fitness in the current population. Their role is to inspired by the emergency response behavior of sparrow popuconduct focused search around promising regions and guide the lations under predation risk. When convergence degradation is evolutionary direction of the population. For each discoverer, detected, such as insufficient population diversity or prolonged a random number 𝑟 ∼ U(0, 1) is generated. According to the stagnation of the best fitness, the mechanism performs a low-frequency adjustment on selected individuals to maintain 7 Since each individual corresponds to only one task-priority vector, and all subsequent operations are performed on the task-priority vector of the diversity while preserving exploitation around promising regions. individual, the individual and its priority vector are treated equivalently hereafter Specifically, during the 𝑔-th generation, a subset of individuals for simplicity, without further distinction. is randomly selected to form the danger-aware set K𝑔 . For any

11

𝑢 𝑚 per unit time. The definitions of the concepts involved in selected individual 𝑜 ∈ K𝑔 , the update rule is  (𝑔) Module C are given as follows: (best,𝑔) (best,𝑔)  , x + 𝝐 ⊙ x𝑜 − x     (III,𝑡 )   if 𝐹 (x𝑜(𝑔) ) < 𝐹 (x (best,𝑔) ),  • Candidate feasible UAV set: For 𝑝 𝑖 , if UAV 𝑢 𝑚 can (𝑔+1) x𝑜 = (38) reach before its deadline while satisfying the remain (𝑔)   x𝑜 + 𝛿𝝃, ing energy constraint, minimum flight-altitude constraint,     if 𝐹 (x𝑜(𝑔) ) = 𝐹 (x (best,𝑔) ), obstacle-avoidance constraint, and the feasibility of subse quent flight after task insertion, then 𝑢 𝑚 is regarded as a where 𝝐 is a random vector uniformly distributed in [0, 1], candidate feasible UAV for 𝑝 𝑖(III,𝑡 ) . The candidate feasible ⊙ denotes the Hadamard product, 𝝃 is a zero-mean random UAV set is denoted by perturbation vector, and 𝛿 is the perturbation amplitude control n o (req) (cand) (start) (𝑡 ) coefficient. These two cases correspond to different danger𝑈𝑖 = 𝑢 𝑚 ∈ U t𝑚,𝑖 < t𝑖(−,𝑡 ) , 𝑒 𝑚 ≥ 𝑒 𝑚,𝑖 , aware behaviors. Individuals with fitness lower than the current (40) best are guided toward the best priority structure to intensify ex(𝑡 ) where 𝑒 𝑚 is the remaining energy of UAV 𝑢 𝑚 at timeslot ploitation of promising regions. In contrast, individuals already (req) 𝑡, and 𝑒 𝑚,𝑖 represents the additional energy consumption reaching the best fitness level are subjected to controlled random required for UAV 𝑢 𝑚 to insert and execute this emergent perturbations, preventing the population from collapsing into a task. single priority structure and preserving exploration capability. • Feasible solution set: A feasible solution 𝐺 𝑖 represents By combining elite-guided exploitation and perturbation-based a UAV group generated by selecting a certain number diversity preservation, the danger-aware mechanism effectively of UAVs from 𝑈𝑖(cand) to respond to the emergent task. mitigates search stagnation and improves the robustness of the offline pre-planning process in high-dimensional task-priority It specifies which UAVs are assigned to execute 𝑝 𝑖(III,𝑡 ) . spaces (see Alg. 4, Appendix). Meanwhile, the selected UAV group should satisfy the 3) Module C: Greedy-empowered timely adjustment when tolerable collision-risk constraint, i.e., Type-III PoIs have needs (Stage 2): Since Type-III PoIs emerge 𝐺 𝑖 ⊆ 𝑈𝑖(cand) , 𝜃 𝑖 (𝐺 𝑖 ) < 𝜃 (max) , (41) without prior knowledge, Module C performs online adaptation where 𝜃 𝑖 (𝐺 𝑖 ) denotes UAV collision risk caused by the based on the offline plan generated by Module B. Rather than cooperative execution of task 𝑝 𝑖(III,𝑡 ) by UAVs in 𝐺 𝑖 . replanning globally, it preserves the overall path structure and • Candidate cooperative set: For each 𝐺 𝑖 , we evaluate the locally adjusts the remaining task sequence and trajectories joint task contribution of its UAVs. If the total available when new Type-III tasks arrive, ensuring real-time responsivedata contribution satisfies the data requirement of the ness with low computational overhead. Upon task detection, Í (avail) emergent task, i.e., 𝑢𝑚 ∈𝐺𝑖 𝑑 𝑚,𝑖 ≥ 𝑑𝑖(III,𝑡 ) , 𝐺 𝑖 can be feasible UAVs are identified according to the current fleet state, regarded as a feasible task-completion solution (FTCS). and candidate cooperative sets are evaluated via a cooperative All FTCSs constitute a candidate cooperative set net-benefit metric that jointly captures task reward, reward n o as (𝑔) (1) (2) ( | G𝑖 | ) dilution, additional energy consumption, and plan disruption. G𝑖 = 𝐺 𝑖 , 𝐺 𝑖 , . . . , 𝐺 𝑖 , . . . , 𝐺 𝑖 , (42) The cooperative set and insertion time maximizing the feasible net benefit are then selected for execution. • SubM C.2: Net-benefit evaluation and greedy assignment • SubM C.1: Construction of task-feasible set (Alg. 5, for candidate cooperative sets. After obtaining G𝑖 , a proper Appendix). When a new Type-III PoI 𝑝 𝑖(III,𝑡 ) ∈ P (III,𝑡 ) appears at selection scheme that jointly consider task reward, additional timeslot 𝑡, it is necessary to first determine whether the currently energy consumption, and variation of ecological penalty caused remaining schedulable UAVs can complete data collection by path adjustment should be designed. Therefore, we inrequirement within the valid time window. Recall (35) and vestigate a net-benefit evaluation mechanism for candidate (III,𝑡 ) denote the original reward obtained the emergent task 𝑝 𝑖(III,𝑡 ) at time 𝑡, with its active time window cooperative sets. Let 𝑟 𝑖 (III,𝑡 ) (−,𝑡 ) (III,𝑡 ) . For a feasible UAV [𝑡, t𝑖 ], and the required amount of collected data 𝑑𝑖 . after completing task related to 𝑝 𝑖 (𝑔) First, for any UAV 𝑢 𝑚 ∈ U, whether it has the basic feasibility group 𝐺 ⊆ G𝑖 , when multiple UAVs cooperate to execute 𝑖 to participate in the emergent task is determined. To this end, the task, the effective task reward is assumed to be equally (III,𝑡 ) the earliest arrival time of UAV 𝑢 𝑚 at the task location under 𝑟 (III,𝑡 ,𝑔) (fly) (fly) (arr) (𝑡 ) shared among the participating UAVs, i.e., 𝑟˜𝑖 = 𝑖 (𝑔) . the current state is defined as t𝑚,𝑖 = t𝑚 + 𝜏𝑚,𝑖 , where 𝜏𝑚,𝑖 |𝐺𝑖 | denotes the flight time required for UAV 𝑢 𝑚 to fly from its For any candidate UAV 𝑢 𝑚 ∈ 𝐺 (𝑔) , after executing task 𝑝 (III,𝑡 ) , 𝑖 𝑖 current position to the task location. This flight time is jointly its individual net benefit  can be:  (fly) (III,𝑡 ,𝑔) (III,𝑡 ,𝑔) determined by the altitude decision, velocity selection, and (hov) (dist) (eco) Δ𝐽𝑚,𝑖 = 𝑟˜𝑖 − 𝐶𝑚,𝑖 + 𝐶𝑚,𝑖 + 𝐶𝑚,𝑖 − 𝐶𝑚,𝑖 (𝑡 ) obstacle-avoidance mechanism in Module B. Moreover, t𝑚 | {z } | {z } denotes the time when UAV 𝑢 𝑚 completes its current task. ecological penalty energy-related Considering that a Type-III task becomes active from its occur(43) rence time 𝑡, the actual data collection start   time of UAV 𝑢 𝑚 can where 𝐶 (fly) denotes the additional flight cost of UAV 𝑢 𝑚 for (start) (arr) (start) 𝑚,𝑖 be expressed as t𝑚,𝑖 = max t𝑚,𝑖 , 𝑡 . When t𝑚,𝑖 < t𝑖(−,𝑡 ) , (hov) reaching the PoI, 𝐶𝑚,𝑖 is the hovering cost caused by waiting UAV 𝑢 𝑚 is temporally feasible to participate in data collection for the task to start or by inconsistent cooperative timing, and before the task deadline. Furthermore, its effective collection (dist) 𝐶𝑚,𝑖 represents the disturbance cost caused by deviating from (eff) (start) duration for this task is defined as Δt𝑚,𝑖 = t𝑖(−,𝑡 ) − t𝑚,𝑖 . the original offline pre-planned path. These three terms together Accordingly, the maximum amount of data that UAV 𝑢 𝑚 can constitute the energy-related cost of the UAV. Moreover, path contribute to task 𝑝 𝑖(III,𝑡 ) can be estimated as adjustment may change the ecological penalty of UAV flight, (avail) (uav) (eff) (eco) 𝑑 𝑚,𝑖 = 𝑑𝑚 Δt𝑚,𝑖 , (39) and 𝐶𝑚,𝑖 denotes the corresponding ecological penalty cost. (uav) where 𝑑 𝑚 denotes the data collection capability of UAV Accordingly, the total cooperative net benefit of 𝐺 𝑖 for task

12

(a)

(b)

(c)

(d)

(e)

(f)

Fig. 2: Prediction on type-II PoIs: three examples. related to 𝑝 𝑖(III,𝑡 ) can be expressed ∑︁as (III,𝑡 ) Δ𝐽𝑖(III,𝑡 ) (𝐺 𝑖 ) = Δ𝐽𝑚,𝑖 .

calculate practical net reward (PrcNR) cross the whole process (offline+online), given by (19). These two metrics provide complementary perspectives for evaluating the effectiveness of 𝑢𝑚 ∈𝐺𝑖 This indicates that, for the same task, although the total reward is online adjustment. While F3TSR characterizes the capability fixed, different cooperative sets may lead to different cooperative of responding to newly emerging online tasks, PrcNR reflects net benefits due to diverse scales, flight states, and disturbance the overall outcome achieved through the joint offline planning levels to the original paths. Therefore, the cooperative set with and online adjustment process. Therefore, the combination of them enables a comprehensive evaluation of both instantaneous the maximum net benefit is selected: online responsiveness and end-to-end operational performance. (∗) (III,𝑡 ) 𝐺 𝑖 = arg max Δ𝐽𝑖 (𝐺 𝑖 ). (45) We next introduce different views on benchmark designs. 𝐺𝑖 ∈ G𝑖 (∗) Pre-planning-related methods. (i) Pre-CS2 A: Leveraging • After obtaining the optimal cooperative set 𝐺 𝑖 , we determine whether the corresponding re-planning action is worthwhile. Transformer-based predictions, conventional SSA is subseIf Δ𝐽𝑖(III,𝑡 ) (𝐺 𝑖(∗) ) > 0, task 𝑝 𝑖(III,𝑡 ) is incorporated into the quently adopted to perform solution-space exploration. (ii) remaining task sequences of the associated UAVs. Otherwise, Pre-GA: Following Transformer-based prediction, a genetic if Δ𝐽𝑖(III,𝑡 ) (𝐺 𝑖(∗) ) ≤ 0, the task is rejected, although it remains algorithm (GA) is employed to search for high-quality schedulfeasible with respect to both timing and data requirements, ing solutions. (iii) Pre-PSO: Following Transformer-based because its gain is insufficient to offset the additional flight and prediction, a particle swarm optimization (PSO) algorithm is employed to search for high-quality UAV paths. (iv) Prepath-disruption costs introduced by re-planning. For 𝐺 𝑖(∗) , each DisG: After obtaining the Transformer-based predictions, Preparticipating UAV moves to execute the Type-III task at the DisG assigns each activated task to the nearest available UAV earliest feasible time after completing its currently assigned task, according to spatial proximity, enabling immediate task service while satisfying the flight, energy, and time-window constraints. upon task arrival. As such, the online re-planning module enables a fast response • Purely online method. To outline the advantages of PoI to Type-III PoIs without re-triggering global optimization, while prediction, We involve a purely online method PureOn-DistG, maintaining the rationality and economic efficiency of local path rendering both Type-I and Type-II PoIs unknown to UAVs. In insertion (see pseudocode of SubM C.2 in Alg. 6, Appendix). this case, task assignment follows a distance-greedy policy that prioritizes the nearest available PoI. IV. E VALUATIONS • Online adjustment methods. We further design representative We conduct extensive experiments on both real-world and online benchmarks for handling emergent Type-III PoIs. It simulated datasets to validate the effectiveness of FORTUNE, is worth emphasizing that, unlike conventional settings, our as well as its scalability across varying problem sizes. UAVs have already pre-generated proper paths to service the former two types of PoIs. Consequently, when a TypeIII PoI unexpectedly appears, UAVs should respond without A. Evaluation Metrics and Benchmark Methods Since FORTUNE offers a unique aspect on the integration of compromising the feasibility of their pre-planned tasks. This offline pre-planning and online adjustment for heterogeneous significantly restricts the set of admissible online actions and PoIs. To better evaluative the performance, we involve the leaves limited room for large-scale trajectory re-optimization. Under such real-time operational constraints, lightweight asfollowing metrics from two perspectives: • Metrics related to offline planning stage. (i) We first signment policies constitute practical and widely adopted online calculate offline fitness function (OffF2) associated with Types- response mechanisms. Accordingly, we consider the following Í |P (I) | (I) representative baselines. (i) On-DistG: Upon the arrival, each I and -II PoIs, as expressed by R (I,II,net) = + UAV independently evaluates whether the additional activate 𝑖=1 𝑟 𝑖 Í |P (II) | Í 𝐴𝑖 (II,𝑎) − f , where f denotes the negative impact task can be completed while still retaining sufficient energy to 𝑖=1 𝑎=1 𝑟 𝑖 only related to these two PoI types. (ii) Then, we consider finish its offline pre-planned mission. If feasible, the UAV selects offline task completion rate (OffTCR), which depends on the the nearest Type-III PoI for data collection under constraint (C2). ratio of the number of tasks successfully completed by UAVs (ii) On-RewdG: When Type-III PoIs emerge, each UAV first during pre-planning to the total number of tasks (Types-I and verifies whether executing an additional sensing task preserves -II). These two metrics aim to validate the effectiveness of our the feasibility of its offline pre-planned mission. Among all Transformer-based forecasting and ES2 A, making sure that the feasible Type-III PoIs, a UAV preferentially selects the one with the highest reward under (C2). If excessive UAV aggregation offline planning stage can get a good beginning. • Metrics related to online adjustment stage. (i) We first discuss violates this constraint, the remaining UAVs are sequentially first-timeslot Type-III task completion ratio (F3TSR), reflecting reassigned to the next highest-reward feasible PoIs. UAVs the ratio between Type-III tasks successfully completed and unable to satisfy the energy requirement remain idle during the total generated Type-III tasks in the first timeslot (see the the current timeslot. (iii) On-RandA: Once a Type-III appears, rationale on choosing F3TSR in Appendix). (ii) Then, we a UAV is randomly selected from the feasible candidate set (44)

13

(𝑈𝑖cand ), consisting of UAVs that can complete the task while maintaining sufficient energy for their pre-planned missions. The selected UAV performs the sensing task, whereas other UAVs continue executing original plans. (a)

B. Experiments on Real-World Dataset This section uses the real-world UTD19 dataset8 , which contains traffic-flow measurements collected from multiple cities worldwide between 2017 and 2019. Traffic data from Basel, Switzerland, on April 17, May 17, and June 17, 2019, are adopted for evaluation. As shown in Fig. 6 as an example (see Appendix), selected sensing locations are categorized into TypeI (blue) and Type-II (orange) POIs. The predicted time windows of Type-II POIs are incorporated into the offline planning stage. To capture unforeseen sensing requests, additional locations are designated as Type-III POIs (red), with randomly generated occurrence times and service windows for online replanning. • Performance on PoI prediction. First, we conduct a comparative study of time-series forecasting models. Specifically, we compare the self-attention-based Transformer model (as our predictor) with the conventional long short-term memory (LSTM) network. The data is split into training, validation, and test sets at a ratio of 7:2:1, and the models are configured as detailed in Table II of Appendix. We adopt the mean squared error (MSE) as the loss function. Across all Type-II PoIs, the Transformer achieves an average MSE of 0.026, substantially lower than the 0.042 obtained by LSTM. Figure 2 presents the predictions for three randomly selected PoIs. Both models capture the overall temporal dynamics of traffic flow well; however, we adopt the Transformer for subsequent forecasting due to its superior accuracy and stronger capability of modeling long-range temporal dependencies. This advantage is particularly important in our setting, where the activation of a Type-II PoI is determined by whether its predicted traffic flow exceeds the threshold 𝑜 (∗) . More accurate forecasts thus enable more reliable identification of PoI activation windows and reduce error propagation in subsequent UAV scheduling and sensing decisions. Accordingly, a Type-II PoI is considered active when its predicted traffic flow exceeds 𝑜 (∗) . Since most PoIs exhibit sustained high traffic demand during the daytime, we set the common take-off time of the UAV swarm to the 60-th time slot. This choice aligns UAV deployment with the predominant activation period of Type-II PoIs, thereby improving task coverage under the energy-efficiency constraint. • Comparison with benchmark methods. The predicted PoI activation windows obtained from the Transformer are subsequently used to configure the offline pre-planning experiments. Parameters of scenario and our ES2 A are summarized in Tables III and IV (see Appendix), respectively. Figs. 3(a)-(b) presents the offline pre-planning results on UTD-19 dataset across different experimental days. Our ES2 A consistently achieves the OffF2 and OffTCR, with the latter approaching 95% across all dates. These gains stem from three 8 https://utd19.ethz.ch/

(a)

(b)

(c)

Fig. 3: Performance on real-world dataset.

(d)

(b)

(c)

(d)

Fig. 4: Performance on numerical data settings.

complementary enhancements. First, Tent-chaotic initialization promotes a more uniform distribution of priority sequences, substantially improving population diversity at the early search stage. Second, a hierarchical heuristic integrating joint 3D obstacle avoidance, adaptive altitude control, optimal sensingaltitude selection, and discrete velocity optimization effectively guides UAVs to complete data collection within the active windows of Type-II PoIs while satisfying tightly coupled 3D physical constraints, thereby reducing unnecessary hovering and energy expenditure. Finally, the combination of Lévy-flightbased long-range exploration and event-driven risk-aware perturbation significantly strengthens the optimizer’s ability to escape local optima, yielding superior global search performance. Figs. 3(c)-(d) further compares the online response strategies for Type-III PoIs based on the pre-planned offline paths. Our FORTUNE consistently outperforms all benchmark methods in both PrcNR (see (19)) and F3TSR. This advantage arises from its collaborative response mechanism, which overcomes the limitation of single-UAV dispatch by dynamically forming a cooperative UAV group 𝐺 𝑖 to satisfy high-volume sensing demands. Moreover, the collaborative net-reward evaluation jointly accounts for mission rewards and response costs, including trajectory deviation and ecological penalties, enabling the selection of globally optimal response strategies. Compared with On-RewdG, On-DistG achieves a higher F3TSR by assigning the nearest available UAV, thereby shortening transit time and extending the effective sensing duration for task execution. Conversely, On-RewdG prioritizes high-reward PoIs, sacrificing partial task coverage in exchange for larger per-task returns, which compensates for unfinished tasks and consequently yields a higher PrcNR than On-DistG. C. Experiments on Numerical Dataset To further assess the scalability of FORTUNE, we construct diverse scenario settings of increasing complexity. The duration of each time window is uniformly sampled from 5 to 10 timeslots. Unless otherwise specified, remaining parameters follow tables in Appendix. Scenario#1: 20 UAVs operate over a (3km × 3km) area containing 10 Type-I PoIs and 10 Type-II PoIs. Scenario#2: 30 UAVs operate over a (4km × 4km) area containing 15 Type-I PoIs and 15 Type-II PoIs. Scenario#3: 40 UAVs operate over a (5km × 5km) area containing 20 Type-I PoIs and 20 Type-II PoIs. Figs. 4(a)-(b) compare OffF2 and OffTCR under varying problem scales. Consistent with the real-world experiments, our FORTUNE consistently achieves the best performance across all settings. This superiority stems from the synergistic integration of multiple algorithmic enhancements, which simultaneously improve population initialization quality and global search capability. More importantly, the results validate the robustness and scalability of FORTUNE, confirming its effectiveness for large-scale offline cooperative trajectory pre-planning in dynamic PoI-driven UAV collaboration.Moreover, Figs. 4(c)(d) exhibit performance trends consistent with those in Fig. 3

14

(a)

(b)

(c)

(d)

(e)

(f)

Fig. 5: Examples of 3D UAV paths: randomly selected four UAVs as examples.

across all three scenarios, further validating the robustness of FORTUNE in accommodating stochastic Type-III PoIs through efficient online collaborative response. Furthermore, we visually illustrate our FORTUNE with examples across different timeslots, shown in Fig. 5. V. C ONCLUSION AND F UTURE W ORK This paper presented FORTUNE, a hierarchical offline-online framework for 3D low-altitude collaborative sensing under heterogeneous spatio-temporal uncertainty. To the best of our knowledge, this is the first work to unify persistent, predictable, and emergent PoIs within a single planning framework while explicitly incorporating altitude-dependent societal and environmental impacts into UAV decision-making. Extensive experimental results demonstrated the effectiveness, adaptability, and scalability. Future research may advance embodied aerial intelligence through self-organizing collaborative autonomy, enabling UAV swarms to dynamically coordinate sensing responsibilities in response to evolving spatio-temporal demands, while achieving LA4G. R EFERENCES [1] Y. Zhao, C. Liu, X. Hu, J. He, M. Peng, D. Wing Kwan Ng, and T. Q. S. Quek, “Joint content caching, service placement, and task offloading in uav-enabled mobile edge computing networks,” IEEE J. Sel. Areas Commun., vol. 43, no. 1, pp. 51–63, 2025. [2] X. Yang, M. Liwang, L. Fu, Y. Su, S. Hosseinalipour, and X. Wang, “Adaptive uav-assisted hierarchical federated learning: Optimizing energy, latency, and resilience for dynamic smart iot,” IEEE Trans. Serv. Comput., vol. 18, no. 6, pp. 3420–3434, 2025. [3] R. Ren, J. Zhao, and Q. Zhang, “Uav-assisted collaborative sensing task offloading and resource allocation in iov,” IEEE Trans. Veh. Technol., vol. 75, no. 4, pp. 6806–6815, 2026. [4] C. Xiang, Z. Li, Q. Zhang, X. Wu, X. Zheng, and Y. Guo, “Eagleeye: Balancing latency, accuracy, and power on edge-assisted uavs for urban crowd surveillance,” IEEE Trans. Mobile Comput., vol. 24, no. 12, pp. 13 062–13 077, 2025. [5] R. Xu, Z. Huang, C. Wang, and H. Yan, “Evolving collaborative differential evolution for dynamic multi-objective uav path planning,” IEEE Trans. Veh. Technol., vol. 75, no. 5, pp. 7456–7468, 2026. [6] Z. Yang, Z. Xiao, Z. Han, and X.-G. Xia, “Joint path planning and transmission scheduling for multi-uav data collection,” IEEE Trans. Veh. Technol., vol. 75, no. 4, pp. 6600–6615, 2026. [7] S. Javed, R. Ahmad, A. Hassan, W. Ahmed, L. Zhao, and M. Guizani, “Critical node-aware uav swarm path planning in disaster zones,” IEEE Internet of Things J., vol. 13, no. 2, pp. 2020–2034, 2026. [8] MarketsAndMarkets, “Unmanned aerial vehicles market,” https://www.marketsandmarkets.com/MarketReports/ unmanned-aerial-vehicles-uav-market-662.html, 2025, accessed: Jun. 4, 2026. [9] L. Liu, Z. Shan, and R. Lv, “Joint optimization of computation offloading and service caching for dag topology tasks in uav-assisted blockchainenabled vec system,” IEEE Trans. Veh. Technol., pp. 1–16, 2026. [10] C. Fang, C. H. Liu, H. Wang, G. Qi, Z. Liu, and D. Wu, “Multi-taskoriented emergency-aware uav crowdsensing: A hierarchical multi-agent deep reinforcement learning approach,” IEEE J. Sel. Areas Commun., vol. 44, pp. 866–882, 2026. [11] H. He, W. Yuan, S. Chen, Y. Hou, S. Chen, and X. Tan, “Two-timescale trajectory planning for uav formation serving hotspot in unknown environments with complex obstacles,” IEEE Trans. Cogn. Commun. Netw., vol. 12, pp. 4261–4276, 2026.

[12] Y. Guo, Y. Chen, H. Li, Y. Wu, and J. Huang, “Aoi-aware incentive mechanism for uav-assisted mobile crowdsensing: A contract-theoretic approach,” IEEE Trans. Mobile Comput., vol. 25, no. 2, pp. 1660–1677, 2026. [13] W. Yuan, G. Gao, Y. Hou, J. Wang, S. Chen, and H. He, “Deep transfer reinforcement learning-based exploration enhanced multi-uav trajectory planning,” IEEE Trans. Commun., vol. 74, pp. 1577–1593, 2026. [14] Y. Ye, Y. Tian, C. H. Liu, L. Dong, G. Qi, and D. Wu, “Aoi-aware air-ground mobile crowdsensing by multi-agent curriculum learning with collaborative observation augmentation,” IEEE Trans. Mobile Comput., vol. 24, no. 11, pp. 11 675–11 687, 2025. [15] H. Wang, C. H. Liu, H. Yang, G. Wang, and K. K. Leung, “Ensuring threshold aoi for uav-assisted mobile crowdsensing by multi-agent deep reinforcement learning with transformer,” IEEE/ACM Trans. Netw., vol. 32, no. 1, pp. 566–581, 2024. [16] P. Hou, S. Liu, H. Zhu, J. Wang, Z. Lu, and S.-C. Huang, “Hierarchical optimization-based multi-uav cooperative trajectory planning and integration of sensing and communication,” IEEE Trans. Veh. Technol., pp. 1–16, 2026. [17] Z. Li, Y. Guo, G. Wang, J. Sun, and K. You, “Informative trajectory planning for air-ground cooperative monitoring of spatio-temporal fields,” IEEE Trans. Autom. Sci. Eng., vol. 22, pp. 2627–2638, 2025. [18] L. Deng, W. Gong, M. Liwang, L. Li, B. Zhang, and C. Li, “Towards intelligent mobile crowdsensing with task state information sharing over edge-assisted uav networks,” IEEE Trans. Veh. Technol., vol. 73, no. 8, pp. 11 773–11 788, 2024. [19] H. Gao, J. Feng, Y. Xiao, B. Zhang, and W. Wang, “A uav-assisted multi-task allocation method for mobile crowd sensing,” IEEE Trans. Mobile Comput., vol. 22, no. 7, pp. 3790–3804, 2023. [20] T. Yu, F. Cao, X. Wang, and J. Hu, “Madrl-based multi-uav 3d trajectory planning for 6g-oriented communication assistance,” IEEE Trans. Intell. Transport. Syst., vol. 26, no. 12, pp. 23 041–23 054, 2025. [21] Y. Wang, F. Hu, H. Xu, and J. Zeng, “A multi-groups cooperative particle swarm algorithm for optimization of multi-vehicle path planning in internet of vehicles,” IEEE Internet Things J., vol. 11, no. 22, pp. 35 839– 35 851, 2024. [22] C. He, H. Ouyang, W. Huang, S. Li, C. Zhang, W. Ding, and Z. Zhan, “An adaptive heuristic algorithm with a collaborative search framework for multi-uav inspection planning,” Applied Soft Comput., vol. 174, pp. 1–21, 2025. [23] H. Liu, Y. P. Tsang, C. K. M. Lee, and C. H. Wu, “Uav trajectory planning via viewpoint resampling for autonomous remote inspection of industrial facilities,” IEEE Trans. Ind. Informat., vol. 20, no. 5, pp. 7492–7501, 2024. [24] W. Yuan, S. Chen, H. He, Y. Hou, S. Chen, and X. Tan, “Hierarchical reinforcement learning-based joint trajectory planning and resource allocation in uav-assisted iot-sensor networks,” IEEE Trans. Commun., vol. 73, no. 12, pp. 14 517–14 533, 2025. [25] J. Pan, Y. Li, R. Chai, S. Xia, and L. Zuo, “Distributed multi-uav 3d trajectory planning based on multi-agent deep reinforcement learning,” IEEE Trans. Cogn. Commun. Netw., vol. 12, pp. 4577–4592, 2026. [26] Z. Guo, R. Chai, R. Sun, C. Liang, and Q. Chen, “System utility function optimization-based flight trajectory and resource allocation for uav-assisted integrated sensing and communication systems,” IEEE Trans. Cogn. Commun. Netw., vol. 12, pp. 6331–6343, 2026. [27] J. Zheng and K. Liu, “3d uav trajectory planning with obstacle avoidance for uav-enabled time-constrained data collection systems,” IEEE Trans. Veh. Technol., vol. 74, no. 1, pp. 1460–1474, 2025. [28] V. Schmuck and O. Celiktutan, “Sang: Socially aware navigation between groups,” Int. J. Social Robot., vol. 17, no. 6, pp. 989–1002, 2025. [29] S. Nahavandi, R. Alizadehsani, D. Nahavandi, S. Mohamed, N. Mohajer, M. Rokonuzzaman, and I. Hossain, “A comprehensive review on autonomous navigation,” ACM Comput. Surv., no. 9, pp. 1–67, 2025. [30] C. Sun, W. Ni, and X. Wang, “Joint computation offloading and trajectory planning for uav-assisted edge computing,” IEEE Trans. Wireless Commun., vol. 20, no. 8, pp. 5343–5358, 2021. [31] L. Chen, X. Wu, A. M. Lopes, D. Wang, P. Gu, M. Zhu, and Y. Chen, “Complex-order quantum-behaved particle swarm optimization with double jump-out strategy,” IEEE Trans. Emerg. Top. Comput. Intell., vol. 9, no. 5, pp. 3469–3487, 2025.

15

Algorithm 1: Altitude optimization for path preplanning Input: Start point 𝑝𝑖 , target point 𝑝𝑖 ′ , obstacle set b𝑖,𝑖 ′

(path)

(a)

(b)

Fig. 6: Schematic maps of PoIs related to offline pre-planning (a) and online replanning (b).

A PPENDIX • Rationale on F3TSR. We specifically evaluate F3TSR because the performance on later online tasks is inherently coupled with historical task execution and accumulated resource consumption, making it difficult to isolate the effectiveness of the online planning strategy itself. In particular, UAVs operate under limited onboard energy budgets, and every online task completed in earlier timeslots consumes flight and sensing resources that cannot be replenished during the mission. Such cumulative energy expenditure progressively reduces the maneuverability and reachable sensing region of each UAV, thereby directly affecting its ability to respond to newly emerging Type-III PoIs in subsequent timeslots. Consequently, the completion rate of later Type-III tasks is influenced not only by the real-time decision-making capability of an algorithm, but also by the historical planning outcomes and resource allocation decisions accumulated over previous timeslots. Comparing algorithms using the overall Type-III completion ratio would therefore inevitably mix the effectiveness of online adaptation with the long-term impact of prior decisions, leading to a biased evaluation. To eliminate this temporal coupling effect and ensure a fair comparison, we evaluate only the Type-III tasks generated in the first timeslot, where all algorithms start from identical initial energy budgets, identical UAV states, and the same offline pre-planned trajectories. Under these controlled conditions, the observed performance differences can be attributed solely to the quality of the online adjustment strategy. Therefore, F3TSR serves as a representative and unbiased indicator for assessing the real-time responsiveness and online task-handling capability of different algorithms. • Pseudocodes related to 𝐸 𝑆 2 𝐴. We show detailed algorithmic tables corresponding to our 𝐸 𝑆 2 𝐴 design. • Parameter setting tables. We also show tables related to different parameter settings.

, maximum

(obs) obstacle height ℎ𝑖,𝑖 ′ , weighting factors 𝛾1 , 𝛾2 , search step 𝑙 (search) (uav,𝑡 )∗ Output: Optimal flight altitude ℎ𝑚 , optimal collection altitude ℎ (collect)∗

// Joint decision of flight altitude and 3D obstacle avoidance (ct) ← max(ℎ , ℎ ′ ); 1 ℎ 𝑖 𝑖 (limit) ← ℎ (obs) + 𝛿 (safe) ; 2 ℎ (eco) (ℎ (eco) ) = 𝜘eco to obtain ℎ (eco) ; 3 Solve 𝑓 (eco) (ℎ (mid) ) = 𝜘mid to obtain ℎ (mid) ; 4 Solve 𝑓 (ct) , ℎ (limit) , ℎ (eco) , ℎ (mid) }; 5 H ← {ℎ 6 foreach ℎ ∈ H do 7 if the path at altitude ℎ is blocked by obstacles then 8 Estimate the Manhattan detour distance 𝐷 (mht) ; 9 Calculate the additional horizontal detour energy consumption 𝑐 (obs,lvl) ; 10

else 𝑐 (obs,lvl) ← 0;

11 12

13 14

Calculate the additional vertical altitude-changing energy consumption 𝑐 (obs,lvl) ; (obs) 𝑐𝑛 ← 𝑐 (obs,lvl) + 𝑐 (obs,vtl) ; (obs) 𝐽 (ℎ) ← 𝛾1 𝑓 (eco) (ℎ) + 𝛾2 𝑐𝑛 ; (uav,𝑡 )∗

ℎ𝑚 ← arg minℎ∈H 𝐽 (ℎ); // Grid search for collection altitude (uav,min) , ℎ (uav,min) + 𝑙 search , . . . , ℎ (eco) }; 16 H (search) ← {ℎ 17 foreach ℎ ∈ H (search) do (uav,𝑡 ) 18 Calculate the data collection quality 𝑞𝑚 (ℎ); (obs) 19 Calculate the energy consumption 𝑐𝑛 (ℎ) and ecological penalty 𝑓 (eco) (ℎ);
(uav,𝑡 ) (obs) 20 𝑅 (ℎ) ← 𝑞𝑚 (ℎ) − 𝑓 (eco) (ℎ) + 𝑐𝑛 (ℎ) ; 15

21

ℎ (collect)∗ ← arg maxℎ∈H (search) 𝑅 (ℎ);

Algorithm 2: Adaptive discrete speed selection Input: Flight segment distance 𝑑𝑖,𝑖 ′ , current time t (now) , task start (start) (end) time t𝑖 of task 𝑝𝑖 , task deadline t𝑖 of task 𝑝𝑖 , speed set V Output: Optimal speed 𝑣 ∗ ∗ 1 Initialize the minimum cost 𝐽 (min) ← ∞ and 𝑣 ← 0; 2 foreach candidate speed 𝑣 ∈ V do (fly) 3 Calculate the flight time: t𝑚 ← 𝑑𝑖,𝑖 ′ /𝑣; (fly) (arr,𝑣) 4 Predict the arrival time: t ← t (now) + t𝑚 ; (energy) (fly) 5 Calculate the energy cost: 𝐶𝑚,𝑖,𝑖 ′ ← 𝑃 (𝑣) · t𝑚 ; 6 7 8 9 10 11

(time)

Calculate the time cost 𝐶𝑚,𝑖,𝑖 ′ ; (energy) (time) 𝐽 (total) ← 𝐶𝑚,𝑖,𝑖 ′ + 𝐶𝑚,𝑖,𝑖 ′ ; if 𝐽 (total) < 𝐽(min) then

𝐽(min) ← 𝐽(total) ; 𝑣 ∗ ← 𝑣; return 𝑣 ∗ ;

16

Algorithm 4: Danger-aware mechanism and fitness update strategy (𝑔) 𝑁

𝑝 Input: Population {x𝑜 } 𝑜=1 , current global best priority vector (best,𝑔) x , number of danger-aware individuals 𝑁𝑑 , elite perturbation coefficient 𝛿 Output: Historical global best priority vector x (best,𝑔+1)

// Danger-aware mechanism Randomly select 𝑁𝑑 individuals from the population to form the danger-aware set K𝑔 ; 2 foreach 𝑜 ∈ K𝑔 do     (𝑔) 3 if 𝐹 x𝑜 < 𝐹 x (best,𝑔) then

1

Algorithm 3: Basic evolutionary update integrated with Levy flight 𝑝 Input: Initial task-priority sequences {x𝑜(0) } 𝑜=1 , maximum (max) number of generations 𝐺 , discoverer ratio 𝜌 f , warning threshold 𝑆 (st) , perturbation amplitude coefficient 𝜀, Levy step-size scaling coefficient 𝛼 (𝑔+1) 𝑁 𝑝 Output: Updated population {x𝑜 } 𝑜=1 , current global best priority vector x (best,𝑔)

𝑁

// Initialization for 𝑜 = 1 to 𝑁 𝑝 do   2 Decode x𝑜(0) and calculate its fitness 𝐹 x𝑜(0) ;

1

3

Sort the population in descending order of fitness and update x (best,0) ;

5

5

6

7 8 9 10 11 12 13

14 15 16 17 18 19 20 21

Divide the top ⌊𝜌 f 𝑁 𝑝 ⌋ individuals as discoverers, and regard the remaining individuals as joiners; // Discoverer update foreach discoverer individual 𝑜 do Generate a random number 𝑟 ∼ U (0, 1); if 𝑟 < 𝑆 (st) then   𝑔+1 (𝑔+1) (𝑔) x𝑜 ← x𝑜 exp − (max) ; 𝐺 else Generate a Gaussian vector z ∼ N (0, I); (𝑔+1) (𝑔) x𝑜 ← x𝑜 + 𝜀z; // Joiner update foreach joiner individual 𝑜 do (1 + 𝜌 f )𝑁 𝑝 then if 𝑜 ≤ 2 (task) Generate a random vector 𝜼 ∼ U (0, 1) 𝑁 ; (𝑔) (𝑔) d𝑜 ← x𝑜 − x (best,𝑔) ;   1 (𝑔+1) (𝑔) x𝑜 ← x (best,𝑔) + 𝜼 − ⊙ d𝑜 ; 2 else Generate a Levy vector L(𝑁 (task) ); (𝑔+1) x𝑜 ← x (best,𝑔) + 𝛼L(𝑁 (task) );

(𝑔+1)

x𝑜

6 7 8 9

(task)

;

(𝑔)

← x (best,𝑔) + 𝝐 ⊙ d𝑜 ;

else Generate a zero-mean perturbation vector 𝝃; (𝑔+1) (𝑔) x𝑜 ← x𝑜 + 𝛿𝝃;

// Re-decoding and fitness update for 𝑜 = 1 to 𝑁 𝑝 do   (𝑔+1) (𝑔+1) 11 Decode x𝑜 and calculate its fitness 𝐹 x𝑜 ;

10

12

(max) − 1 do 4 for 𝑔 = 0 to 𝐺

// Sorting and role division Sort the population in descending order according to (𝑔) 𝐹 x𝑜 and update x (best,𝑔) ;

Generate a random vector 𝝐 ∼ U (0, 1) 𝑁 (𝑔) (𝑔) d𝑜 ← x𝑜 − x (best,𝑔) ;

4

13

Sort the population in descending order of fitness and update x (best,𝑔+1) ; return x (best,𝑔+1) ;

Algorithm 5: Construction of the task-feasible set: feasible UAV set construction and candidate cooperative set generation (III,𝑡 )

Input: Emergent task 𝑝𝑖 appearing at the current timeslot 𝑡; current UAV fleet state 𝑊 (𝑡 ) = { (l𝑚 , t𝑚 , 𝐸𝑚 ) | 𝑢𝑚 ∈ U}; (III,𝑡 ) (III,𝑡 ) UAV set U; task data requirement 𝑑𝑖 ; task reward 𝑟𝑖 ; (−,𝑡 ) valid task time window [𝑡 , t𝑖 ]; collision-risk threshold 𝜃 max Output: Candidate cooperative set G𝑖 (cand) 1 𝑈𝑖 ← ∅; 2 foreach 𝑢𝑚 ∈ U do (start) 3 Estimate the earliest service start time 𝑡𝑚,𝑖 for UAV 𝑢𝑚 to (III,𝑡 ) insert and execute task 𝑝𝑖 based on its current state (l𝑚 , t𝑚 , 𝐸𝑚 ); (req) 4 Estimate the additional energy consumption 𝑒𝑚,𝑖 ; (avail) 5 Estimate the available data contribution 𝑑𝑚,𝑖 within the task time window; (req) (start) (−,𝑡 ) 6 if t𝑚,𝑖 < t𝑖 and 𝐸𝑚 ≥ 𝑒𝑚,𝑖 then (cand) (cand) 7 𝑈𝑖 ← 𝑈𝑖 ∪ {𝑢𝑚 }; (cand)

if 𝑈𝑖 = ∅ then 9 return No feasible local re-planning solution;

8

G𝑖 ← ∅; (cand) foreach candidate UAV group 𝐺𝑖,𝑔 constructed from 𝑈𝑖 do 12 Calculate the cooperative collision risk 𝜃𝑖,𝑔 of 𝐺𝑖,𝑔 ; 13 Calculate the joint available data contribution Í (avail) 𝐷𝑖,𝑔 = 𝑢𝑚 ∈𝐺𝑖,𝑔 𝑑𝑚,𝑖

10 11

22

(𝑔+1) 𝑁 𝑝 } 𝑜=1 and x (best,𝑔) ;

Output {x𝑜

14 15

(III,𝑡 )

if 𝜃𝑖,𝑔 < 𝜃 max and 𝐷𝑖,𝑔 ≥ 𝑑𝑖 G𝑖 ← G𝑖 ∪ {𝐺𝑖,𝑔 };

then

17

if G𝑖 = ∅ then return The current task cannot be completed; no local re-planning is executed;

18

return G𝑖 ;

16

17

Algorithm 6: Net-benefit evaluation and greedy selection for candidate cooperative sets (III,𝑡 )

Input: Emergent task 𝑝𝑖 ; candidate cooperative set G𝑖 ; original (III,𝑡 ) task reward 𝑟𝑖 Output: Optimal cooperative set 𝐺𝑖∗ ; maximum cooperative net (max) benefit Δ𝐽𝑖 𝐺𝑖∗ ← ∅; (max) 2 Δ𝐽𝑖 ← −∞; 3 if G𝑖 = ∅ then (max) 4 return 𝐺𝑖∗ , Δ𝐽𝑖 ; 1

5 6

foreach 𝐺𝑖,𝑔 ∈ G𝑖 do (III,𝑡 )

Calculate the effective task reward 𝑟˜𝑖,𝑔

𝑟

(III,𝑡 )

𝑖 = |𝐺

𝑖,𝑔 |

(III,𝑡 )

7 8 9 10 11 12

13 14 15 16

17

Δ𝐽𝑖 (𝐺𝑖,𝑔 ) ← 0; foreach 𝑢𝑚 ∈ 𝐺𝑖,𝑔 do (fly) Estimate the flight cost 𝐶𝑚,𝑖 ; (hov) Estimate the hovering cost 𝐶𝑚,𝑖 ; (dist) Estimate the path disturbance cost 𝐶𝑚,𝑖 ; (eco) Estimate the ecological penalty cost 𝐶𝑚,𝑖 ; Calculate the individual net benefit   (fly) (III,𝑡 ) (III,𝑡 ) (hov) (dist) (eco) Δ𝐽𝑚,𝑖,𝑔 = 𝑟˜𝑖,𝑔 − 𝐶𝑚,𝑖 + 𝐶𝑚,𝑖 + 𝐶𝑚,𝑖 − 𝐶𝑚,𝑖 ; (III,𝑡 ) (III,𝑡 ) (III,𝑡 ) Δ𝐽𝑖 (𝐺𝑖,𝑔 ) ← Δ𝐽𝑖 (𝐺𝑖,𝑔 ) + Δ𝐽𝑚,𝑖,𝑔 ; (III,𝑡 )

(max)

if Δ𝐽𝑖 (𝐺𝑖,𝑔 ) > Δ𝐽𝑖 then (max) (III,𝑡 ) Δ𝐽𝑖 ← Δ𝐽𝑖 (𝐺𝑖,𝑔 ); 𝐺𝑖∗ ← 𝐺𝑖,𝑔 ; (max)

return 𝐺𝑖∗ , Δ𝐽𝑖

;

TABLE II: Hyperparameters for Transformer and LSTM Parameter

Transformer

LSTM

Hidden Size Layers Heads Learning Rate Batch Size Epochs Optimizer

64 2 4 0.01 32 300 Adam

64 2 N/A 0.01 32 300 Adam

TABLE III: Scenario parameter settings for offline pre-planning stage based on UTD19 Parameter

Value

Number of UAVs Map size/km Total time slots Total PoIs (Type I/II) Base reward per task Minimum flying altitude / m Maximum flying altitude / m Critical altitude/m Marginal reward coefficient for data quality Ecological penalty weight

20 4×4 200 10 / 10 [2, 5] 50 150 100 0.5 0.05

TABLE IV: Core parameter settings of our ES2 A Parameter

Value

Population size Maximum iterations Proportion of discoverers Alarm threshold Lévy flight step scaling factor Number of danger-aware individuals Perturbation coefficient for best individual Task priority encoding range

50 300 0.2 0.7 0.01 12 0.05 [0, 1]

Related documents

• Integrating the multiple perspectives of people and nature in place-based marine spatial planning#350658
• Manned-Unmanned Teaming Cooperative Formation Flight - A Project Review#481992
• TARGET-CENTERED, ADAPTIVE PATH PLANNING FOR UAS–USV OPERATIONS IN GPS-DENIED MARITIME ENVIRONMENTS#674684
• MA-LIPP: Cooperative Multi-Agent Load-Aware Informative Path Planning for Heterogeneous Robot Teams#1035135
• Graph-based Complexity Forecasts in UK En Route Airspace Using Relevant Aircraft Interactions#222595