1 Introduction

The growing adoption of Unmanned Aerial Vehicles (UAVs) in a wide array of industries has been driven by significant technological advancements and the emergence of drone-friendly policies [1,2,3]. These developments have enabled innovative and creative applications of drones across various sectors, from surveillance and search and rescue missions [4, 5] to aerial inspection, landmine detection, defense, and beyond [6,7,8,9,10]. Among these UAVs, multirotor drones, due to their affordability and versatility, have become a cornerstone of technological progress, particularly in swarm robotics, which leverages coordination, cooperation and local interaction between drones to achieve complex tasks that surpass the capabilities of individual units [11,12,13,14]. Forming a swarm of aerial robots enables agents to establish communication and coordination channels, allowing them to leverage the resources and capabilities of their fellow agents, thereby improving individual and overall swarm performance [15].

As the use of multirotor UAV swarms continues to expand, robust, flexible, and scalable coordination algorithms have become essential to tackle key challenges such as task allocation and trajectory planning [16]. One of the primary difficulties is assigning tasks to individual drones in a way that maximizes efficiency by providing optimal assignment, while ensuring collision-free paths for the entire swarm [17]. As the number of drones increases, the complexity of both task assignment and trajectory generation grows exponentially, necessitating advanced algorithms to handle the dynamic environment in which these UAVs operate [18].

In certain applications of multi-drone based systems, such as drone light shows, UAVs are interchangeable, meaning that any drone can perform any task due to identical configurations and capabilities [19]. This interchangeability adds a layer of flexibility to task assignment, as the specific assignment of tasks to drones becomes less critical. However, this also introduces the challenge of optimizing both task assignment and trajectory planning concurrently, while ensuring the mission is completed efficiently and without collisions [20].

Numerous approaches to task assignment and path planning for UAV swarms have been explored in the literature [21]. For example, centralized algorithms such as the Hungarian Algorithm (HA) and Branch and Bound (B&B) are frequently employed for their ability to find optimal solutions in task assignment [22, 23]. However, they often suffer from high computational costs, especially when applied to large-scale problems. In decentralized systems, algorithms like C-CAPT and D-CAPT have been introduced, offering collision-free trajectory planning for swarms of unlabeled robots, though they tend to produce suboptimal results compared to centralized approaches [24]. Metaheuristic methods such as Genetic Algorithms (GA), Particle Swarm Optimization (PSO), and Ant Colony Optimization (ACO) are also widely used to solve combinatorial optimization problems, including the task assignment problems in UAV swarms. While, these methods are effective in generating near-optimal solutions, they can be computationally intensive for larger swarms [25,26,27].

Path planning combined with task assignment remains a complex NP-complete problem, particularly in large-scale multi-UAV systems [28]. Researchers have proposed various methods to address this challenge, including geometry-vector algorithms for flight path planning in convex areas [29] and optimal assignment algorithms to manage multiple targets in multi-UAV scenarios [30]. These approaches, while promising, often require cooperation between UAVs to optimize overall performance. On the other hand, trajectory generation has also been widely studied, with several strategies aiming to minimize the Euclidean distance traveled, as seen in the works of [31] and [32, 33]. However, some of these methods lack robust collision avoidance [34]. Hybrid approaches, such as [35], offer more comprehensive solutions by combining global and local planning techniques. Suboptimal strategies focus on optimizing task allocation, while ensuring UAV safety, though they still face challenges in real-time, large-scale applications [36].

Despite the significant progress in task allocation and trajectory planning for UAV swarms, many existing studies address these aspects in isolation, focusing either on assignment or trajectory generation [37, 38]. Moreover, few studies consider the dynamics of drones or generate time-parameterized trajectories for UAVs in real-time environments. This limitation creates a gap in the literature, as both aspects-assignment and trajectory generation-are crucial for practical and effective swarm operations.

In light of these limitations, our research aims to fill this gap by presenting an approach that simultaneously addresses the task assignment and trajectory planning challenges in UAV swarms. Our Simultaneous Allocation and Path Planning (SAPP) framework integrates these two key aspects, providing an optimal solution for assigning tasks and generating time-parameterized trajectories for multirotor drones, while considering their dynamic constraints. Unlike previous methods, our approach offers a more comprehensive solution that addresses both assignment efficiency and collision-free path generation. Through extensive simulations, we demonstrate the effectiveness of our method in improving swarm coordination and performance. The key contributions of this work can be summarized as follows:

  • Simultaneous Task Assignment and Path Planning (SAPP) We propose a comprehensive optimization framework that solves both the task assignment and path planning problems concurrently. Unlike conventional methods that treat these as separate stages, our approach ensures a more efficient coordination of aerial robots, leading to optimized task assignments and dynamically feasible, collision-free trajectories.

  • Dynamic Feasibility and Collision Avoidance The proposed algorithm not only guarantees collision-free trajectories through a robust real-time collision avoidance mechanism but also ensures that the paths generated respect the physical and dynamic constraints of each robot. This enhances the safety and operational efficiency of the robot swarm, especially in unstructured environments.

  • MultiStage Evaluation with Complex Scenarios Extensive simulations across multiple scenarios demonstrate the robustness and adaptability of the proposed approach. The introduction of dynamic, random environments in the simulations provides insights into the performance of the algorithm in real-world applications, particularly for scenarios with unstructured and evolving patterns.

  • Scalability for Large Swarms The proposed SAPP framework is designed to scale efficiently, allowing for the coordination of large numbers of drones without compromising the quality of the task assignments or trajectory planning. This is particularly beneficial for large-scale operations, where multiple drones must coordinate simultaneously.

The remainder of this paper is structured as follows: Section 2 provides an overview of the related literature on swarm control algorithms and task allocation methods. Section 3 describes the proposed SAPP approach in detail. In Section 4, we present the simulation results conducted in MATLAB to evaluate the performance of the approach, along with the discussion of these results. Finally, Section 5 concludes the paper, summarizing our contributions to addressing the SAPP problem for UAV swarms.

2 Combinatorial Optimization and Multiple Robots

Recently, advances in science and engineering have led to the integration of several disciplines in interdisciplinary research, resulting in many scientific and technological breakthroughs in various fields. One of the most visible areas of multidisciplinary research is in robotic systems. A key challenge in multiple robots is determining how to make decisions over the robots’ actions to optimally achieve the overall system objective.

Optimization problems can be considered a generalization of decision-making problems, including objective functions to evaluate solutions and find those corresponding to optimal values [39]. Optimizing an objective function over a combination of finite discrete objects, where exhaustive search is not tractable, falls into the category of problems known as combinatorial optimization problems. These problems have substantial applications in various fields, including tasks allocation, vehicle routing, and transportation problems. One of the most universally applicable approaches to address such problems is the branch-and-bound algorithm [40, 41]. In the next subsections, a brief overview of some typical combinatorial optimization problems and their applications in multirobot systems will be highlighted.

2.1 Tasks Assignment and Interchangeability

The assignment problem is considered one of the well-known problems in combinatorial optimization, with numerous applications in tasks allocation, scheduling, and vehicle routing problems. Moreover, it emerges as a subproblem in several NP-hard problems. In its most general form, this problem can be stated as follows: given N agents and M tasks with a completion cost associated with each task for each agent so that any task can be accomplished using any agent. It is required to assign each task to at most one agent and each agent to at most one task in a way that minimizes the total assignment cost. The assignment problem is said to be balanced if the number of agents is equal to the number of tasks (N=M); otherwise, it’s called an unbalanced allocation problem [42, 43].

The Linear Allocation Problem (LAP) is a subset of the task assignment problem that concern with the problems when the assignment total cost of the whole tasks is similar to the summation of the individual cost of each agent. Several approaches have been proposed to solve the LAP each of which has its time complexity. Notable examples include the Auction Algorithm (AA) and the HA [44, 45]. Both AA and HA provide optimal solutions for assignment problems with similar solution quality. However, a study [46] points out a significant difference in their computational time. Specifically, the computational time for AA increases considerably as the number of agents in the assignment task grows. On the other hand, HA demonstrates clear superiority in scalability, efficiently solving LAP in polynomial time with a complexity of \(O(\max (N,M)^3)\). This advantage makes HA the preferred choice for assignments involving a large number of agents, as it can handle larger problem instances with efficiency.

In multi-robot systems, when the achievement of every task is independent of the robot, i.e., the objectives of every task can be completely accomplished by using any robot of the team, then it is a completely interchangeable team. It is often the case when all robots are identical and have the same set of sensors necessary for task completion. For instance, using a team of aerial robots in supporting precision farming for multiple rows of fields in crop health monitoring, soil health scanning, yield data estimating, and providing valuable data for analysis and decision-making. In such cases, it is indifferent to which aerial robot is in which row.

Unlike prespecified tasks assignment that requires certain robots to reach specific goals, interchangeability provides an additional degree of freedom to be considered in the designed algorithm. It is required to not only find the shortest, collision-free paths between the robot and the intended goals but also select the assignment that guarantees achieving the mission objectives with an optimal total cost.

2.2 Vehicle Routing and Traveling Salesman Problems

Another planning problem concerning tasks assignment for multi-agent systems is to assign multiple tasks for every robot in the team. This class of problems has several applications among many disciplines including operations research, logistics coordination, and the multi-robot community. It is considered one of the most intensively studied problems in combinatorial optimization. One of the basic and well-known problems of this class is the Traveling Salesman Problem (TSP) that is included in several operations problems [47]. The aim of TSP is to find the minimum cost route that the salesman can follow to visit exactly once each of the prescribed (m) cities and return to its original location.

An extension of TSP deals with multiple agents, for instance, finding the optimal total-cost plan that allocates a team of aerial robots to visit a large set of distributed goals at most once. Moreover, it must be done without any prior determination or preference for which robot visits which goal or in what order, and then return to their initial departure points. After releasing the collision avoidance constraints, this problem became quite similar to the Multiple Traveling Salesman Problem (MTSP) [48]. In the case that multiple goals are assigned to a single robot, not only planning routes to visit the goals is required, but also the order in which to visit goals needs to be considered to arrive at the best possible total cost.

The multi-robot and operations research community includes several studies and contributions with the aim of achieving exact or approximate solutions that optimally plan routes for multiple robots. For instance, the proposed algorithms to solve the Vehicle Routing Problem (VRP), which aims to generate routes for a team of robots leaving one or more warehouses to reach a number of goals and return back to their initial locations [49]. There is a huge variety of VRP according to the problem formulations, objective functions, and incorporated assumptions that lead to different solutions [50, 51].

The objective function selection criteria vary according to the mission requirements. For instance, in most cases, the objective function of VRP is to find the best solution that minimizes the total traveling distance of all robots. In such criteria, the mission completion time is not taken into account; the concern is only to minimize the total distance traveled by all robots as shown in Fig. 1a. In this case, the minimum cost is achieved by only one robot, \(R_1\), such that it moves 11 units. However, in many cases, where the mission completion time is an essential issue, minimizing the maximum cost “distance” is preferred against minimizing the total distance traveled by all robots, so as to minimize the mission completion time as shown in Fig. 1b. In this situation, the minimum-maximum cost is achieved by the two robots such that both move six units, 12 units in total. Adopting the min-cost criteria will take approximately twice as long as the min-max solution.

When dealing with multiple robots, it is not sufficient to plan assignment strategies for the robots; an additional essential issue that needs to be considered is the collision avoidance constraints, to arrive at optimal collision-free routes.

Fig. 1
figure 1

The common two objective functions of VRP; the min-cost and min-max cost solutions are shown in Fig. (a) and Fig. (b), respectively

Full size image

3 The Proposed SAPP Framework

The task allocation problem, which aims to assign a team of flying robots to predefined goal destinations, is a complex combinatorial challenge in the domain of multi-robot systems. Complicating this challenge further is the requirement to generate corresponding collision-free, time-parameterized trajectories for each individual robot. The objective of this article is to address these challenges simultaneously by proposing a solution to the SAPP problem for a swarm of flying robots.

In the SAPP framework, task allocation depends on the balance between the number of robots (N) and the number of goals (M). When \( N > M \), the algorithm selects the subset of robots that minimize the mission cost, leaving some robots unassigned. Conversely, if \( M > N \), some goals remain unassigned, a situation that is considered part of the broader Multi-Robot Guidance Problem (MRGP), which will be addressed in future work.

Achieving optimal task allocation is critical as it directly impacts planning performance and overall system efficiency. Task assignments can be classified into two types: labeled tasks and unlabeled tasks. In the labeled tasks every robot is assigned to visit one prespecified target, for example, assembly tasks, where agents deliver pieces or parts to the right assembly location, (piece a to site A and piece b to site B... etc.). In contrast, unlabeled tasks, the goals are satisfied to be assigned by any robot for mission completion such as the previous example if every robot has the same part and all goals need that part. Another example of unlabeled tasks is when a group of identical aerial robots is assigned to monitor and cover agricultural fields that comprise numerous rows of trees and crops because no matter which robot is at which row. Robots in the unlabeled tasks are provided with an additional degree of freedom since any robot can visit any goal. However, the notions of priority and preference might be necessary, for example in the motion planning and optimization problems; even if any robot can visit any goal, but a certain assignment will result in better efficiency in terms of task completion cost and time. Thus, even in unlabeled tasks, factors like priority and preference play a role in optimizing the overall performance of SAPP.

In this context, the well-known LAP is employed to solve the SAPP problem. The LAP framework efficiently allocates N robots to N tasks, minimizing the overall cost, while ensuring that each task is performed by a single robot. Moreover, for SAPP problems, where no obstacles are considered during path planning, the generated trajectories must be collision-free and dynamically feasible. This requires addressing Robot-to-Robot (R2R) collision avoidance, which is an essential component of ensuring the safe execution of planned paths for the swarm of robots. Therefore, time-parameterized trajectories must not only meet performance objectives but also ensure that robots avoid colliding with each other during mission execution.

3.1 Multicopters As Test Platform

In this study, multicopters, specifically Quadrotors, have been chosen as the test platform. Their agile, precise, and stable four-rotor design makes them ideal for evaluating the SAPP techniques proposed for aerial robot swarms. Quadrotors are capable of precise control over multidirectional movements, facilitating intricate aerial maneuvers essential for the tasks of task assignment and path planning. Quadrotors offer versatility, accommodating a wide range of flight patterns, thereby providing creative adaptability to different task scenarios. Additionally, their safety features make them suitable for both indoor and outdoor experiments, ensuring the feasibility of deploying the proposed techniques in various environments. Their established track record in high-profile events underscores their suitability as a platform for testing and validating aerial swarm algorithms. For a detailed analysis of quadrotor dynamics and their suitability for aerial swarm applications, refer to the comprehensive insights provided in [52].

3.2 Problem Definition and Theoretical Analysis

The primary challenge in the SAPP problem involves efficiently assigning multiple drones to their respective goals while ensuring safe navigation in a three-dimensional (3D) environment. This requires addressing both the assignment problem, where each goal is allocated to exactly one drone, and the trajectory planning problem, where collision-free paths must be generated for each drone to its assigned goal. The concept of interchangeability plays a crucial role, indicating that any drone can be assigned to any goal, thus simplifying the task assignment phase without preference for specific pairings.

Figure 2 illustrates the typical SAPP setup, where drones are tasked with reaching specific goals. The objective is twofold: assign each goal optimally to a drone and generate collision-free trajectories, while maximizing operational efficiency. Theoretical considerations such as collision avoidance, dynamic feasibility, and optimization of resource utilization are crucial for achieving reliable and effective mission execution.

Fig. 2
figure 2

Schematic of the SAPP problem: drones must optimally navigate to predefined goals, while avoiding collisions in a 3D environment

Full size image

3.2.1 Mathematical Formulation of the SAPP Problem

The SAPP problem can be formally described by defining the trajectory of each drone as a time-dependent path \(\zeta (t)\), which is optimized over a cost functional that takes into account both spatial and temporal factors. The goal is to find the optimal trajectories \(\zeta ^*(t)\) that minimize the total cost over the entire mission duration, from \(t = t_0\) to \(t = t_f\). Mathematically, this is expressed as:

$$\begin{aligned} \zeta ^*(t) = \underset{\zeta (t)}{\text {arg min}} \int _{t=t_0}^{t=t_f} L(\zeta (t), t) \,\textrm{dt}, \end{aligned}$$
(1)

, where \(L(\zeta (t), t)\) is the cost function associated with each trajectory \(\zeta (t)\), which typically reflects the energy expenditure or the distance traveled by the drones. The optimization is subject to the following constraints:

  • Initial and Terminal Conditions The drones must start and end their trajectories at predefined locations corresponding to their assigned tasks, ensuring proper task execution [18].

  • Interchangeability All drones are treated as interchangeable, meaning the assignment does not favor any particular drone-goal pairing.

  • Valid Assignment Ensuring that each goal is assigned to exactly one drone constitutes a valid assignment. This constraint guarantees the proper allocation of tasks among the drone team [53].

  • Collision Avoidance The drones must avoid collisions both with each other and any potential obstacles in the environment, although an unobstructed environment is assumed in this study.

  • Drone Constraints The generated trajectories must respect the physical constraints of each drone, including maximum speed, acceleration limits, and maneuverability. Incorporating these factors ensures that the trajectories are feasible for execution by the drones [54].

3.2.2 SAPP Problem Subcomponents

The SAPP problem can be decomposed into two key subproblems: (1) the task allocation or assignment problem, and (2) the trajectory generation problem. Both are interdependent and must be solved in tandem.

1. Task Allocation: The assignment problem is represented as an optimization problem, where N drones are assigned to M goals. The task is to minimize the total cost of assignment, expressed through an assignment matrix \(\psi \), where each element \(\psi _{ij}\)equals one if drone i is assigned to goal j and zero otherwise:

$$\begin{aligned} \psi _{\textrm{ij}} = {\left\{ \begin{array}{ll} 1 & \text {if drone}\,i\hbox { is assigned to goal }j, \\ 0 & \text {otherwise.} \end{array}\right. } \end{aligned}$$
(2)

This assignment must ensure that each drone is allocated exactly one goal and vice versa, which is mathematically represented by the constraints:

$$\begin{aligned} \sum _{i=1}^{N} \psi _{\textrm{ij}} = 1, \quad \sum _{j=1}^{M} \psi _{\textrm{ij}} = 1, \quad \forall i, j. \end{aligned}$$
(3)

2. Path Planning: Once, the assignment is determined, the next challenge is to generate trajectories that minimize the chosen cost functional, while satisfying dynamic and safety constraints. Therefore, generating motion trajectories for each drone involves addressing the following key aspects:

  • Optimality: The path designed for each drone must meet the optimization criteria shown in Eq. 1, ensuring the minimization of the specified cost functional.

  • Dynamic Feasibility: Accounting for drone dynamics is crucial in trajectory design. Drones cannot effectively follow arbitrary paths composed solely of straight-line segments. Therefore, trajectories must be crafted to ensure the dynamic feasibility of the drones [55].

  • Safety: While, the SAPP problem assumes obstacle-free environments, ensuring collision avoidance among drones is paramount. Equation 9 defines the minimum distance between any two drones, incorporating a safety margin parameter \(\phi \) to enhance safety. The constraint ensures that this distance remains greater than twice the radius R of a spherical-like drone. An additional safety margin accommodates factors like aerodynamic interference and uncertainties, applied over the time interval \([t_0, t_f]\).

3.3 Optimizing Task Allocation Criteria

As we will utilize the HA to solve the LAP, it is necessary to determine the cost matrix that the algorithm will use to search for the optimal assignment. Creating the cost matrix depends on the selected optimization criteria, such as minimizing the sum of distances between each robot and all goals, or minimizing the sum of squared distances. As mentioned earlier, the selected Optimizing Task Allocation Criteria (OTAC) directly impacts the overall performance of the SAPP problem. The sum criterion may not guarantee R2R collision-free trajectories, while the robots travel to their destinations, as illustrated in [24].

In this work, we will select the OTAC as follows: find the optimal assignment that minimizes the summation of the traveled distances by all robots to their assigned goals. According to the calculus of variations [56], this criterion corresponds to finding the paths with the minimum velocity norm squared, and thus the cost matrix will be determined according to Eq. 4:

$$\begin{aligned} B^* = \underset{\zeta (t)}{\text {arg min}} \int _{t=t_0}^{t=t_f} \left| \dot{\zeta }(t)\right| ^2 \, \textrm{dt}, \end{aligned}$$
(4)

, where \(\dot{\zeta }(t)\) represents the velocity components. Since the solution of Equation (4) for SAPP will consist of straight-line trajectories connecting each robot with all goals. These connecting waypoints, located along the straight-line paths, will be essential for constructing dynamically feasible trajectories. This construction will be accomplished by leveraging the algorithm introduced in [55]. Consequently, Eq. 4 can be reformulated as follows:

$$\begin{aligned} B_{\textrm{ij}} = ||\mathbf {\chi }_\textrm{i}^R - \mathbf {\chi }_j^G ||^2, \quad i=1:N, \quad j=1:M \end{aligned}$$
(5)

, where \(\mathbf {\chi }_i^R\) and \(\mathbf {\chi }_j^G\) represent the initial position of robot i and the location of goal j, respectively. \(B \in \mathbb {R}^{N \times M}\), and \(B_{\textrm{ij}}\) denotes the element of the cost matrix corresponding to row i and column j.

3.4 Considerations for Inter-Robot Collision Avoidance

Ensuring collision-free trajectories among swarm drones is a fundamental requirement in solving the SAPP problem [57]. This subsection details the strategies employed to mitigate R2R collisions, focusing solely on inter-robot avoidance, as no external obstacles are considered in this scenario.

The SAPP framework incorporates several collision avoidance mechanisms based on different operational scenarios. These mechanisms include the concept of interchangeability and a pre-established safe distance between drones, denoted as \(\Delta _{\text {sf}}\), which is assumed to be greater than \(2\sqrt{2} r\), where r is the maximum moment-arm of the quadrotor [24]. This constraint is designed to prevent R2R collisions under normal operating conditions, ensuring that drones maintain safe separation, while performing their tasks.

However, in certain cases, such as when drones have varying speeds or different mission completion times, the potential for collisions increases, as shown in Fig. 3 [58]. As shown in Fig. 3, the optimal assignment determined by the HA leads to the pairs (R1, G2), (R2, G3), and (R3, G1), with the corresponding cost and assignment matrices shown in Eq. 6. A potential collision may arise between the pairs (R2, R1) and (R2, R3), necessitating activation of the R2R collision avoidance mode to prevent such occurrences.

$$\begin{aligned} B = \begin{bmatrix} 440.64 & 482.76 & 531.36 \\ 116.64 & 158.76 & 207.36 \\ 440.64 & 482.76 & 531.36 \end{bmatrix}, \quad \psi = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} \end{aligned}$$
(6)
Fig. 3
figure 3

A Case study represents the possibility of R2R collision

Full size image

To address such scenarios, the R2R Collision Avoidance Mode is activated, which includes several possible corrective actions:

  • Assignment Adjustments Reassign drones to different goals to avoid collision-prone pairings.

  • Replanning Mode Modify trajectories dynamically to prevent collisions, while ensuring mission objectives are still met.

  • Timing Adjustments Alter the mission completion times of certain drones to create staggered arrival times and avoid conflict.

  • Nonlinear Trajectory Generation Switch from straight-line to nonlinear trajectories to evade potential collisions.

The choice of avoidance strategy depends on the specific context of the mission. For example, when drones are operating with identical speeds and homogeneous characteristics, maintaining the interchangeability constraint is sufficient for safe operations. However, when speed discrepancies or timing variations exist, more dynamic interventions, such as replanning or nonlinear trajectory generation, are necessary.

In another words, to ensure robust inter-robot collision avoidance, the SAPP Framework employs a combination of static constraints (e.g., fixed safe distance) and dynamic collision avoidance strategies (e.g., assignment adjustments, replanning). These methods collectively ensure the safe execution of trajectories, accounting for both static and dynamic operational variables.

3.5 SAPP Solution Procedure

The SAPP approach addresses the simultaneous assignment and trajectory planning problems for swarm drone formations through a structured procedure outlined in Algorithm 1. Initially, the algorithm begins by specifying the necessary settings, including the initial states of the drones and their respective goals. The process then unfolds in several key steps:

  • Assignment Problem The algorithm constructs a cost matrix B in line 6, which is critical for determining the optimal assignments of drones to goals. In line 7, the LAP is solved using the Hungarian Algorithm (HA). The HA efficiently identifies optimal costs for each assignment, offering a significant computational advantage with a time complexity bound of \( O(\max (N,M)^3) \) compared to the factorial complexity of \( O(\max (N,M)!) \).

  • Trajectory Generation Once the assignments are established, the algorithm generates time-parametrized trajectories for each robot-goal pair in lines ([8–12]), utilizing the proposed Trajectory Generation and Optimization Algorithm (TGOA) [18]. This ensures that each drone is assigned a clear and feasible path to its designated goal.

  • Collision Avoidance To ensure safety during operation, line 14 incorporates a critical check for potential R2R collisions. This assessment is performed dynamically as trajectories are generated, allowing the algorithm to adaptively modify paths if necessary. This step significantly reduces the risk of collisions among the drones, enhancing the overall safety of the operation.

  • Coordination and Local Interaction A decentralized communication strategy facilitates coordination among drones. Each drone shares its current state, planned trajectory, and local observations with neighboring drones. This information exchange enables adaptive decision-making and real-time adjustments to trajectories, ensuring efficient resource allocation and effective collaboration. By leveraging local interactions, the SAPP framework enhances the robustness and adaptability of swarm operations, allowing drones to respond dynamically to environmental changes and mission parameters.

Algorithm 1
figure a

SAPP Solution Algorithm

Full size image

By following this methodical procedure, the proposed SAPP approach effectively integrates the assignment and trajectory planning tasks, ensuring coordinated and safe movement for the drone team. The systematic handling of both aspects leads to optimized performance in complex operational environments.

The theoretical soundness of the SAPP approach can be proven by analyzing both the assignment and path planning components. We begin by proving the optimality of the assignment step using the HA, which guarantees an optimal solution for LAPs in polynomial time. Given a cost matrix \(B \in \mathbb {R}^{N \times M}\), where each element \(B_{ij}\) denotes the cost of assigning drone i to goal j, the HA solves the assignment problem by minimizing the total cost:

$$\begin{aligned} \psi ^* = \underset{\psi \in \{0,1\}^{N \times M}}{\text {arg min}} \sum _{i=1}^{N} \sum _{j=1}^{M} \psi _{\textrm{ij}} B_{\textrm{ij}}. \end{aligned}$$
(7)

The time complexity of the HA is \(O(N^3)\), making it computationally feasible even for large-scale problems.

Next, we turn to the path planning problem. The cost functional in Eq. 4 is minimized when the velocity norm is constant over the duration of the trajectory, leading to straight-line paths. This solution can be verified by applying the Euler-Lagrange equation to the cost functional, yielding a constant velocity for each drone:

$$\begin{aligned} \frac{d}{\textrm{dt}} \left( \frac{\partial L}{\partial \dot{\zeta }} \right) - \frac{\partial L}{\partial \zeta } = 0 \quad \Rightarrow \quad \ddot{\zeta }(t) = 0. \end{aligned}$$
(8)

Thus, the optimal trajectory is a straight-line path, with the velocity vector \(\dot{\zeta }(t)\) remaining constant throughout the mission.

The final component of the theoretical proof concerns collision avoidance. To ensure safe navigation, the Euclidean distance between any two drones must remain greater than a predefined safety margin, \(\phi \), as expressed in Eq. 9:

$$\begin{aligned} \Vert \eta _i(t) - \eta _j(t) \Vert \ge 2 R \phi , \quad \forall t \in [t_0, t_f], \quad i \ne j, \end{aligned}$$
(9)

, where R represents the radius of each drone, and \(\phi > 1\) is a safety factor accounting for aerodynamic interference and uncertainties. This condition ensures that the trajectories generated are not only dynamically feasible but also safe from inter-drone collisions.

4 Simulation Results

This section presents an extensive set of simulation results aimed at evaluating the performance and effectiveness of the proposed SAPP framework for swarm flying robots. The simulations were conducted using MATLAB R2023b on a machine powered by an Intel(R) Core(TM) i7-1185G7 CPU @ 3.00GHz and 16 GB of RAM, ensuring sufficient computational resources for dynamic, large-scale simulations. A series of diverse scenarios were tested to assess the algorithm’s ability to handle different task assignment and path-planning challenges in a dynamic multi-robot environment.

The scenarios focus on varying the number of robots and goals, the complexity of the patterns, and the task allocation strategies, thus providing a comprehensive evaluation of the algorithm’s adaptability and robustness in real-world applications. The simulation results clearly demonstrate the SAPP framework’s ability to assign tasks efficiently, generate collision-free and dynamically feasible trajectories, and adapt to both structured and unstructured environments.

4.1 Scenario 1: Single-stage SAPP with \(\textbf{N}_\textbf{R} = \textbf{M}_\textbf{G} = 50\) (Random-based Pattern Formation)

In this scenario, 50 quadrotor robots are randomly placed in the environment, and each is assigned to one of 50 randomly distributed goal destinations. Figure 4 depicts the initial configuration of the robots and their goals. The SAPP framework optimally assigns each robot to its optimal goal, minimizing the total assignment cost, while ensuring collision avoidance. The algorithm also accounts for real-world uncertainties by enforcing safe minimum distances between robots and their goals.

The generated optimal trajectories, shown in Fig. 5, demonstrate the algorithm’s precision in trajectory generation. The simulation runs over 13 s, allowing adequate time for observing dynamic interactions between robots as they follow their planned trajectories to their respective goal positions. The results showcase the effectiveness of the SAPP framework in coordinating a large team of robots in a collision-free manner.

Fig. 4
figure 4

Initial random placement of 50 quadrotor robots and their goal destinations in Scenario 1, ensuring compliance with collision avoidance constraints

Full size image
Fig. 5
figure 5

Optimal task assignment and generated trajectories for 50 quadrotor robots using the SAPP framework, ensuring collision-free navigation and minimizing mission cost

Full size image

4.2 Scenario 2: Multistaged SAPP with \(\textbf{N}_\textbf{R} = \textbf{M}_\textbf{G} = 20\) (Specified-based Pattern Formation)

In the second scenario, 20 quadrotor robots are initially arranged in a circular formation and are assigned to form different predefined shapes (square, star, and circle) at each stage of the mission. Figure 6 illustrates the initial and subsequent target formations.

This multi-stage simulation evaluates the SAPP framework’s ability to handle continuous reassignments and dynamically changing environments. The visualized optimal trajectories, shown in Fig. 7, reveal how the robots adjust their paths in response to new patterns, while maintaining inter-drone collision avoidance. The time histories of quadrotor states, as shown in Fig. 8, allow for detailed analysis of the drones’ velocity, position, and orientation during the entire process.

Fig. 6
figure 6

Initial circular arrangement of 20 quadrotor robots in Scenario 2, set to transition through multiple predefined formations (square, star, and circle) during the simulation. The goal formations are designed to evaluate the SAPP framework’s ability to adapt to evolving task demands

Full size image
Fig. 7
figure 7

Optimal task assignments and dynamic trajectories for quadrotor robots in Scenario 2 during transitions between specified patterns. The SAPP framework ensures efficient task allocation and trajectory optimization as the swarm adapts to each formation

Full size image

4.3 Scenario 3: Multistaged SAPP with \(\textbf{N}_\textbf{R} = \textbf{M}_\textbf{G} = 20\) (Random-based Pattern Formation)

This scenario builds on Scenario 2 by introducing random patterns at each stage instead of predefined formations. The desired goals are set at four different heights: 5 m, 10 m, 15 m, and 20 m. At each height, the x and y coordinates are randomly generated using permutations of integers, adjusted to ensure no repetition and to maintain a safe distance between robots. The 20 quadrotor robots are dynamically reassigned to these random positions over multiple stages, testing the SAPP framework’s ability to adapt to unstructured environments, while generating collision-free and dynamically feasible trajectories for various configurations.

Fig. 8
figure 8

Time history of quadrotor no. 1’s states, including position, velocity, and orientation during Scenario 2. This provides a detailed analysis of the robot’s performance as it navigates through multiple goal configurations, demonstrating the algorithm’s efficiency in trajectory generation

Full size image

Figure 9 shows the configuration at different stages, while Fig. 10 presents four snapshots of the robots’ movement during the simulation. The dynamic paths generated by the algorithm enable the swarm to avoid collisions, while successfully completing their tasks. Table 1 offers a detailed account of Robot no. 15’s state throughout the stages, as a sample for the drone swarm, showcasing the precision with which the algorithm handles both spatial and temporal constraints. The time histories, shown in Fig. 11, provide deeper insights into how the robot’s state evolves as it executes its assigned tasks.

Table 1 Sample of the simulation Configuration for Robot no, 15
Full size table
Fig. 9
figure 9

Sequential stages of random-based goal configurations for 20 quadrotor robots in Scenario 3. The robots are dynamically reassigned to randomly placed goals in each stage

Full size image
Fig. 10
figure 10

Snapshots of dynamic trajectories in Scenario 3, showcasing smooth transitions between randomly assigned goal destinations. The images highlight coordinated movements and collision avoidance ensured by the SAPP framework

Full size image
Fig. 11
figure 11

Time history of Robot no. 15’s states (position, velocity, and orientation) throughout Scenario 3. This plot provides insights into the robot’s dynamic behavior and highlights the SAPP framework’s effectiveness in ensuring optimal dynamically-feasible trajectory generation and task completion

Full size image

4.4 Scenario 4: Multistaged SAPP with \(\textbf{N}_\textbf{R} > \textbf{M}_\textbf{G}\) (Random-based Pattern Formation)

In the fourth scenario, 15 quadrotor robots are assigned to 10 goals, creating an unbalanced task allocation problem. The SAPP framework optimally selects which robots to assign to goals based on the mission’s cost minimization requirements, while the unassigned robots remain stationary at their initial positions.

Figure 12 shows the robots’ dynamic paths during this scenario. The results highlight the SAPP framework’s ability to handle unbalanced task assignments efficiently, ensuring that only the robots contributing to the optimal solution are actively engaged. Figure 13 presents the time history for Robot no. 5 as a sample for the team, allowing us to assess the robot’s behavior over time.

Across all scenarios, the SAPP framework consistently demonstrated its ability to generate optimal task allocations and collision-free trajectories for a swarm of flying robots. The dynamic reallocation of robots to goals, real-time trajectory adjustments, and continuous collision avoidance underscore the robustness and flexibility of the framework. A supplemental video of the simulations can be accessed at http://youtu.be/QAHZlkwhVDQ, offering an in-depth visualization of the drones behaviors and algorithm performance.

The simulation results indicate that the SAPP framework can significantly improve task allocation and path planning for swarm flying robots, even in complex and dynamic environments. These findings suggest its potential for applications in search and rescue missions, environmental monitoring, and large-scale robotic coordination tasks.

Fig. 12
figure 12

Configuration and optimal assignment for 15 robots in Scenario 4 with 10 available goals. The SAPP framework assigns tasks efficiently, leaving unassigned robots stationary, while ensuring collision-free paths

Full size image
Fig. 13
figure 13

Time history of the states of quadrotor No. 5 "as a sample for the team" during Scenario 4, depicting the robot’s trajectory, velocity, and orientation over the simulation period

Full size image

5 Conclusions

This study presents a Simultaneous Allocation and Path Planning (SAPP) framework that effectively addresses the simultaneous task allocation and path planning challenges in swarm flying robots. Through extensive simulations across varied configurations, environments, and scenarios, the SAPP framework has demonstrated its ability to generate dynamically-feasible, collision-free trajectories, while efficiently managing task assignments. The algorithm’s adaptability to different formations, task complexities, and varying numbers of robots underscores its potential to enhance the coordination and performance of swarm flying robots. These results suggest that the SAPP framework is a versatile solution, capable of meeting the demands of real-world applications, including those requiring dynamic task reallocation and precise path optimization. Future work will explore physical experiments to further validate the algorithm’s practical applicability.