# A Hierarchical Mission Planning Method for Simultaneous Arrival of Multi-UAV Coalition
## 1 Introduction  
Over the last decades, unmanned aerial vehicles (UAVs) have been widely used in a large range of applications, such as environmental monitoring [1], searching and attacking [2], forest fire fighting [3] and so on. Due to the capability limitation of a single UAV, multiple UAVs working together in coordination are expected to perform more complex missions under various types of attack [4]. For example, multiple UAVs can accomplish an attack mission much better than a single UAV when those UAVs arrive simultaneously to the target. Two main aspects in multi-UAV attack mission are task allocation and path planning. The complexity of these problems increases with the number of UAVs and tasks. In addition, in some specific scenarios, the imposed constraints, such as resource requirement, collision avoidance and simultaneous arrival constraints further increase the complexity of those problems. Many researchers treated the task allocation and path planning as two sub-problems separately in the in multi-UAV attack mission, they use a centralized or distributed approach to obtain a feasible task allocation strategy and then use path planning algorithms to generate feasible paths for UAVs. [PERSON] et al. [5] proposed a cooperative ad-hoc network framework for multi-UAV using a neural network, cooperative task allocation and path planning algorithms can be used in the framework in different applications. [PERSON] et al. [6] developed an iterative mission planning framework for the task allocation and path planning problems, an improved auction algorithm with an iterative strategy was proposed in the task allocation process. When multi-UAV is used to perform multi-task, the task allocation and path planning process are coupled [7], as the performance of task allocation depends on an accurate path length of UAVs, and the path planning depends on the UAV's task allocation results. To solve the coupled task allocation and path planning problems, there are two main ways. In the first class of methods, Euclidean distance between UAVs and targets is seen as the input in the task allocation process [8; 9]. After obtaining the feasible allocation results, the path planning process is used to generate flyable and safe paths/trajectories for UAVs considering a variety of constraints. However, the length of the generated paths/trajectories are quite different from the Euclidean distance, especially when there are obstacles in the environment. This deviation will result in poor quality of solutions obtained in the task allocation process. The second method considers the task allocation and path planning process as an integrated optimization problem, and encoding the solution of the coupled problem, genetic-based [10; 11] and decision tree [12] algorithms are usually used. However, simultaneously solving task allocation and path planning needs a large amount of computation. The presented task allocation studies above assume each target can be performed by single UAV and the resources of UAVs do not deplete. However, in a real situation, some targets may need a variety of resources and should be performed by multi-UAV simultaneously, such as for a simultaneous attacking mission, multiple UAVs are required to reach the target simultaneously with a different entry angle to maximize the mission performance. This problem can be called the single-task, multi-robot (ST-MR) problem according to the taxonomy criteria proposed by [PERSON] et al. [13]. The ST-MR problem is also known as the coalition formation problem [14], a coalition means a team of UAVs performing the same target. To solve the coalition formation problem for multiple UAVs performing multi-target, two distributed sub-optimal coalition formation algorithms were proposed to form coalition with minimum time and size to destroy targets simultaneously [15; 16]. In a search and destroy mission for multiple UAVs, a welfare-based coalition formation algorithm for heterogeneous UAVs was presented by [PERSON] et al.