Keywords
|
| Swarm, bit communication, model, reverse approach, non-reverse approach. |
INTRODUCTION
|
| The concept of this project is called swarm. Swarm refers to a large number or mass of small animals or insects, especially when, in motion. Swarm Intelligence (SI) is the discipline that deals with natural and artificial systems that is composed of many individuals that coordinate using decentralized control and self-organization. In particular, the discipline focuses on the collective behaviours that result from the local interactions of the individuals with each other and with their environment. The systems are typically made up of a population of simple agents interacting locally with one another and with their environment. The agent follows very simple rules, and although there is no centralized control structure dictating how individual agents should behave, local interactions between such agents lead to the emergence of complex global behaviour. Natural examples of SI include bee colonies, ant colonies, bird flocking, animal herding, bacterial growth, and fish schooling. |
| Bit-communication using swarm intelligence is about transmitting data from a sender to a receiver within a specific area. The data must be delivered to every receiver in the area. This process is closely related to broadcasting in a manner, through bit communication, to spread the data amongst the receivers. The goal of this project is to send data to all these agents using Netlogo® Software. Swarm technique is implemented because it is useful for bit communication behaviour. Two techniques are used for the transmitting and receiving process. The first is the reverse technique where the data can be retransmitted to the sender for the next cycle. Here, the program randomly selects one of nearest agent for transmitting the data. The second technique is non-reverse, whereby the data cannot retransmit to the sender in the previous cycle. NetLogo® is a simple agent simulation environment based upon StarLogo. These Users program use turtles as the agents and patches as the environment. In NetLogo®, the environment has active properties and is ideal in that it supports stigmergy or group work. Agents can be easily modified to sense information of the local patch or patches within some neighbourhood. Unlike conventional programming languages, the programmer does not have control over agent execution and cannot assume uninterrupted execution of agent behaviour. A fairly sophisticated user interface is provided and new interface components can be introduced using a drag-and-drop mechanism. Interaction with model variables is easily achieved through form-based interfaces. The user codes, in NetLogo®Ã¢ÂÂs own language, are simple and type-free. |
LITERATURE REVIEW
|
| A. Swarm Intelligence of Bees |
| Swarm intelligence is a modern form of artificial intelligence (AI) where the focus is on a system design based on using multiple agents. This is particularly useful in applications such as robotics and application optimization. The design method using swarm intelligence is different from intelligence compared with traditional methods. |
| “He must be a dull man who can examine the exquisite structure of a comb so beautifully adapted to its end, without enthusiastic admiration.” [Charles Darwin, 1872]. 5000 years ago, Egyptians stored honeybees. They were amazed at the beauty of the comb of the honeybee. How do bees construct hexagonal cells properly? It is proposed that the hexagonal form is most resistant to honey. R.A.F de Réaumur reviewed that material and wax is required to build the hexagonal spaces. To create the form of a hexagon, each corner requires a 120 ° spread for six angles. However for the bees, the colony did not learn that; because bees “blindly use the highest mathematics by divine guidance and orders” [1]. The theory that bees needed guidance was used because it is natural for bees to construct hexagonal cells for the colonies. |
| D'Arcy Wentworth Thompson, Darwin inspired member and mathematician, wrote a book On Growth and Form [9]. In the book, Thompson said the hexagonal cells, built by bees, is a simple example of the pattern created for all layers of foam in free space. BeeâÂÂs wax candles are soft. They just pull the perfect hexagonal cells into various forms with physical techniques. Hence the pattern is formed spontaneously and not by natural selection or divine interference [1]. Swarm behavior shows that the formation of the pattern for each swarm can be explained by physical forces, and this explains the arrangement of cells found in our environment. It is not surprising that the hexagonal pattern inspired many people whether they are scientists or not. In addition the analysis of some patterns, reveal similarities among themselves. Lately, it was found that bee hexagon pattern in their honeycombs is not unique. By using chemical reactions, the patterns can also be made to be in the form of hexagonal. |
| Honey bee comb is not only a maze of perfect forms of hexagonal cells. The honey bees also fill each cell with eggs for the next population. The eggs will then turn into larvae, pupae and eventually become a new bee in the colony. In addition the bee can also fill the cell with pollen and honey. Patterns can be differentiated into three parts; eggs (new people), pollen and honey, as shown in Figure 1(b). Eggs and pollen must get closer to each other, because the eggs need food to survive before it can change to new bees. After the new bees were produced, it should strive to find food and honey to the colonies. This process continues until the bees can produce eggs. |
| The beauty about working bees is that they work in macroscopic entities that are very small to be seen with the naked eye. Honeybees are suitable for observation and study, because honeybee colonies can be experimented in the area or small house, as shown in Figure 1(a). For deeper observation, the bees can be marked with numbers to see the movement and the interaction between them. The best way to mark all the bees is to put the numbers on their heads. However adherence to all the population, bees must put in their environment, where the ecosystem for the residents is not to be interrupted. In addition, new bees can be determined by observing the bees without any number pasted on them. The observation on bees behaviour may be distinguished into three different parts i.e. food, eggs and honey. All three divisions are clearly assigned in some pattern to processes at any time. |
| Figure 1(b) shows the structural pattern of a honeybee colony. Hexagon coloured grey indicates honey; white indicates pollen and black indicates egg. More eggs are in the hexagonal cells: about 54.49% are eggs, 16.02% are pollen and 29.49% honey. This percentage shows that the bees are more focused on residents to improve their society and their colonies. Meanwhile, the eggs occupy is about twice the amount of honey hexagonal cells. In honeybee colonies, pollens collected per day will be consumed within the same day. This means pollens are not kept for more than a day. This shows that bees work on a consistent basis because they need to find food (pollen) on an ongoing basis. Finally the location of pollen is close to the brood. This is because the broods will have to be stored for an extended period of time before the eggs will turn into adults (after three weeks). The duration of 21 days show that cells will be uninterrupted or filled pollen and honey, but in between the interface zone honey and brood, pollen is always replaced with the new ones daily as aforesaid. So for the brood cell, the cell will be emptied after 21 days, and will be replaced by a new brood. |
| B. Communication behaviour in recruitment mechanism for foraging |
| Recruitment is a collective term for any behaviour that results in an increase in the number of individuals at a particular place [4], and allows insect societies to forage efficiently in an environment in which food sources are patchily distributed or are too large to be exploited by single individuals [2,3,5]. Communication behaviour among bees allows foraging, i.e the process of storing food, to be organized. The recruitment processes are required for the social insects. In addition, the colonies of insect can forage the food within a 10km radius. This shows that when the insects find food, they can go up to within a 62.84 km square area [7]. The insects can survive because the area is large compared to the size of the insects. This foraging process is repeated every day until they migrate to another place or location. In the case of honeybees, the recruiters perform a stylized „danceâ which encodes information on the direction and distance of the food source found. Up to seven dance followers [6], potential recruits, are able to extract and decrypt this information. |
| The recruitment mechanism can be divided into two classes, which are direct and indirect mechanisms. Direct mechanism involves transferring information via figuratively speaking, word-of-mouth. The best example of the direct mechanism can be observed in beesâ colonies. Some of the bees, called „dancing beesâ have their own dance language to provide information on direction to their colonies. Then the recruits will place the food in the specific location of cells. These dancing bees are formed from several numbers of total populations of bees. Mass recruitment by way of a chemical trail is an example for the indirect, the recruiter and recruited are not in physical contact with each other. Communications among them are achieved through modulation of the environment with the trail. The recruiters leave a pheromone on their way back from foraging while the recruits follow the trail. This mechanism pattern is comparable to the process of broadcasting, whereby the sender transmit information without specifying any exact receiver. Radio and television signals broadcasting are the best example to describe the process of broadcasting data. |
| In the case of ant colonies, ants finding food put the pheromone in their path so that, the ants at the back will follow the path according to the trail. An experiment showed that after some time the forages converged on the shorter path [7]. The result of shortest path is the positive feedback process. The trail behaviour allowed the ants to choose the best quality of the food source that they will take. Ants will put pheromone in their trail depending on the quality of food. The relationship between quantity of pheromone and quality of food is proportional to each other. If the ants found the two sources of food in their forage, it will distinguish between the two trails based on which food is better. Therefore, the process is continuous until the foods are finished or they have enough foods for their colonies. |
| The success of the pheromone trail mechanism is likely to be due, at least in part, to the non-linear response of ants to pheromone trails where, for example, the distance that an ant follows a trail before leaving it is a saturating function of the concentration of the pheromone [4]. Furthermore the ants will follow the trail has a probability value that is not equal to zero. The probability is based on the strength of the trail. In mathematical view, the non-linearity in response is the complexity of the model equation that underlying foraging for ants colonies. However, in biological view, differential equation corresponds between ants and food implies more flexibility. In addition, the ants choose the food source using many possible solutions. When the food is in limited capacity, the ants will put a negative pheromone to indicate the food is running low. The negative pheromone will inform other ants not to follow the trail anymore. So the ants can continue to find another food source or go back to their colonies to continue other work. However, there is a drawback for this mechanism process. If the ants are relying on the pheromone, it will have low probability to follow new pheromone that guide to better food source, which was found by other ants. This is because the trail is diverse from the previous trail. Furthermore, other ants may be difficult to compete with existing trail. If, due to initial conditions, a mediocre food source is discovered first, ants that have found a better quality food source after the first trail has established will not be able to build up a trail strong enough to recruit nest mates to the newly discovered bonanza [8]. Therefore, the ants are stuck on sub-optimal solution. |
METHODOLOGY
|
| To design a little communication to swarm model, it is necessary to understand well the basic collective behavior, biology and sociology, about swarms and wireless network. The behavior of each agent of the swarm is different from each other because they have a unique pattern of survival. The processes of communication in swarm will have a protocol that has to be followed in the colonies. After that the process of communication and data transmission in the colony will be developed to determine their behavior. A swarm model can be designed using static agents and uniform. This model is designed so as to be able to determine graphically or numerically the behavior of the swarm. The model can then be assessed and analyzed using statistical methods for averaging data, interpretation and verification of data. |
| Bit-communication is the process of sending data to other agents in an area. Basically there are two approaches used in this paper to do the communication process; reverse and non-reverse approach upside-down. In bit-communication, agents who have data that can send data to other agents near it. Random agent initially selected to send data to other agent(s) in the arena. This first cycle, the data will be sent to the neighbor(s) directly. Data sent will depend on how many bits are used in the process of communication. On the other hand, the approach can retransmit data or send back to the sender in the previous cycle. However non-reverse approaches upside down, no data will be forwarded back to the sender in the next cycle. A different approach is to review the swarm behavior during data transmission to others. In this paper, single bit up to three bit communications are studied. |
| Cue-based Model in swarm is the process of direct communication between agents. Agents take action depending on the signal environment. Stigmergy is an example of cue-based behaviors. Stigmergy is a mechanism of communication going on between the indirect agent coordination. This is because stigmergy is self-organization and free. It produces a complexity and seemed like a smart structure, because without planning, direct and control the communication between agents. In addition, simple agents support stigmergyâÂÂs lack of information and are aware of other agents. |
| In this paper, the software used to review the algorithm is NetLogo® software version 4.1.1. NetLogo® is open source software that uses Java as their development tools. It is a multi agent modelling environment and can be programmed and be used to design a model in any environment. |
RESULT AND DISCUSSION
|
| In this paper, results are obtained for one-bit, two-bit and three-bit communications, shown in the following pages. The model was simulated for 50 replications to get the average, number of ticks or cycles and margin of errors for 900 agents in the area. The value of 900 agents used was because when the program is simulated for 400 agents, the result obtained was very fast for one bit-communication model. In order to get a higher accuracy result, the number of agents used was increased to 900 agents. The result can then be analysed clearly. At the beginning of the simulation, an agent is selected randomly from within the area shown in Figure 2(a). The number of agents for the initialization is only one. This is because the program needs to choose where to start. |
| However for the cue-based model, during initialization process, the white agent is set to the centre of the arena. This is an example of radio or television broadcasting, in which it only has one transmitter and others are receivers. In this model, 899 agents were used as the receivers. Figure 2(b) shows the snapshot of one of the simulation run at ticks = 732. As the continuation from Figure 2(a), the data were transmitted from the initial agent to its neighbours. Firstly the agent will determine its eight neighbours. For 1-bit communication, it will randomly select one agent from itâÂÂs neighbours to transmit the data. For 2-bit and 3-bit communications, the transmission become faster because of the agents with the data will retransmit to its neighbours using n-bit data. In order to make sure that all 900 agents received the data, reverse and non-reverse approaches can be used. The pattern of data distribution will be different for every replication due to the randomness in the choice of receivers and the methods of data transfer. The goal is to send the data to all agents. To indicate that agents have received the data, the recipient agents will change their colour to white. |
| The cue-based process is an indirect communication process. As shown in Figure 2(c), a rectangular shape is used for analysis. When surrounding neighbours find that one of their neighbours is different from others, they will initiate the behaviour of other agents by changing their colour to white. The agent simple react to the environmental stimuli without using any direct communication among agents. So, there is no datum being transmitted in the whole process |
| Figure 3(a) compares the time taken to transfer data against the number of agents in one bit-communication for reverse and non-reverse approaches. The graph shows the results for 900 agentsâ is different for both approaches. As seen in the Figure 3(a), the non-reverse approach is about 1/3 times quicker compared to the reverse approach (non-reverse approach completes the process in 18000 ticks while reverse approach in 28000 ticks). |
| A combination graph of the time-taken against the number of agents for two bit-communication using the reverse and the non-reverse approach is shown in Figure 3(b). It shows that there is no obvious difference in the curves plotted for reverse and non-reverse. The non-reverse approach is marginally quicker than the reverse approach for two bitcommunication. |
| Figure 4(a) shows the combination graph for three bit-communication result for reverse and non-reverse methods. It shows that the results obtained are similar to each other. The difference is very little and is not obvious at all. Meanwhile Figure 4(b) has been plotted for cue based communication. As can be seen from Figure 4(b), all agents received the data in 14 ticks. |
| Figure 3(a) shows the result of a 1-bit communication for non-reverse and reverse approaches. From the result, it shows that a it takes more than 26,000 cycle to complete this task, compared with reverse cycle approach taking 16,000. As mentioned earlier, data cannot be forwarded back to the sender to non-back approach. Back processes will increase the probability to be selected to receive data on the basis of 1/7 of 1/8. As can be seen from the plot, non-reverse techniques take shorter time to complete the task as compared to the reverse approach. Non-reverse approach completed in cycles of 33; a shorter cycle than for the reverse approach. This indicates that the non-reverse approach is favourable in the dissemination of data for all agents. The plot also shows that the communication techniques for 2-bit complete faster than with the 1-bit. The graphs also shows a plot for 3-bit communication, where it takes up to 24 cycles to complete this task. The fact is, when using higher bits; the task will be completed faster. From the data, the results are gathered to converge into a linear graph. After obtaining a linear graph for higher-communication, the model can be calculated using a linear equation. This mimic the cue-based approach completed a task in just 14 cycles, as shown in Figure 4(b). In addition, the probability of an agent to change itself depending on the environment is 1. |
| Bit-communication in swarm agents have different results depending on the number of bits used. From the revenue earned in 1-bit communication, it takes up to 26,000 cycles to disseminate data to all agents in the arena. Graphs plotted, taken from the 50 walking simulation for each technique, shows that the 1-bit communication process was like passing a ball in a field. However the 2-bit communication seems to complete quicker. This is because the process of data sent is squared. Each agent can send data to two different agents. It shows that up to 40 cycles will be required to complete the task. The technique of 3-bit communication is faster than the other approaches because the factors that send data are to the power of 3. This means that data can be sent to the three different agents in one cycle. When the process of increased up to 4-bit communication process, it does have a little to improve performance. This shows the performance of the 3-bit communication is better than the communication 1-bit and 2-bit. However, the complexity of the design of higher bit is more because it requires the ability to send data to a number of agents in a single cycle. In terms of cost, this is proportional to the complexity of the design.Communications based on cue is a process of indirect mechanisms. When an agent sees other agents doing a task, the agent will do the same thing. For example, when one ant colony leaves a pheromone for other ants, the other ants will follow. The concept of this approach is just to follow others compared to the previous communication approach that gives direction to others to do something. |
CONCLUSION
|
| The performance using higher communication bit is better in terms of speed but more complex and costly compared to just 1-bit. Implementing indirect communication such as signal-based, will improve performance because the swarm can do the same things as the source. |
Figures at a glance
|
 |
 |
 |
 |
| Figure 1a |
Figure 2 |
Figure 3a |
Figure 4a |
|
| |
References
|
- Ball, P., “The self-made tapestry. Pattern formation in nature.” Oxford University Press, Oxford UK, pp. 287, 1999.
- Beckers, R., Deneubourg, J. L., Gross, S. and Pasteels, J. M., “Collective decision making through food recruitment.” Insects Sociaux,37:258-267, 1990.
- Beekman, M. and Ratnieks, F. L. W., “Long range foraging by the honeybee,”Apismellifera L. Functional Ecology, 14:490-496, 2000.
- Deneubourg, J. –L., Aron, S., Foss, S., Pasteels, J. M. and Duerinck, G., “Random Behaviour, amplification processes and number ofparticipants: how they contribute to the foraging properties of ants,” Physica D, 22:176-186, 1986.
- Detrain, C. and Deneubourg, J. –L., “Complexity of environment and parsimony of decision rules in insect societies,” Biological Bulletin,202:268-274, 2002.
- Tautz, J. and Rohrseitz, K., “What attracts honeybees to a waggle dancer?” Journal of Comparative Physiology A, 183:661-667, 1998.
- Blum, Christian, and Daniel Merkle, eds. “Swarm intelligence: introduction and applications,” Springer, 2008.
- Sumpter, D. J. T. and Beekman, M.,“From non-linearity to optimality: pheromone trail foraging by ants,” Animal Behaviour, 66:273-280,2003.
|
Menu