Swarm Intelligent Optimization Algorithms and Its Application in Mobile Robot Path Planning

Introduction

Mobile robot path planning had received significant attention in the past few decades. And it was very useful in human’s social activities, for example, if a mobile robot knew which path was best, it could save a lot of time in the implementation of rescue, detection and other tasks. Not only in the mobile robots area, but also in other fields such as the production and normal life, path planning had played a vital role. To solve mobile robot path planning problems, many researchers proposed a lot of methods. According to Jason (1995), a viewed method was proposed. This method regarded mobile robot as a particle, linked the starting point and target point of mobile robot and the apexes of polygon obstacles to a network using lines, which ensure that these lines couldn’t intersect with the obstacles. It was simple but had some disadvantages. If the starting point or the target point was changed, then the network should be rebuilt. And this method was only suitable to polygon obstacles, but not suitable to circular obstacles. After that, Pehlivanoglu (2012) proposed a vibrational genetic algorithm enhanced with a Voronoi diagram for path planning. This method used lines as far away from obstacles as possible to build a connection network, then the possibility that the mobile robot attached obstacles is the smallest.

Castellanos et al. (1998) proposed a grid method that divided the motion environment into rectangular grids with equal size. Assuming that the grid and the mobile robot had the same size, and making that the solid grid with a high value meant obstacle and the hollow grid with a low value meant moving space, then the mobile robot would choose grids with lower value to moving on and elude grids with higher value. Path planning in this way was to find a series of connected grids to link the starting point and the target point. And the size of grid had a significance impact on the time cost of path planning.

There were also some other method in path planning, such as potential field method (Rimon & Doditschek, 1992) and free space method (Fu & Liu, 1990). However, a path planning problem, especially in dynamic and uncertain environment, was an NP hard problem. And the traditional optimization methods had some common disadvantages, such as that the computational complexity was high (Lozano-Perez & Wesley, 1979), the adaptability was lacking and the planning effect was poor (Kevin, 2001). To solve these problems, many researchers used intelligent optimization algorithm to deal with path planning, such as genetic algorithm (Li et al., 1997), artificial neural network (Holenstein & Badreddin E, 1991) and simulated annealing algorithm (Kastella, 1991). Based on these methods, Qu et al. (2013) proposed an improved genetic algorithm with co-evolutionary strategy for global path planning. Duan and Huang (2014) proposed an imperialist competitive algorithm optimized artificial neural networks for unmanned combat aerial vehicle (UCAV) global path planning. Miao and Tian (2013) proposed an enhanced simulated annealing (SA) approach for dynamic robot path planning which integrates two additional mathematical operators and initial path selection heuristics into the standard SA.

Swarm intelligent optimization algorithms are population-based meta-heuristic approaches. They seek near-optimal solutions of the difficult optimization problems by simulating the collective behavior of social insects such as, ant colony optimization (ACO) (Dorigo, & Gambardella, 1997), particle swarm optimization (PSO) algorithm (Kennedy, & Eberhart, 1995; Shi, & Eberhart, 1998), artificial bee colony (ABC) (Basturk, B., & Karaboga, 2006), and firefly algorithm (FA) (Yang, 2008). They have received people’s attention due to their simple ideas and easy operating properties (Kennedy, & Eberhart, 2001).