Optimal Redeployment of Multirobot Teams for Communication Maintenance

In this paper, we consider the problem of maintaining and restoring connectivity among a set of agents (humans or robots) by incrementally redeploying a team of mobile robots acting as communication relays. This problem is relevant in numerous scenarios where humans and robots are jointly deployed for tasks like urban search and rescue, surveillance, and the like. In this case, as the humans move in the environment, connectivity may be broken, and consequently, robots need to reposition themselves to restore it. We study the computational complexity of the problem, also in terms of approximation hardness, and present an Integer Linear Programming formulation to compute optimal solutions. We then analyze the performance of the proposed resolution approach against a heuristic algorithm taken from the literature, and we demonstrate how our method favorably compares in terms of solution quality and scalability.