Flocking
Robots must move together as a group, following a leader while roughly keeping a formation.
Problem statement and measuresexpand
Robots, the followers, follow a designated robot, the leader, whose path is not known in advance, while keeping (approximately) a given formation (a shape the robots must hold, placed relative to the leader) and avoiding collisions (two robots at the same position).
Measures: Time, rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known; Colours, colours of the light per robot (0 for oblivious robots).
Progress map
tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Colours
Oblivious robots following a leader + point, + unlimited visibility, + transparent, + no faults
0 open · 1 results
unknown
\(\text{finite}\) vs —
tight
\(0\) vs —
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.