  This paper presents a new online multi-agent trajectory planning algorithm
that guarantees to generate safe, dynamically feasible trajectories in a
cluttered environment. The proposed algorithm utilizes a linear safe corridor
(LSC) to formulate the distributed trajectory optimization problem with only
feasible constraints, so it does not resort to slack variables or soft
constraints to avoid optimization failure. We adopt a priority-based goal
planning method to prevent the deadlock without an additional procedure to
decide which robot to yield. The proposed algorithm can compute the
trajectories for 60 agents on average 15.5 ms per agent with an Intel i7 laptop
and shows a similar flight distance and distance compared to the baselines
based on soft constraints. We verified that the proposed method can reach the
goal without deadlock in both the random forest and the indoor space, and we
validated the safety and operability of the proposed algorithm through a real
flight test with ten quadrotors in a maze-like environment.
