Definition: An Artificial Immune System (AIS) is a program modeled after the human biological immune system which can be applied to a large number of analytical problems. The AIS program consists of components referred to as “Antibodies” which seek out and destroy a specified target or “virus”. These antibodies are capable of communicating with one another, increasing the efficiency of their search. Furthermore, each antibody undergoes clonal selection and mutation throughout each iteration of the program, increasing efficiency each time.
For this project, I applied the Artificial Immune System problem solving method to a virtual Mine Detection (MD) problem. So the mines are the “virus” that the agents are searching for in a confined virtual space. Both the AIS and MD programs were created using Matlab.
To help clear things up, here is a basic list of steps the program follows:
- Generate a virtual mine field and populate random locations with a set amount of mines.
- Generate an initial population of antibodies (approximately twice the number of mines) and populate random empty locations in the mine field.
- Antibodies search for mines until all are cleared.
- Perform clonal selection to generate high affinity clones.
- Mutate clones at a high rate to ensure randomness is still present.
- Remove antibodies whose fitness value is below a predefined threshold.
- Introduce randomly generated antibodies into the population.
- Repeat steps 3-7 until the highest fitness population possible is created.
The following is a graphic representation of the virtual mine field I created, containing both antibodies and mines. The green squares represent mines, the red squares represent antibodies, and the blue is just empty space.
During the processing of the program. All of the red antibodies move about the defined area, searching for the mines. When any antibody detects that it is adjacent to a mine, it stops moving. When a mine is successfully surrounded by four antibodies in any of the 8 spaces surrounding it, the mine is deleted or “diffused”. The initial antibodies are programmed to move randomly and do not communicate or undergo clonal selection or mutation. This was done intentionally to determine the baseline efficiency of completely random movement of the antibodies.
Here is a video of the baseline solution:
Several additional features were coded into the antibodies, one at a time, to determine the efficiency increase provided by each attribute. These features include fitness based diffusing, communication ,clonal selection, and mutation.
Fitness based diffusing assigns a random point value to the initial population of antibodies. This makes some antibodies better at diffusing mines than others. Therefore, the antibodies with a higher fitness value can diffuse a bomb with fewer other antibodies helping. Additionally, a higher fitness value gives the antibody a better chance of carrying over into the next population, effectively increasing the overall fitness of the antibody population with each iteration of the program.
Communication allows any antibody that detects a mine, to “call out” to any other antibodies within a 3 block radius of itself. Upon being called, nearby antibodies will gradually make their way to the coordinates of the mine detected. As seen in the video later, this drastically increased the speed at which mines are found.
This video demonstrates the added quickness with which the antibodies are capable of clearing the mine field compared to the previous video:
Clonal selection and mutation are where the Artificial Immune System aspects really come into play. Clonal selection takes the two antibodies from the previous generation with the highest fitness value, and uses them as “parents” of the new generation. This creates clones with a higher average fitness than the last population. These clones are then mutated at a high rate, so as to ensure that some randomness is still introduced into the population. The randomness allows for the possibility of newer, more effective antibodies than even the parents of the current generation. This ensures that the population of antibodies is constantly changing and searching for a better “solution” through randomness.
The following graph represents the increase in efficiency with each function added to the antibodies. It can be seen here that the introduction of communication between antibodies allowed for the single greatest increase in efficiency across all added features. The first data point represents the baseline efficiency mentioned earlier. The last data point represents the highest efficiency reached with all AIS components in place.
And finally, here’s a video to show how the final solution works. This iteration is a bit more convoluted due to the limits of the color scheme and display methods used. The antibodies change color to represent their respective fitness value. You will see that, after many iterations, the population is mostly the same color. This shows the progress towards the highest fitness value. The mines in this video are unfortunately almost the same color as the background, but are still easily spotted since they are stationary.
The applications of this project are not limited to a virtual environment. With the right robotic equipment, the Artificial Immune System problem solving method could be used in military endeavors to clear real world mine fields far faster than manual methods. Also, with emerging nanotechnology, human immune systems could be supplemented with nanobots running an artificial immune system program.
This project was created for my Artificial Intelligence course and I, Mike Thomas, am the sole contributor.
If you enjoyed reading about this project, here is a great site showing how a genetic algorithm can improve the design of a car over time: boxcar2d