Continuous local strategies for robotic formation problems

We consider a scenario with a team of autonomous mobile robots which are placed in the plane. Their goal is to move in such a way that they eventually reach a prescribed formation. Such a formation may be a straight line between two given endpoints (Robot Chain Problem), a circle or any other geometric pattern, or just one point (Gathering Problem). In this survey, we assume that there is no central control that guides the robot's decisions, thus the robots have to self-organize in order to accomplish global tasks like the above-mentioned formation problems. Moreover, we restrict them to simple local strategies: the robots are limited to "see" only robots within a bounded viewing range; their decisions where to move next are solely based on the relative positions of robots within this range. Most strategies for these type of problems assume a discrete time model, i.e., time is divided into rounds, in a round, each robot moves to some target point defined by the observations of its environment. In this talk, we focus on a much less examined class of local strategies, namely continuous strategies. Here, each robot continuously observes his environment and continuously adapts its speed and direction to these observations. focus on these type of strategies and survey recent results on local strategies for short robot chains and gathering in the continuous time model. We present such strategies for the Robot Chain and the Gathering Problem and analyze them w.r.t. the distance traveled by the robots. For both problems, we survey bounds for the "price of locality", namely the ratio between the cost of our local algorithms and the optimal cost assuming global view, for each individual start configuration.