Anytime Fault-tolerant Adaptive Routing for Multi-Robot Teams

Abstract

The Correlated Team Orienteering Problem (CTOP) is a routing problem where the objective is to determine a set of routes that maximizes the summation of collected rewards in the environment while respecting the vehicles’ budget. However, solutions to this problem usually consider static instances and may produce poor results in dynamic real-world scenarios. In this paper, we propose an approach to deal with the execution of missions planned as a CTOP instance, especially when vehicles of the team are prone to failure and may not complete their routes. The main contribution of this paper is a novel anytime heuristic that iteratively adapts the initial set of routes, allowing to increase the overall robustness of the mission and still collect the most profitable rewards. The methodology was thoroughly evaluated considering different scenarios and in all the cases was able to achieve comparable or better results in terms of reward than planning a new set of routes, however, spending considerably less time.