CS Paper Radar

Synergizing Drone Delivery Order Pooling and Road Network Monitoring through Monitoring-Task Orderization

Yulong Hu, Meng Xu, Sen Li, Nikolas Geroliminis

cs.MA cs.LG ·submitted 2026-10-04 14:45 UTC · v1

Abstract

This paper investigates the real-time dispatch of a shared drone fleet for on-demand food delivery and urban road network monitoring. We consider a courier-drone collaborative setting in which couriers transport orders to launchpads and drones complete the final delivery leg to kiosks. Drones may consolidate multiple origin-destination orders within one flight and make monitoring-aware route adjustments to collect real-time traffic information subject to delivery-time constraints. This yields a joint decision problem coupling dynamic order-to-drone matching, multi-order pooling, routing, and time-varying monitoring under fleet-level competition and uncertainty. We propose monitoring-task orderization, which periodically converts road-network nodes with high congestion and stale information into virtual monitoring orders. Pooling these virtual tasks with food-delivery orders creates a unified heterogeneous task set and transforms the coupled matching-and-routing problem into an order-level decision process. Building on this abstraction, we formulate a decentralized graph-interdependent Multi-Agent Markov Decision Process and develop Graph Multi-Agent Q-Learning (Graph-MAQL), which captures localized inter-agent dependencies through bipartite match coordination graphs. Agent-task value estimates are then used as edge weights in a dynamic heterogeneous bipartite matching program for globally feasible execution. Experiments using real-world data reveal strong operational synergy between delivery and monitoring. Monitoring-task orderization improves monitoring performance by 25.1% with less than a 1% reduction in delivery performance, while Graph-MAQL improves the aggregate objective by up to 20.8%, reduces deadline violations by over 40%, and transfers zero-shot to higher demand intensity without retraining.

Closest papers

Nearest neighbours by meaning across the whole index.

HALO: Heterogeneous Allocation Via Localized Observations for the Vehicle Routing Problem

cs.RO cs.MA ·2026-09-30 ·Andrew Meighan, Hyungsub Kim, Or Dantsker
theory similarity 0.64
Abstract · 2026 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future me…

Scalable robotic fleets have become increasingly popular for various applications such as package delivery, warehouse management, and military operations. Prior fleet control algorithms solve centralized routing problems with up to $1{,}000$ tasks in controlled environments, yet they fail to consider realistic constraints such as limited observation and communication ranges typical of decentralized fleets. Thus, deploying existing fleet control algorithms into real-world settings is currently infeasible. To tackle this, we propose Heterogeneous Allocation via Localized Observations (HALO) to solve the Vehicle Routing Problem (VRP). HALO is a hybrid method that splits the VRP into allocation and routing portions to provide onboard, real-time solutions to robots in dynamic environments. During the allocation phase, HALO utilizes a heterogeneous graph neural network framework with unique message passing layers to explicitly separate the learning of spatial distributions and task-to-robot compatibility. Evaluation results on a partially observable, online variant of the VRP show HALO significantly outperforms the heuristic baseline while maintaining similar solution quality to an all-knowing offline variant of HALO. While HALO is explicitly designed for partially observable environments, it imposes no strict upper bound on the observation space allowing us to test HALO on the traditional static, single-depot VRP. Here, HALO outperforms state-of-the-art architectures strictly optimized for the static variant of the VRP by up to $14.06\%$. Throughout all testing, this framework maintains the quickest execution times which emphasizes its potential for large-scale, real-time deployment.

0.36

SenseAlign: Learning Decision-Aligned Predictive Representations for Active Urban Sensing with UAVs

cs.AI ·2026-11-19 ·Weijiang Xiong, Nikolas Geroliminis
similarity 0.63
Abstract

Active urban sensing orchestrates a mobile sensor fleet to proactively inspect a dynamic road network and gather critical information for system management. This problem simultaneously requires understanding the complex spatio-temporal evolution and making decisions with partial observations. In this work, we focus on active sensing in a large-scale urban road network with utilities grounded in dynamic traffic states, while prior work has rarely considered these factors jointly. We propose \emph{SenseAlign}, a Reinforcement Learning-based (RL) framework that learns decision-aligned predictive representations for coordinating an urban sensing drone fleet. SenseAlign first trains a privileged teacher agent that exploits future ground-truth traffic for optimal sensing choices. The student agent has an auxiliary branch that learns to predict future traffic with partial observations, in addition to the RL-trained actor and critic branches. During student learning, our framework matches the action distributions of the teacher under ground-truth and student-predicted future traffic, while keeping the teacher's observations unchanged. Such a design shapes the latent space for decision-making instead of prediction alone. At inference time, the student agent has no overhead as all this learning is done in training. We conduct comprehensive experiments with the real road network of central Barcelona containing 1570 road segments, and demonstrate that our method consistently outperforms the baselines on multiple utility formulations. The codebase will be made publicly available upon paper acceptance.

0.23

AoI-Driven Hierarchical Learning for Cooperative Resource Sharing in Multi-Operator UAV Networks

eess.SY ·2026-09-19 ·Atefeh Hajijamali Arani, Mahyar Shirvanimoghaddam, Abolfazl Mehbodniya, Halim Yanikomeroglu, Fumiyuki Adachi
similarity 0.63
Abstract

Uncrewed aerial vehicle (UAV)-assisted networks provide a versatile paradigm for on-demand connectivity. However, in multi-operator aerial networks (MOANs), the joint optimization of cooperative resource sharing and 3D trajectory control to maintain information freshness is a complex combinatorial problem, which can be shown to be NP-hard. To address this computational complexity, we propose an age of information (AoI)-driven hierarchical deep reinforcement learning (DRL) framework. Specifically, a Dueling Double Deep Q-Network (D3QN) architecture is deployed at both the operator and UAV decision layers to mitigate overestimation bias and enhance stability in high-dimensional state spaces. To improve system resilience, we introduce an AoI- and load-aware outage compensation mechanism that prioritizes users based on instantaneous transmission demands and temporal freshness. Furthermore, a normalized load exchange balance metric is incorporated to regulate cooperative behavior and ensure resource fairness across operators. Simulation results demonstrate that the proposed hierarchical D3QN significantly outperforms conventional DRL, non-cooperative, and cooperative benchmarks, reducing the average AoI by up to 56.1% under severe congestion while ensuring superior inter-operator fairness and outage mitigation.

0.11

Drive, Pack, Fly: The Travelling Thief Problem with Drone

cs.AI cs.NEmath.OC ·2026-08-17 ·Kabir Murjani, Abhay Sobhanan
benchmark similarity 0.62
Abstract

In collection operations, accumulating payload progressively slows the vehicle, imposing a cumulative penalty on routing efficiency. An onboard drone can offset this penalty by retrieving outlying items, thereby shortening the makespan and increasing operational profit. However, travel time remains load-dependent, and each item collected by the ground vehicle shifts the arrival times that govern the drone's launch and rendezvous points. This paper introduces the Travelling Thief Problem with Drone (TTP-D), which maximises the collected profit, net of a time-based rental cost, by jointly optimising item selection, vehicle routing, and flight synchronisation. We formulate a mixed-integer linear program that solves small instances to optimality, and develop both metaheuristics and an attention-based Deep Reinforcement Learning (DRL) policy for larger instances. We further propose a learner-initialised hybrid solver, in which the DRL policy constructs an initial solution that a short annealing run subsequently refines. On two benchmark sets, this hybrid recovers most of the metaheuristic baseline's quality at a fraction of its computational budget, although the largest instances still require the baseline at its full budget. Finally, a sensitivity analysis reveals that the rental ratio is the primary driver of profitability, whereas the fleet parameters affect profit only at the margin.

0.12

Prediction is Better than Detection: Traffic Congestion Control using Drones

cs.RO cs.MA ·2026-09-30 ·Samira Hayat, Christian Raffelsberger
similarity 0.61
Abstract · 7 pages, 9 figures

A central question in deploying teams of mobile robots for persistent monitoring is how task performance scales with fleet size, and whether this scaling holds once sensing drives downstream action rather than mere observation. We study this question for a team of drones performing traffic-jam detection and prediction in a simulated road network, whose reports drive an adaptive traffic-signal controller in closed loop. We build a multi-agent simulation, with vehicles following Nagel-Schreckenberg cellular-automaton dynamics and drones patrolling junctions via a round-robin policy, and sweep fleet size, traffic level, and network size to evaluate detection rate, detection delay, and prediction rate. We show how performance plateaus for fleet size approximating the number of junctions being monitored, and offer a general fleet-provisioning rule for persistent-monitoring deployments. More significantly, adapting the signal on a predicted jam, rather than a detected one, roughly doubles the resulting reduction in jam duration, showing that the value of onboard prediction in a sensing-to-action pipeline can exceed the value of adding more robots. Prediction accuracy, not sensing coverage, is now the binding constraint on further improvement, pointing to onboard inference, not fleet size, as the more promising direction for future work.

0.20

Distributed Trajectory Planning and Resource Allocation for Dynamic Multi-UAV Collaborative Computing

cs.NI ·2026-08-24 ·Tiankui Zhang, Wenlong Xu, Tianyi Shi, Xiaoxia Xu, Arumugam Nallanathan
publishedbenchmark similarity 0.61
Abstract

This paper investigates a multiple uncrewed aerial vehicles (UAVs)-enabled distributed mobile edge computing (MEC) framework, where the set of collaborative UAVs dynamically varies over time due to their energy states and service loads. The joint optimization of trajectory planning and resource allocation is formulated as a Stackelberg game, where UAVs and mobile terminals (MTs) are modeled as leaders and followers, respectively. UAVs aim to maximize their benefits by balancing executed workload, energy cost, and resource allocation revenue, while MTs seek to minimize their total overhead, composed of computing delay and resource costs, through offloading and resource-request decisions. A hierarchical joint optimization algorithm is developed within a multi-agent deep reinforcement learning (MADRL) framework to coordinate UAVs and MTs in a distributed manner. At the leader level, UAVs jointly determine their trajectories, task migration ratios, MT-UAV association, and unit computing resource pricing. Each UAV is modeled as an agent in a partially observable Markov decision process, and the agents are jointly trained via multi-agent proximal policy optimization (MAPPO) under the centralized-training-and-decentralized-execution paradigm. At the follower level, MTs determine their optimal task offloading ratios and requested computing resources using a two-stage iterative algorithm. Simulation results demonstrate stable convergence under dynamic UAV participation. Compared to the no-collaboration benchmark, the proposed algorithm improves UAV efficiency by 18.58% through inter-UAV task migration and reduces average MT overhead by 33.77% over the fully offloading scheme. It also outperforms other benchmarks under varying network scales and capabilities by jointly optimizing UAV operations and resource utilization.

0.35

Collaborative Computation and Migration in Multi-UAV Networks with Semantic Communication

eess.SY ·2026-09-13 ·Bin Li, Yuchen Ou, Yinqiu Liu, Abbas Jamalipour
top venue similarity 0.61
Abstract · 14 pages, 10 figures

Uncrewed Aerial Vehicle (UAV)-assisted Mobile Edge Computing (MEC) is a key technology for future 6G networks, providing wide coverage and flexible computing services. However, the limited resources of UAVs and the dynamic changes in the network structure make it difficult to maintain high efficiency. Existing methods often ignore the semantic information of tasks and the complex relationships among UAVs and mobile terminals, resulting in poor coordination. This paper proposes a joint optimization framework for task offloading, task migration, and trajectory control in semantic communication-enabled multi-UAV edge computing systems, aiming to maximize semantic similarity while minimizing task latency and system energy consumption. To tackle the resultant problem, we develop a Heterogeneous Graph Attention Network-based Multi-Agent Twin Delayed Deep Deterministic Policy Gradient (HAN-MATD3) algorithm. Specifically, we use a heterogeneous graph to model the network topology and apply HAN to extract important semantic features. These features are then integrated into the MATD3 framework to support joint optimization.

0.26

Robust and Scalable UAV-UGV Planning for Aerial Monitoring under Energy and Precedence Constraints

cs.RO cs.MAeess.SY ·2026-10-08 ·Cahit Ikbal Er, Yasin Yazicioglu
similarity 0.60
Abstract

We consider planning for unmanned aerial vehicle (UAV) and unmanned ground vehicle (UGV) teams in aerial monitoring missions with ordering requirements on the monitoring points to be visited by the UAV. The system consists of multiple UAV-UGV teams, each comprising one UAV and one UGV. UAV energy limitations are modeled through endurance, defined as the maximum flight time on a full battery. The UGVs serve as mobile charging stations and transport the UAVs between consecutive aerial tours. Given a set of monitoring points subject to ordering constraints and the teams' initial and terminal positions, the objective is to minimize mission completion time while satisfying UAV energy limits and the required visit order under bounded travel-time disturbances that may arise during execution. Unlike prior work, the plan jointly determines vehicle routes and their timing, allowing teams to slow down as needed to satisfy the ordering constraints. We develop a polynomial-time algorithm that generates efficient solutions to the underlying NP-hard planning problem. We establish feasibility guarantees, characterize the algorithm's computational complexity, and evaluate its performance via numerical comparisons.

0.19