Building a Communication Bridge With Mobile Hubs

Abstract

Mobile robots can be used as mobile hubs to provide communication services on-demand. This capability is especially valuable in disaster response scenarios where there is no communication infrastructure. In such scenarios, mobile hubs can provide a communication infrastructure in a dynamic fashion. In this paper, we study the problem of building a communication bridge between a source s and a destination t with mobile robots. Given a set of robots P and their initial locations, our goal is to find a subset S of robots and their final locations such that the robots in S create a communication bridge between s and t in their final locations. We introduce a new optimization problem for building communication bridges. The objective is to minimize the number of hubs (i.e., |S|), while simultaneously minimizing the robots' motion. The two mobility measures studied in this paper are: (i) maximum travel distance and (ii) total travel distance of the robots. For a geometric version of the problem where the robots must move onto the line segment [s, t], we present polynomial time algorithms which use the minimum number of hubs while remaining within a constant factor of a given motion measure.