Hierarchical Binary-Tree-Based Coordination for Multi-Uncrewed-Aerial-Vehicle Traversal Through a Gap

This paper presents a hierarchical binary tree-based framework for multiple uncrewed aerial vehicles (UAVs) to pass through a gap in a three-dimensional environment. The proposed framework uses the gap entry point and the initial UAV positions as nodes to construct a hierarchical binary tree, which provides a deterministic route for the UAVs and facilitates the identification of potential prone-to-collision nodes. A path cost function is proposed, which accounts for the crossing angles at the prone-to-collision nodes and the sum of path lengths covered by all UAVs. A genetic algorithm coupled with a greedy algorithm is utilized to obtain the hierarchical binary tree structure by minimizing the proposed path cost. Further, an occupancy zone is defined at each prone-to-collision node, and a decentralized scheduling policy assigns conflict-free time intervals to the UAVs for their entry into and exit from the occupancy zone. Numerical simulations demonstrate the effectiveness of constructing hierarchical binary trees by employing the greedy-genetic algorithm approach and validate the proposed scheduling policy in various scenarios.