Collision-aware adaptive horizon model predictive control for multi-agent path planning

Recent research in unmanned system autonomy has focused on multi-robot systems, such as vehicles or unmanned aerial vehicles (UAVs), performing missions autonomously without mutual collisions in dynamic environments. In multi-agent operational settings, conventional centralized path planning methods face limitations in system scalability, as computational complexity increases sharply with the number of agents. Therefore, this research proposes a collision-aware adaptive horizon model predictive control (MPC) algorithm based on distributed model predictive control, which is advantageous for scalability. For computational efficiency, the proposed algorithm dynamically adjusts the length of the prediction horizon based on whether a collision is predicted on the planned path, and integrates a control barrier function (CBF) as a constraint to ensure safety even when the prediction horizon is shortened. The entire optimization problem is formulated as a computationally efficient quadratic programming; however, the linearized constraints used in this formulation can lead to deadlock. To address this issue, this work applies a detour strategy to increase the success rate of path planning. The performance of the proposed algorithm was validated in a three-dimensional simulation of a path-crossing scenario with a multi-agent system of UAVs. Specifically, an ablation study analyzing the computational efficiency of the adaptive horizon and the safety enhancement from the CBF demonstrated that the proposed method enables agents to reach their target destinations efficiently and safely, reducing the average computation time by 35% and increasing the mission success rate by 13%.