{'fraction_non_alphanumeric': 0.03690836262568462, 'fraction_numerical': 0.008215482710700564, 'mean_word_length': 4.577159790289492, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Enhanced Decentralized Autonomous Aerial Swarm with Group Planning

Autonomous aerial swarm remains a grand challenge in robotics. Existing works in this field can be categorized as centralized and decentralized. Centralized methods suffer from scale dilemmas, while decentralized ones often lead to poor planning quality. In this paper, we propose an enhanced decentralized autonomous aerial swarm system with group planning. According to the spatial distribution of agents, the system dynamically divides the swarm into several groups and isolated agents. For conflicts within each group, we propose a novel coordination mechanism named group planning. The group planning consists of efficient multi-agent pathfinding and trajectory joint optimization, which can significantly improve the planning quality and success rate. We demonstrate simulations and real-world experiments that our method not only has applicability for a large-scale swarm, but also has top-level planning quality.


I. INTRODUCTION
Robot swarm is a grand challenge in robotics and has great advances and impacts in the next 5 to 10 years [1]. Aerial swarm, as a popular topic in the swarm community, can solve many challenges faced by human civilization, such as natural disasters, space colonization, and air traffic.
Judging by the way to deploy computation and communication resources, planning of aerial swarm can be categorized as centralized and decentralized methods. Centralized methods [2]- [5] simultaneously solve the planning problem for all agents and then allocate the plans to each one, However, the interaction among agents makes the complexity growing combinatorially. Also, it is impractical to share information across the large scale robot swarm online. The abovementioned issues prevent the application of centralized methods to large robot teams in real world. Recently, our community witnesses the emergence of decentralized methods [6]- [8], although they can be applied to larger-scale swarms by amortizing the computation and communication, the planning only uses single agent's environmental information. As a result, the planning quality and success rate deterioate as scale increases, especially in obstancle-dense environments.
Investigating the above issues, we propose an enhanced decentralized aerial swarm system with group planning. This paper tackles the conflict of effeciency and quality, balances the coordination of individuals and groups, and introduces a robust and flexible framework for aerial swarms (in Fig. 3). We consider the key challenges for building an applicable large-scale aerial swarm to be twofold. There is a need for a 1 Academy for Engineering and Technology, Fudan University, Shanghai, 200433, China. 2 State Key Laboratory of Industrial Control Technology, Institute of Cyber-Systems and Control, Zhejiang University, Hangzhou, 310027, China. 3 Huzhou Institute of Zhejiang University, Huzhou, 313000, China. powerful trajectory planning backbone, as well as a flexible grouping mechanism to solve potential conflicts originated from agents and environments. When agents cluster in a narrow space, we dynamically form several groups based on their spatial distribution, while regarding each agent as an independent individual when they disperse. As for groups, we propose a method called group planning, as a portable plugin for fully decentralized methods. It conducts trajectory planning utilizing complete information of multiple agents where hard-to-resolve inter collisions may happen. We first implement an online multi-agent pathfinding method to generate multiple collision-free paths. Based on these paths, we propose a trajectory optimization method such that all trajectories can converge to the joint optimum. Exploiting our group planning strategy, the proposed system is a significantly enhanced decentralized one over the solution in [8].
We compare our method with start-of-the-art methods. The results show that our method can generate the shortest flight time and distance of trajectory with the fewest replan times. In addition, we implement a systematic solution for decentralized autonomous aerial swarm, while perception, planning, control, and communication are integrated into a onboard system. The contributions of this paper are summarized as follows: 1) A more efficient three-dimensional online multi-agent pathfinding method, combined with the ECBS [9], for finding multiple collision-free paths that are close to the optimal trajectories.
2) An enhanced decentralized autonomous aerial swarm system with group planning where joint optimization is conducted on demand to significantly improve planning quality and success rate.
3) Open-source code of our system that is extensively validated by simulations and real-world experiments.

II. RELATED WORK
A. Multi-Agent Pathfinding The MAPF problem is to find a spatial-temporal collisionfree path for each agent in the group, given prescribed start and goal positions. Table I summarizes the properties of the  search-based methods corresponding to MAPF. If the A* search is simply performed by joining the state spaces of all the agents, the search space will grow exponentially with the number of agents, resulting in computational intractability. To solve the problem of the combinatorial explosion, Cooperative A* (CA*) [10] performs A* search in priority order, which is suboptimal and incomplete. A*+ID [11] breaks the problem down into several independent subproblems and solves each one separately. When there is a conflict between the subproblems, the corresponding subproblems are combined to solve the conflict. The solutions of all subproblems are combined as the final solution until no conflict occurs, but the scalability of algorithm is restricted. A*+OD [11] specifies that only one agent can move at a time, reducing the search dimension but increasing the depth of the search tree. M* [12] dynamically changes the search dimension based on whether or not a conflict occurs. When there is no conflict, each agent takes the best action possible on its own; otherwise, the local search dimension is increased at the conflict. Conflict-based methods address the problem on two levels. The high level converts conflicts into constraints added to agents, while the low level performs a search to see if the search is feasible. ICTS [13] algorithm searches on increasing cost tree (ICT) using the corresponding search algorithm. The CBS algorithm [14] performs searching on the constraint tree (CT). When there is a conflict, the high level creates a new node and converts the conflict into a constraint added to the agents, while the low level agents perform A* search. When all of the agents reach their respective targets with no conflict, the node is the final solution. The CBS is optimal and complete, but it is more time consuming to solve. The ECBS algorithm [9] sacrifices a small amount of solution quality in exchange for greater efficiency and scalability.
All of the methods mentioned above have limitations, and there is no universal winner. In the paper, we use MAPF to generate the initial paths and provide an initial value for the back-end optimization. We prefer algorithms with high completeness, scalability, and efficiency, even slightly sacrificing some optimality. We choose the ECBS algorithm as the front-end of group planning based on comparison.
Because the majority of current MAPF implementations are in a two-dimensional environment or in an offline threedimensional environment [4], [5], [9], we implement ECBS on an online three-dimensional gridmap and add the tie breaker function to improve the search efficiency and the quality of solution.

B. Aerial Swarm
For centralized strategies, the methods proposed by Mellinger and Augugliaro [2], [3] can generate feasible trajectories for small aerial swarms in a few seconds, but they hardly handle for large aerial swarms and have limited application scope. Honig and Park [4], [5] use B-spline or Bézier to generate safe and dynamically feasible trajectories for aerial swarms in an offline known environment. The convex hull of the B-spline or the Bézier compresses the space of solution, preventing a trajectory from being aggressive near its physical limits. Similar to ours, they also use the ECBS algorithm for a front-end search, but our implementation is more efficient and the generated paths is closer to the optimal trajectory.
For decentralized strategies, Bareiss and Zhou [15], [16] propose a lightweight solution to generate collision-free motion commands for aerial swarm. However, it cannot produce high-order continuous trajectories, making it difficult for drones to execute. In dense environments, there also exists a risk of deadlock. Tordesillas and How [6] propose a decentralized asynchronous solution that employs MINVO basis to alleviate the issue of compressed solution space. However, the work is only validated through simulation without integrated perception module. Zhou et al. [7] propose a decentralized and asynchronous systematic solution that can be used in real-world scenarios. Because of the use of B-spline, optimizing the time term is difficult, which results in a twist trajectory when multiple drones meet. To solve the problem of the trajectory twist, Zhou et al. [8] propose  However, the planning quality and success rate decrease dramatically when multiple drones meet, especially in dense environments. The proposed method solves the problem.

III. ENHANCED AERIAL SWARM FRAMEWORK
The proposed framework is illustrated in Fig. 3. According to the Group Check module, the system can flexibly switch the planning mode between group planning and singleagent planning. The group planning consists of front-end efficient multi-agent pathfinding (Section IV) and back-end group trajectory joint optimization (Section V). The efficient multi-agent pathfinding performs a two-level search based on obstacles and conflicts among agents to generate multiple collision-free paths that are closer to the optimal trajectories. Based on these paths, the group trajectory joint optimization generates multiple optimal trajectories in a coarse-to-fine process. It first prunes the paths and creates the intial trajectories as the initial value of the optimization problem. Then, these trajectories are jointly dynamically optimized by coordinating trajectories. Finally, multiple safe, dynamically feasible and minimum control trajectories [17] are generated.

IV. EFFICIENT MULTI-AGENT PATHFINDING
In this section, our purpose is to find a collision-free path that is closer to the optimal trajectory for each agent in a group. For the first time, we implement a more efficient online multi-agent pathfinding (EMAPF) method on a threedimensional (3D) gridmap based on ECBS [9].
Same as ECBS, our method performs high-level and lowlevel searches in Algorithm 1. The two level searches use focal search (f 1 , f 2 ) [9], where f 1 and f 2 have different meanings at different levels. The focal search contains two lists of OPEN and FOCAL, which can limit the maximum cost of the solution to ω * C * (ω is the suboptimal factor and C * is the minimum cost of the node in OPEN). f 1 determines which nodes in OPEN are in FOCAL (FOCAL is subset of OPEN that includes all nodes n in OPEN where f 1 (n) <= ω * f 1min , f 1min is the minimal value of f 1 .), and f 2 determines which node in FOCAL should be expanded.
In high level, the search is performed on a Conflict Tree (CT) consisting of multiple nodes. The solution of a node contains the paths of all the agents{a 1 , ..., a i , ..., a k } in the group. If a conflict exists among the paths in the extended node, it is converted into a low-level constraint and a new node is formed. The search terminates until we get a collision-free node that contains the collision-free paths of all the agents in the group. In low level, the agent performs constraint-based pathfinding, and the node represents the position of the agent. The specific implementation of the two-level search in our method is detailed as follows.

A. High-level Search
High-level search applies focal search (f 1 , f 2 ) on a CT, the goal is to find a conflict-free node. In high level, f 1 is the cost of the CT node, and f 2 is an inadmissible heuristic function that represents the number of CT node conflicts. The lower bound (LB) and FOCAL of CT are as follows: where LB(n) and n.cost come from the return value of low level search.

B. Low-level Search
Low-level search applies focal search (f 1 , f 2 ) to find a path for each agent a i . In low level, we set where g is the current best estimate of the accumulated cost from the start node to the current node, h is the estimated lowest cost from the current node to the goal node. Function t is the distance from the current traversed node to the connection between the start node and the goal node, which is called the tie breaker function. f 2 is an inadmissible  heuristic function that represents the number of conflicts in the current path. The purposes of designing the tie breaker function t are: (1) to reduce the traversal space; In Fig. 4, if f 1 is set to f = g + h as in the A * [18] algorithm, there will be multiple nodes with the same f value when searching the path, which would result in a larger traversal space; (2) to make the searched path closer to the optimal trajectory. The entire search is performed on a real-time updated 3D gridmap, and it only takes O(1) time complexity to determine whether the node in the traversed space is occupied. A lower bound on the cost of path for agent a i is f min (i) in low level search. Therefore, we can construct the lower boundary LB(n) and the cost of the current CT node n in high level as follows: where k is the number of agents in the group. Then the searching will return to high level with newly updated LB(n) and n.cost of the CT node n.
In summary, our method reduces traversal space during the search process while efficiently checking the information about obstacles. The obtained paths are close to the optimal trajectories (see Fig. 6), providing a good initial value for trajectory optimization. The quantitative comparison is shown in the TABLE II.

V. GROUP TRAJECTORY JOINT OPTIMIZATION
In this section, our purpose is to make the trajectories of all agents in group converge on a common optimum. Therefore, we jointly optimize all trajectories. However, it is challenging to achieve reciprocal avoidance among dynamically changing trajectories. We address the problem in Section V-B.3.c. The trajectory representation and the joint trajectory optimization problems are detailed as follow.

A. MINCO Trajectory Class
In this paper, we adopt T MINCO [17] for trajectory representation, which is a minimum control effort polynomial trajectory class defined as where c = (c T 1 , . . . , c T M ) T ∈ R 2M s×m the polynomial coefficient, c i ∈ R 2M s×m is the cofficient matrix of the i-th piece.β(t) = [1, t, · · · , t N ] T is the natural basis.
All trajectories in T MINCO are compactly parameterized by only q and T . Evaluating an entire trajectory from q and T can be done via the linear-complexity formulation: The task-specific second-order continuous penalty functions F (c, T) with available gradients are applicable to T MINCO trajectories. The corresponding objective of T MINCO is computed as: The mapping Eq.6 gives a linear-complexity way to compute ∂J/∂q and ∂J/∂T from the corresponding ∂F/∂c and ∂F/∂T. Sequentially, a high-level optimizer is able to optimize the objective efficiently.

B. Joint Optimization Problem Formulation
The basic requirements on trajectories in the group include safety, smoothness, dynamical feasibility. Meanwhile, it is preferable to minimize control effort cost and execution time of all trajectories.
We adopt the compact parameterization of T MINCO , temporal constraint elimination, and constraint penalty to transform trajectories generation problem into an unconstrained nonlinear optimization problem: where K is the number of agents in the group, λ is the weight vector. 1) Control Effort J e : The control effort cost of the k-th agent trajectory and the gradients for its i-th piece are: 2) Temporal Constraint Elimination: An open-domain constraint is T 0, which is directly eliminated by variable transformations as is done in [17]: where τ i is the unconstrained virtual time. Execution Time Cost J t : The execution time cost J t = M i=1 T i and its gradient ∂J t /∂c i = 0, ∂J/∂τ i = (∂J/∂T i )e τi .
3) Penalty for Continuous-Time Constraints: Continoustime constraints G(p(t), . . . , p (s) (t)) 0, ∀t ∈ [0, T ] contain infinite inequality constraints that cannot be directly solved using constrained optimization. We transform G into finite inequality constraints using integral of constraint violations [19]. The penalty with gradient for k-th agent trajectory can be derived: where κ i is the sample number on the i-th piece,ω j the quadrature coefficients from the trapezoidal rule [20], χ ∈ R ng ≥0 is a vector of penalty weights. We define the points determined by {c i , T i , j/κ i } as constraint pointsp i,j = p i ((j/κ i )T i ) with the i-th piece p i (t).
a) Dynamical Feasibility Penalty J d : According to the limit of agent maximum velocity v m , acceleration a m , jerk j m , constraints of dynamic are denoted as where x = {v, a, j}, n = {1, 2, 3}, and t = jT i /κ i . By substituting Eq. 14 15 into Eq. 13 we get the penalty J d and the gradient about c i and T i . b) Obstacle Avoidance Penalty J o : We adopt collision evalution from Zhou et al [21], which defines the distance from agent to obstacle as d(p(t)). To enforce the safety requirement, we formulate a collision penalty, which is triggered when the distance to obstacles less than a safe clearance C o . The obstacle avoidance constraint and its gradient are as follows where C o ≥ d(p(t)), 0) and t = jT i /κ i . c) Group Reciprocal Avoidance Penalty J w : We jointly optimize all trajectories, which means that the trajectories of other agents change dynamically during the iterative optimization of one agent's trajectory. If we consider only the gradients about c and T for current agent's trajectory, the optimization problem would fail to converge. Therefore, in each iteration, we consider the influence of the current agent on all trajectory gradients.
In Fig. 5, we demonstrate the reciprocal avoidance process of the u-th agent's trajectory p u (t) and one of the other trajectories in the group (k-th agent's trajectory p k (t)) at the time stamp τ . τ is denoted as: τ = T u1 + · · · + jT ui /κ i = T k1 + · · · + T k(n−1) + t , (18) where t = jT i /κ i is the relative time of u-th agent. t is the relative time of k-th agent. τ locates in the i-th piece of u-th agent and the n-th piece of k-th agent. We define the constraint at the j-th constraint point on the i-th piece of p u (t) as where the matrix E is the downwash model of agent.
The gradient to T ul for any 1 ≤ l ≤ i should be computed as The gradient to T km for any 1 ≤ m ≤ n − 1 should be computed as d) Uniform Distribution Penalty J u : Since the collision avoidance is constrained by finite constraint points, nonuniform distribution increases the possibility of skipping some thin obstacles. Therefore, we penalize the variance of the squared distances between pairs of adjacent constraint points. For more details, please refer to [8].

VI. EVALUATION
In this section, we conduct detailed evaluation tests on the proposed contributions. All programs run on an Intel Core i7-10700KF CPU at 5.1GHz.

A. Efficient Multi-Agent Pathfinding
In Fig. 6, we show that four agents search paths using RBP [5] and the proposed method with the same conditions. The initial path searched by the proposed method is closer to the optimal trajectory, which provides a good initial value for the nonlinear optimization problem. The flight time and distance of the proposed method are shorter. The numerical comparison is shown in the TABLE II.
In Fig. 7, to demonstrate the performance of our method, we test the search time from three aspects: the number of agents, the density of obstacles, and the size of the search space. All data is the average of 10 runs. We consider the search time of more than 0.1s as the unacceptable case for real-time scenarios. As a result, we usually limit the number of agents in the group up to 8, and the maximum search space up to 1276m 3 . The average search time is 0.0381s, which is adequate for the online environment.

B. Comparisons
In TABLE II, we compare the proposed method with RBP [5], Mader [6], EGO (EGO-Swarm) [7], DSTO [8]. All data is the average of 8 agents in 10 experiment runs. Maximum velocity and acceleration are set to 1.7m/s and 6.2m/s 2 . The bold data represents the best value in the corresponding category. We can see from the comparison that RBP has sub-optimal more conservative trajectories with better smoothness and the longest flight time and distance. Compared with the offline method, the online methods have a replan mechanism and require less solution time. EGO and Mader appear to be more conservative because the trajectories are constrained by the convex hull, and the trajectories are aggressive. EGO, DSTO, and especially Mader need high-frequency replan when the drones meet each other.
In Fig. 2, we create an extremely challenging environment, consisting of a wall with a narrow gate. Each side of the wall has three drones, and their goal points are diagonal positions  on the other side. We can see evidently that only all drones in the proposed method pass through this narrow gate. From the comparison, the proposed method shows toplevel performance with the shortest flight time and distance, as well as the fewest replan times. This is attributed to the group planning with the coordination ability. In a 50 × 50m map, we simulate future air traffic scenarios. The initial positions of 50 drones are generated at random, and each drone must pass through three randomly generated goal positions. The Fig. 8 depicts a screenshot of the mission at a certain moment. When multiple drones meet the grouping conditions, group planning is triggered. Group planning is triggered 35 times during the whole mission. The robustness and flexibility of the proposed method in largescale aerial swarms are verified.

Local Target
Obstacle Fig. 9: The impact of shared maps on trajectory; The red curve indicates the trajectory with shared maps. The green curve indicates the trajectory without shared maps.
In group planning, we compress the local map of each drone and share it within the group. Therefore, we can see in Fig. 9 that the proposed method can produce safer trajectory.

VII. REAL-WORLD EXPERIMENTS A. Indoor
In the indoor experiments, we place eight drones on two concentric circles with diameters of 10m and 4m respectively (four drones on each circle). We set the speed limit  Fig. 1, we set up two environmental experiments: (1) sparse environment (left); (2) dense environment (right); In the mission, the entire system completes the mode switch in a manner of "Single-agent Planning to Group Planning to Single-agent Planning".

B. Outdoor
In the outdoor experiment, the four drones cross and exchange positions every 8m in the longitudinal direction in a dense environment. The entire mission has 5 crossflights, and each cross-flight performs the mode switch in a manner of "Single-agent Planning to Group Planning to Single-agent Planning". In Fig. 10, the process of one crossflight is shown. When four drones are dispersed, each drone performs single-agent planning. When four drones assemble, group planning is triggered. Please watch the video for more information.

VIII. CONCLUSIONS AND FUTURE WORK
In this work, we propose an enhanced decentralized autonomous aerial swarm system with group planning. The system tackles the conflict of planning efficiency and trajectory quality, balances the coordination of individual and group. Extensive evaluations demonstrate top-level planning quality and the ability to deploy in a large-scale aerial swarm. Realworld experiments demonstrate the robustness and flexibility of the system. In the future, we will further improve the efficiency and scalability of the multi-agent path finding method, while considering the kino-dynamic constraints. We will also explore applications in the field of transportation.