AntSim

Note: Although it contains some background information related to Ant Colony Optimisation, this article is about a graphical simulator I wrote for research purposes related to ACO and is not so much about the actual research itself.  For those interested in ACO and the various algorithms, I include a list of references at the bottom of this page (you are also very welcome to contact me).

Jump to: AntSim in Action / Downloads / References

Introduction

Ant Colony Optimisation forms part of the Swarm Intelligence paradigm, an artificial intelligence paradigm founded on the principles that collective intelligence emerges from the interaction of distributed, decentralised groups of simple agents. The ACO meta-heuristic, a common framework designed to be applied to the development of applications making use of the Ant System algorithm is a heuristic approach to the solution of combinatorial optimisation problems.

“AntSim” was developed for a research project of mine titled: “Utilising swarm intelligence to navigate the shortest route between a known starting and unknown destination position in an unknown, hazardous terrain”.  In my research, I showed that an application of an ACO algorithm in conjunction with the use of “smart” pheromones consistently found shorter routes between known starting points and unknown destinations in unknown, hazardous terrains (than random search could) and also that the inclusion of smart pheromones provided better results than simply using ACO without the benefits of the additional information these pheromones provided.

The Simulator

Application

The virtual simulation (AntSim) was designed and implemented as a GUI-based software application that uses a version of the Ant System algorithm in order to solve the previously mentioned research problem. The application consists of two separate layers namely, (1) the GUI interface and graphical representation of the world, agents, etc. which makes use of, and is dependent on, the cross-platform Qt/C++ framework and (2) the algorithmic and supporting logic implemented in “pure” C++ 11 with no further dependencies on any other Qt modules or third-party libraries.

The application allowed me to build graphical 2D worlds within which the foraging agents (“AntBots”) executed their search and also allowed me to set and adjust the various input parameters used by the simulation, the world and the AntBots during search executions. The application was furthermore responsible for gathering raw data for each search run (a “run” commenced as soon as the first AntBot was spawned and ended when the allotted time for the search execution had elapsed) as well as the logging of said data to file. All data gathering and logging activities were automated in order to optimise and simplify these processes.

World

“AntWorlds” are built with the aid of the application interface and are represented by 2D terrain grids consisting of square, graphical world tile objects. Possible tile types are:

  • spawn points – AntBot “nests” or starting points (purple)
  • walls – non-traversable tiles (blue)
  • hazards – “killing” tiles, AntBots coming into contact with a hazard tile are deleted and removed from the world (red)
  • paths – traversable tiles (white)
  • targets – AntBot “food” or destination points (green)
AntSim Graphical Application Interface and Unpopulated World
AntSim Graphical Application Interface and Unpopulated World

The world itself owns all AntBots and pheromones and ensures that search logic, AntBot movement and pheromone updates are synchronized at regular user-specified intervals or “ticks” (e.g. a tick rate of 5 ms means that the world as well as all AntBots and pheromones execute their respective logic every 5 ms).

Restrictions and Limitations

  1. Each world must have exactly one spawn point and one search target, but can have any number of walls, paths and hazards.
  2. A world will always contain a valid foraging target and the foraging target will always be reachable (in other words the AntBots will never engage in exercises of foraging futility).
  3. Once a run has started, the application will not accept changes to the environment or input variables, i.e. the foraging target, hazards and obstacles will remain stationary, the world’s size will remain fixed and none of the input variables can be altered – worlds remain static for the duration of the run.
  4. AntBot movement within the world is restricted to a single North, South, East and West step per AntBot per update cycle. No diagonal movement is allowed.

Pheromones

For this experiment, “smart” pheromones were introduced which are a simple variation on standard pheromones; in addition to knowing their position and density, smart pheromones also know their type:

  1. “Food” pheromones – these pheromones are dropped and updated by AntBots on paths leading from the source to the search target.
  2. “Hazard” pheromones – these pheromones are dropped next to hazardous tiles as warnings.

Hazard pheromones were not subject to evaporation since they come at the cost of an AntBot, but all food pheromones evaporate as per the standard Ant System pheromone evaporation equation (Dorigo & Socha 2006).

Both types of pheromone influenced AntBot behaviour, food pheromones were used to determine a tile’s probability of selection during the AntBot foraging update cycle and hazard pheromones acted as warnings to prevent further AntBot casualties around hazardous tiles.

AntBots

AntBot movement is dictated by a combination of the Ant System probability equation (Dorigo & Socha 2006) and randomised tie-breaker heuristics. For the purposes of this experiment, the standard AS probability equation was adjusted slightly (simplified) to determine the tile probability of selection (for tiles containing “food” pheromone).

In order to ensure that tie-breakers were built into the decision logic, a global probability range was introduced as a basis for ranking tiles’ probabilities of selection. Non-traversable tiles as well as those containing hazard pheromones (see “Pheromones” above) are assigned a zero probability of selection and tiles that an AntBot visited recently are subject to penalties lowering their probability of selection (unlike hazards and non-traversable tiles, these tiles are not entirely eliminated as possible destinations, a requirement for consistent, randomised AntBot behaviour) preventing AntBots from getting stuck and “stuttering” back and forth between neighbouring tiles. The decision logic that each AntBot runs through per update cycle is therefore the following:

  1. For each N, S, E, W tile neighbouring the AntBot’s current position, calculate the neighbouring tile’s probability of selection based on tile type and pheromone density:
if the tile is a hazard or wall tile or contains a hazard pheromone (i.e. not allowed/traversable)
   return 0;
if the tile was recently visited
   apply recently visited penalty factor to global probability range
calculate and return the probability of selection from the (possibly adjusted) global probability range
  1. Normalise all probabilities with respect to the global probability range and sort the probabilities in ascending order (e.g. let’s assume the total global range is 0 – 10 and the four neighbouring tiles, N, S, E and W have normalised probabilities of selection of 5, 3, 9 and 0 respectively. Then, upon ordering the probabilities, W will have no probability of being selected, S will span the 1 – 3 range of being selected, N the 4 – 5 and E the 6 – 10).
  2. Randomly select a value from within the global probability range so that AntBots will keep exploring alternative routes and not always select the tile with the highest probability of selection (continuing the example from step 2, assume the randomly selected probability is 4).
  3. Find the tile whose local probability range includes the randomly selected value (continuing the example from steps 2 and 3, this will mean that tile N will be selected).
  4. Move to that tile.

Note: The larger the global probability range is, the finer the decision resolution and the less likely the odds of two tiles having the same probability of selection. In the unlikely event that two or more tiles end up having the same probability of selection, the first one encountered in the sorted list is selected.

Internal Graph

AntBots have no knowledge of their worlds other than that gained during their exploration of them and each AntBot maintains a simple internal graph for itself consisting of nothing more than its own known shortest route from source to destination, provided it has discovered the target. Each time a previously unknown tile is encountered, it is added to the graph and whenever a known tile is revisited, the entire loop leading up to that point (i.e. all the nodes accumulated since the last time the tile was visited) is eliminated from the graph (the reason being that the target obviously wasn’t discovered along the loop or else the tile would never have been revisited, it is pointless to remember “x” nr of nodes that are not contributing to the shortest source-target path). The internal graph is completed by the AntBot’s discovery of the target and this destination tile becomes the first node on the return path to source.

Foraging and Pheromone Activity

Once an AntBot has discovered the target, it returns to the source via its internal shortest path (the internal graph discussed above), dropping food pheromones along the way. As soon as the AntBot returns to the source it restarts its foraging activities, but continues to contribute to pheromones along its known source-target path (this contribution will obviously be indirect since the AntBot’s position and those of the pheromones will not necessarily coincide) until such time as it re-discovers the search target (if at all), where after its internal graph may be reset depending on whether or not the newly discovered source-target path is shorter than the previously known (to the AntBot) shortest path. If the new path is shorter, “old” pheromones are forgotten and no longer contributed to and the process of dropping pheromone on the way back to the source from the target is repeated.

Finally, upon encountering a hazardous tile, an AntBot will drop a hazard pheromone that serves as a warning to other AntBots to stay clear of the hazard. This pheromone comes at the cost of the AntBot itself which is deleted from the world on the next update cycle, effectively “killing” it and thereby preventing further updates from the AntBot to pheromones it may have been contributing to.

AntSim in Action

Now that you know how it works, watch the little guys in action:

Downloads

The GUI aspects of AntSim was originally very specific to my needs. However, I have removed most of the project specific logic and have decided to release the GUI code along with the “back-end” logic, warts and all (in other words, you won’t get exactly what you see in the video).

The source code is available on GitHub and the documentation is right here

If you just want to play with the app, just let me know and I’ll see what I can do for your operating system.

Enjoy!

References

Angus, D., 2005. Solving a unique Shortest Path problem using ant colony optimisation. Communicated by T. Baeck.

Blum, C., 2005a. Ant colony optimization: Introduction and recent trends. Physics of Life reviews, 2(4), pp.353–373.

Blum, C., 2005b. Beam-ACO Hybridizing ant colony optimization with beam search: An application to open shop scheduling. Computers & Operations Research, 32(6), pp.1565–1591.

Bullnheimer, B., Hartl, R.F. & Strauss, C., 1997. A new rank based version of the Ant System. A computational study.

Cordon, O. et al., 2000. A new ACO model integrating evolutionary computation concepts: The best-worst Ant System.

Dorigo, M., Birattari, M. & Stutzle, T., 2006. Ant colony optimization. Computational Intelligence Magazine, IEEE, 1(4), pp.28–39.

Dorigo, M. & Di Caro, G., 1999. Ant colony optimization: a new meta-heuristic. In Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on.

Dorigo, M., Caro, G.D. & Gambardella, Luca M, 1999. Ant algorithms for discrete optimization. Artificial life, 5(2), pp.137–172.

Dorigo, M. & Gambardella, Luca Maria, 1997. Ant colony system: A cooperative learning approach to the travelling salesman problem. Evolutionary Computation, IEEE Transactions on, 1(1), pp.53–66.

Dorigo, M. & Socha, K., 2006. An introduction to ant colony optimization. Handbook of approximation algorithms and metaheuristics, pp.26–1.

Fountas, C., 2010. Swarm Intelligence: The Ant Paradigm. In Multimedia Services in Intelligent Environments. Springer, pp. 137–157.

Fox, B., Xiang, W. & Lee, H.P., 2007. Industrial applications of the ant colony optimization algorithm. The International Journal of Advanced Manufacturing Technology, 31(7-8), pp.805–814.

Gao, M., Xu, J. & Tian, J., 2008. Mobile robot global path planning based on improved augment ant colony algorithm. In Genetic and Evolutionary Computing, 2008. WGEC’08. Second International Conference on. pp. 273–276.

Garcia, O.C., Triguero, F.H. & Stützle, T., 2002. A review on the ant colony optimization metaheuristic: basis, models and new trends. Mathware \& Soft Computing, 9(3), pp.141–175.

Graham, R., McCabe, H. & Sheridan, S., 2003. Pathfinding in computer games. ITB Journal, 8.

Koenig, S. & Liu, Y., 2001. Terrain coverage with ant robots: a simulation study. In Proceedings of the fifth international conference on Autonomous agents. pp. 600–607.

Martens, D., Baesens, B. & Fawcett, T., 2011. Editorial survey: swarm intelligence for data mining. Machine Learning, 82(1), pp.1–42.

Mocholi, J.A. et al., 2010. An emotionally biased ant colony algorithm for pathfinding in games. Expert Systems with Applications, 37(7), pp.4921–4927.

Rivera, G.G.A., 2012. Path planning for general mazes.

Stutzle, T. & Hoos, H.H., 2000. MAX-MIN ant system. Future generations computer systems, 16(8), pp.889–914.

One Reply to “AntSim”

  1. Very cool. Video nice and can see that each movement of an ant is completely random. As soon as soon as the food source is found it actually speeds back to the spawning point and retries.wow

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s