Improved ant colony optimization algorithm based on islands type for mobile robot path planning

Abstract

According to the characteristics of ant colony optimization (ACO) algorithm in mobile robot path planning, such as local optimal solution, slow convergence speed, low search efficiency, and propensity to produce numerous deadlock ants, an improved ACO algorithm based on island type (insular ACO (INACO)) is introduced. In this algorithm, firstly, several islands are established between the starting and the ending position of environment, serving as intermediate nodes for the paths searched by the ants. This greatly reduces the number of deadlock ants. Additionally, rectangular areas are initialized with non-uniform pheromone levels between adjacent islands, while other areas are set to a constant minimum pheromone value. This prevents blind searches during the initial stages of path planning. Furthermore, an adaptive volatilization coefficient is introduced into the global pheromone update rules to balance the convergence and global search ability. Finally, optimal parameter combinations of INACO are determined by simulation. INACO algorithm is simulated in various grid maps and compared with other improved ACO algorithms. Results demonstrate its superior global optimal search capability and rapid convergence speed. The average iterative times is 2.7 in a 20 × 20 grid environment and 4.7 in a 30 × 30 grid environment. Notably, INACO produces very few lost ants, with mean values of 50.1 and 95.2 in 20 × 20 and 30 × 30 grid environments, respectively.