Download Bachelor`s Thesis
Transcript
4 Algorithm Outline 4.2 Phase 2: Seed Election During the execution, a robot can have two different roles, either the one of a seed or that of a non-seed. In the beginning, no robot is assign to a role. A seed robot’s task is to construct a local coordinate system. To ensure that enough of these local coordinate systems are distributed amongst the swarm, every non-seed robot must eventually see at least two seeds. Similarly, every seed must see at least one other seed. To elect the seed robots, two protocols are executed, one for the so called top seed election and one for the bottom seed election. Starting with the top seed election, every robot sends its ID to its neighbours. Whenever a robot receives a value greater than its own ID, it does not become a seed. If none of the messages contain a greater ID, the robot becomes a top seed. The remaining non-seeds continue with the bottom seed election protocol. The idea is the same as before: Every non-seed broadcasts its ID and becomes a seed if no message is received that indicates that a neighbour is assigned a greater ID. Once a robot becomes a seed, it starts to announce its new role. In the end of the bottom seed election protocol, every robot checks whether it is able to see enough seeds. If this is not the case, it broadcasts a message, inducing a new bottom seed election with its neighbours. This procedure is repeated, until every robot sees at least two, respectively every seed at least one other seed robot. The roles of the top and bottom seeds are identical, and they are not distinguished any more in the phases below. Figure 4.1: Possible excerpt of a collective. Red: seed robots with respective communication ranges. 12