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

• Published in: Neurocomputing (Amsterdam) 2013-03, Vol.103, p.172-185
• Main Authors: Zhang, Yong, Gong, Dun-wei, Zhang, Jian-hua
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Algorithms; Applied sciences; Computer science; control theory; systems; Constraints; Control theory. Systems; Danger source; Exact sciences and technology; Fires; Mathematics; Multi- objective optimization; Navigation; Optimization; Particle swarm optimization; Path planning; Probability and statistics; Risk; Robot path planning; Robotics; Robots; Sampling theory, sample surveys; Sciences and techniques of general use; Statistics; Theoretical computing; Uncertainty
• ISSN: 0925-2312; 1872-8286
• DOI: 10.1016/j.neucom.2012.09.019

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 effectiveness. Finally, simulation results demonstrate the capability of our method to generate high-quality Pareto optimal paths.