This is my final project for the CS580 AI class, submitted December 2011. The project is an ant colony simulation program that focuses on principles of usability to introduce novice programmers (or non-programmers) to the idea of emergence in an open environment while also allowing experienced users to manipulate the simulation parameters to achieve specific optimization goals.
Real-life ants are relatively simple insects that don't do much that humans would call intelligent. In fact, most of their behaviors are basic reflexes to their immediate environment. However, ant colonies as a whole exhibit extremely complicated behaviors, accomplishing difficult tasks that no single ant could do by itself. For example, no single ant has a map telling it how to get from the nest to food and back again, yet the colony accomplishes exactly that- all while navigating an ever-changing environment of obstacles, hazards, and kids with magnifying glasses.
The emergence of these complex behaviors has inspired the artificial intelligence field to think about old problems in a new way. Instead of investing massive resources into smarter individual agents that know or can learn everything about an environment, researchers can release many simple agents and let their simplistic behaviors combine to accomplish complicated goals.
Ants navigating a complex environment.
The gist of this algorithm is as follows:
- Ants start at the nest and travel randomly.
- As they travel, ants leave behind pheromones that lead back to the nest.
- When an ant stumbles upon food, it follows the pheromone trail back to the nest, leaving behind another pheromone trail leading back to the food.
- If an ant finds a pheromone trail, it follows it to the food.
- Pheromones evaporate over time, and it takes ants more time to traverse longer paths. Therefore, longer paths eventually dissipate as shorter paths are favored.
Given the probabilistic nature of the algorithm (ants have a chance to explore cells with no pheromones), the algorithm adapts in real time to dynamic environments.
Ants find food, then navigate around a new obstacle, then discover a closer food has been placed.
This algorithm contrasts with the more traditional, deterministic search algorithms. However, the ant colony search algorithm can be used to solve classic search problems, such as the travelling salesperson problem (given a starting location and a set of goals, how do you find the shortest path from the start, through every goal, and back to the start?). This program introduces a system that uses unique pheromones for each food/goal, and by enforcing a rule that ants must find every one before returning to the nest, they come up with reasonable (though admittedly not always optimal) solutions to the problem.
A path from the nest, through 25 goals, and back to the nest.
For more information, feel free to read the accompanying research paper or the wikipedia article on ant colony optimization, or better yet, start playing with the program! My intention was for this to be usable enough for novices to jump in and start exploring the ideas of emergence, so I'm hoping all of the features that crept in did not eclipse that goal. What types of environments are the ants good at solving? What types are they bad at solving? What happens if you make a drastic change to the environment halfway through? Sorry, there's no magnifying glass in this version... maybe in version two!