Research on Collaborative Task Allocation of Heterogeneous UAVs With Complex Constraints

Shaokun Yan, Yuanqing XiaIEEE Access 2023 · DOI

TL;DR

This paper introduces the Dynamic Clustering Consensus-Based Bundle Algorithm (DCCBBA), a decentralized framework that slashes the communication overhead of multi-UAV task allocation by up to 80%. By organizing drones into clusters and using a two-tier consensus strategy—coupled with realistic path planning via Pythagorean Hodograph curves—the authors enable heterogeneous swarms to solve complex, constrained missions more efficiently than standard industry baselines.

What Problem Does This Paper Address?

Coordinating a swarm of Unmanned Aerial Vehicles (UAVs) to perform tasks like reconnaissance and strike missions is a massive computational and logistical headache. While centralized controllers are easy to design, they represent a "single point of failure." Decentralized methods like the Consensus-Based Bundle Algorithm (CBBA) are more robust, but they suffer from a "chatter" problem: as the number of drones and tasks grows, the amount of communication required for every drone to agree on a plan explodes exponentially.

Furthermore, real-world missions involve complex constraints: some tasks require "duo cooperation" (two drones working together), drones have different capabilities (heterogeneity), and tasks must be completed within strict time windows. Most existing algorithms also simplify path planning to straight lines, which leads to inaccurate cost estimations because real drones can't make instantaneous 90-degree turns.

Methods

The authors propose DCCBBA, which improves upon the baseline CBBA in three major ways:

  1. Dynamic Clustering: Instead of every drone talking to every other drone, the system uses a modified K-means algorithm to group UAVs based on their spatial distribution. They use a specific circular initialization method to ensure stable, consistent clusters.
  2. Two-Tier Consensus & Vital Nodes: Within each cluster, the algorithm identifies a "Vital Communication Node" using a combination of centrality measures (Betweenness, Closeness, Degree, and Eigenvector centrality).
  3. Inner Conflict Resolution: Drones resolve bids within their cluster via the vital node.
  4. Outer Conflict Resolution: Vital nodes from different clusters communicate with each other to ensure global agreement.
  5. Pythagorean Hodograph (PH) Curves: The algorithm integrates 5th-order PH curves for path planning. Unlike straight lines or simple splines, PH curves provide smooth, "flyable" trajectories. This ensures that the "cost" a drone calculates for a task actually matches the distance it will fly in reality.

Datasets

The study relies on numerical simulations rather than public datasets. The authors constructed several scenarios in Matlab:

  • Environment: A 10km x 10km area.
  • Agents: 4 to 10 heterogeneous UAVs (categorized for reconnaissance or strike).
  • Tasks: 5 to 45 tasks including reconnaissance, strike, and integrated "R&S" tasks.
  • Monte-Carlo Simulations: The team ran 100 iterations per scenario to ensure statistical significance.

Key Insights and Ideas

  • Hierarchical Communication is Key: The "aha moment" here is that global consensus doesn't require global broadcasting. By limiting most "bidding wars" to local clusters and only passing the winning bids between clusters via vital nodes, the network bandwidth is preserved without sacrificing the quality of the final assignment.
  • The "Flyability" Gap: The authors found a 9.03% difference in total path length when comparing their PH curve planning to standard task allocation that ignores path smoothing. In a fuel-constrained mission, that 9% error could be the difference between a successful return and a lost drone.
  • Centrality Matters: Not all drones are equal in a network. By using eigenvector and betweenness centrality to pick "vital nodes," the system ensures that the drones with the best "reach" in the communication graph handle the heavy lifting of inter-cluster negotiation.

Key Results

  • Communication Efficiency: DCCBBA significantly outperformed the baseline CBBA. In scenarios with high network density, communication events were reduced by roughly 48% to 80%.
  • Robustness: Compared to other variants like Cluster-Formed CBBA (CF-CBBA), DCCBBA showed a much lower rate of "allocation failures," meaning it was better at finding valid solutions for all tasks even as complexity increased.
  • Convergence: The algorithm consistently reached a conflict-free global agreement in a small number of iterations (typically around 5 in the primary test case).
  • Scalability: As the number of tasks increased from 5 to 45, the communication load for DCCBBA grew linearly, whereas the baseline CBBA grew much more aggressively.

Limitations and Future Work

While the results are promising, the authors acknowledge a few hurdles:

  • Static Environments: The current model assumes task and UAV locations are known at the start. In reality, new tasks pop up and drones move, requiring "dynamic replanning" which isn't fully explored here.
  • Computational Complexity: While communication is reduced, the local computation required for 5th-order PH curves and centrality measures is higher than simpler models.
  • Guarantee of Optimality: Like most bundle algorithms, DCCBBA is a greedy heuristic. While it is fast and robust, it doesn't mathematically guarantee the absolute best possible assignment (the global optimum), though it gets very close.

The team suggests that future research should focus on applying DCCBBA to uncertain environments where communication links might drop or task requirements might change mid-flight.

Summary updated

BibTeX
@article{yan2023research,
  author = {Shaokun Yan and Yuanqing Xia},
  title = {{Research on Collaborative Task Allocation of Heterogeneous UAVs With Complex Constraints}},
  journal = {IEEE Access},
  year = {2023},
  doi = {10.1109/access.2023.3323951},
}
Figure