Frontiers in Computing and Intelligent Systems ISSN: 2832-6024 | Vol. 14, No. 2, 2025 55 Research on Task Assignment and Path Planning Algorithm for Multi‐UAV Collaboration Yisheng Zeng * School of Engineering Technology, Nanchang Vocational University, Nanchang, Jiangxi, 330500, China * Corresponding author Email: Zengyishengbdp@163.com Abstract: This paper investigates the co-optimization problem of task allocation and path planning in multi-UAV collaborative systems. Addressing the challenges of strong coupling, high dimensionality, and real-time requirements in dynamic complex environments, a distributed co-optimization framework integrating hierarchical planning concepts with spatiotemporal constraints is proposed. By constructing a multi-objective mixed-integer programming model, designing a lightweight event- triggered task allocation algorithm (improved CBBA), and integrating a hierarchical path planning strategy (global meta- heuristic search + local model predictive control), the framework enhances task execution efficiency and system robustness while reducing communication overhead. Simulation and experimental results demonstrate its superior performance in typical scenarios such as disaster relief and precision agriculture. This research provides an efficient, reliable, and scalable solution for practical applications involving large-scale heterogeneous UAV swarms, holding significant theoretical implications and engineering value. Keywords: Cooperative Optimization; Consensus Auction Algorithm; Model Predictive Control; Distributed Optimization; Digital Twin. 1. Introduction With continuous breakthroughs in unmanned aerial vehicle (UAV) technology across control, navigation, and communication domains, multi-UAV cooperative systems have emerged as a research hotspot due to their superior efficiency, enhanced robustness, and expanded coverage capabilities during mission execution [1]. These systems demonstrate immense application potential in complex scenarios such as disaster relief, precision agriculture, smart city logistics, and military reconnaissance. However, as application scenarios grow increasingly complex and swarm sizes continue to expand, the collaborative control of multi-UAV systems faces unprecedented challenges. Among these, task allocation and path planning — core issues determining the system's overall performance—have become bottlenecks hindering the practical application of large-scale UAV swarms due to their inherent strong coupling, high dimensionality, and dynamic uncertainty. Task allocation aims to rationally assign task sequences to heterogeneous UAV clusters to optimize overall objectives (e.g., minimum completion time, maximum benefit), while path planning must generate collision-free, low-energy feasible trajectories while satisfying UAV dynamic constraints. In dynamically uncertain environments, these are not isolated problems: optimal task allocation relies on precise path costs, and feasible path planning requires specific task sequences as prerequisites. Traditional solutions often decouple these tasks or employ centralized optimization methods. While effective for small-scale problems, these approaches generally suffer from high computational complexity, substantial communication bandwidth requirements, and poor environmental adaptability. They struggle to meet the stringent demands for real-time performance, scalability, and robustness required by large- scale swarms. Extensive research has been conducted globally on this issue. Swarm intelligence algorithms (e.g., enhanced genetic algorithms, particle swarm optimization) have been applied to complex multi-objective optimization problems, yet face challenges of insufficient universality in dynamic environments. Market auction mechanisms offer distributed solutions [2], yet their inherent periodic communication protocols generate substantial redundant overhead during scalability. For path planning, Dubin curve-based approaches or model predictive control effectively handle dynamic constraints, but spatiotemporal collision avoidance in multi-agent coordination remains poorly addressed. Methods like mixed-integer programming enable precise modeling but suffer from high computational complexity [3]. In recent years, novel approaches such as distributed reinforcement learning have been introduced to enhance online learning and decision-making capabilities. However, deeply integrating these with traditional optimization methods within a lightweight, efficient collaborative framework remains a significant research challenge [4]. Given these limitations, this paper addresses the gap s in existing research by delving into the collaborative optimization of task allocation and path planning for multi- UAV cooperation. We propose a distributed collaborative optimization framework that integrates hierarchical planning concepts with spatio-temporal constraints. The core innovations of this framework are: First, constructing a multi- objective mixed-integer programming (MOMIP) model to comprehensively quantify spatio-temporal constraints, heterogeneous capabilities, and task coupling relationships, thereby providing theoretical guidance for algorithm design; Second, it designs a lightweight event-triggered task assignment algorithm (enhanced CBBA) that significantly reduces bandwidth consumption through innovative communication mechanisms. Third, it employs a hierarchical path planning strategy (global meta-heuristic search + local model predictive control adjustment) to ensure efficient and safe trajectory generation in complex dynamic environments. 56 Finally, by constructing a simulation verification platform supporting digital twins and conducting physical experiments, the proposed framework demonstrates outstanding performance in enhancing task efficiency, reducing communication overhead, and strengthening system robustness across typical scenarios such as disaster relief and precision agriculture. This research not only pursues theoretical innovation but also aims to provide an efficient, reliable, and scalable technical solution for the practical application of large-scale heterogeneous UAV swarms, holding significant theoretical implications and broad engineering application prospects. 2. Concept of Multi-UAV Collaboration Multi-UAV collaboration refers to a technical system where multiple unmanned aerial vehicles form an organic whole to jointly accomplish tasks through communication networking, information sharing, and collaborative decision-making [5]. Its core value lies in achieving "1+1>2" benefits through swarm intelligence [6], significantly enhancing task execution efficiency while enabling complex missions beyond the capability of individual drones. This collaborative model not only improves system reliability and robustness but also reduces overall mission risk by leveraging multiple low-cost drones [7]. Technologically, multi-UAV collaboration systems comprise four key layers: communication networks, collaborative perception, task decision-making, and motion planning [8]. Communication networks form the foundation for information exchange between UAVs. Collaborative perception builds global environmental awareness through data fusion. Task decision-making addresses "what to do," typically employing intelligent optimization algorithms for task allocation. Motion planning generates safe, feasible flight trajectories while ensuring collision avoidance among multiple aircraft. Currently, three primary control architectures are employed: centralized, distributed, and hybrid, as summarized in Table 1. Centralized control offers simplicity but lacks reliability, while distributed control provides robustness but faces optimization limitations. Hybrid control combines the advantages of both and is the most widely adopted in practice. These architectures support diverse collaborative modes, including typical application scenarios such as area-cooperative search, cooperative transport, networked monitoring, and swarm performances. The field still faces numerous technical challenges, including communication bandwidth limitations, real-time response in dynamic environments, scalability for large-scale clusters, and system security assurance. With advancements in artificial intelligence, new methods such as reinforcement learning and deep learning are driving breakthroughs in multi- UAV collaboration, propelling it toward greater intelligence and autonomy. Multi-UAV collaboration technology is transitioning from laboratory research to practical applications. It holds vast potential in future urban management, disaster relief, agricultural crop protection, and other fields, representing a crucial direction for UAV technology development and a foundational pillar for realizing intelligent unmanned systems Table 1. Comparison of Multi-UAV Control Frameworks (Reference [9]) Control Architecture Communication Mode Advantages Disadvantages Applicable Scenarios Centralized Star Topology Theoretically optimal solution, simple algorithm Single point of failure, poor scalability, high communication load Small-scale static environments Distributed Mesh topology High robustness, good scalability Limited optimization capabilities, convergence difficult to guarantee Large-scale dynamic environment Hybrid Hierarchical hybrid communication Balances performance and robustness Complex design requiring coordination of inter-layer interactions Medium-scale complex scenarios Control Architecture Communication Mode Advantages Disadvantages Applicable Scenarios Centralized Star Topology Theoretically optimal solution, simple algorithm Single point of failure, poor scalability, high communication load Small-scale static environments 3. Task Allocation Algorithm Selection for Multi-UAV Collaboration Selecting a task allocation algorithm is a core decision in multi- UAV collaborative operations, directly determining system efficiency and performance. Algorithm selection is not arbitrary but requires comprehensive consideration of mission scenarios, UAV capabilities, communication conditions, and optimality requirements. No single algorithm excels in all situations, making it crucial to understand the characteristics and applicable scenarios of various algorithms. For small-scale, computationally well-resourced static environments requiring globally optimal solutions, centralized optimization algorithms are ideal. Typically based on integer linear programming (ILP) or mixed-integer linear programming (MILP), these methods rely on a central computing unit to aggregate all information and compute the theoretically optimal task allocation for the entire fleet. While delivering optimal solutions, their computational complexity grows exponentially with the number of UAVs and tasks. Additionally, the high risk of single-point failure at the central node makes them unsuitable for large-scale or dynamic environments. Distributed algorithms demonstrate significant 57 advantages when system scale is large, rapid response is required, or communication is constrained. Among these, market-based consensus auction algorithms represent a paradigm of distributed solutions [10]. Each drone acts as an autonomous agent, "bidding" based on the local cost of executing a task (e.g., additional flight distance required). Through proximity communication and negotiation with neighbors, the system ultimately achieves a globally efficient allocation outcome. This approach is highly robust; the failure of a single node does not cause system collapse, making it well-suited for ad-hoc networks and dynamic task insertion. In practical applications, problems are often highly complex, involving numerous constraints and making exact optimal solutions difficult to obtain. This is where meta- heuristic algorithms like genetic algorithms and particle swarm optimization become powerful tools. By simulating natural processes such as evolution or collective behavior, they find high-quality approximate solutions to complex problems within acceptable timeframes. These algorithms are particularly well- suited for multi-objective optimization problems, such as scenarios requiring simultaneous balancing of mission completion time, total energy consumption, and load distribution. Ultimately, algorithm selection is an art of trade-offs. Engineers must make decisions based on task urgency, fleet size, communication network reliability, and computational platform performance. In practice, hierarchical hybrid architectures are gaining popularity: centralized macro-task allocation at higher levels, combined with distributed rules allowing drones to make local adjustments at lower levels. This flexible approach ensures global coordination while leveraging the robustness and responsiveness of distributed systems. 4. Path Planning Algorithm Selection for Multi-UAV Collaboration 4.1. Electing Core Algorithms Based on Mission Scenarios and Constraints Selecting path planning algorithms for multi-UAV collaboration involves a complex decision-making process. Its core objective is to generate collision-free flight trajectories for the entire fleet while satisfying safety, efficiency, and dynamic feasibility requirements. The fundamental difference from single-UAV path planning lies in addressing the core challenge of inter-UAV collision avoidance, demanding algorithms capable of handling high-dimensional, coupled constraints. The choice of algorithm is highly dependent on the mission scenario, communication conditions, real-time requirements, and computational resource constraints. For known static global environments, search-based algorithms (e.g., A*, D* Lite) and their multi-agent extensions (e.g., MAPP) provide a solid foundation [11]. These algorithms typically operate on discrete grid maps and can find a complete and optimal (or suboptimal) path for all UAVs. However, their computational complexity increases sharply with the number of UAVs, potentially failing to meet real-time planning demands for large fleets. Moreover, they often do not adequately account for the continuous dynamic models of UAVs. Sampling-based algorithms (e.g., RRT, PRM) and their asymptotically optimal variants (e.g., RRT) excel at handling high-dimensional continuous state spaces, making them well- suited for planning complex feasible trajectories for individual UAVs. However, directly applying these methods in multi-agent collaboration incurs prohibitively high computational costs. Improved approaches—such as parallelized sampling, embedding collision avoidance constraints during sampling, or using them as high-level global planners to provide initial path points for subsequent local planning— are more commonly adopted. Currently, the most effective approach for handling dynamic environments and real-time collision avoidance is optimization-based methods, particularly model predictive control (MPC). MPC employs rolling-horizon optimization strategies where, within each control cycle, each drone optimizes its trajectory for a short future time window based on its current state and predictive models, incorporating collision avoidance constraints with other drones as optimization conditions [12]. This approach naturally handles dynamic constraints and real-time disturbances, making it highly suitable for distributed implementations. It allows each drone to autonomously optimize its trajectory while sharing intentions via communication to achieve coordinated avoidance. For tasks like assembly and formation flight in open airspace for ultra-large-scale swarms (e.g., hundreds of drones), rule- based biomimetic algorithms (such as the Boid model) offer a lightweight and efficient solution. These methods design simple local interaction rules (e.g., separation, alignment, aggregation) to enable the emergence of complex global coordinated behavior within the swarm. They require no central computation, have low communication demands, and exhibit strong robustness. While not guaranteeing optimality, they achieve remarkable scalability and dynamic adaptability. 4.2. Hierarchical Fusion: A Robust Architecture Balancing Global and Local Considerations Ultimately, algorithm selection lacks a single solution and often requires a layered fusion strategy. A common architecture employs a top-level global planner (e.g., A* or RRT*) to generate coarse collision-free reference paths for each drone, while a bottom-level local planner (e.g., MPC) handles real-time tracking, dynamic obstacle avoidance, and fine- grained inter-vehicle adjustments. This combination balances global efficiency with local reactivity, representing the most robust and widely adopted solution in engineering practice [13]. 5. Integrated Approaches for Multi- UAV Task Allocation and Path Planning 5.1. Three Classic Integration Approaches: Sequential, Iterative, and Joint Integrated approaches for multi-UAV task assignment and path planning are central to resolving their strong coupling, hinging on accurately estimating and feeding back task execution costs (primarily determined by path length/time). Based on integration depth, three classic methods emerge [14]. Sequential integration is the most intuitive and widely adopted method. It employs a serial workflow of either "allocate first, then plan" or "plan first, then allocate." The former approach assigns tasks first (typically based on simplified cost assumptions, such as straight-line distance) before performing detailed path planning for the assigned task sequence. The latter calculates precise path costs for all possible "UAV-task" pairs to form a cost matrix, then allocates tasks based on this matrix. 58 Sequential methods are simple to implement but suffer from potential suboptimal solutions due to inaccurate cost estimates. They may even require reallocation if path conflicts are discovered during planning. As shown in Figure 1. Figure 1. Flowchart of the Improved CBBA Algorithm Iterative integration improves upon sequential methods by introducing feedback loops. Its typical workflow proceeds as follows: First, tasks are assigned based on initial cost estimates. Detailed path planning then calculates precise costs. If significant discrepancies between precise costs and initial estimates are detected, or if unsolvable conflicts arise during planning, the new cost information is fed back to the assignment module for re-allocation. This process iterates cyclically until the solution converges or meets specified criteria. While iterative methods enhance overall performance, they increase computational time and complexity. Joint integration represents the most comprehensive yet complex approach. It unifies task assignment (discrete decision variables) and path planning (continuous variables) within a unified mathematical framework for simultaneous optimization, typically modeled as a mixed-integer linear programming or mixed-integer nonlinear programming problem. This approach theoretically achieves global optimality by directly incorporating full path constraints and collision avoidance requirements during allocation. However, due to its extremely high computational complexity, it remains applicable only to scenarios with small-scale UAVs and limited tasks, making large-scale implementation in practical engineering challenging. 5.2. Two Practical Engineering Paradigms: Market Mechanisms and Hierarchical Architectures Beyond the aforementioned approaches, market-based distributed coordination has gained significant practical traction, exemplified by consensus-based auction algorithms. In this method, task assignment and path cost calculation are tightly intertwined: each drone must invoke its local path planner in real-time to compute the precise incremental cost of executing a task while "bidding" for it. Through multiple rounds of distributed negotiation, the swarm ultimately achieves an overall optimal allocation scheme based on precise path costs. This approach inherently combines distributed and iterative elements, offering advantages of high robustness and strong scalability. Finally, in practical system design, hierarchical integration represents a common engineering compromise. 59 The system is divided into a decision layer and an execution layer: the decision layer performs coarse-grained task allocation and generates a global reference path for each drone based on approximate costs; the execution layer handles local real-time planning, finely managing dynamic constraints and sudden collision avoidance, and requests reallocation or adjustment from the decision layer when execution deviations become excessive. This architecture balances global optimality and real-time computational efficiency, serving as an effective strategy for tackling complex real-world environments. Table 2. Comparison of Task Allocation and Path Planning Integration Methods (Reference: Kulkarni & Srivastava, 2022) [15] Integrated Approach Degree of Coupling Computational Complexity Communication Requirement Optimality Applicable Scale Sequential Low Low Low Low to Medium Small to Medium Scale Iterative Medium Medium Medium Medium to High Medium-scale Combined High High High High Small-scale Distributed Market Mechanism Medium to High Medium Medium Medium to high Medium to large scale Stratified Medium Medium~Low Low~Medium Medium Large-scale Integration Methods Coupling Level Computational Complexity Communication Requirements Optimality Applicable Scale 6. Conclusion Task allocation and path planning in multi-UAV collaborative systems are key technologies for achieving swarm intelligence, and their coordinated optimization is crucial for enhancing overall system performance. This paper systematically explores task allocation algorithms, path planning methods, and the selection and design of integrated strategies around this core issue, aiming to provide theoretical support and solutions for practical applications of large-scale heterogeneous UAV swarms. Research indicates a strong coupling between task allocation and path planning, making isolated optimization incapable of achieving global optimality. Task allocation algorithms must be flexibly selected based on application scale, dynamics, and communication conditions: centralized optimization suits small-scale static environments; distributed algorithms (e.g., consensus auctions) excel in scalability and robustness; while meta-heuristic algorithms excel at handling complex multi-objective constrained problems. For path planning, environmental characteristics, real-time requirements, and computational resources must be comprehensively considered: search-based algorithms suit static global planning; sampling-based methods excel in high- dimensional spaces; Model Predictive Control (MPC) effectively handles dynamic environments and real-time collision avoidance; while bio-inspired algorithms provide lightweight solutions for ultra-large-scale fleets. Regarding ensemble methods, sequential, iterative, and joint approaches each possess distinct advantages and limitations. Sequential methods offer simplicity but may yield suboptimal results, iterative methods enhance performance through feedback loops yet increase computational burden, while joint methods achieve theoretical optimality at the cost of computational complexity. Market-based distributed ensemble and hierarchical ensemble methods represent effective engineering compromises, balancing robustness, scalability, and real-time performance, particularly suited for complex dynamic environments. The proposed collaborative optimization framework, integrating hierarchical planning with spatiotemporal constraints, achieves significant improvements in task completion efficiency, communication overhead, and system robustness by enhancing the combination of the Consensus Bidding Auction (CBBA) algorithm and Model Predictive Control (MPC). Future research will further explore the deep integration of artificial intelligence (such as reinforcement learning and deep learning) with traditional optimization methods to enhance the system's online learning and adaptive capabilities in unknown dynamic environments. Concurrently, it will promote the widespread application of digital twin technology in simulation verification and physical deployment, ultimately enabling efficient and reliable autonomous collaboration of multi-UAV clusters across broader scenarios. References [1] Khamis, A., Hussein, A., & Elmogy, A. (2015). Multi-robot task allocation: A review of the state-of-the-art. Robotics and Autonomous Systems, 66, 3-13. [2] Choi, H. L., Brunet, L., & How, J. P. (2009). Consensus- based decentralized auctions for robust task allocation. IEEE Transactions on Robotics, 25(4), 912-926. [3] Schouwenaars, T., De Moor, B., Feron, E., & How, J. P. (2001). Mixed integer programming for multi-vehicle path planning. In Proceedings ofthe 2001 American Control ConferencesEE. [4] Kantaros, Y., & Zavlanos, M. M. (2020). Distributed communication-aware planning for mobile sensor networks. IEEE Transactions on Robotics, 36(2), 351-368. [5] Hauert, S., et al. (2011). Reynolds flocking in reality with fixed-wing robots: communication range vs. maximum turning rate. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). [6] Vásárhelyi, J., et al. (2018). Outdoor flocking and formation flight with autonomous aerial robots. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). [7] Cao, Y., Yu, W., Ren, W., & Chen, G. (2013). An overview of recent progress in the study of distributed multi- agent coordination. IEEE Transactions on Industrial Informatics, 9(1), 427-438. [8] Ollero, A., et al. (2021). The AEROARMS project: Aerial robots with advanced manipulation capabilities for inspection and maintenance. IEEE Robotics & Automation Magazine. 60 [9] Çetin, M., & Ergüner, Ö . (2019). Coordination of unmanned aerial vehicles. In Path Planning for Autonomous Vehicles - Ensuring Reliable Driverless Navigation and Control Maneuver (pp. 1-20). IntechOpen. [10] Duan, H., & Qiao, P. (2014). Pigeon-inspired optimization: a new swarm intelligence optimizer for air robot path planning. International Journal of Intelligent Computing and Cybernetics. [11] Švestka, P., & Overmars, M. H. (1998). Coordinated path planning for multiple robots. Robotics andAutonomous Systems, 23(3), 125-152. [12] Richter, C., Bry, A., & Roy, N. (2016). Polynomial trajectory planning for aggressive quadrotor flight in dense indoor environments. The International Journal ofRobotics Research, 35(7), 787-798. [13] Kushleyev, A., Mellinger, D., Powers, C., & Kumar, V. (2013). Towards a swarm of agile micro quadrotors. Autonomous Robots, 35(4), 287-300. [14] Dias, M. B., Zlot, R., Kalra, N., & Stentz, A. (2006). Market- based multirobot coordination: A survey and analysis. Proceedings ofthe IEEE, 94(7), 1257-1270. [15] Kulkarni, A., & Srivastava, S. (2022). A review of distributed and integrated multi-robot task and motion planning. Autonomous Intelligent Systems, 2(1), 1-16.