This is my Bachelor’s thesis project, completed in May 2011. The topic is self-proposed. The abstract to the thesis, reproduced below, summarises this work:
Modular Self-Reconﬁgurable (MSR) robots are potentially capable of many interesting behaviours due to their ability to rearrange the conﬁguration of their physical parts. To realise this potential it is necessary to consider the problem of distributed and robust self-assembly of MSR robots. Although this is a broad undertaking, we argue that the distributed control of a robot formation can be used as a suitable intermediate problem towards the more general goal — It preserves the essential features of the robotic self-assembly problem, which is to get initially dispersed/separated robots to aggregate and then form a shape. Once this is done, the shape must be maintained while performing some task, which we have chosen to be a distributed navigation and sensing problem. To accomplish this task as a whole, we need to solve various sub-problems including aggregation, sensing, collective decision-making and robot localisation, for which we have developed distributed and robust algorithms and methods. Some of these methods are biologically-inspired, such as the exploitation of randomness to break symmetry and the use of inhibitory messages to enforce asymmetry. Our shape formation algorithm is also capable of self-repair.
Scattered robots wander around randomly to find each other and aggregate into larger groups. The group wanders about in search of other robots, turning about now and then to explore in a random direction. Robots in a group maintain a common sense of time (Mirollo & Strogatz’s firefly synchronisation algorithm), and after moving in a certain direction for awhile, they compete to suggest a new direction for the group to wander. In a large group, there are bound to be many ‘opinions’, but through a process of averaging, everyone quickly reaches a consensus.
This entire process is visualised in the first part of the video below. Note the arrows on the circles that denote robot direction. Grey robots are just moving along, blue robots are ready to suggest a new direction, red robots are the first in the vicinity to actually do that, and white flashes show the propagation of messages communicating these suggestions globally. The second part shows an example of scattered robots aggregating using this process.
In order to form a shape, the robots collectively set up a coordinate system to locate themselves in the swarm. Through a combination of competitive and inhibitory processes, the swarm elects a single ‘position reference robot’ (marked red in the video below) that serves as the origin of the coordinate system. If this robot fails or disappears, the process naturally generates another reference to take its place. The white flashes in the video visualise the propagation of inhibitory messages sent by the position reference robot at periodic intervals to prevent multiple references from existing at the same time.
Shape formation and self-repair are regarded as two sides of the same coin, namely, the problem of “shape maintenance” — arguably, this notion deserves further testing and exploration not performed in this work. The method employed here is a combination and adaptation of the DASH (Rubenstein and Shen) and SHAPEBUGS (Cheng et al) algorithms. Assuming that the number of robots in the swarm is fixed and known beforehand (BAD flaw in my work here!!), each robot gets a plan of how the shape looks like. With information about its position in a global coordinate system (see previous section), the robots try to position themselves within the shape of the formation, guided by an artificial potential field.
The following video shows robots forming a shape, which is later damaged, and subsequently ‘repaired’ by the shape formation algorithm, which is ‘always-on’:
It is clear that the present method suffers from an ‘inertia’ problem – robots entering the shape from outside must do so by ‘pushing’ those already inside further in. Things should work better with more ‘proactivity’ built in, but this was not explored in this work.
Distributed sensing and navigation
The swarm of robots must navigate their way towards a target location that emits a ‘scent’. Every robot has a noisy sensor, but by sharing its own estimate of the target’s heading, and computing that estimate by averaging the estimates received from robots nearby, information is propagated globally throughout the swarm and averaged to obtain high-quality data. This method is due to Mandar Chitre.
The grey patch in the video below represents the target which the robots, visualised by arrows that represent their heading, are trying to get to:
Putting it all together now
In a single video:
Robust and Distributed Formation Control of a Simulated Swarm of Robots, Bachelor’s thesis, 2011.
Videos accompanying thesis presentation (numbered in order of appearance when shown with the presentation slides):
- Wandering and aggregation demonstration
- Localisation demonstration
- Star shape formation, 30 robots
- Star shape formation, 60 robots
- Triangle shape formation and self-repair demonstration, 80 robots
- Group movement demonstration
- Complete task demonstration