Integrated Multi-Drone Task Allocation, Sequencing, and Optimal Trajectory Generation in Obstacle-Rich 3D Environments

Yunes Alqudsi; Murat Makaraci

cs.ROMar 26, 2026

Integrated Multi-Drone Task Allocation, Sequencing, and Optimal Trajectory Generation in Obstacle-Rich 3D Environments

Authors: Yunes Alqudsi, Murat Makaraci

Organizations: Aerospace Engineering Department, Faculty of Aeronautics and Astronautics, Kocaeli University, Kocaeli, Turkiye · Interdisciplinary Research Center for Aviation and Space Exploration, KFUPM, Dhahran, Saudi Arabia · Mechanical Engineering Department, Faculty of Aeronautics and Astronautics, Kocaeli University, Kocaeli, Turkiye

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.

Figures & tables

Fig. 1 : The IMD–TAPP system schematic. The framework takes as inputs the 3D environment with obstacles, robot start states $v_{R}^{i}$ , and goal set $G$ . The core processing stages include: (i) graph discretization and search to compute cost matrices $\mathbf{C}_{RG}$ and $\mathbf{C}_{GG}$ , (ii) IPSO with MLA guidance to optimize assignment and visit sequences, and (iii) minimum-snap trajectory generation to produce time-parameterized trajectories. The final stage validates obstacle clearance and inter-robot separation ( $\geq 2R_{r}\phi$ ) through simulation rollout, outputting collision-free multi-drone trajectories.

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.

Symbol	Meaning
$R_{N}$	number of robots (drones)
$G_{N}$	number of goals
$Sq_{i}$	ordered goal sequence assigned to robot $i$
$C(\cdot)$	travel cost computed from geometric paths
$J^{\ast}$	optimal mission objective (makespan)
$\eta_{i}(t)$	position of robot $i$ over time

Table 1: Key notation used in the IMD–TAPP formulation.

Fig. 3 : High-level overview of the IMD–TAPP pipeline: (i) 3D workspace discretization and graph-search computation of obstacle-aware travel costs,(ii) discrete optimization of goal assignment and visit sequencing using an injected (PSO) algorithm guided by multiple linear assignment, and (iii) smooth trajectory generation followed by safety validation with iterative replanning when necessary.

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 $v_{R}^{i}$ , goals $g_{p}$ and $g_{q}$ . (b) Graph-search distances populate the robots-to-goals matrix $\mathbf{C}_{RG}$ (with entries $C(v_{R}^{i},g_{j})$ ) and the goals-to-goals matrix $\mathbf{C}_{GG}$ (with entries $C(g_{p},g_{q})$ ), which are then used by the discrete optimizer to determine assignments and visit sequences.

Panel of Figure 6 — 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.

Panel of Figure 7 — 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 $v_{R}^{i}$ , 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 $\int\|\frac{d^{4}\mathbf{x}}{dt^{4}}\|^{2}dt$ subject to continuity constraints (position, velocity, and acceleration continuous at junctions), producing smooth position, velocity, and acceleration profiles suitable for quadrotor execution.

Panel of Figure 9 — 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., $\|\eta_{i}(t)-\eta_{j}(t)\|\geq 2R_{r}\phi$ ). If conflicts occur, local re-planning updates the plan and the trajectories are regenerated until feasibility is achieved.

Fig. 9 : 3D obstacle-filled environment used in the simulation study, illustrating the initial positions of the robots and the set of goal locations.

Item	Setting
Software	MATLAB R2023b
CPU	Intel Core i7-1065G7 @ 1.30 GHz
GPU	NVIDIA GeForce GTX 1650 (4 GB)
RAM	16 GB
Robot model parameters	As in [ 3 ]
Environment	3D workspace with obstacles (Figure 9 )

Table 2: Simulation and implementation settings used in the case study.

Panel of Figure 12 — 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.

Panel of Figure 13 — Fig. 11 : Comparison of (a) geometric paths and (b) time-parameterized trajectories for the optimized assignment sequence.

Panel of Figure 14 — Fig. 12 : Simulation outputs: (a) robot states over time and (b) safety validation metrics for the executed trajectories.

Explore similar work

Sep 20, 2026

FlockDiffusion: Assignment-Conditioned Diffusion for Multi-Drone Task Allocation and Completion

Autonomous multi-drone navigation requires fleets to service distributed objectives in cluttered environments under tight computational budgets. Efficient coordination depends on task bundling, where each drone visits multiple objectives along its route. Separate solvers for cost estimation, assignment, and execution incur redundant graph search and produce long, abrupt paths. We propose FlockDiffusion, a learned framework combining a scene graph encoder, an explicit allocation head, an assignment conditioned diffusion transformer, and a closed form trajectory decoder. An autoregressive teacher provides offline supervision for parallel fleet trajectory generation. PyBullet ablations show that bundling increases task completion from 50% to 100%, while our complete teacher further reduces route cost by 8.4% relative to MAGNNET with bundling. In the optimized scalability benchmark, evaluated on 100 scenes per density with ten drones, FlockDiffusion achieves 6.2 to 7.6 times faster inference and approximately 37% shorter routes than the classical pipeline. As nominal task counts increase from 20 to 40, latency rises from 7.8 to 11.1 ms, compared with 48.0 to 75.8 ms for the baseline. In a separate evaluation across five Gazebo environments, FlockDiffusion achieves 100% planner coverage and reduces planned route cost by 15.4% relative to the baseline with bundling. These results demonstrate efficient planning under increasing task density in configurations that are demanding to reproduce with physical drone fleets.

Iana Zhura, Satenik Akopyan, Roohan Ahmed Khan +3

Skolkovo Institute of Science and Technology, Moscow, Russia

Multi-Robot Motion Planning Aerial Robotics Trajectory Generation Diffusion-Based Planning Multi-Robot Task Allocation

Ask PDF

Sep 1, 2026

TriSAR: Task Coordination and Collision Avoidance for Aerial Robot Teams in Disaster Response

Multi-Unmanned Aerial Vehicle (UAV) disaster-response systems require coordinated task assignment and local trajectory control, yet the individual and combined contributions of these coordination layers to mission efficiency and operational safety remain insufficiently characterised under controlled experimental conditions. TriSAR is evaluated as a five-UAV coordination system operating in a physics-based Gazebo simulation of an earthquake-damaged urban environment. A 2 x 2 factorial design compares two task-allocation strategies (Genetic Algorithm and greedy fitness-based allocation) with reactive collision avoidance enabled or disabled. Each of the four configurations was evaluated over 30 stochastic episodes in a common scenario of five UAVs and eight targets. Under greedy allocation, enabling repulsion eliminated recorded collision-threshold violations, confirmed by a Mann-Whitney test (U = 885, p = 4.03 x 10^-12, rank-biserial r = 0.97). Under GA allocation, the same protective effect was confirmed (U = 675, p = 1.26 x 10^-5, rank-biserial r = 0.50). For mission-efficiency metrics, GA-based allocation showed no statistically detectable advantage over greedy allocation when repulsion was enabled, but a significant advantage in steps, path length, and energy when repulsion was disabled (Welch's t-tests, |g| between 0.92 and 1.76). These results show that reactive repulsion provides a substantial, allocation-dependent safety benefit, while the additional computational complexity of GA-based task allocation yields a detectable mission-efficiency benefit only when repulsion is disabled.

Aditya Anil Kapile, Pedro Machado, Isibor Kennedy Ihianle

School of Science and Technology, Nottingham Trent University, Nottingham, United Kingdom

Aerial Robotics Multi-Robot Coordination Multi-Robot Task Allocation Search-and-Rescue Robotics Robot Collision Avoidance

Ask PDF

Apr 13, 2026

Dynamic Multi-Robot Task Allocation under Uncertainty and Communication Constraints: A Game-Theoretic Approach

We study dynamic multi-robot task allocation under uncertain task completion, time-window constraints, and incomplete information. Tasks arrive online over a finite horizon and must be completed within specified deadlines, while agents operate from distributed hubs with limited sensing and communication. We model incomplete information through hub-based sensing regions that determine task visibility and a communication graph that governs inter-hub information exchange. Using this framework, we propose Iterative Best Response (IBR), a decentralized policy in which each agent selects the task that maximizes its marginal contribution to the locally observed welfare. We compare IBR against three baselines: Earliest Due Date first (EDD), Hungarian algorithm, and Stochastic Conflict-Based Allocation (SCoBA), on a city-scale package-delivery domain with up to 100 drones and varying task arrival scenarios. Under full and sparse communication, IBR achieves competitive task-completion performance with lower computation time.

Maria G. Mendoza, Pan-Yang Su, Bryce L. Ferguson +1

Department of Mechanical Engineering, University of California, Berkeley, Berkeley, CA, United States · Department of Electrical Engineering and Computer Science, University of California, Berkeley, Berkeley, CA, United States · Thayer School of Engineering, Dartmouth College, Hanover, NH, United States

Multi-Robot Task Allocation Multi-Agent Systems Multi-Robot Coordination

Ask PDF