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

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

Xiujuan Lei (Shaanxi Normal University, China), Fei Wang (Shaanxi Normal University, China) and Ying Tan (Peking University, China)
DOI: 10.4018/978-1-4666-9572-6.ch011
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Mobile robot path planning is generally a kind of optimal problems, which is to find a best path of a track between a starting point to a goal point in the constraint conditions. Mobile robot path planning can be divided into two categories according to different environment planning awareness information: one is the global path planning and the other is the local path planning. We employed ACO, PSO, FA, FOA, FWA and ABC swarm intelligent optimization algorithms to optimize the global and local path planning of mobile robot, and gave the detailed implement steps and the comparing results to show the feasibility of using swarm intelligence optimization algorithms to solve the robot path planning problems.
Chapter Preview
Top

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).

Key Terms in this Chapter

Particle Swarm Optimization Algorithm: An algorithm that is a simulation of birds foraging process.

Start Point: An original position that the mobile robot is locating and preparing for moving.

Fruit Fly Optimization Algorithm: An algorithm that simulates the foraging behavior of fruit flies.

Firework Algorithm: An algorithm that simulates the process of fireworks exploding.

Target Point: A final position that the mobile robot is moving to.

Artificial Bee Colony Algorithm: An algorithm that simulates the foraging behavior of bee colony.

Mobile Robot: An automatic mechanical that can move and select the direction all by itself.

Firefly Algorithm: An algorithm that simulates the luminescence properties of fireflies based on the group search.

Complete Chapter List

Search this Book:
Reset