Paper Info
Title
Continuous local strategies for robotic formation problems
Abstract
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.
Year
DOI
Venue
2012
10.1007/978-3-642-30850-5_2
SEA
Keywords
Field
DocType
continuous time model,gathering problem,continuous local strategy,simple local strategy,robot chain problem,short robot chain,robot move,local algorithm,above-mentioned formation problem,autonomous mobile robot,robotic formation problem,local strategy
Line (geometry),Locality,Mathematical optimization,Computer science,Optimal cost,Discrete time and continuous time,Robot,Mobile robot,restrict,Bounded function
Conference
Citations 
PageRank 
References 
0
0.34
22
Authors
2
Name
Order
Citations
PageRank
Barbara Kempkes11279.43
Friedhelm Meyer auf der Heide21744238.01