We present a decentralized algorithm to achieve segregation into an arbitrary number of groups with swarms of autonomous robots. The distinguishing feature of our approach is in the minimalistic assumptions on which it is based. Specifically, we assume that (i) Each robot is equipped with a ternary sensor capable of detecting the presence of a single nearby robot, and, if that robot is present, whether or not it belongs to the same group as the sensing robot; (ii) The robots move according to a differential drive model; and (iii) The structure of the control system is purely reactive, and it maps directly the sensor readings to the wheel speeds with a simple 'if' statement. We present a thorough analysis of the parameter space that enables this behavior to emerge, along with conditions for guaranteed convergence and a study of non-ideal aspects in the robot design.
Segregation is a common behavior in nature, and it can be observed across scales. For example, cell segregation is a basic building block of embryogeneis in tissue generation processes @cite_3 @cite_0 ; while social insects, such as ants, organize their brood into ring-like structures @cite_14 .
@cite_0 @cite_14 @cite_3
1977973890 2001868359 2103852413
Leptothorax unifasciatus ant colonies occupy flat crevices in rocks in which their brood is kept in a single cluster. In artificial nests made from two glass plates sandwiched together, designed to mimic the general proportions of their nest sites in the field, such colonies arrange their brood in a distinct pattern. These patterns may influence the priority with which different brood are tended, and may therefore influence both the division of labour and colony demography. Different brood stages are arranged in concentric rings in a single cluster centred around the eggs and micro-larvae. Successively larger larvae are arranged in progressive bands away from the centre of the brood cluster. However, the largest and oldest brood items, the prepupae and pupae, are placed in an intermediate position between the largest and most peripheral larvae and the larvae of medium size. Dirichlet tessellations are used to analyze these patterns and show that the tile areas, the area closer to each item than its neighbours, allocated to each type of item increase with distance from the centre of the brood cluster. There is a significant positive correlation between such tile areas and the estimated metabolic rates of each type of brood item. The ants may be creating a “domain of care” around each brood item proportional to that item's needs. If nurse workers tend to move to the brood item whose tile they happen to be within when they have care to donate, they may apportion such care according to the needs of each type of brood. When colonies emigrate to new nests they rapidly recreate these characteristic brood patterns. The establishment and maintenance of precisely organized tissues requires the formation of sharp borders between distinct cell populations. The maintenance of segregated cell populations is also required for tissue homeostasis in the adult, and deficiencies in segregation underlie the metastatic spreading of tumor cells. Three classes of mechanisms that underlie cell segregation and border formation have been uncovered. The first involves differences in cadherin-mediated cell–cell adhesion that establishes interfacial tension at the border between distinct cell populations. A second mechanism involves the induction of actomyosin-mediated contraction by intercellular signaling, such that cortical tension is generated at the border. Third, activation of Eph receptors and ephrins can lead to both decreased adhesion by triggering cleavage of E-cadherin, and to repulsion of cells by regulation of the actin cytoskeleton, thus preventing intermingling between cell populations. These mechanisms play crucial roles at distinct boundaries during development, and alterations in cadherin or Eph ephrin expression have been implicated in tumor metastasis.