Abstract

Path Planning is a widely studied issue due to its several applications in robotics, relief planning, trade route planning, and even in the video game industry. The path planning techniques are therefore diverse, seeking to solve problems in unknown environments until finding a trail with the smoothest navigation. Unfortunately, this diversity provokes that some methods overlook certain aspects by attending to a specific-purpose problem, limiting characteristics such as execution time, adaptability behavior, and environment representations. The current project aims to design a path planning algorithm based on Ant Colony Optimization (ACO), which considers improvements for these limitations. The experiments followed an incremental style. Starting from a basic algorithm, we add some global and local interventions. Then, we selected the configurations with the best performance to define our final proposal and compare it with other already known methods. Finally, we display some results in a graphic simulation (using Unity3D) to showcase its adaptive behavior. The algorithm generates promising results with an accuracy of around 95%, proving to solve the limitations mentioned above.

Video (Unity3D)

Global Interventions (Random Walks)

We perform global interventions known as Random Walks, impacting the whole pheromones distributions. These random walks are proposed as pheromones initialization techniques to provide an advantage at the beginning of the algorithm.

Indeed, a random walk enables initial controlled randomness, which helps to encourage a controlled trade-off between exploration and exploitation in the early steps of the algorithm. Furthermore, we hypothesized that these methods would reduce the convergence time and produce solutions closer to the optimal.

We proposed two different tendency random walks: Proximity Random Walk (PRW) and Random Nodes Walk (RNW).

Proximity Random Walk is purely based on a distance heuristic to the target called proximity to choose the next node with a probability (r_ij).

Random Nodes Walk is a two-step process based on a random nodes selection and the proximity random walk mentioned above. The idea is to randomly select nodes with probability (s_i) and connect the floating nodes by PRW.

Local Interventions

The local interventions help us to control ants' behavior when confronted with obstacles during execution time. The principal problem of adding many obstacles is that it can generate several stuck conditions that delay the algorithm and even prevent it from converging. We proposed three interventions: local search, partial path decay, and neighbour decay.

Local Search
We perform a local search to find nodes that produce a stuck condition and prevent access to these positions (or, as we called, forbid the given nodes).

Partial Path Decay
We perform an uneven pheromone decay on a portion of the path each time an ant gets stuck. As a result, we promote roads of less exploration in the long run.

Neighbor Decay
We perform an uneven pheromone decay on neighbor nodes around the stuck node each time an ant gets stuck. As a result, we promote regions of less exploration in the long run.

Results

Our algorithm works in a graph representation, so it is easy to extrapolate the two behavior previously mentioned into a three-dimensional environment. Particularly, we experimented with four different topographic instances: mountain, valley, double valley, and Perlin noise graphs

We evaluated the performance of the algorithms using a PCA mechanism and defining the following evaluation metrics:

Execution Time (ET)

Total Iterations (TI)

Ground Truth Percent (GT)

Stuck Roads (SR)

Nodes Exploration (NE)

Edges Exploration (EE)

Useful Exploration (UE)

Additionally, we explored some evaluation metrics in isolation to confirm PCA results.

Graphic Simulation
Finally, we perform a graphical simulation using Unity3D to verify our findings. Specifically, we examined how our algorithm would perform when obstacles suddenly appear.

Related links

- The Ant Colony System algorithm (basic algorithm) used in this work is defined in "Ant colony optimization." by Dorigo M. et al..
- Review Path Planning Simulation in Controlled Environments using the Ant Colony Optimization Algorithm for an overview of path planning problems and multiple ways to solve them.

Citations

Powered by Jon Barron and Michaël Gharbi.