We study a path planning problem which arises when multiple robots are used to gather data from stationary devices with wireless communication capabilities. Each device has a given communication range, and stores a fixed amount of data. The objective of the robots is to gather the data from these devices and to upload it to a base-station/gateway. We introduce a new optimization problem called the Data Gathering Problem (DGP). In DGP, the objective is to compute a tour for each robot in such a way that minimizes the time to collect data from all devices. In order to download the data from a device, a robot must visit a point within the communication range of the device. Then, it spends a fixed amount of time to download the data. Thus, the time to complete a tour depends on not only the travel time but also the time to download the data, and the number of devices visited along the tour. First, we study a special case of DGP where the robots' motion is restricted to a curve which contains the base station at one end. Next, we study the 2D version. We show that two existing algorithms for variants of the Traveling Salesperson Problem can be combined and adapted to obtain a constant factor approximation to DGP. Afterwards, we present an improvement for sparse deployments. We also present simulations which shed light on the utility of data gathering using mobile robots.
展开▼
