Cooperative Detour Planning for Dual-Task Drone Fleets

This paper proposes a decentralized "meet-and-merge" framework for dual-task drone fleets that dynamically coordinates local joint path planning to simultaneously optimize delivery efficiency and real-time urban traffic monitoring, achieving near-global optimality with significantly reduced computational overhead compared to centralized approaches.

The Gist

Imagine a city where thousands of delivery drones are buzzing around, dropping off packages. Usually, these drones are like single-minded taxis: they take the absolute shortest, fastest route from Point A to Point B, ignoring everything else.

But what if these drones could do double duty? What if, while dropping off your pizza, they could also act as flying eyes in the sky, taking pictures of traffic jams, accidents, and road conditions to help the city run smoother?

This paper proposes a clever system to make that happen without slowing down deliveries too much. Here is the breakdown using simple analogies.

The Problem: The "Lonely Taxi" vs. The "Team Player"

Currently, if you have 30 delivery drones, they all act like lonely taxis.

• The Shortest Path Trap: If three drones need to go to three different places nearby, they might all fly over the exact same busy street because it's the fastest way.
• The Result: They waste their battery and time looking at the same traffic jam three times, while other parts of the city remain in the dark. They miss the chance to gather useful data.

The Solution: The "Meet-and-Merge" Strategy

The authors propose a new way for drones to think. Instead of flying solo, they use a "Meet-and-Merge" strategy.

The Analogy: The Coffee Shop Chat
Imagine the drones are people walking through a city.

1. Solo Mode: When a drone is far away from others, it just walks the shortest path to its destination.
2. The Meeting: When two or more drones get close enough to talk (within a 300-meter "Wi-Fi bubble"), they stop and have a quick chat.
3. The Merge: They share their "mental maps." One drone might say, "I just flew over Main Street; it's clear." The other says, "I haven't been to 5th Avenue in a while; it might be jammed."
4. The Re-Plan: Together, they decide: "Okay, since you know Main Street is clear, you take that path. I'll take the longer, winding route through 5th Avenue to check it out. We'll split up to cover more ground."

They then go their separate ways, having optimized their paths to cover the whole city better, even if it means taking a slightly longer detour.

The Rules of the Game

To make this work, the system has to follow two strict rules, like a game of chess:

1. The Delivery Promise: The drone must still get the package to the customer. It can take a detour, but not too far (the paper suggests up to 30% longer than the fastest route).
2. The Battery Budget: The drone has a limited amount of energy. It can't fly forever. The system calculates exactly how much "extra" energy it has to spare for checking traffic before it needs to land and recharge.

How It Works in Real Life (The "Brain" of the System)

The paper describes a mathematical brain (a Mixed-Integer Linear Programming model) that solves this puzzle instantly.

• Centralized vs. Decentralized:
  • The Old Way (Centralized): Imagine one giant super-computer in a tower trying to control all 30 drones at once. It's powerful, but if the city gets busy, the computer gets overwhelmed and crashes.
  • The New Way (Decentralized): The drones only talk to their neighbors. They solve the puzzle locally. It's like a group of friends planning a road trip by talking in small groups rather than waiting for a single leader to give orders to everyone. It's faster, cheaper, and scales up easily.

The Results: Why It Matters

The researchers tested this in a simulation of Barcelona, Spain. Here is what they found:

• Better Coverage: The "Meet-and-Merge" drones covered 80% of the city's roads, compared to only 46% for the drones just taking the shortest path.
• Fresh Data: The traffic information they gathered was much newer and more accurate.
• Efficiency: They didn't slow down deliveries significantly (only about 22% longer on average), but they gained massive amounts of useful traffic data.
• Speed: Because they didn't rely on a super-computer, the system was fast enough to run in real-time.

The Big Picture

Think of this as turning a fleet of delivery drones from single-purpose couriers into community helpers. They still deliver your package, but on the way, they help the city see what's happening on the roads, all while working together like a well-coordinated team of friends rather than a group of strangers.

This approach proves that you don't have to choose between delivering goods and monitoring the city; with smart planning, you can do both at the same time.

Technical Summary

1. Problem Definition

The paper addresses the challenge of optimizing Urban Air Mobility (UAM) fleets that perform dual tasks: delivering parcels and monitoring urban traffic conditions simultaneously.

• Core Conflict: Delivery drones are typically routed via shortest paths to minimize time and energy. However, this leads to redundant coverage of the same road segments, leaving other areas unmonitored. Conversely, dedicating drones solely to monitoring is inefficient given limited flight resources.
• Objective: Develop a routing strategy that allows drones to deviate from their shortest delivery paths (within a defined "detour budget") to maximize the collection of fresh traffic information across the road network.
• Constraints:
  • Battery Budget: Drones have limited energy.
  • Detour Limit: Delivery delays must not exceed a specific percentage (e.g., 30%) of the shortest path time.
  • Communication: Drones operate in a decentralized environment with limited communication ranges; they cannot rely on a central controller with global real-time knowledge.
  • Information Dynamics: Traffic information on road segments degrades over time (uncertainty grows). The value of monitoring a segment depends on how long it has been since the last visit.

2. Methodology

The authors propose a Decentralized Event-Triggered Cooperative Detour Planning framework based on a "Meet-and-Merge" strategy.

A. Traffic Information Modeling

• Information Reward ($R_{ij}$): Modeled as a linear function of the time elapsed since the last visit to a road segment $(i, j)$, multiplied by an uncertainty growth density ($\beta_{ij}$).
• Belief Matrix: Since global state is unknown in a decentralized system, each drone maintains a local belief matrix ($B$) representing the estimated last visit time for all edges.
• Reward Saturation: Rewards are capped ($R_{max}$) to prevent infinite accumulation for unvisited edges.

B. Optimization Formulation (MILP)

The problem is formulated as a Mixed-Integer Linear Programming (MILP) problem for a cluster of drones ($K$) within communication range.

• Decision Variables: Binary variables ($x_{ijk}$) indicating if drone $k$ traverses edge $(i, j)$, and continuous variables for arrival times ($t_{i,k}$) and scan times ($t^{scan}_{ij}$).
• Objective: Maximize the total cooperative information gain ($\sum R_{ij}$) collected by the cluster.
• Constraints:
  • Flow Conservation: Ensures valid paths from origin to destination.
  • Battery & Detour: Limits the total travel time to the effective remaining budget ($B_{eff,k}$), calculated based on remaining battery and maximum allowable delay.
  • Temporal Feasibility: Ensures arrival times respect travel speeds and current drone positions.
  • Redundancy Prevention: Ensures that if multiple drones cover an edge, the reward is calculated only once (based on the earliest scan time).

C. Decentralized Algorithm ("Meet-and-Merge")

1. Event Trigger: Drones initially plan paths independently. When two or more drones enter a communication radius ($R_c$), they form a cooperative cluster.
2. Synchronization: The cluster synchronizes their local belief matrices by taking the element-wise maximum of their individual matrices (assuming the most recent observation is the truth).
3. Joint Optimization: The cluster solves the MILP jointly to replan paths for all members, redistributing exploration tasks to maximize coverage while respecting individual constraints.
4. Edge Pruning: To ensure computational tractability, an ellipsoid bounding technique is used to prune the graph, removing nodes that are unreachable given the remaining battery/detour budget of any drone in the cluster.
5. Fallback: If the MILP solver fails, drones revert to their shortest paths to ensure delivery completion.

3. Key Contributions

1. Dual-Task Framework: A novel approach that treats traffic monitoring as an active, optimized objective rather than a passive byproduct of delivery flights.
2. Decentralized "Meet-and-Merge" Strategy: A scalable solution that avoids the computational bottlenecks of centralized control. Drones only coordinate when they are physically close, allowing for dynamic, local joint optimization.
3. Segment-Level Monitoring: Unlike previous works that treat monitoring as visiting discrete Points of Interest (POIs), this model focuses on road-segment-level information refresh, which is more relevant for traffic state estimation.
4. Real-World Validation: The method is tested on a realistic simulation using the road network of Barcelona, Spain, with dynamic delivery requests and battery constraints.

4. Results and Analysis

The proposed method was compared against three baselines:

• Shortest Path: No monitoring optimization.
• Distributed: Drones plan individually without sharing beliefs (no coordination).
• Centralized: Global optimization with perfect knowledge (theoretical upper bound).

Key Findings (based on 30 drones, 150 parcels):

• Information Gain: The proposed Decentralized method achieved 789,091 total information gain, significantly outperforming the Distributed approach (711,301) and nearly matching the Centralized upper bound (831,278).
• Spatial Coverage: The proposed method covered 80.67% of the city edges, compared to 46.92% for the Shortest Path and 76.54% for the Distributed approach.
• Data Freshness (AoI): The Average Age of Information was 46.46%, comparable to the Centralized method (46.30%) and much better than Distributed (50.30%).
• Delivery Efficiency: The method incurred an average delivery delay of 22.15% (within the 30% budget), a slight increase over the Shortest Path but necessary for the monitoring gains.
• Computational Efficiency:
  • The Centralized approach required 1,655 MILP calls with high CPU time, making it impractical for real-time scaling.
  • The Proposed method required only 609 calls (a 63% reduction) with lower average CPU time per call, demonstrating superior scalability.

5. Significance

• Scalability: The decentralized nature of the algorithm makes it feasible for large-scale drone fleets where centralized computation is impossible due to latency and communication limits.
• Resource Efficiency: It demonstrates that delivery drones can effectively double as mobile sensor networks without significantly compromising delivery performance, maximizing the utility of limited flight resources.
• Practical Implementation: By using event-triggered local clustering, the system adapts to dynamic environments (new orders, battery levels, communication topology) in real-time, bridging the gap between theoretical optimization and real-world deployment in Urban Air Mobility.

The paper concludes that this "meet-and-merge" strategy offers a near-optimal solution for network coverage with significantly reduced computational overhead, paving the way for integrated logistics and traffic monitoring systems in smart cities.