This paper proposes a graph-based formation sequence generation algorithm for efficient formation navigation for multiple flying robots in confined and complex 3D environments. The proposed method accounts for formation rotation and scale variation, enabling stable and continuous formation transitions within narrow spaces. Based on the given map information and a 3D global path, candidate formation patterns that can be assigned to each waypoint along the path are generated and represented as nodes in a formation graph. To reduce the size of the graph and the complexity of the subsequent search, formation candidates that do not satisfy inter-robot spacing constraints or minimum obstacle clearance requirements are pre-filtered. Furthermore, transition costs are defined between adjacent nodes to maintain continuity in formation transitions while ensuring smooth progression along the global path. Simulation experiments compare the proposed 3D method with a conventional 2D formation planning approach under identical environments. The results demonstrate that the proposed method reduces graph construction time and search time, decreases the number of generated nodes, and increases the average clearance from obstacles. These findings confirm that formation stability and spatial efficiency are improved, particularly in narrow corridors and complex obstacle regions. The proposed algorithm provides an effective path planning framework that maintains shape continuity and collision safety for formations of multiple flying robots in complex 3D environments. It also exhibits scalability for real-time formation control of multiple flying robots.
You et al. (2026) studied this question.