Paper deep dive
Integrated Multi-Drone Task Allocation, Sequencing, and Optimal Trajectory Generation in Obstacle-Rich 3D Environments
Yunes Alqudsi, Murat Makaraci
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/27/2026, 1:18:08 AM
Summary
The paper introduces IMD-TAPP, an end-to-end framework for multi-drone task allocation, sequencing, and trajectory generation in obstacle-rich 3D environments. It integrates graph-search-based cost construction, an Injected Particle Swarm Optimization (IPSO) algorithm guided by multiple linear assignment for discrete planning, and a minimum-snap trajectory generation routine with iterative safety validation.
Entities (5)
Relation Signals (3)
IMD-TAPP โ performs โ Trajectory Generation
confidence 100% ยท the resulting waypoint tours are transformed into time-parameterized minimum-snap trajectories
IMD-TAPP โ utilizes โ IPSO
confidence 100% ยท These costs are then embedded within an Injected Particle Swarm Optimization (IPSO) scheme
IPSO โ guidedby โ Multiple Linear Assignment
confidence 95% ยท IPSO scheme, guided by multiple linear assignment, to efficiently explore coupled assignment/ordering
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Coordinating teams of aerial robots in cluttered three-dimensional (3D) environments requires a principled integration of discrete mission planning-deciding which robot serves which goals and in what order -- with continuous-time trajectory synthesis that enforces collision avoidance and dynamic feasibility. This paper introduces IMD-TAPP (Integrated Multi-Drone Task Allocation and Path Planning), an end-to-end framework that jointly addresses multi-goal allocation, tour sequencing, and safe trajectory generation for quadrotor teams operating in obstacle-rich spaces. IMD--TAPP first discretizes the workspace into a 3D navigation graph and computes obstacle-aware robot-to-goal and goal-to-goal travel costs via graph-search-based pathfinding. These costs are then embedded within an Injected Particle Swarm Optimization (IPSO) scheme, guided by multiple linear assignment, to efficiently explore coupled assignment/ordering alternatives and to minimize mission makespan. Finally, the resulting waypoint tours are transformed into time-parameterized minimum-snap trajectories through a generation-and-optimization routine equipped with iterative validation of obstacle clearance and inter-robot separation, triggering re-planning when safety margins are violated. Extensive MATLAB simulations across cluttered 3D scenarios demonstrate that IMD--TAPP consistently produces dynamically feasible, collision-free trajectories while achieving competitive completion times. In a representative case study with two drones serving multiple goals, the proposed approach attains a minimum mission time of 136~s while maintaining the required safety constraints throughout execution.
Tags
Links
- Source: https://arxiv.org/abs/2603.24908v1
- Canonical: https://arxiv.org/abs/2603.24908v1
Trouble viewing inline? Open PDF directly โ
Full Text
44,178 characters extracted from source content.
Expand or collapse full text
Integrated Multi-Drone Task Allocation, Sequencing, and Optimal Trajectory Generation in Obstacle-Rich 3D Environments Yunes ALQUDSI a,b,โ , Murat MAKARACI c a Aerospace Engineering Department, Faculty of Aeronautics and Astronautics, Kocaeli University, Kocaeli, Turkiye b Interdisciplinary Research Center for Aviation and Space Exploration, KFUPM, Dhahran, Saudi Arabia c Mechanical Engineering Department, Faculty of Aeronautics and Astronautics, Kocaeli University, Kocaeli, Turkiye A R T I C L E I N F O Keywords: Multi-UAV mission planning multi-robot task allocation multi-goal routing obstacle-aware graph search collision avoidance trajectory optimization A B S T R A C T Coordinating teams of aerial robots in cluttered three-dimensional (3D) environments requires a principled integration of discrete mission planningโdeciding which robot serves which goals and in what orderโwith continuous-time trajectory synthesis that enforces collision avoidance and dynamic feasibility. This paper introduces IMDโTAPP (Integrated Multi-Drone Task Allocation and Path Planning), an end-to-end framework that jointly addresses multi- goal allocation, tour sequencing, and safe trajectory generation for quadrotor teams operating in obstacle-rich spaces. IMDโTAPP first discretizes the workspace into a 3D navigation graph and computes obstacle-aware robot-to-goal and goal-to-goal travel costs via graph-search-based pathfinding. These costs are then embedded within an Injected Particle Swarm Optimization (IPSO) scheme, guided by multiple linear assignment, to efficiently explore coupled assign- ment/ordering alternatives and to minimize mission makespan. Finally, the resulting waypoint tours are transformed into time-parameterized minimum-snap trajectories through a generation- and-optimization routine equipped with iterative validation of obstacle clearance and inter- robot separation, triggering re-planning when safety margins are violated. Extensive MATLAB simulations across cluttered 3D scenarios demonstrate that IMDโTAPP consistently produces dynamically feasible, collision-free trajectories while achieving competitive completion times. In a representative case study with two drones serving multiple goals, the proposed approach attains a minimum mission time of 136 s while maintaining the required safety constraints throughout execution. 1. Introduction Unmanned aerial vehicles (UAVs), including multirotor platforms, have evolved from laboratory prototypes into widely deployed autonomous systems for inspection, mapping, monitoring, and logistics. This progress has been enabled by advances in onboard sensing, computation, and control, together with the operational flexibility of vertical take-off and landing vehicles [1, 2]. Consequently, mission planning for UAVs is commonly studied through routing and path-planning formulations, and surveys summarize the breadth of algorithms proposed for UAV routing and for autonomous aerial operations in real environments [3, 4]. Many practical deployments remain challenging for a single vehicle because of limited endurance, sensing range, and payload capacity. Coordinated multi-drone teams mitigate these limitations by distributing goals across robots, improving mission completion time, coverage, and robustness [5]. At the same time, cooperation introduces tightly coupled challenges such as shared-airspace safety, congestion around obstacles, and the need for scalable coordination as the team size grows [6]. Benchmarking and evaluation suites for swarm robotics highlight the importance of standardized, reproducible testing when comparing multi-robot coordination approaches [7, 8], and state-of-the-art reviews emphasize the remaining gaps between laboratory demonstrations and reliable, scalable field operation [9]. A persistent difficulty in multi-drone operation is guaranteeing safety while preserving efficiency. Collision avoidance must be enforced both with respect to static obstacles and between robots moving in the same airspace, often under dynamic constraints and imperfect information [10]. Surveys of collision-avoidance schemes and autonomous drone swarms emphasize the importance of principled separation constraints and reliable replanning mechanisms that remain stable when multiple vehicles interact in close proximity [11, 12]. In parallel, research on distributed โ Corresponding author yunes.alqadasi@kocaeli.edu.tr (Y. ALQUDSI) ORCID(s): 0000-0002-4246-9654 (Y. ALQUDSI) Yunes ALQUDSI, and Murat MAKARACI: Preprint submitted to ElsevierPage 1 of 14 arXiv:2603.24908v1 [cs.RO] 26 Mar 2026 Integrated Multi-Drone Task Allocation and Trajectory Generation in 3D Obstacle-Rich Environments coordination and collective decision-making in robot swarms continues to develop mechanisms that support scalable group behavior under limited communication [13, 14, 15]. From a planning standpoint, multi-drone missions typically couple at least two interacting layers. At the discrete layer, the planner must assign goals to robots and determine feasible visit sequences (multi-robot task allocation) [16, 17]. At the continuous layer, the planner must generate collision-free trajectories that respect obstacle constraints, inter-robot separation, and vehicle dynamics [18]. While decoupling these layers can simplify implementation, it can also yield brittle solutions: an assignment that appears optimal under geometric distances may become infeasible once obstacles, timing, and dynamic limits are enforced. Related work in other domains has similarly argued for integrated schedule-and-trajectory optimization when conflicts arise in shared spaces [19]. Metaheuristic optimization remains a practical choice for the resulting combinatorial search space, especially when the objective is a makespan and constraints must be checked repeatedly during evolution [20, 21, 22]. This work addresses this coupling through the Integrated Multi-Drone Task Allocation and Trajectory Gener- ation framework (IMDโTAPP), which builds environment-aware travel-cost matrices via graph search, optimizes assignments and visit orders via an injected particle swarm optimization (IPSO) algorithm guided by multiple linear assignment, and then synthesizes smooth, dynamically feasible trajectories with iterative safety validation and replanning. By combining environment-aware cost construction with discrete optimization and continuous-time trajectory synthesis, IMDโTAPP targets obstacle-rich 3D settings where both efficiency and safety are critical [23]. The main contributions of this paper are: (1) an obstacle-aware cost-construction module that uses 3D graph search to populate robot-to-goal and goal-to-goal travel-cost matrices in cluttered environments; (2) a joint assignment-and- sequencing optimizer based on IPSO with multiple linear assignment (MLA) guidance, improving convergence toward low-makespan solutions under the visit-once constraint; and (3) an end-to-end planning-to-trajectory workflow that generates optimal trajectories and iteratively revalidates obstacle clearance and inter-robot separation, triggering local replanning when safety constraints are violated. A detailed system schematic for the work presented in research is provided in Figure 1, showing the inputs, core processing stages, and validation loop of the complete IMDโTAPP framework. The remainder of the paper is organized as follows. Section 2 reviews representative work on multi-robot task allocation and multi-agent path planning. Section 3 formalizes the IMDโTAPP problem, objective, and safety constraints. Section 4 presents the proposed framework. Sections 5 and 6 describe the simulation setup and discuss the results. Section 7 concludes the paper and summarizes limitations and future research directions. 2. Related Work Multi-robot task allocation (MRTA) has been studied extensively, with foundational work providing taxonomies that distinguish problem variants by robot heterogeneity, task structure, and assignment coupling [24, 25]. In the context of UAVs and autonomous flying robots, MRTA is frequently coupled to routing because feasibility and cost depend strongly on travel distances through obstacle fields and on timing constraints [26]. Surveys of UAV routing and multi- UAV mission planning emphasize that coupling allocation decisions with environment-aware travel costs is essential for realistic performance evaluation [1, 27, 28] and has motivated distributed MRTA strategies for scalability [14]. A related line of research concerns the routing formulations that underlie multi-goal allocation problems. Multiple- traveling-salesman and vehicle-routing variants have been investigated through mathematical programming and heuristic approaches, including formulations and algorithms that address assignment, sequencing, and feasibility constraints [29, 30, 31]. Dynamic variants incorporating additional limitations, such as energy constraints, further motivate algorithms that balance solution quality with computational tractability [32, 33]. Optimization methods for combinatorial multi-robot planning span exact solvers, heuristics, and soft-computing techniques. Population-based methods are frequently adopted when exact formulations are impractical at scale or when repeated feasibility checks are required under complex constraints [21]. Swarm-inspired coordination and hybrid metaheuristics have also been explored for distributed settings [22], and recent work on collective decision-making highlights how adaptable mechanisms can support scalable group behavior in robot swarms [13]. Safe multi-agent navigation is equally critical in shared 3D environments. Many coordination problems can be mapped to multi-agent pathfinding (MAPF) on graphs, which plans conflict-free paths for multiple agents while optimizing criteria such as makespan [34]. For large teams, scalability and safety are central concerns, and prior work has investigated safe, scalable, and complete motion planning for large groups of interchangeable robots [35]. In the UAV context, complete flight trajectory planning for multiple vehicles has also been studied, providing useful insights Yunes ALQUDSI, and Murat MAKARACI: Preprint submitted to ElsevierPage 2 of 14 Integrated Multi-Drone Task Allocation and Trajectory Generation in 3D Obstacle-Rich Environments Fig. 1: The IMDโTAPP system schematic. The framework takes as inputs the 3D environment with obstacles, robot start states ํฃ ํ ํ , and goal set ํบ. The core processing stages include: (i) graph discretization and search to compute cost matrices ํ ํ ํบ and ํ ํบ , (i) IPSO with MLA guidance to optimize assignment and visit sequences, and (i) minimum-snap trajectory generation to produce time-parameterized trajectories. The final stage validates obstacle clearance and inter-robot separation (โฅ 2ํ ํ ํ) through simulation rollout, outputting collision-free multi-drone trajectories. into feasibility under constraints [36]. Collision avoidance remains a persistent challenge in practice, and surveys review sensing, planning, and avoidance strategies as well as open issues [10, 11, 12]. Integrated task assignment and path planning has therefore attracted increasing attention. Distributed and decen- tralized strategies have been explored to support coordination under limited communication, dynamic conditions, and real-time replanning requirements [15, 37, 38]. Recent studies examine synergistic coupling of allocation with obstacle- aware planning [39] and learning-based coupling of assignment and navigation in dynamic obstacle environments [40]. More broadly, related research in shared conflict zones has demonstrated the value of integrating scheduling and trajectory optimization in a single decision loop [19], which is conceptually aligned with the motivation of IMDโTAPP. Finally, trajectory generation for quadrotors commonly relies on polynomial optimization to obtain smooth and dynamically feasible flight profiles; minimum-snap formulations are particularly influential because they promote smoothness and enable constraint enforcement along waypoint corridors [41]. Complementary work has developed numerically stable trajectory generation and general optimization frameworks for highly maneuverable multirotor drones in complex environments [42, 43], and integrated task assignment with trajectory generation has been investigated to improve collision avoidance and flight efficiency in multi-drone operations [44]. IMDโTAPP follows this broad philosophy by combining graph-search cost construction with discrete optimization and continuous-time trajectory synthesis, while maintaining an explicit safety-validation loop. 3. Problem Formulation We consider a team of ํ ํ aerial robots that must collectively visit a set of ํบ ํ goals in a bounded 3D workspace containing obstacles. Each goal must be visited exactly once by any robot, and each robot must return to its takeoff point after completing its assigned goals (Figure 2). Yunes ALQUDSI, and Murat MAKARACI: Preprint submitted to ElsevierPage 3 of 14 Integrated Multi-Drone Task Allocation and Trajectory Generation in 3D Obstacle-Rich Environments Fig. 2: Illustrative IMDโTAPP scenario: two drones must cooperatively visit seven goals in a 3D environment with obstacles, with each goal visited exactly once and each drone returning to its start location. The robots are treated as interchangeable with respect to goal servicing, and the environment is modeled as obstacle- rich and potentially challenging for line-of-sight motion. Let ํํ ํ denote the goal sequence assigned to robot ํ. ํ ํํ = 1 if goal ํ is assigned to drone ํ 0 otherwise (1) The traversal cost of a robot tour is denoted by ํถ(ํฃ ํ ํ โ ํํ ํ โ ํฃ ํ ํ ) and is computed from obstacle-aware geometric path costs between successive waypoints, including (i) travel from the robot start ํฃ ํ ํ to the first goal, (i) travel between consecutive goals in ํํ ํ , and (i) return from the last goal back to ํฃ ํ ํ . The IMDโTAPP objective is to minimize the mission makespan, i.e., the maximum tour cost among all robots: ํฝ โ = min ํํ 1 ,...,ํํ ํ ํ max ํโ1,...,ํ ํ ํถ ( ํฃ ํ ํ โ ํํ ํ โ ํฃ ํ ํ ) .(2) In many multi-goal aerial missions, each drone is required to terminate at a specified home or recovery location, which influences both allocation and timing decisions. where ํฃ ํ ํ is the initial state of robot ํ and ํํ ํ denotes its ordered list of assigned goals (possibly empty). For feasibility, robot motion must satisfy obstacle avoidance and inter-robot safety. Collision avoidance between robots ํ and ํ is enforced through the distance constraint โํ ํ (ํก) โ ํ ํ (ํก)โ โฅ 2ํ ํ ํ, ํ > 1, ํก โ [ํก 0 ,ํก ํ ],(3) where ํ ํ (ํก) is the position of robot ํ at time ํก, and ํ ํ is a spherical safety radius that conservatively approximates the robot body. In addition, dynamic feasibility must be considered when generating time-parameterized trajectories, including bounds on velocities and accelerations [43]. To improve readability, Table 1 summarizes the main symbols used in the formulation and algorithm description. 4. Proposed IMDโTAPP Framework The proposed pipeline addresses the IMDโTAPP problem by combining (i) 3D graph construction and graph- search-based pathfinding, (i) IPSO optimization guided by multiple linear assignment, and (i) trajectory generation and validation for dynamic feasibility and collision avoidance. Figure 3 provides a high-level view of the complete pipeline. Yunes ALQUDSI, and Murat MAKARACI: Preprint submitted to ElsevierPage 4 of 14 Integrated Multi-Drone Task Allocation and Trajectory Generation in 3D Obstacle-Rich Environments Table 1 Key notation used in the IMDโTAPP formulation. Symbol Meaning ํ ํ number of robots (drones) ํบ ํ number of goals ํํ ํ ordered goal sequence assigned to robot ํ ํถ(โ )travel cost computed from geometric paths ํฝ โ optimal mission objective (makespan) ํ ํ (ํก)position of robot ํ over time ํ ํ conservative robot safety radius ํsafety inflation factor (ํ > 1) Fig. 3: High-level overview of the IMDโTAPP pipeline: (i) 3D workspace discretization and graph-search computation of obstacle-aware travel costs,(i) discrete optimization of goal assignment and visit sequencing using an injected (PSO) algorithm guided by multiple linear assignment, and (i) smooth trajectory generation followed by safety validation with iterative replanning when necessary. 4.1. Cost-matrix construction via graph search The IMDโTAPP discretizes the obstacle-filled workspace into a 3D graph and uses a graph-search algorithm (GSA) to compute feasible paths between relevant pairs of states [45, 46, 47]. Specifically, shortest-path costs are computed between each robot start state and each goal (robots-to-goals matrix), and between each pair of goals (goals-to-goals matrix). Unreachable pairs are filtered to prevent infeasible assignments from entering the optimization stage. Figure 4 illustrates the discretization of the 3D workspace into a navigable graph and demonstrates how obstacle- aware shortest paths computed via graph search (e.g., A*) populate the robots-to-goals cost matrix ํ ํ ํบ and goals-to- goals cost matrix ํ ํบ that serve as inputs to the discrete optimization stage. To clarify how environment-aware graph-search costs are converted into a discrete optimization input, Figure 5 illustrates the construction of the robots-to-goals and goals-to-goals cost matrices and the corresponding particle encoding used by the IPSO stage (goal permutation and breakpoints ensuring that each goal is visited exactly once). Yunes ALQUDSI, and Murat MAKARACI: Preprint submitted to ElsevierPage 5 of 14 Integrated Multi-Drone Task Allocation and Trajectory Generation in 3D Obstacle-Rich Environments Fig. 4: 3D discretization and obstacle-aware travel-cost computation. (a) The workspace is discretized into a voxel graph with free-space nodes; obstacles block direct paths, requiring graph search to find collision-free routes between robot starts ํฃ ํ ํ , goals ํ ํ and ํ ํ . (b) Graph-search distances populate the robots-to-goals matrix ํ ํ ํบ (with entries ํถ(ํฃ ํ ํ ,ํ ํ )) and the goals-to-goals matrix ํ ํบ (with entries ํถ(ํ ํ ,ํ ํ )), which are then used by the discrete optimizer to determine assignments and visit sequences. 4.2. Assignment and sequencing via injected (PSO) algorithm Given travel-cost matrices, the discrete optimization stage seeks an assignment of goals to robots and an ordering of visits that minimizes the makespan objective in (2). The search space is combinatorial, grows rapidly with the number of goals, and is generally NP-hard. The framework therefore adopts a (PSO) algorithm variant [48] with injection mechanisms and structured guidance, exploiting both exploration and exploitation to avoid premature convergence. Multiple linear assignment (MLA) is leveraged to generate high-quality candidate sequences and to guide reordering within the PSO evolution loop, improving convergence toward low-cost solutions. Figure 6 summarizes the IPSO decision loop and highlights where multiple linear assignment (MLA) is used to seed and periodically replace low-quality particles, thereby accelerating convergence while maintaining feasibility under the visit-once constraint. 4.3. Trajectory generation and safety validation After obtaining an optimized discrete plan, each robotโs geometric path is converted into a time-parameterized trajectory. The trajectory generation stage uses intermediate waypoints and an optimization routine that promotes smoothness (minimizing snap) while satisfying dynamic constraints [42, 49]. The resulting trajectories are then iteratively validated against the inter-robot separation constraint in (3); if violations are detected, local re-planning is triggered, and the final trajectories are revalidated [44]. The trajectory generation pipeline is detailed in Figure 7, which illustrates how geometric waypoints obtained from the discrete plan are transformed into smooth, dynamically feasible trajectories through time allocation, piecewise polynomial optimization with snap minimization, and enforcement of continuity constraints at waypoint junctions. As shown in Figure 8, the continuous-time stage converts the discrete plan into smooth trajectories and then iteratively checks obstacle clearance and inter-drone separation; if violations are detected, the framework triggers local re-planning and regenerates trajectories until the safety constraints are satisfied. Algorithm 1 summarizes the complete IMDโTAPP procedure. Yunes ALQUDSI, and Murat MAKARACI: Preprint submitted to ElsevierPage 6 of 14 Integrated Multi-Drone Task Allocation and Trajectory Generation in 3D Obstacle-Rich Environments 3D workspace obstacles + bounds 3D graph nodes + edges Graph search (GSA) shortest paths RobotsโGoals matrix ํถ ํ โโ ํ ํ รํบ ํ [ํถ ํ ] ํ,ํ = cost(ํฃ ํ โ ํ ํ ) GoalsโGoals matrix ํถ ํบ โโ ํบ ํ รํบ ํ [ํถ ํบ ] ํ,ํ = cost(ํ ํ โ ํ ํ ) Fitness evaluation makespan ํฝ = max ํ ํถ(ํํ ํ ) Particle position (solution encoding) A particle encodes (i) a permutation of all goals (visit order) and (i) breakpoints that partition the ordered list among the ํ ํ drones. Example (ํ ํ =2, ํบ ํ =7): ํ = [4, 1, 6, 3, 2, 5, 7], breakpoint ํ=3 (first three goals for drone 1, remaining goals for drone 2). Drone 1: [4, 1, 6]โ return|Drone 2: [3, 2, 5, 7]โ return Feasibility checks (enforced during decoding/repair) (1) remove unreachable assignments (invalid matrix entries), (2) repair duplicates/miss- ing goals to satisfy โvisit each goal onceโ, (3) validate breakpoint partitions for all drones. Fig. 5: Cost-matrix construction and solution encoding for the discrete optimization stage. Graph search produces robots- to-goals and goals-to-goals travel-cost matrices, which are evaluated through a PSO particle representation encoding a goal-visit permutation and breakpoints that partition the ordered goals among drones while enforcing the visit-once constraint. 5. Simulation Setup Simulations were executed using MATLAB R2023b on a laptop equipped with an Intel(R) Core(TM) i7-1065G7 CPU @ 1.30GHz, NVIDIA GeForce GTX 1650 GPU with 4 GB dedicated memory, and 16 GB RAM. Quadrotor parameters followed [50]. The robots were assumed to have onboard sensing sufficient to detect obstacles and to support replanning within the IMDโTAPP pipeline. Figure 9 shows the representative 3D obstacle-filled environment used to illustrate the algorithm. The initial robot states and goal locations are indicated for reproducibility of the qualitative results. To facilitate reproducibility, Table 2 summarizes the main simulation and implementation settings reported in this study. 6. Results and Discussion The IMDโTAPP objective is to determine an optimal sequence of goal visits for each robot such that all goals are serviced exactly once and each robot returns to its start point. The discrete stage therefore balances the combinatorial Yunes ALQUDSI, and Murat MAKARACI: Preprint submitted to ElsevierPage 7 of 14 Integrated Multi-Drone Task Allocation and Trajectory Generation in 3D Obstacle-Rich Environments Inputs ํถ ํ ,ํถ ํบ constraints Swarm init. particles encode routes+breakpoints Fitness makespan ํฝ PSO update (ํ,ํ 1 ,ํ 2 ) ํฃ,ํฅ ํํํํ ํก / ํํํํ ํก update MLA-guided injection (i) Seed ํ seed particles from MLA solutions (i) Every ํ inj iters: replace worst particles Repair / normalization enforce โvisit onceโ fix breakpoints remove duplicates Stop ํผ max or tolerance Output best routes (ํํํํ ํก) Fig. 6: Injected PSO with MLA guidance for joint goal assignment and sequencing. Particles encode routes and breakpoints; fitness is evaluated using graph-search costs under the makespan objective. MLA is used both for seeding a fraction of the swarm and for periodic injection (replacement of the worst particles), while a repair step maintains feasibility (each goal visited once and valid partitioning). Fig. 7: Time-parameterized minimum-snap trajectory generation pipeline. The discrete plan provides geometric waypoints (robot start ํฃ ํ ํ , assigned goals, and return-to-start). Segment time allocation assigns durations to each path segment. Piecewise polynomial trajectories are then optimized to minimize integrated snap โซ โ ํ 4 ํฑ ํํก 4 โ 2 ํํก subject to continuity constraints (position, velocity, and acceleration continuous at junctions), producing smooth position, velocity, and acceleration profiles suitable for quadrotor execution. Discrete plan goal sequences ํํ ํ geometric waypoints Trajectory generation TGO / min-snap time parameterization Trajectory rollout sample states ํ ํ (ํก) Safety valid? obstacle & separation Local re-planning adjust timing / insert waypoint / reroute segment Final trajectories collision-free dynamically feasible yes no Key constraints Inter-robot: โํ ํ (ํก) โ ํ ํ (ํก)โ โฅ 2ํ ํ ํ Dynamics: bounds on ํฃ(ํก),ํ(ํก) Fig. 8: Safety validation and re-planning loop in the continuous stage. The discrete plan is converted into time-parameterized trajectories; simulated rollouts are checked for obstacle clearance and inter-robot separation (e.g., โํ ํ (ํก) โ ํ ํ (ํก)โ โฅ 2ํ ํ ํ). If conflicts occur, local re-planning updates the plan and the trajectories are regenerated until feasibility is achieved. search over permutations and partitions of goals across robots. As expected for PSO-based methods, the balance between exploration and exploitation affects both convergence speed and solution quality [51, 52]. Following the IMDโTAPP procedure, graph search is first used to generate collision-free geometric paths and to populate cost matrices. The injected (PSO) algorithm then selects routes and breakpoints that minimize the makespan. An example of the resulting optimal sequence and task assignments is provided in Figure 10a, where the assignment indicates which goals are visited by each robot and in what order. The evolution of the mission-time objective over iterations is shown in Figure 10b. The figure illustrates the convergence behavior of the discrete optimizer toward a low-cost assignment and ordering. After selecting the optimal discrete plan, geometric paths are generated for each robot and visualized in Figure 11a. These paths provide obstacle-avoiding routes connecting each robotโs start state to its assigned goals. Yunes ALQUDSI, and Murat MAKARACI: Preprint submitted to ElsevierPage 8 of 14 Integrated Multi-Drone Task Allocation and Trajectory Generation in 3D Obstacle-Rich Environments Algorithm 1: IMDโTAPP Algorithm Input: Number of drones, initial states, goals, safe distance Output: Optimized trajectories 1 Initialization; 2 Input drone numbers, initialize states and goals, define safe distance; 3 Graph Generation and Pathfinding; 4 Construct 3D graph of environment; 5 for each drone ํ and goal ํ do 6 Compute optimal paths using GSA; 7 Populate Robots-to-Goals and Goals-to-Goals cost matrices; 8 end 9 Filter unreachable goals and drones; 10 Assignment Optimization based on IPSO; 11 Initialization; 12 Define IPSO parameters:; 13 Swarm size (ํ ํ ), maximum iterations (ํผ max ), inertia weight (ํ), cognitive and social coefficients (ํ 1 ,ํ 2 ), velocity bounds (ํฃ max ); 14 Define injection settings:; 15 MLA seeding ratio (ํ seed ), MLA replacement frequency (ํ inj ), random perturbation probability (ํ pert ); 16 Define Cost Function (Min-Time / makespan); 17 Initialize particle positions as candidate routes and breakpoints (encode task order + partitioning), seed a subset using MLA solutions; 18 Initialize velocities and evaluate fitness for all particles; 19 Set personal bests (ํํํํ ํก) and global best (ํํํํ ํก); 20 Swarm Evolution; 21 for ํก = 1 to ํผ max do 22 Update velocity and position of each particle using PSO rules; 23 Repair/normalize infeasible encodings (duplicate goals, missing goals, invalid breakpoints); 24 Evaluate fitness (makespan); 25 Update ํํํํ ํก and ํํํํ ํก; 26 if mod(ํก, ํ inj ) = 0 then 27Replace the worst particles with MLA-refined solutions (injection); 28 end 29 Apply random perturbation / reinitialization with probability ํ pert to avoid stagnation; 30 end 31 Obtain the best routes and breakpoints from ํํํํ ํก; 32 Trajectory Generation; 33 for each drone ํ do 34 Compute intermediate waypoints and generate trajectory states based on Trajectory Generation and Optimization (TGO) algorithm [42]; 35 Validate and re-plan for collision avoidance; 36 end 37 Synthesize and re-validate dynamic trajectories [44]; 38 Simulation and Visualization; 39 Execute animation and derive simulation results; Next, time-parameterized trajectories are synthesized from the geometric paths. Figure 11b presents the resulting trajectories, which satisfy waypoint passage and promote smooth motion by minimizing snap, while respecting feasibility constraints. In this representative case study with two quadrotor robots, the minimum total mission time achieved by the algorithm was 136 sec. Yunes ALQUDSI, and Murat MAKARACI: Preprint submitted to ElsevierPage 9 of 14 Integrated Multi-Drone Task Allocation and Trajectory Generation in 3D Obstacle-Rich Environments Fig. 9: 3D obstacle-filled environment used in the simulation study, illustrating the initial positions of the robots and the set of goal locations. Table 2 Simulation and implementation settings used in the case study. ItemSetting SoftwareMATLAB R2023b CPUIntel Core i7-1065G7 @ 1.30 GHz GPUNVIDIA GeForce GTX 1650 (4 GB) RAM16 GB Robot model parameters As in [50] Environment3D workspace with obstacles (Figure 9) ObjectiveMinimize makespan (Equation 2) Safety constraintInter-robot separation (Equation 3) For a detailed view of the robot states and their evolution over time, Figure 12a provides sample state trajectories. Overall, the results demonstrate that IMDโTAPP can allocate tasks and generate safe trajectories for aerial robot teams operating in cluttered 3D environments. To validate that the generated trajectories satisfy the required safety constraints throughout a mission, Figure 12b presents time histories of the minimum inter-robot separation and minimum obstacle clearance of another mission scenario. Both metrics remain above their respective safety thresholds for the entire mission duration, confirming collision-free operation. 7. Conclusion and Future Work This paper presented IMDโTAPP, an integrated framework for multi-drone goal allocation, visit sequencing, and trajectory generation in obstacle-rich 3D environments. The framework (i) computes obstacle-aware travel costs via 3D graph search, (i) solves the coupled assignment-and-ordering problem using IPSO with MLA guidance under a makespan objective, and (i) produces smooth minimum-snap trajectories with iterative safety validation and local re-planning. MATLAB simulations demonstrate end-to-end feasibility on representative 3D obstacle fields, including Yunes ALQUDSI, and Murat MAKARACI: Preprint submitted to ElsevierPage 10 of 14 Integrated Multi-Drone Task Allocation and Trajectory Generation in 3D Obstacle-Rich Environments (a)(b) Fig. 10: Discrete optimization results. (a) Example optimal sequence and task assignment obtained by the IPSO optimizer, showing the ordered goals assigned to each robot and the required return to the takeoff point. (b) Mission-time objective as a function of iteration number, demonstrating the convergence behavior of the discrete optimization stage. (a) Obstacle-avoiding geometric paths generated for the opti- mized assignment sequence, illustrating each robotโs planned route through its assigned goals. (b) Time-parameterized trajectories generated for each robot, en- suring smooth motion and passage through all designated points while promoting dynamic feasibility via snap minimization. Fig. 11: Comparison of (a) geometric paths and (b) time-parameterized trajectories for the optimized assignment sequence. a case study in which two drones service multiple goals and complete the mission in 136 sec while satisfying obstacle- avoidance and inter-robot separation constraints. Future work should strengthen the empirical evaluation and broaden applicability. Hardware experiments are needed to evaluate robustness to state-estimation uncertainty, communication delay, and model mismatch, and to validate computational performance under real-time constraints. Finally, extending the framework to handle heterogeneous robots, limited battery budgets, and mission-level constraints (e.g., time windows, precedence, or revisits) would further increase its relevance to practical inspection, monitoring, and search-and-rescue deployments. Declaration of competing interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. References [1] D. Rojas Viloria, E. L. Solano-Charris, A. Muรฑoz-Villamizar, J. R. Montoya-Torres, Unmanned aerial vehicles/drones in vehicle routing problems: a literature review, International Transactions in Operational Research 28 (2021) 1626โ1657. Yunes ALQUDSI, and Murat MAKARACI: Preprint submitted to ElsevierPage 11 of 14 Integrated Multi-Drone Task Allocation and Trajectory Generation in 3D Obstacle-Rich Environments (a) Sample simulation results showing the states of each robot as a function of time for the generated time-parameterized trajectories. (b) Safety validation metrics during multi-drone execution. (i) Minimum inter-robot separation versus time, demonstrating that the constraint is sat- isfied throughout the mission. (i) Minimum obstacle clearance versus time, showing that all robots maintain adequate separation from obstacles. Both metrics remain above their safety thresholds, validating the collision-free operation of the generated trajectories. Fig. 12: Simulation outputs: (a) robot states over time and (b) safety validation metrics for the executed trajectories. [2] J. del Cerro, C. Cruz Ulloa, A. Barrientos, J. de Leรณn Rivas, Unmanned aerial vehicles in agriculture: A survey, Agronomy 11 (2021) 203. [3] Y. Alqudsi, H. Sulaiman, Advancements and challenges in vtol uavs configurations and emerging trends, in: 2025 5th International Conference on Emerging Smart Technologies and Applications (eSmarTA), IEEE, 2025, p. 1โ8. [4] R. Maity, R. Mishra, P. K. Pattnaik, Flying robot path planning techniques and its trends, Materials Today: Proceedings 80 (2023) 2187โ2192. [5] Z. Du, C. Luo, G. Min, J. Wu, C. Luo, J. Pu, S. Li, A survey on autonomous and intelligent swarms of uncrewed aerial vehicles (uavs), IEEE Transactions on Intelligent Transportation Systems (2025). [6] Y. Alqudsi, Coordinated formation control for swarm flying robots, in: 2024 1st International Conference on Emerging Technologies for Dependable Internet of Things (ICETI), IEEE, 2024, p. 1โ8. [7] Y. Zhang, L. Zhang, H. Wang, F. E. Bustamante, M. Rubenstein, Swarmtalk-towards benchmark software suites for swarm robotics platforms, in: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, 2020, p. 1638โ1646. [8] R. Ghanem, I. M. Ali, K. Kasmarik, M. Garratt, A decision support framework on simulation fidelity for transferable and autonomously optimised swarm behaviour, International Journal of Production Research (2025) 1โ22. [9] S. Javed, A. Hassan, R. Ahmad, W. Ahmed, R. Ahmed, A. Saadat, M. Guizani, State-of-the-art and future research challenges in uav swarms, IEEE Internet of Things Journal (2024). [10] H. Hafezi, A. Bakhtiari, A. Khaki-Sedigh, Design and implementation of a fault-tolerant controller using control allocation techniques in the presence of actuators saturation for a vtol octorotor, Robotica 40 (2022) 3057โ3076. [11] M. R. Rezaee, N. A. W. A. Hamid, M. Hussin, Z. A. Zukarnain, Comprehensive review of drones collision avoidance schemes: Challenges and open issues, IEEE Transactions on Intelligent Transportation Systems (2024). [12] J. Saunders, S. Saeedi, W. Li, Autonomous aerial robotics for package delivery: A technical review, Journal of Field Robotics 41 (2024) 3โ49. [13] A. Almansoori, M. Alkilabi, E. Tuci, On the evolution of adaptable and scalable mechanisms for collective decision-making in a swarm of robots, Swarm Intelligence 18 (2024) 79โ99. [14] O. Shorinwa, T. Halsted, J. Yu, M. Schwager, Distributed optimization methods for multi-robot systems: Part 1โa tutorial, IEEE Robotics & Automation Magazine (2024). [15] Z. Wang, J. Li, J. Li, C. Liu, A decentralized decision-making algorithm of uav swarm with information fusion strategy, Expert Systems with Applications 237 (2024) 121444. [16] Y. Song, Z. Ma, N. Chen, S. Zhou, S. Srigrarom, Comparative analysis of centralized and distributed multi-uav task allocation algorithms: A unified evaluation framework, Drones 9 (2025) 530. [17] W. Dai, U. Rai, J. Chiun, C. Yuhong, G. Sartoretti, Heterogeneous multi-robot task allocation and scheduling via reinforcement learning, IEEE Robotics and Automation Letters (2025). [18] Y. Alqudsi, Advanced control techniques for high maneuverability trajectory tracking in autonomous aerial robots, in: 2024 1st International Conference on Emerging Technologies for Dependable Internet of Things (ICETI), IEEE, 2024, p. 1โ8. [19] Z. Yao, H. Jiang, Y. Cheng, Y. Jiang, B. Ran, Integrated schedule and trajectory optimization for connected automated vehicles in a conflict zone, IEEE Transactions on Intelligent Transportation Systems 23 (2020) 1841โ1851. Yunes ALQUDSI, and Murat MAKARACI: Preprint submitted to ElsevierPage 12 of 14 Integrated Multi-Drone Task Allocation and Trajectory Generation in 3D Obstacle-Rich Environments [20] Y. Alqudsi, An injected multi-objective metaheuristic approach for optimizing aerial-robot swarm guidance in cluttered environments, Applied Soft Computing (2025) 113379. [21] E. Osaba, J. Del Ser, A. Iglesias, X.-S. Yang, Soft computing for swarm robotics: new trends and applications, Journal of Computational Science 39 (2020) 101049. [22] Y. Meng, O. Kazeem, J. C. Muller, A hybrid aco/pso control algorithm for distributed swarm robots, in: 2007 IEEE Swarm Intelligence Symposium, IEEE, 2007, p. 273โ280. [23] Y. Alqudsi, Integrated optimization of simultaneous target assignment and path planning for aerial robot swarm, The Journal of Supercomputing 81 (2025) 1โ24. [24] B. P. Gerkey, M. J. Matariฤ, A formal analysis and taxonomy of task allocation in multi-robot systems, The International journal of robotics research 23 (2004) 939โ954. [25] S. A. Ghauri, M. Sarfraz, R. A. Qamar, M. F. Sohail, S. A. Khan, A review of multi-uav task allocation algorithms for a search and rescue scenario, Journal of Sensor and Actuator Networks 13 (2024) 47. [26] Y. Chen, R. Chen, Y. Huang, Z. Xiong, J. Li, Distributed task allocation for multiple uavs based on swarm benefit optimization, Drones 8 (2024) 766. [27] J. Song, K. Zhao, Y. Liu, Survey on mission planning of multiple unmanned aerial vehicles, Aerospace 10 (2023) 208. [28] Q. Peng, H. Wu, R. Xue, Review of dynamic task allocation methods for uav swarms oriented to ground targets, Complex System Modeling and Simulation 1 (2021) 163โ175. [29] E. Lalla-Ruiz, M. Mes, Mathematical formulations and improvements for the multi-depot open vehicle routing problem, Optimization Letters 15 (2021) 271โ286. [30] Y. Shuai, S. Yunfeng, Z. Kai, An effective method for solving multiple travelling salesman problem based on nsga-i, Systems Science & Control Engineering 7 (2019) 108โ116. [31] S. Saad, W. N. Wan Jaafar, S. J. Jamil, Solving standard traveling salesman problem and multiple traveling salesman problem by using branch-and-bound, in: AIP Conference Proceedings, American Institute of Physics, 2013, p. 1406โ1411. [32] G. Polychronis, Investigating the Dynamic Multi-Vehicle Routing Problem under Energy Constraints, Masterโs thesis, University of Thessaly, 2021. [33] Y. Alqudsi, M. Makaraci, Towards optimal guidance of autonomous swarm drones in dynamic constrained environments, Expert Systems 42 (2025) e70067. [34] R. Stern, N. Sturtevant, A. Felner, S. Koenig, H. Ma, T. Walker, J. Li, D. Atzmon, L. Cohen, T. Kumar, et al., Multi-agent pathfinding: Definitions, variants, and benchmarks, in: Proceedings of the International Symposium on Combinatorial Search, volume 10, 2019, p. 151โ158. [35] M. Turpin, Safe, scalable, and complete motion planning of large teams of interchangeable robots, 2014. Publicly Accessible Penn Dissertations. [36] M. Burger, M. Huiskamp, T. Keviczky, Complete field coverage as a multi-vehicle routing problem, IFAC Proceedings Volumes 46 (2013) 97โ102. [37] Y. Du, Multi-uav search and rescue with enhanced a* algorithm path planning in 3d environment, International Journal of Aerospace Engineering 2023 (2023) 8614117. [38] Y. Li, S. Li, Y. Zhang, W. Zhang, H. Lu, Dynamic route planning for a usv-uav multi-robot system in the rendezvous task with obstacles, Journal of Intelligent & Robotic Systems 107 (2023) 52. [39] G. E. M. Abro, Z. A. Ali, R. J. Masood, Synergistic uav motion: A comprehensive review on advancing multi-agent coordination, IECE Transactions on Sensing, Communication, and Control 1 (2024) 72โ88. [40] X. Kong, Y. Zhou, Z. Li, S. Wang, Multi-uav simultaneous target assignment and path planning based on deep reinforcement learning in dynamic multiple obstacles environments, Frontiers in Neurorobotics 17 (2024) 1302898. [41] D. Mellinger, V. Kumar, Minimum snap trajectory generation and control for quadrotors, in: 2011 IEEE international conference on robotics and automation, IEEE, 2011, p. 2520โ2525. [42] Y. Alqudsi, M. Makaraci, A. Kassem, G. El-Bayoumi, A numerically-stable trajectory generation and optimization algorithm for autonomous quadrotor uavs, Robotics and Autonomous Systems 170 (2023) 104532. [43] Y. S. Alqudsi, A. H. Kassem, G. El-Bayoumi, A general real-time optimization framework for polynomial-based trajectory planning of autonomous flying robots, Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering 237 (2023) 29โ41. [44] Y. S. Alqudsi, R. A. A. Saleh, M. Makaraci, H. M. Ertunรง, Enhancing aerial robots performance through robust hybrid control and metaheuristic optimization of controller parameters, Neural Computing and Applications 36 (2024) 413โ424. [45] K. Arshid, A. Krayani, L. Marcenaro, D. M. Gomez, C. Regazzoni, Toward autonomous uav swarm navigation: A review of trajectory design paradigms, Sensors (Basel, Switzerland) 25 (2025) 5877. [46] Z. Zhang, J. Jiang, K. V. Ling, X. Wang, W. A. Zhang, Cooperative path planning for heterogeneous uav swarms: A stackelberg game approach, IEEE Transactions on Automation Science and Engineering (2025). Early Access. [47] Y. Alqudsi, Analysis and implementation of motion planning algorithms for real-time navigation of aerial robots in dynamic environments, in: 2024 4th International Conference on Emerging Smart Technologies and Applications (eSmarTA), IEEE, 2024, p. 1โ10. [48] F. Tao, Z. Chen, Z. Wang, L. Zhu, J. Wang, Multi-strategy improved particle swarm optimization algorithm for path planning of uav in 3-d low altitude urban environment, IEEE Internet of Things Journal (2025). [49] L. Lian, X. Zong, K. He, Z. Yang, Trajectory optimization of unmanned surface vehicle based on improved minimum snap, Ocean Engineering 302 (2024) 117719. [50] Y. Alqudsi, A. Kassem, G. El-Bayoumi, A robust hybrid control for autonomous flying robots in an uncertain and disturbed environment, INCAS Bulletin 13 (2021). Yunes ALQUDSI, and Murat MAKARACI: Preprint submitted to ElsevierPage 13 of 14 Integrated Multi-Drone Task Allocation and Trajectory Generation in 3D Obstacle-Rich Environments [51] Y. Qi, H. Jiang, G. Huang, L. Yang, F. Wang, Y. Xu, Multi-uav path planning considering multiple energy consumptions via an improved bee foraging learning particle swarm optimization algorithm, Scientific Reports 15 (2025) 1โ16. [52] Y. Liu, H. Zhang, H. Zheng, Q. Li, Q. Tian, A spherical vector-based adaptive evolutionary particle swarm optimization for uav path planning under threat conditions, Scientific Reports 15 (2025) 2116. Yunes ALQUDSI, and Murat MAKARACI: Preprint submitted to ElsevierPage 14 of 14