Team:ZJU-China/Modeling/first


Termite Simulation

Abstract

The last step of wet lab proves the poison effect of toxic proteins and the practicability of the device. After that, before our products come into service, one necessary step is simulating the action of termites, which can prove that toxic proteins work in reality. Also, in order to test the robustness and the effectiveness of the simulation code in an unknown environment, we load some environment images into the code and then test the performance of the code.

Keywords

Ant colony algorithm

Dynamic path planning

Stochastic process


Purpose

In this model, we focus on the simulation of the termite behavior.

Including stochastic process, probability and statistic, ant colony algorithm, our model aims to accurately simulating the behavior of termites.

The highlight of our model is the core algorithm which controls the direction of termites. The control method is different from ant colony algorithm, because ant colony algorithm is an algorithm that learns from the behavior of termites and is used to optimize other function. What we did is to simulate the behavior of termites itself, so we need to control the termites behavior by polar coordinates rather than rectangular coordinates.

As far as we know about termites, they find the food quite quick by the pheromone. The termite which has found the food leaves the pheromone through the way it comes back home. The following termites will probably but not necessarily follow the pheromone. Searching in this way after a period of time, the termites will move and get the food through the almost shortest road.

Solutions

We can get the following solutions from the simulation model:

1. The time spent on finding the food in the exact radius.

2. The consumption rates of food.

Finally, according to the housing structure or the environmental geographic map, we can know the best location to set the food, which is our final target.

Code

The core algorithm

The core algorithm called ChangeDir, which means to control and change the direction of the termites. Every step of the termite movement follows the rules:

1. Calculate the center of mass of the pheromone, and the direction will change between the direction to this center and the original center.

2. Add a gauss distribution on it.

How to estimate the center of mass and judge if it's credible? For the reason that it will significantly influence the result of the simulation, we pay huge attention on it.

First of all, to calculate the center of mass of the pheromone, the termites should get the adjacent value of map. Besides, based on for loop, it’s convenient to get a rectangle, but aim at make it realistic, we change it into a circle. Also, to increase the robustness of the algorithm, we define that the termite moves to the core of the mass of the pheromone only when the distance between the termite and the core is large enough. In the end, the circle is changed into a sector to prevent the termite goes back home half of the way.

Adding a housing structure or an environmental geographic map

First, we input an image (jpg or bmp or png).

Second, we write an AvoidBan function for the termites to avoid ban. We use a while loop to change the termites’ direction continuously. The results of the simulation conform to our conjecture. Without the AvoidBan function, termites will crush in the obstacles, which will not happen in the reality.

After adding the AvoidBan function, we can regard termites as a gather of points controlled by two systems, the AvoidBan function system and the ChangeDir function. In other words, one will control the termites to avoid obstacle, the other will control the termites to find the food.

Normalization functions:

1. Store a map by a matrix will meet an axis transition problem, so we write a MatrixToAxis function to normalize this process. We should always pay attention to this problem when doing the simulation with an input map and output map. Actually, maps in this simulation often are heat maps. (In our simulation is a heat map of pheromone.)

2. To restrict the angle of the termites’ direction from zero to 2 pi, we write a AngleNormalization function.

Other functions:

We write a Plo function to plot the termites with their directions. But it is slower than the plot function when playing the video.

Also, some people associate our model with the ant colony algorithm. Actually, the ant colony algorithm is one kind of optimization algorithm. The key of this algorithm is simulate the actions of ants and uses it to optimize other objective function. In other words, the ant colony algorithm comes from the actions of ants. On the contrary, our function pays attention to the termites and aims to show termites' action in the nature (referring to some studies, the action of termites is the same as ants). That's why our core function so significant and we have rewritten it from time to time.

Simulation

Load house structure image

One significant point of our model is how to link it with the reality. When it comes to solving a specific problem, we can’t simulate on an infinite plane of x-y axis and without any environmental factors or the structure of a building or house.

So the first step we should load an image of a monolayer house structure.

In this step, we found an image from the Internet, which helps to show the results of this model.

The image of a real house structure

After that, we should edit the image and prepare for loading in to the matlab and running the code.

The image after edited

When we load it into the code, we can get the movie of the simulating based on this image. And also, after loading a new image of the house structure, we can simulate again in a new environment.

Why the simulation based on a real environment is significant (why we must build the image interface to load the image into the code)?

The results of the simulation that termites move in an infinite plane of x-y axis are so simple. The stochastic process that termites move in the plane can only tell us the correlativity between the finding time and the distance between termites' nest and the food, which is not enough for us. The correlativity between finding time and the distance is complex in the reality for the reason that walls or doors will be obstacles when the termites are finding food. Also, other environmental factor will play a significant role in this simulation. So the simulation based on a real environment is more realistic and reliable.

Single nest simulation without an exactly image of environment

In order to run the single nest simulation, we define a location where termites come out from it and a location of food source. Termites coming out of the nest will come back after roaming a certain distance. Under the control of the ChangeDir function, the termites in the code act like real termites. Maybe some of termite characters are ignored in our simulation, but we hope that by such kind of hypothesis and simulation, we can reappear the process of termites foraging.

Without an exactly image of environment, the result of the simulation will only be influenced by the distance between food and nest.

So in this part, we mainly change the distance between food and nest and test the influence of it.

Multiple nests simulation

Considering of the situation that a myriad of houses have more than one nest, multiple nests simulation is necessary. In our model, we describe it as two sources of termites, which means termites come out from two locations and move to find food.

A better reflection of reality simulation

When we meet a problem in reality, it often comes with multiple nests and multiple food source. In our model, this problem also can be completely solved. Below, we will show you the simulation based on multiple nests and multiple food source.

After initialization, termites come out from the nest (coordinate (-50,-50) and (100,0) ). There are two coordinates which is the food source (coordinate (80,120) and (50,-30) ). Below is the image of the situation after initialization.

After the first termite finding the food, it leaves the pheromone on the map and the color of the map will change. And we can see some of the paths are obviously on the map.

Here is the heat map after the finding food process:

In the image, the center of the red point is the food source. It also means that the concentration of pheromone there is very high. It’s also the reason why the termites can find the food efficiently.

Simulation process

Results

The number and the rate of termites which have found the food

After running the code, we plot two figures of results. There are the figure of the number of termites which have found the food and the rate of it. The simulation above will get the figures below.

The first figure only consider the number of the times of termites finding the food, but in the second figure:

$$termites \quad number \quad rate = \frac{termites \quad number \quad (in \quad first \quad figure)}{iteration \quad number \quad (alse \quad means \quad the \quad time)}$$

Below are images of Simulation of the device:

First time:

Second time:

Below are images of distance testing of device:

1. nest (75,-50) device center(75,-125)

2. nest (75,0) device center(75,-125)

3. nest (75,50) device center(75,-125)

Compare the figure below, we know that the distance increases, and the number of termites which find the food source decreases.

Below are images of angle testing of device:

1. angle = 0

2. angle = 30

3. angle = 60

4. angle = 90

Simulation of the house structure

initialization

After initialization, termites move and search for the food.

A screen capture of the simulation, the white points in the image of the termites which move as time goes by.

Simulation of the device

The teammate who designs the device points out the importance of the termite simulation based on the shape of the device. So at the end of simulation, we add this part of content to show the result of simulation based on the shape of the device.

First, we get two images of the device. One is the image of the food source, the other is the image of the device frame. In the following image, we put these two images together.

Above is the image that we just told about. The line and the circle in grey is the food source and the black is the frame of device.

Using the same method to load the image, we get the initialization in the matlab.

As the termites find the food, the color of the map, the heat map of the pheromone, will change the color. It also means we update the map in every step as the termites move. At the end of the simulation, we print the final image. The path where termites have gone by changes color. So the final image, the heat map of pheromone, also shows the path that most of termites went by.

As you can see on the following image, the hole on the device will play a significant role on deciding paths of termites.

Changing into black background will help you observe the paths:

Testing of distance

1. nest (75,-50) device center(75,-125)

2. nest (75,0) device center(75,-125)

3. nest (75,50) device center(75,-125)

..

The distance will be an significant factor to control the results.

Testing of angle

The angle of the food also influences the results, because the device is in an irregular shape. In other words, Testing of angle is necessary.

In this simulation, the distance between the food source and the nest is a constant value. After testing of distance, we find the setting distance = 125 is reasonable. So in the testing of angle, distance = 125 and we change the angle from 0 degree to 90 degree.

0 degree:

30 degree:

60 degree:

(first time)

(second time)

When the angle is 90 degree, the number get small.

close up:

Analysis:

Angle is a less significant factor in our simulation, because it will not influence the results obviously. But as we can see from the results, the angler gets larger, the termites number decrease. We think that it is because the viewing angle from the nest to the device is decreasing as the angle is increasing. And the viewing angle influence a lot, such as the probability of the termites to find the food source by stochastic process.

Comparison

In order to prove that the pheromone left on the path really will help termites to find the food, we compare termites’ action between which are under the influence of pheromone and which are not.

Without leaving the pheromone on the map, termites will change direction randomly. Based on such kind of movement, the rule that the finding food time is only decided by the distance is still right.

But it also can be proved that without leaving the pheromone on the map, termites can’t find the food as fast as those under the assistance of pheromone.

Firstly, without the pheromone, termites move randomly. In that case, if the distance between the food source and the nest is constant, as the simulating time increases, the number of termites which have found the food will increase. Actually, the relationship between them is a directly proportional relationship.

But with the control of the pheromone, as time increases, the relationship will not be a directly proportional relationship. It will like an exponential relationship in our assumptions. However, what the relationship exactly is? We should do some simulations to find out it.

According to our assumption, we should ensure the distance is a constant and change the simulating time, after comparing the results of them we should get the solutions.

Simulation time = 500

Simulation time = 1000

Simulation time = 2000

Simulation time = 5000

(first)

(second)

(third)

(fourth)

Simulation time = 10000

(first)

(second)

(third)

(fourth)

Simulation time = 20000

(first)

(second)

After more simulation, we get more data and plot the figure:

Getting the mode of each Iteration number, we get the figure below,

Improvement

In the comparison part, we find that the robustness of our simulation can be improved. It also tells us that the result will be more stable if we increase the simulating time. From the point of view of reality, at the same environment, the costs of the foraging time will not be the same. In a certain environment, influenced by a myriad of factors, this process will be very complex. For example, the time of the first termite to find time food will make a huge impact. That’s because that the first termite foraging is a random event which is without the control of pheromone. It is our idea that without considering this period of time can make the simulation more precise.



introduction
termit