CAT-ORA: Collision-Aware Time-Optimal Formation Reshaping for Efficient Robot Coordination

Link to publication: https://doi.org/10.1109/TRO.2025.3547296
Authors' version: https://mrs.fel.cvut.cz/data/papers/c...
Code: https://github.com/ctu-mrs/catora

Full reference:
V. Kratky, R. Penicka, J. Horyna, P. Stibinger, T. Baca, M. Petrlik, P. Stepan, M. Saska, "CAT-ORA: Collision-Aware Time-Optimal Formation Reshaping for Efficient Robot Coordination in 3-D Environments," in IEEE Transactions on Robotics, vol. 41, pp. 2950-2969, 2025.

Abstract:
In this article, we introduce an algorithm designed to address the problem of time-optimal formation reshaping in three-dimensional environments while preventing collisions between agents. The utility of the proposed approach is particularly evident in mobile robotics, where agents benefit from being organized and navigated in formation for a variety of real-world applications requiring frequent alterations in formation shape for efficient navigation or task completion. Given the constrained operational time inherent to battery-powered mobile robots, the time needed to complete the formation reshaping process is crucial for their efficient operation, especially in case of multi-rotor uncrewed aerial vehicles (UAVs). The proposed collision-aware time-optimal formation reshaping algorithm (CAT-ORA) builds upon the Hungarian algorithm for the solution of the robot-to-goal assignment implementing the interagent collision avoidance through direct constraints on mutually exclusive robot-goal pairs combined with a trajectory generation approach minimizing the duration of the reshaping process. Theoretical validations confirm the optimality of CAT-ORA, with its efficacy further showcased through simulations, and a real-world outdoor experiment involving 19 UAVs. Thorough numerical analysis shows the potential of CAT-ORA to decrease the time required to perform complex formation reshaping tasks by up to 49%, and 12% on average compared to commonly used methods in randomly generated scenarios.

An MRS open-source research UAV platform was used for experiments presented in this video. See http://mrs.felk.cvut.cz/system for details and the source code of the MRS UAV platform, which enables all essential capabilities for research, development, and testing of novel methods. For publications describing the applied system and control stack, see:

T. Baca, M. Petrlik, M. Vrba, V. Spurny, R. Penicka, D. Hert and M. Saska, “The MRS UAV System: Pushing the Frontiers of Reproducible Research, Real-world Deployment, and Education with Autonomous Unmanned Aerial Vehicles,” Journal of Intelligent & Robotic Systems 102(26):1–28, May 2021, https://doi.org/10.1007/s10846-021-01....

D. Hert et al., "MRS Modular UAV Hardware Platforms for Supporting Research in Real-World Outdoor and Indoor Environments," 2022 International Conference on Unmanned Aircraft Systems (ICUAS), 2022, pp. 1264-1273, doi: 10.1109/ICUAS54217.2022.983608, https://doi.org/10.1109/ICUAS54217.20....

This work was accomplished by the MRS group at CTU in Prague http://mrs.felk.cvut.cz . For more experiments with the MRS UAV research platforms, see http://mrs.felk.cvut.cz/publications