The Ant Colony Optimization for Robot Path Planner in C++
The Ant Colony Optimization (ACO) metaheuristic algorithm was inspired by nature (ant colony behavior). Marco Dorigo pioneered the algorithm. Here you can find his book.
The article focuses on solving two optimization problems in the graph. I solved the most critical problem relevant to the robot path planner, finding the shortest path between the start and the goal in the graph. Additionally, I solved the problem related to the popular problem in the graph, which is defined as Traveling Salesman Problem (TSP).
The implementations of these two problems in C++ you find on my GitHub.
Ant colony optimization
The algorithm can be derived from the behavior of an ant colony. Ants hunt for food by moving away from the nest in search of food to bring back. Pheromones are tiny molecules that each individual ant spread during their travels. Other ants will be drawn to the pheromones, which increases the likelihood that they will follow the same paths as earlier ants.
When the ants find the food, they return to the nest. Every time an ant makes this journey, the pheromone trail is strengthened, making it more appealing and assuring that additional ants join in the activity of obtaining food from the source. The ants alone are unable to find the way on their own. However, that amount of pheromones increases the probability the ant chooses the optimal (shortest) way. Since the ant colony is a dynamic system it includes pheromones degradation parameter — evaporation, which affects the condensation of pheromones over time (as expected the condensation of pheromones decreases over time).
In the context of the algorithm, the pheromone can be considered by ants as an indicator of a “brilliant way to food”.
The most important variable in the discussed algorithm is the update mechanism of the pheromones (the pheromone table) while ants move between nodes in the graph looking for food (goal). The pheromone table is the only interesting “parameter” that allows ant to decide which way is shortest. The table is common for the colony (shared by all ants). The table in the algorithm is updated per iteration after each ant moves to the goal.
The following figure presents a simplified idea of the discussed algorithm. There are two ways to the goal (food) A, B. The length of B is two times longer than A. It means that in the same amount of time the number of ants moving on path A is in principle two times larger.
Going further, as discussed before the ant leaves the pheromone on the path, so path A will have more pheromones on. Finally, the density of pheromones will affect the increase of the probability of choosing the path.
The mathematical formulas of the algorithm, you will find on Wikipedia. Here I will give you the intuition.
The most important is to understand the update of the Pheronomone table and how the ant chooses the next node in the graph.
Thank you for reading.
