Control >> Finding object/goal >> Chain formation

Chain formation

In this section we describe an experiment where a group of three s-bots forms chains starting from a nest object which is represented by an s-toy. We focus our analysis on the dynamics of the chain formation process and the impact of two probabilistic control parameters. Therefore a goal object is omitted. In the following the behaviour-based controller is described. Afterwards, we introduce the experimental setup and disuss the results

Controller

A behaviour-based control architecture is used. For a detailed description we refer to the one given in the D11.

Our basic goal is to let the s-bots form visually connected chains, where each s-bot aggregated into a chain has to activate an appropriate color such that a chain becomes a directed structure that can be used for navigation purposes. Our controller executes a particular behavioral set, which may differ in time depending on the state of an s-bot. There are three simple behaviors:

• Adjust distance (AD): attraction/repulsion with respect to one given object. The AD behaviour depends on the perceived distance and direction to the respective object, and on a distance constant d(aa) that represents the desired distance.
• Move perpendicular (MP): executed with respect to one given object. When executed in combination with the AD behaviour it results in turning around a certain object. The MP behaviour depends on the perceived direction to the respective object only.
• Avoid obstacles (AO): repulsion from each object that causes an activation of the proximity sensors.

Each of the behaviors computes a two dimensional vector that represents the desired direction of movement (direction of the vector) and the desired speed (length of the vector). While for the AD and MP behaviors the required information is taken from the camera, the AO behavior uses the proximity sensors. In each state the vectors of the respectively active behaviours are added and the resulting vector is used to determine the activation of right and left wheel. The following three states can be distinguished:

• Explorer: The intial state for each s-bot at the beginning of an experiment. An explorer searches an existing chain and, in case it finds one, moves to its end to eventually connect itsself to the chain. In order to connect to a chain the s-bot has to reach a certain distance from the chain and then activate its LED ring with the appropriate colour. The active behaviours are AD, MP and AO.
• Chain member: the control for a chain member is very simple. It keeps its position and does not move until it disaggregates from the chain. As no movement is required, no behavior is active.
• Lost: when a robot cannot perceive any chain member it enters the lost state. First, the s-bot turns into the direction where it last perceived a chain member and moves straight until it either regains contact to a chain, or perceives an obstacle with its proximity sensors. In the latter case, the s-bot turns on the spot for a random amount of time and continues moving straight.

A transition from the explorer to the chain member state is triggered probabilistically. For an explorer there is a probability P(expl->chain) to become a chain member at each control time-step. A control time-step has a length of approximately 120 ms. This value is not constant because it depends on the camera frame rate. Correspondingly, the transition from the chain member to the explorer state is governed by the probability P(chain->expl). After a chain member becomes an explorer, it moves back along the chain towards the nest and, once the nest is reached, it either moves along another chain or starts one by itsself. As the colour of the nest is not exclusive, but may also be used by another s-bot aggregated into a chain, an s-bot can not determine whether a blue object is the nest or a chain member. We use a simple method to make this distinction. Moving back along a chain, the s-bot will turn around different chain members with different colours. In case the colour of the object the s-bot turns around is blue and does not change for 80 time-steps, the s-bot perceives the blue object as the nest, otherwise as a chain member.

Note that there are several conditions that have to be fulfilled for an explorer and for a chain member to allow them to switch their state. These conditions are necessary to assure the stability of a chain and to avoid loops. We refer to the D11 for more details.

Experimental setup

Figure 1 shows the experimental environment which consists of a squared arena with a side length of 2.40 m. An s-toy, which represents the nest, is placed in the center of the arena. In order to be recognized by the s-bots the blue LEDs of the s-toy are turned on. As indicated by the black and red dots around the nest, there are 40 different initial positions. At the beginning of an experiment an s-bot is randomly placed at one of them. For this discretised initial placement three different distances from the nest, either 25, 40, or 55 cm, and 16 different angles are used. Furthermore, the initial orientation of an s-bot is determined randomly out of four possible directions as well.

Figure 1. The experimental environment: a squared arena with a side length of 2.40 m with an s-toy, which represents the nest, placed in its center. In order to be recognized by the s-bots the blue LEDs of the s-toy are turned on. As indicated by the black and red dots around the nest, there are 40 different initial positions at three distances and 16 angles. At the beginning of an experiment an s-bot is randomly placed at one of them. Furthermore, an s-bot's initial orientation is determined randomly as well.

Three s-bots are used. Each trial is characterized by the values of the two control parameters P(expl->chain) and P(chain->expl), and by a seed that initializes a random number generator to determine the initial positions of the robots, and their probabilistic choices during an experiment. For each of the two probabilities three different values are applied:

P(expl->chain) ∈ {0.01;0.1;1}

P(chain->expl) ∈ {0.001;0.01;0.1}.

Out of the nine possible combinations we have chosen five which consist of the possible combinations with P(expl->chain)=0.1 or P(chain->expl)=0.01. We have chosen these values because (i) our previous experience with the simulations has shown that the range of parameter values is the most interesting one, (ii) preliminary experiments with the s-bots have confirmed this experience. For each combination, ten seeds are used to initialize an experiment. An experiment runs for 100 seconds.

Results

The goal of this experiment is to reveal the impact of the two probabilistic control parameters. We do this by comparing the fraction of s-bots in each of the three states when changing one of two probabilities.

Figure 2 shows the average number of s-bots residing in each of the three states for different probability sets. The lowest of the three lines represents the number of explorers. The space between the lowest and the middle line displays the number of chain members. The last fraction, given by the space between the middle line and the top line, is the average number of lost s-bots.

Figure 2(a)

Figure 2(b)

Figure 2(c). The average number of s-bots residing in each states for different probability sets. The lowest of the three lines represents the number of explorers. The space between the lowest and the middle line displays the number of chain members. The last fraction, given by the space between the middle line and the top line, is the average number of lost s-bots. Errorbars are displayed once every ten seconds to indicate the standard deviation. On the left (right) part of the image P(expl->chain) is fixed to 0.1. The value of the other probability is growing from its minimum on the top to its maximum on the bottom.

In Figure 2 P(expl->chain) is fixed to 0.1, and P(chain->expl) takes the values 0.001 (Figure 2(a)), 0.01 (Figure 2(b)) and 0.1 (Figure 2(c)). Comparing the three graphs, we can see that initially the three probability sets lead to a similar behaviour. The equal probability to aggregate into a chain in each case leads to approximately one s-bot becoming a chain member within the first five seconds. Afterwards, the behaviours of the three systems differ significantly. When applying the lowest value for P(chain->expl), after 20 seconds until the end of the experiment approximately two of the three s-bots are in average aggregated into a chain. For P(chain->expl)=0.01, there is in average approximately one s-bot that aggregated into a chain, and for the highest value P(chain->expl) this fraction drops even further. In general, we can say that the higher the value of P(chain->expl), the lower is the fraction of chain members.

To uncover the impact of P(expl->chain), let us look more closely at Figure 3, where P(chain->expl) is fixed to 0.01, and P(expl->chain) takes the values 0.01 (Figure 3(a)), 0.1 (Figure 3(b)) and 1 (Figure 3(c)). The difference between the three probability sets is already disclosed at the initial stages of the experiment. A higher probability to aggregate into a chain leads the s-bot to become chain members faster. This difference is well expressed in Figures 3(a) and (e). However, for the highest value of P(expl->chain) it takes a surprisingly high amount of time until the s-bots form a chain. This is due to a condition that impeaches an explorer from aggregating into a chain. In order to avoid loops, an explorer may only aggregate into a chain in case it perceives only one colour. Given that P(expl->chain)=1, all s-bots will initially try to start a chain and, while trying to do so, activate the appropriate colour. As this is done simultaneously by all s-bots, they will initially impeach each other from becoming a chain member in case they perceive each other.

Figure 3(a)

Figure 3(b)

Figure 3(c). The average number of s-bots residing in each states for different probability sets. The lowest of the three lines represents the number of explorers. The space between the lowest and the middle line displays the number of chain members. The last fraction, given by the space between the middle line and the top line, is the average number of lost s-bots. Errorbars are displayed once every ten seconds to indicate the standard deviation. P(chain->expl) is fixed to 0.01. The value of the other probability is growing from its minimum on the top to its maximum on the bottom.

Example movie:
• Chain formation with low probability to aggregate into a chain (MOV, 9.2 MB).
Example movie:
• Chain formation with high probability to aggregate into a chain (MOV, 9.3 MB).