Energy-efficient strategies for building short chains of mobile robots locally

• Published in: Theoretical computer science 2013-10, Vol.509, p.97-112
• Main Authors: Brandes, Philipp, Degener, Bastian, Kempkes, Barbara, Meyer auf der Heide, Friedhelm
• Format: Article
• Language: English
• Subjects: Construction; Consumers; Convergence speed; Distributed algorithms; Dynamics; Energy consumption; Geometric networks; Local algorithms; Mathematical models; Mobile robots; Planes; Robot formation problems; Robots; Stations; Strategy
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2012.10.056

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. The robots are modeled as points in the plane which cannot collide. We use a discrete and synchronous time model, but we restrict the movement of each mobile robot to a distance of δ 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 [Bastian Degener, Barbara Kempkes, Peter Kling, Friedhelm Meyer auf der Heide, A continuous, local strategy for constructing a short chain of mobile robots, in: SIROCCO’10: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity, 2010, pp. 168–182]. We adapt the Go-To-The-Middle strategy by Dynia, Kutylowski, Lorek and Meyer auf der Heide (BICC 2006): 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 of 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 δ∈Θ(1n), 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.