Online Path Repair: Adapting to Robot Failures in Multi-Robot Aerial Surveys

Multiple Unpiloted Aerial Vehicles (UAVs) working together have the potential to efficiently survey large geographical areas. Unfortunately, UAVs in the field may fail midway through a survey due to adverse weather, faster-than-expected battery drain, or mechanical malfunction, leaving part of the survey area uncovered. Here we propose an algorithm to re-plan coverage routes online for multiple UAVs to take over the remaining route of a failed team member. We first present a greedy path recovery algorithm whereby each UAV greedily absorbs the closest remaining vertices from the failed UAV's route into its own route. This method is then extended using a Tabu search method for multi-agent path repair to give successively better quality paths. We call the new path repair algorithm GRIT (Greedy Repair Initializes Tabu search), and demonstrate it performing path repair for nominal paths planned with both a traditional lawnmower-style planner and a more sophisticated integer program based planner. We show that GRIT achieves adequate re-plans 10-50 times faster than two benchmark planners, making it ideal for online path repair in mid-flight, although the benchmarks eventually outperform GRIT if given unlimited computation time.