# Failure-Robot Path Complementation for Robot Swarm Mission Planning
## 1 Introduction
### Related Works
[PERSON] and [PERSON] [13] used a two-phased method to identify an optimal solution to solve the dynamic vehicle routing problem (DVRP). Unlike MTSP, DVRP limits the vehicle capacity Fuzzy C-mean techniques were used to divide existing customers, while a cost function was adopted to determine the initial solution in the first phase. In the second phase, TS was combined with 2-opt and or-opt to improve the cross-routes and in-routes, respectively, and to solve the problem related to multi-vehicle path programming. In their research on MTRP, [PERSON] et al. [8] mentioned that their system could determine real-time optimal paths for traveling among multiple target points on their own platform with a robot swarm; they successfully completed the assignment as well as the failure complementation; however, this trajectory was not the best solution. Because when failure occurred, a failed robot's unfinished duty could be carried out by other healthy robots only when they had finished their own original assigned paths. In addition, this solution did not consider the maximum distance limit (battery power limit). There have been numerous studies and scholarly journal articles on multi-vehicle path programming, but on-site experiments with cars to verify the effectiveness of the programming are rare. Moreover, these studies do not include a no-travel zone or vehicle failure conditions. In MTSP, the maximum and minimum numbers of cities that each salesman should visit are defined and limited, but the tasks may still fail to be completed due to the limited energy source mounted on each car. Thus, in the present study, a maximum distance limitation was added. To focus on the issues of maximum distance and vehicle failure, a mathematical model along with a distance array were set for path programming. If any path programmed covered the no-travel zone, the A* Search algorithm was adopted to find an alternative path. Then, the two-phased module served as the solution module. In the first phase, TS was combined with the 2-opt swap method to program a single optimal path, and an initial solution was obtained by splitting the path into multiple sub-paths. In the second phase, [PERSON] and [PERSON]'s solving module, which combined TS with the 2-opt swap method to improve in-route and cross-route solutions, was adopted. The modified module improved the application of TS on cross-route programming and ensured the solution would not exceed the maximum distance. A diversification strategy, which was similar to the GA, was implemented for in-route path improvements. This strategy recorded and selected the optimal solution or the second-best solution as the initial solution for in-route path improvement later so that an unwanted regional optimal solution could be avoided. The second phase was operated repeatedly until the termination conditions were reached. In the final phase, this solution was verified by experiments using real robot cars running on the programmed paths. If any vehicle in the swarm failed, its unfinished route was randomly inserted into the other route as an initial condition, and then a re-programming process began immediately. After the experiments were completed, the distance of paths generated from the path programming algorithm and the differences between the trajectories of the actual and theoretical paths were examined.