Robot path planning in uncertain environment using multi-objective particle swarm optimization

In many real-world applications, workspace of robots often involves various danger sources that robots must evade, such as fire in rescue mission, landmines and enemies in war field. Since it is either impossible or too expensive to get their precise positions, decision-makers know only their action ranges in most cases. This paper proposes,a multi-objective path planning algorithm based on particle swarm optimization for robot navigation in such an environment. First, a membership function is defined to evaluate the risk degree of path. Considering two performance merits: the risk degree and the distance of path, the path planning problem with uncertain danger sources is described as a constrained bi-objective optimization problem with uncertain coefficients. Then, a constrained multi-objective particle swarm Optimization is developed to tackle this problem. Several new operations/improvements such as the particle update method based on random sampling and uniform mutation, the infeasible archive, the constrained domination relationship based on collision times with obstacles, are incorporated into the proposed algorithm to improve its effediveness. Finally, simulation results demonstrate the capability of our method to generate high-quality, Pareto optimal paths. (C) 2012 Elsevier B:V. All rights reserved.