Swarm Communication
Communication works different in most robotic swarms, depending mostly on factors like the environment, the size of the robots, the budget of the project and on the limitations set by creators or other instances. The larger the robots are, the more possibilities are there for building up a properly working communication between the robots. Some ways of communication are bluetooth, wireless LAN, communication via the environment(stigmergy) or like in the case of Jasmine via infrared LEDs.
Stigmergy
Observing swarms in nature, we will soon notice, that the single individuals don't communicate via messages. But showing some collective behavior, the members must exchange information in some way. This is done by a phenomena called stigmergy, which means communicating by changing the environment. 'The concept of stigmergy was introduced by Pierre-Paul Grasse in the 1950's to describe the indirect communication taking place among individuals in social insect societies. Ants and termites coordinate the building up of their nests by using the nests themselves to exchange information. For finding shortest paths at foraging or other tasks, ants don't tell every single of their mates where to go, but change the environment by placing some pheromone on the way they chose. Following the most odorous path and leaving their pheromone on this way again, the other ants cooperate and after a short period, the shortest way stabilizes. It's not easy to use this method in artificial swarms. Creating artificial pheromone is nearly impossible at the moment and can't be considered as a serious way to create swarm behavior. Observing the behavior of the other members and acting after interpreting their actions or the changes appearing in the nearest environment is possible and can be a way to work with stigmergy.
Communication via messages
Due to the inapplicability of stigmergy in an efficient way at the moment, we have to find another way of intra-swarm and inter-robot communication. This way can be the sending of messages, if the robots have this capability. The most common technologies for sending messages from robot to robot in swarms are bluetooth, wireless LAN or infrared. Advantage and disadvantage at the same time of infrared communication is the fact, that robots have to be in direct vision and direct communication is not possible with robots not in sight. Why this is a disadvantage should be clear, but how can this be an advantage? In natural swarms we can very often find that swarm-members only react to their direct environment. By using infrared technology, we can adopt this concept to the artificial swarm easily and the robots won't percept information that does not come from their direct environment. Infrared communication has also the advantage of needing not to much resources and is applicable for micro-robots. On the other hand we have to note, that sun-light and other sources of light may disturb communication. Wireless LAN is more likely to be applied in middle-size robotic teams, the volume of transmitted data can be very high here. Disturbance by radiation of other units is possible. The technique of bluetooth communication is settled between infrared and wireless LAN communication, regarding to size and range. The communication technique only gives the basic conditions for direct inter-robot communication. Now it is necessary to put those messages into some context. Therefore assigning a unique ID to every robot and specifying types and content of messages is useful. Simpler message could contain information like 'Come here, I found the target of interest!'. More complex messages could contain requests for specific robots, either by their ID or by their capabilities. These messages should be distributed as intelligent as possible through the swarm and therefore a more or less simple routing protocol should be used.
Important points of Communication
There are some parameters regarding communication that are very important and have great effect on how communication works and should be chosen carefully by the developer:
Communication Range
If the communication range is too small, robots can't communicate or only if they are nearby. If the communication range is big, this means that communication can jam, because every robot has to listen to every message that was sent. For comparsion: If we would here every word spoken in a range of 1000 meters, this won't be very useful, because it won't be possible anymore to filter out really important messages.
Communication Area
In ideal case, the robot covers an area of 360°. If only one communication unit at the top exists, this can be achieved, but if communication is splitted to different units like affordable at 'Jasmine', a 360° communication area can only guaranteed for about half of the communication range. This causes great constraints in regularity of communication and can thereby cause problems in realization of swarm behavior.
Length of Messages
Short messages produce a large overhead due to the header information normally sent with every message (contains ID, target,...). Large message tend to fail more often than short ones.
Propagation Time
The time it takes to send a message through the whole swarm. How is messages forwarding processed?
Interferences
Nearly every type of communication unit has to deal with interferences and other external influences. This can be signals from a nearby Wireless LAN, the sunlight or things like the infrared port of a laptop. Depending on the location, possible interferences have to be taken into account.
Stigmergy
Observing swarms in nature, we will soon notice, that the single individuals don't communicate via messages. But showing some collective behavior, the members must exchange information in some way. This is done by a phenomena called stigmergy, which means communicating by changing the environment. 'The concept of stigmergy was introduced by Pierre-Paul Grasse in the 1950's to describe the indirect communication taking place among individuals in social insect societies. Ants and termites coordinate the building up of their nests by using the nests themselves to exchange information. For finding shortest paths at foraging or other tasks, ants don't tell every single of their mates where to go, but change the environment by placing some pheromone on the way they chose. Following the most odorous path and leaving their pheromone on this way again, the other ants cooperate and after a short period, the shortest way stabilizes. It's not easy to use this method in artificial swarms. Creating artificial pheromone is nearly impossible at the moment and can't be considered as a serious way to create swarm behavior. Observing the behavior of the other members and acting after interpreting their actions or the changes appearing in the nearest environment is possible and can be a way to work with stigmergy.
Communication via messages
Due to the inapplicability of stigmergy in an efficient way at the moment, we have to find another way of intra-swarm and inter-robot communication. This way can be the sending of messages, if the robots have this capability. The most common technologies for sending messages from robot to robot in swarms are bluetooth, wireless LAN or infrared. Advantage and disadvantage at the same time of infrared communication is the fact, that robots have to be in direct vision and direct communication is not possible with robots not in sight. Why this is a disadvantage should be clear, but how can this be an advantage? In natural swarms we can very often find that swarm-members only react to their direct environment. By using infrared technology, we can adopt this concept to the artificial swarm easily and the robots won't percept information that does not come from their direct environment. Infrared communication has also the advantage of needing not to much resources and is applicable for micro-robots. On the other hand we have to note, that sun-light and other sources of light may disturb communication. Wireless LAN is more likely to be applied in middle-size robotic teams, the volume of transmitted data can be very high here. Disturbance by radiation of other units is possible. The technique of bluetooth communication is settled between infrared and wireless LAN communication, regarding to size and range. The communication technique only gives the basic conditions for direct inter-robot communication. Now it is necessary to put those messages into some context. Therefore assigning a unique ID to every robot and specifying types and content of messages is useful. Simpler message could contain information like 'Come here, I found the target of interest!'. More complex messages could contain requests for specific robots, either by their ID or by their capabilities. These messages should be distributed as intelligent as possible through the swarm and therefore a more or less simple routing protocol should be used.
Important points of Communication
There are some parameters regarding communication that are very important and have great effect on how communication works and should be chosen carefully by the developer:
Communication Range
If the communication range is too small, robots can't communicate or only if they are nearby. If the communication range is big, this means that communication can jam, because every robot has to listen to every message that was sent. For comparsion: If we would here every word spoken in a range of 1000 meters, this won't be very useful, because it won't be possible anymore to filter out really important messages.
Communication Area
In ideal case, the robot covers an area of 360°. If only one communication unit at the top exists, this can be achieved, but if communication is splitted to different units like affordable at 'Jasmine', a 360° communication area can only guaranteed for about half of the communication range. This causes great constraints in regularity of communication and can thereby cause problems in realization of swarm behavior.
Length of Messages
Short messages produce a large overhead due to the header information normally sent with every message (contains ID, target,...). Large message tend to fail more often than short ones.
Propagation Time
The time it takes to send a message through the whole swarm. How is messages forwarding processed?
Interferences
Nearly every type of communication unit has to deal with interferences and other external influences. This can be signals from a nearby Wireless LAN, the sunlight or things like the infrared port of a laptop. Depending on the location, possible interferences have to be taken into account.
For collective systems a communication plays the role of nervous system in human body. Since microrobots in a swarm can communicate only locally with their neighbors, such a "swarm nervous system" can be produced only by a mechanism that propagates information through multiple robot-robot connections. Parameters of a global circulation of information (like global propagation speed or global propagation time) depend on characteristics of local communication (communication radius R_c, the number of robots within R_c). In this section we derive this relation, which is necessary for further development of the robot's communication hardware.
Since parameters of local communication between robots depend on their behavior, we differentiate three following behavioral cases:
-
Robots move only in small areas, so called clusters. In this case robots are situated more or less closely to each other, so that swarm peer-to-peer network (SPPN) is created "automatically" (we call SPPN also "communication street", see vidoes). The main problem is a communication between such clusters.
-
Robots move in large areas (typical swarm scenario). Robots exchange information only when they meet each other. The inter-cluster communication belongs to this case.
-
Part of robotic swarm purposely creates and supports the SPPN. This is the most interesting case, that provide stable communication in swarm
In the further calculation we consider the most hardest case of a large-area swarm. We can intuitively assume that the communication radius R_c, the swarm density D_{sw}, the robots motion velocity v and the time t are closely related in propagating the information. For deriving a relation between them, we take several analogies to molecular-kinetic theory of ideal gas, more exactly diffusion in ideal gas (by these analogies we denote also a "diffusion of information"). We introduce the following notions: the sensor radius R_s, where a collision-avoiding procedure is started; l_c the length of free path from the start of motion till the first communication contact; l_s the length of free path from the start of motion till the first collision-avoiding contact; n_c and n_s are correspondingly the number of communication and collision-avoiding contacts; S_c and S_s are the area of the "broken" rectangles built by a motion in some time interval t with R_c and R_s.
In Figure below we sketch our consideration.
In Figure below we sketch our consideration.
Firstly, we are interested in the number of communication contacts n_c happen during the motion. This value is equal to the average number of robots in the area S_c, n_c=S_c D_sw, where D_sw is the swarm density. We assume that the collision avoiding radius and the robot's rotation radius are small so that we can neglect the area of fractures. In this case S_c=2 R_c \upsilon t. D_sw can be calculated as the number of robots N in swarm divided by the area available for the whole swarm S_sw:
In the relation (1) we assume only one robot moves whereas other are motionless. More exact relation, when all robots move, differs from (1) only by the numeric coefficient \sqrt(2) (as proved by Maxwell for a diffusion in ideal gas). For the further calculation we use
Now we have to estimate how the information will be propagated after the first communication contact. This propagation dynamics is similar to "epidemic infection" dynamics, estimated as the series:
and written iteratively as
that is the "standard" exponential form (n_c+1)^n. We are interested in the case when all robots are "infected" (n_c+1)(power n) > N or n=log_(n_c+1)N. From real experiments we know that for establishing a communication contact and transmitting messages, robots need some time p_t, that can be measured experimentally. The information transfer starts when the first robot "infects" one additional robot(n_c=1); the time till the first infection t_first and the total time t_total= n~t_first+Np_t for infecting the whole swarm can be obtained as:
In the performed simulations (p_t=0), the swarm areal is 800x650~pixels**2, N=50 with D_sw ~10pix./sec., R_c=40pix. The formula above gives us t_{total}~ 52sec.. In many performed simulation cycles we observed t_total between 30 and 90 sec. This formula is also useful in estimating the energy needed for each robot. For example, swarm during the running time has to propagate 100 different messages; it takes about 2 hours in the mentioned example. So the power supply should provide energy at least for 2 hours.
For developing a real microrobotic swarm we can take S_sw=1000x1000~mm**2, N=50 and assume first p_t=0 for the real p_t). In Figure above (b) we plot t_total depending of R_c with different values of N and v. We see, that for the average propagation time 1 min, the R_c for N=50 lies between 50 mm and 140 mm. Thus, for the targeted robots body of 23 mm, the communication radius R_c is of 4-5 times larger then the size of the robot.
At the end we discuss such an important point as the critical swarm density D_sw. The critical swarm density and the "coefficient of swarm efficiency" (the relation between the number of robots with useful/desired and useless/undesired activities) determine the minimal number of robots N_min in some areal S_ws required to perform some operation successfully. For the considered example with the given S_sw=1000x1000~mm**2, t_total=30~sec., R_c=100~mm and v=20mm/sec. (related to the random motion), the minimal number N_min~ 29 and the critical swarm density D_sw=28.46**(-6). This relation is not exact, because it does not involve the size of a robot into this calculation, however in the microrobotic case with S_robot << S_sw, it can serve as a good approximation.
Communication of Jasmine-III uses IR equipment and has been improved continuously with every version of the robot (see more in description of SBII and SBIII. The shielding and the positions of emitters and sensors have been optimized and the communication protocol has been changed several times. At the moment it is possible to choose between different length of messages(8-,12-, 16-bit), wether an acknowledgement has to be sent and if the channels should be processed in parallel or sequentially while sending. In the above picture you can see the Communication area of 'Jasmine'. It is not possible to cover a 360° communication range for the whole communication radius. Due to alignment of the emitters there will always be some dead areas and angles.
The IR-equipment has also the problem of interferences. They appear, like in RF case, when several neighbor robots transmit simultaneously. The problem of IR-interferences can be avoided by restricting an opening angle of a pair IR-receiver-transmitter. For four communication channels, the opening angle of each channel is 90°. In this case we have 2- and 3-robots IR-interferences even in the "closest" radius (50 mm). Reducing the opening angle to 60° or to 40° allows avoiding IR-interferences in the "close" and "near" radius (100 mm)
Since many microcontrollers have 8-channel ADC (one ADC input is used by the distance sensor), we choose 6-channel directional communication.
Directional communication is extremely important in a swarm also from another reason. The point is that a robot has to know not only a message itself, but also the context of this message (e.g. the direction from which the message is received, intensity of signal, communicating neighbor and so on). Without directional communication hardware, we cannot implement algorithms providing a spatial context. From many software requirements the communication radius R_c and the number of directional communication channels are the most important ones. From this viewpoint, the IR is more suitable for robot-robot communication than the RF. The host-robot communication can also be implemented with IR (a sensor with PCM-filter for receiving global modulated signal). Such a signal can be thought as of a remote control or a global information exchange between robots and host.