Grid-Based Pathfinding Using Ant Colony Optimization Algorithm

Abstract

The unique behavior of ants has inspired a number of methods, and ant colony optimization (ACO) method has been the most successful general-purpose optimization technique. The ant colony metaheuristic has been shown to be effective in solving complex problems such as combinatorial problems and NP-Hard problems, frequently producing the best solution in the shortest time. However, ACO has received insufficient attention as a way of solving problems with optimal solutions that can be found using other approaches. The pathfinding problem is without a doubt one of the most important areas of navigation and telecommunications. Ants release chemical substances known as a pheromone in the ground while searching for food to mark a path that is preferred by them, and other ants will get a hint about which path to follow from the strong smell of pheromone. The ACO algorithm uses a similar mechanism. So, in ACO, solutions to an optimization problem are being created by a group of artificial ants by exchanging information on their quality using a communication mechanism that is similar to actual ants. In this paper, an approach to implement the ACO algorithm for pathfinding in a 2D grid as the search space has been proposed.