Hierarchical Reactive Task Allocation with Dynamic Conflict Resolution Framework for Collaborative Aerial 3D Printing

Abstract This paper presents a novel reactive coordination and planning framework for collaborative aerial 3D printing with Unmanned Aerial Vehicles (UAVs) while ensuring their safe and efficient simultaneous operation. The proposed framework incorporates a hierarchical dynamic scheduling embedded with a conflict resolution mechanism, enabling it to account for online adaptability to operational uncertainties and unforeseen events during execution. The novelty of the approach lies in its two-tiered hierarchical structure that tightly integrates dynamic assignment with an online conflict resolution mechanism, providing a flexible, adaptive and conflict-free solution for aerial construction tasks. This hierarchical framework introduces the first layer, which is responsible for dynamically assigning the tasks to the available fleet of UAVs. The task assignment considers precedence constraints to ensure structural integrity during construction while also prioritizing safe operation by minimizing the probability of conflicts and highly dependent tasks. In the second layer, conflicts arising from assigned paths are dynamically decomposed into smaller independent sub-graphs and resolved locally to reduce the computational complexities. Towards this, an online locally optimal spatiotemporal conflict resolution scheme is introduced for multi-agent systems to address the local conflicts efficiently. This mechanism dynamically adjusts the UAVs’ speeds with minimal deviation from an optimal reference to mitigate conflicts and ensure printing performance. Additionally, building on this local conflict resolution strategy, the framework enforces reactiveness by iteratively relaxing the problem when conflicts cannot be resolved immediately. This is executed via dynamic reduction and rearrangement of the concurrent tasks’ space to resolve the conflict between them. Moreover, insights gained from failed resolution attempts are dynamically integrated into the global dependency graph, preventing redundant computations in subsequent steps and enhancing overall efficiency and versatility. The framework is distinguished by its use of reactive task-space reconfiguration, informed by infeasible conflict resolutions, and the assignment of guaranteed conflict-free paths, unlike existing sequential or non-guaranteed approaches. The efficacy of the proposed framework is demonstrated through two case studies, constructing both a rectangular and a dome mesh with a collaborative team of UAVs, in a high-fidelity ROS-Gazebo simulation. A video of the mission can be found here https://youtu.be/Ow_qDPWmgDw .