Ant Colony Optimization (ACO) in Path Planning of Robots


Introduction

The original idea of ACO comes from observing the exploitation of food resources among ants, in which ants’ individually with limited cognitive abilities have collectively been able to find the shortest path between a food source and the nest [T. S. Marco Dorigo, Ant Colony Optimization, London: Bradford Book, The MIT Press Cambridge., 2004].

Ants navigate from the nest to the food source. They eventually find the shortest path to the food source in spite of Ants being blind. In the beginning, ants start moving randomly in the environment. Ants deposit pheromone on the path as they move. Pheromone slowly evaporates with time. Due to this behaviour when more and more ants start moving in the environment randomly, ants that actually had a quicker time to food source have stronger pheromone deposits. This increases the probability of that path being followed. 



ACO Layer for Path Selection

Using this behaviour of ants guided by pheromones in a different way in Path Planner of automated guided vehicles (AGVs). Computing the shortest paths from source to destination in a grid-type layout can be easily done with A* based algorithms. We often have multiple paths from source to destination. While choosing between various paths, the waiting time of robots due to congestion needs to be accounted for in productivity calculations. The pheromones in a particular path, for us, are the cost (waiting time) of taking that path. To reduce the overall cycle time, since we are using the path with least pheromones.

The pheromone values are a function of time. We can accurately predict the pheromone of the segment at different instances of time and as the position of existing robots in the system can be known, we can easily compute the probable pheromone on each grid on a different quantum of time, in a very deterministic way.

  • Each highway, service lane and junction acts like an edge having its own identity. The cost of these edges or segments plays an important role in path selection

  • Each time a robot selects a segment with a certain probability, it drops a pheromone on that segment. The pheromone intensity to be dropped in each segment of a potential path of a robot, is a function of the probability of the robot taking that segment. For each potential path, the relative costs can be converted into a probability of taking that path and its segments. 

    


  • Basic path planning for a typical robot is done using Dijkstra’s or similar algorithms, which give out multiple paths and their respective costs. The best path is selected using the probability function of the ACO, which accounts for the costs of the paths and the cumulative current pheromone values of each segment in the path. At every junction, a robot’s path is reevaluated again, considering the updated pheromone values of the system at that instant.  

  • The powers α and β are constants varied to achieve a balance between the impact of congestion and cost of the different paths. A typical ACO algorithm has both values positive. Particularly in our system, the layout is simple and the impact of congestion increases significantly with more robots added in. A negative α helps in avoiding segments with heavy traffic. Hence, we call the algorithm a Negative α ACO.

  • Once a robot selects a particular path, the immediate segment probability changes to 1, and the probability of the segments which were rejected becomes 0. Similarly, the probability of the subsequent segments of all the potential paths are also corrected and their pheromone values are updated.

  • The total pheromone value of each segment is the summation of the pheromone intensity of each robot potentially taking that segment.

  • The evaporation constant accounts for the balance between the historic trends of the system and the dynamic nature or the randomness of the system. An optimal value can be arrived at with a DOE approach. 


ACO based Multi-Robot Path Planner contains 2 main components:

  1. Cost Map: It is the data structure holding the heuristic length information for each segment in the system map. This map is static and doesn’t change with time.

  2. Pheromone Map: It is the data structure holding the pheromone information for each segment in the system map. This map keeps changing over time.


WHY ACO?

  1. Efficiency: ACO algorithms are highly efficient due to their probabilistic nature, which allows them to explore the search space in an intelligent and adaptive way. Ants deposit pheromones on the paths they travel, and these pheromones evaporate over time. As a result, the paths that are frequently travelled by the ants with food are reinforced with stronger pheromone trails. This reinforcement process guides the ants towards the shortest path to the food source. Similarly, in an ACO algorithm, the pheromone trail represents the quality of a solution and the algorithm updates the pheromone trails based on the quality of the solutions found. This encourages the algorithm to focus on promising solutions and avoid exploring unpromising solutions, which makes the algorithm more efficient.

  2. Robustness: ACO algorithms are highly robust and can handle noisy or incomplete data. This is because the algorithm is designed to adapt to changes in the environment or problem domain. In an ant colony, individual ants may become disoriented or lost, but the colony as a whole is able to find the food source by collectively exploring the environment. Similarly, in an ACO algorithm, individual ants may get stuck in local optima, but the algorithm as a whole is able to find the global optima by exploring the search space in a collaborative and adaptive manner.

  3. Flexibility: ACO algorithms are highly flexible and can be applied to a wide range of optimization problems. They are not restricted to any particular domain and can be used to solve problems in transportation, logistics, scheduling, telecommunications, and many other areas.

  4. Global Optimization: ACO algorithms are capable of finding global optima, which is a major advantage over other optimization methods that can only find local optima. This is because the pheromone trails guide the algorithm towards promising solutions and discourage it from exploring unpromising solutions. Over time, the algorithm converges towards the best solution found, which is often the global optima.

  5. Scalability: ACO algorithms can be easily parallelized, which makes them suitable for solving large-scale optimization problems. By dividing the search space into smaller subspaces and running the algorithm on each subspace independently, the overall computational time can be reduced significantly. This makes ACO particularly useful for solving problems that involve a large number of variables or constraints.

  6. User-Friendly: ACO algorithms are relatively easy to understand and implement. Unlike other optimization methods that require complex mathematical equations or advanced programming skills, ACO can be implemented using simple programming techniques and a basic understanding of the underlying principles. This makes ACO accessible to a wide range of users, including researchers, students, and practitioners.


Approach

To illustrate a simplified version of the approach, consider the layout shown below, where a robot starting from the BLUE DOT has the destination as the RED DOT. 

             Basic Layout                          Optimal Path selection                     Re-routing

  • In the second image, multiple paths with low travel distance, as narrowed down by Dijkstra's algorithm, are highlighted as potential paths that the robot can take to reach the destination. 

  • Using the ACO algorithm, we arrive at the most optimal path (highlighted in green), or the path with the combination of least total congestion and cost. 

  • As the robot finishes the first segment, and reaches junction C, the system reevaluates the available paths and the ACO algorithm now identifies a different path to be most optimal. This approach is more advanced, I call it “Junction based replanning with ACO”.


Summary

  1. ACO algorithm, which is inspired by the behavioural patterns of ants navigating from their nest to the food source. In spite of Ants being blind, they navigate from the nest to the food source by eventually finding the shortest path by depositing pheromones on the path as they move. Pheromone slowly evaporates with time and hence paths with quicker time to the food source have stronger pheromone deposits. This increases the probability of that path being followed. 

  1. Setup with 100s of robots moving together, along with the distance, congestion plays a big role in robot cycle time. Using the pheromone concept to account for Real Time Congestion and a modification in the probability function of the ACO, I arrive at the most optimal path or the path with the combination of least total congestion and cost. 

  1. ACO has been successfully applied to a wide range of optimization problems, including the travelling salesman problem, the vehicle routing problem, and the job shop scheduling problem. The algorithm has several advantages over other optimization algorithms, including its ability to handle multiple objectives, constraints, and uncertainties. It is also designed to find the global optimum solution, rather than getting stuck in local optima.

  1. ACO has been extended and modified in various ways to improve its performance and applicability. For example, Ant System (AS) is a variant of ACO that uses a simple pheromone update rule and a stochastic decision rule. Ant Colony System (ACS) is another variant that uses local search and an additional pheromone trail to guide the ants. MAX-MIN Ant System (MMAS) is a variant that uses a dynamic pheromone trail update rule to balance exploration and exploitation. Additionally, ACO has been combined with other optimization algorithms, such as genetic algorithms and particle swarm optimization, to create hybrid optimization algorithms.