Flocking
Robots must move together as a group, following a leader while roughly keeping a formation.
Problem statement and measurescollapse
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).
A first look
the basic problem, a simple algorithm and why some things cannot be done, for a newcomer
Think of a flock of birds following a leader whose route nobody knows in advance, keeping roughly the same shape and never bumping into each other. In the flocking problem the birds are robots in the plane: the followers must follow a designated leader robot along an unpredictable path while keeping approximately a given formation, a shape placed relative to the leader (for example, a V shape), and avoiding collisions (two robots at the same position). The robots are oblivious (they forget everything after each move) and silent: they coordinate only by looking at each other's positions. The catalogue records only the first formal treatment Gervasi & Prencipe 2004 and has not checked its exact assumptions, so this page describes the problem and the simplest reasoning about it.
A standard approach, assuming the followers can recognise the leader and know the target formation:
- Look at all robots and find the leader.
- Place the target formation with the leader at its tip, oriented, say, along the leader's last observed direction of motion.
- Choose the free slot of the formation (a position in it reserved for one follower) that is closest to you (with a fixed tie-break rule).
- Move towards that slot, but never closer to another robot than a safety distance.
Why it matters. Reducing a moving formation to "chase your slot" is the basic design idea of leader-follower formation control.
Suppose followers can move no faster than the leader. Let the leader run at full speed in a straight line. A follower that is a distance \(\eta > 0\) behind its slot moves at most as fast as the slot moves, so the gap never shrinks.
Why it matters. It explains why "approximately" in the problem statement is not a detail but a necessity.
What is known
The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.
What the community started looking at
Flocking was posed as a coordination problem without communication for oblivious robots Gervasi & Prencipe 2004; the questions were feasibility and, later, fault tolerance and self-stabilisation.
All settings
The assumption tree (1 settings, 1 branch points)
The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Colours); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Body › Visibility › Opacity › Faults › Scheduler › Lights (persistent memory) › Agreement on coordinates › Movement › Multiplicity detection › Randomness › Identifiers.
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.