Energy-Efficient Strategies for Building Short Chains of Mobile Robots Locally

摘要

We are given a winding chain of n mobile robots between two stations in the plane, each of them having a limited viewing range. It is only guaranteed that each robot can see its two neighbors in the chain. The goal is to let the robots converge to the line between the stations. We use a discrete and synchronous time model, but we restrict the movement of each mobile robot to a distance of 8 in each round. This restriction fills the gap between the previously used discrete time model with an unbounded step length and the continuous time model which was introduced in [1J. We adapt the strategy by Dynia et al. [2]: In each round, each robot first observes the positions of its neighbors and then moves towards the midpoint between them until it reaches the point or has moved a distance of δ. The main energy consumers in this scenario are the number observations of positions of neighbors, which equals the number of rounds, and the distance to be traveled by the robots. We analyze the strategy with respect to both quality measures and provide asymptotically tight bounds. We show that the best choice for δ for this strategy is δ ∈ Θ(1). since this minimizes (up to constant factors) both energy consumers, the number of rounds as well as the maximum traveled distance, at the same time.