Balancing Efficiency and Fairness: An Iterative Exchange Framework for Multi-UAV Cooperative Path Planning

Hongzong Li 1 , Luwei Liao 2* , Xiangguang Dai 3 , Yuming Feng 3 · 2025

Read Balancing Efficiency and Fairness: An Iterative Exchange Framework for Multi-UAV Cooperative Path Planning by Hongzong Li 1 , Luwei Liao 2* , Xiangguang Dai 3 , Yuming Feng 3 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-00410.txt.

Introduction

Planning paths for a team of drones means avoiding collisions while sharing work fairly. Hongzong Li, Luwei Liao, Xiangguang Dai, and Yuming Feng present an iterative exchange framework for multi-UAV cooperative path planning in 2025. Efficiency means minimizing total mission cost, while fairness means balancing workload across aircraft.

A plan that is merely efficient can overburden individual drones, draining batteries and risking failures. The exchange framework trades tasks between aircraft step by step to balance both goals. Balanced, collision-free planning matters for delivery fleets, mapping missions, and search operations run by cooperating drones. Collision-free trajectories are the non-negotiable constraint underneath the efficiency and fairness goals. Iterative exchange improves the plan in small trades instead of one global solve.

Catalog record

CREATORHongzong Li 1 , Luwei Liao 2* , Xiangguang Dai 3 , Yuming Feng 3
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE16 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-00410

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Balancing Efficiency and Fairness: An Iterative Exchange Framework for Multi-UAV Cooperative Path Planning Hongzong Li 1 , Luwei Liao 2* , Xiangguang Dai 3 , Yuming Feng 3 Abstract Multi-UAV cooperative path planning (MUCPP) is a fundamental problem in multi-agent systems, aiming to generate collision-free trajectories for a team of unmanned aerial vehicles (UAVs) to complete distributed tasks efficiently. A key challenge lies in achieving both efficiency , by minimizing total mission cost, and fairness , by balancing the workload among UAVs to avoid overburdening individual agents. This paper presents a novel Iterative Exchange Framework for MUCPP, balancing efficiency and fairness through iterative task exchanges and path refinements. The proposed framework formulates a composite objective that combines the total mission distance and the makespan, and iteratively improves the solution via local exchanges under feasibility and safety constraints. For each UAV, collision-free trajectories are generated using A* search over a terrain-aware configuration space. Comprehensive experiments on multiple terrain datasets demonstrate that the proposed method consistently achieves superior trade-offs between total distance and makespan compared to existing baselines. Rong Feng 4,5 , Shiqin Tang 4 I Introduction Unmanned aerial vehicles (UAVs) have been increasingly deployed in various mission-critical applications such as monitoring [ 13 ] , search and rescue [ 5 ] , delivery [ 4 ] , and agriculture [ 16 , 12 ] . Many of these tasks require a team of UAVs to cooperatively plan collision-free trajectories that efficiently cover multiple task points distributed in complex 3D environments with obstacles and terrain. This problem, referred to as Multi-UAV Cooperative Path Planning (MUCPP) [ 20 , 19 ] , poses significant challenges in terms of computational complexity, environment constraints, and coordination fairness. A desirable cooperative plan should not only minimize the overall mission cost, such as the total traveled distance or energy consumption, but also balance the workload among UAVs to prevent overburdening a subset of agents. This leads to a multi-objective optimization problem involving both efficiency and fairness . Existing approaches typically optimize one aspect at the expense of the other: Specifically, clustering-based and assignment-based methods prioritize minimizing total distance but can yield highly unbalanced workloads [ 3 ] , while prioritized or fairness-driven methods ensure better load distribution but sacrifice global efficiency [ 8 ] . To address these issues, an Iterative Exchange Framework is proposed for MUCPP. This framework iteratively refines task assignments and path structures via local exchanges guided by a composite objective. The proposed framework integrates assignment heuristics and path refinement via A* search into a unified optimization loop. By explicitly balancing total mission distance and makespan, our method attains superior trade-offs between efficiency and fairness. The main contributions of this paper are summarized as follows: • The MUCPP problem is formulated as a multi-objective optimization problem with a weighted sum of total distance and makespan, where both efficiency and fairness in cooperative missions are jointly captured. • A novel iterative exchange framework is proposed, where task allocations and paths are progressively improved through neighborhood exchanges under feasibility constraints. • Extensive experiments demonstrate that the proposed method consistently achieves superior performance over all baselines. II Related Work Early studies formulate MUCPP as a variant of the multi-traveling salesman problem (mTSP) [ 6 ] , where each UAV is treated as a salesman responsible for a subset of tasks. Classical solutions include clustering-first-routing-second approaches, such as k -means or Christofides-based clustering [ 11 ] , followed by independent route optimization. Although computationally efficient, these methods often produce unbalanced task distributions and long makespans. Assignment-based methods, including Hungarian and insertion heuristics [ 23 , 2 ] , assign tasks by solving cost-minimizing bipartite matching problems. They ensure good total distance but may result in unfair workload allocation. Metaheuristic algorithms such as genetic algorithms (GA) [ 21 , 14 ] , ant colony optimization (ACO) [ 7 ] , and GRASP [ 18 ] introduce stochastic search to explore more diverse solutions, achieving improved performance at higher computational cost. Prioritized planning and fairness-driven scheduling methods focus on balancing workloads but sometimes ignore global optimality. Recent works incorporate fairness-aware objectives [ 22 ] , such as minimizing makespan or variance of path lengths, yet balancing efficiency and fairness remains an open challenge, particularly in terrain-constrained environments. Our proposed framework addresses this by integrating iterative exchange operations that explicitly minimize a composite cost considering both criteria. III Problem Formulation Consider K UAVs with start positions \mathcal{S}=\{s_{1},\dots,s_{K}\} and N tasks \mathcal{T}=\{t_{1},\dots,t_{N}\} , each to be visited exactly once by one UAV. Each UAV u_{k} executes a collision-free route \pi_{k} that starts at s_{k} and sequentially visits its assigned tasks \sigma_{k}=(t_{k,1},\dots,t_{k,n_{k}}) . The route length is L(\pi_{k}) , computed using a distance oracle D(\cdot,\cdot) based on A* pathfinding. A multi-UAV plan \Pi=\{\pi_{1},\dots,\pi_{K}\} is feasible if all tasks are covered exactly once and all path segments satisfy the collision-free condition. The objective is to balance total efficiency and fairness by minimizing J(\Pi)=\alpha\sum_{k=1}^{K}L(\pi_{k})+(1-\alpha)\max_{k}L(\pi_{k}), (1) where \alpha\in[0,1] is a trade-off parameter. In our experiments, \alpha=0.5 . The problem generalizes the multi-depot m -TSP and is NP-hard. IV Method Algorithm 1 Iterative-Exchange Framework for Multi-UAV Cooperative Planning 1: Start positions \{s_{k}\}_{k=1}^{K} , tasks \mathcal{T} , distance oracle D(\cdot,\cdot) , trade-off \alpha , iteration budget I_{\max} 2: Feasible multi-route plan \Pi=\{\pi_{k}\}_{k=1}^{K} 3: Initialize empty routes \sigma_{k}\leftarrow() for all k 4: Assign tasks using LPT heuristic minimizing marginal increase of J 5: for each route \sigma_{k} do 6: Order tasks by nearest-neighbor; refine using open 2-opt 7: end for 8: for i=1 to I_{\max} do 9: Perform relocate moves on critical routes; apply best improvement 10: Perform swap moves between critical pairs 11: Apply intra-route 2-opt 12: Apply cross-exchange between routes 13: Rebalance with KL-style boundary reallocation if J improves 14: if no improvement then 15: break 16: end if 17: end for 18: for each route \sigma_{k} do 19: Stitch A*-feasible path \pi_{k} through ordered tasks 20: Set altitude z(x,y)=h(x,y)+H_{\text{safety}} 21: end for 22: return \Pi=\{\pi_{k}\}_{k=1}^{K} To solve the optimization problem defined in ( 1 ), an Iterative-Exchange Framework is developed to directly minimize the composite cost over K open routes. The framework operates entirely in the task-assignment space with implicit path feasibility ensured by an A*-based geodesic oracle. It integrates three key components: (i) a balanced initialization to generate feasible routes, (ii) a rich set of neighborhood exchange operators for iterative improvement, and (iii) an efficient incremental evaluation scheme leveraging the precomputed distance oracle D(\cdot,\cdot) . The method progressively refines the multi-UAV plan \Pi=\{\pi_{1},\dots,\pi_{K}\} by applying improving moves that jointly reduce the total distance term \sum_{k}L(\pi_{k}) and the makespan term \max_{k}L(\pi_{k}) in ( 1 ). All updates strictly maintain feasibility (unique task coverage and collision-free segments). Algorithm 1 outlines the overall procedure. The algorithm starts from a two-stage initialization: first, tasks are roughly allocated to UAVs based on a load-balancing heuristic; second, each route is internally ordered using nearest-neighbor construction followed by local 2-opt refinement. Subsequently, multiple types of exchange moves—such as relocate, swap, and cross-exchange—are explored to iteratively improve the objective until convergence or iteration budget exhaustion. Stage A (LPT-style balanced assignment). We estimate the marginal cost of inserting each task t_{j} into route k from start s_{k} by its nearest-neighbor distance proxy: \widehat{c}_{k}(t_{j})\;=\;\min\!\big(D(s_{k},t_{j}),\min_{t\in\sigma_{k}}D(t,t_{j})\big). Tasks

Read the complete text