# Failure-Robot Path Complementation for Robot Swarm Mission Planning
## 1 Introduction
### Related Works  
Many scholars have conducted studies on path programming, and the path from the start point to the end point is often an essential element. In addition, if there is an obstacle or a no-travel zone on the path, the path programming should consider how to avoid it. In reference [3], [PERSON] et al. applied image processing to detect the obstacle and the turning point, and the [PERSON] algorithm was used to identify the shortest path while bypassing the obstacle. Unfortunately, apart from computer simulations, there is no field experiment to validate this research. The A* Search algorithm [4], developed in 1968 based on a best-first search and [PERSON]'s algorithm, has proven to have a better performance than [PERSON] alone by combining the advantages of the two algorithms. It has been widely applied to determine the optimal path for online game characters and some industrial carriers from current locations to specified destinations [5; 6]. In terms of path programming and scheduling for multiple target points and multiple vehicles, for years, many studies have focused on solving the vehicle routing problem (VRP) and the multiple traveling salesman problem (MTSP). As Figure 1 shows, MTSP involves \(m\) salesmen who must visit a set of \(n\) cities; each salesman starts and ends at the same place (city), and each city must be visited exactly once by one salesman. The objective of the problem is to find the shortest total distances travelled by all the salesmen. In practice, each salesman has similar abilities and limitations; therefore, using MTSP with an ability constraint is more appropriate for studying real-world problems. For example, it is unrealistic that one salesman would travel to all the cities, while others would visit only one city. As such, the number of cities to which each salesman travels is limited [7]. The multiple traveling robot problem (MTRP) further extends the traditional traveling salesman problem (TSP) and involves a team of robots visiting target points at least once (and ideally more than once). The overall solution quality is dependent on both the quality of the solution constructed by the paths of the robots and the efficient allocation of the targets to the robots [8]. Figure 1: Schematic diagram of the multiple traveling salesman problem (MTSP). In this NP-hard problem, the complexity of the solution increases as the number of target points increases. Because it is almost impossible to go through all the feasible paths and to determine the best solution within an acceptable timeframe, heuristic algorithms have been adopted to obtain approximate solutions. [PERSON] et al. [9] used a new modified ant colony optimization (NMACO) mixed with insert, swap, and 2-Opt algorithms as well as an efficient candidate list to improve the efficiency of ant colony optimization (ACO). [PERSON]'s algorithm is quite competitive with other meta-heuristic algorithms, which have solved a library of sample instances for the traveling salesman problem (TSPLIB); however, the solution it yielded can still be improved. [PERSON] et al. [10] used five modified ACOs to solve MTSP. The maximum number \(L\) and minimum number of cities that each salesman should visit \(K\) were defined and limited to solve MTSP instances using the TSPLIB. Furthermore, [PERSON] et al. [11] used a hybrid genetic algorithm (GA) and simulated annealing (SA) to solve MTSP, enhancing the local search ability to achieve a better global optimal solution than could be obtained using a general GA; however, the solution was proven not to be the best in later research. Using ACO and GA to solve MTSP problems may not always yield consistent solutions even under exactly the same initial test setting, and each case must be tested continuously to converge the best solution. [PERSON] et al. [12] used the Tabu search (TS) to solve the VRP and to test it with benchmark instances. The test results not only achieved convergence in a reasonable time but were also superior in distance for the benchmark instances.