logo

SCIENCE CHINA Information Sciences, Volume 61, Issue 5: 052204(2018) https://doi.org/10.1007/s11432-016-9115-2

Path planning for mobile robot using self-adaptive learning particle swarm optimization

More info
  • ReceivedDec 20, 2016
  • AcceptedMay 16, 2017
  • PublishedNov 15, 2017

Abstract

As a challenging optimization problem, path planning for mobile robot refers to searching an optimal or near-optimal path under different types of constrains in complex environments. In this paper, a self-adaptive learning particle swarm optimization (SLPSO) with different learning strategies is proposed to address this problem. First, we transform the path planning problem into a minimisation multi-objective optimization problem and formulate the objective function by considering three objectives: path length, collision risk degree and smoothness. Then, a novel self-adaptive learning mechanism is developed to adaptively select the most suitable search strategies at different stages of the optimization process, which can improve the search ability of particle swarm optimization (PSO). Moreover, in order to enhance the feasibility of the generated paths, we further apply the new bound violation handling schemes to restrict the velocity and position of each particle. Finally, experiments respectively with a simulated robot and a real robot are conducted and the results demonstrate the feasibility and effectiveness of SLPSO in solving mobile robot path planning problem.


Acknowledgment

This work was supported by National Basic Research Program of China (973 Program) (Grant No. 2013CB035503).


References

[1] Volos C K, Kyprianidis I M, Stouboulos I N. A chaotic path planning generator for autonomous mobile robots. Robotics Autonomous Syst, 2012, 60: 651-656 CrossRef Google Scholar

[2] Chaari I, Koubaa A, Trigui S, et al. SmartPATH: an efficient hybrid ACO-GA algorithm for solving the global path planning problem of mobile robots. Int J Adv Robot Syst, 2014, 11: 399--412. Google Scholar

[3] Zuo L, Guo Q, Xu X. A hierarchical path planning approach based on A ? and least-squares policy iteration for mobile robots. Neurocomputing, 2015, 170: 257-266 CrossRef Google Scholar

[4] Wu Y, Qu X J. Path planning for taxi of carrier aircraft launching. Sci China Technol Sci, 2013, 56: 1561-1570 CrossRef Google Scholar

[5] Li G S, Chou W S. An improved potential field method for mobile robot navigation. High Technol Lett, 2016, 22: 16--23. Google Scholar

[6] Miao H, Tian Y C. Dynamic robot path planning using an enhanced simulated annealing approach. Appl Math Comput, 2013, 222: 420--437. Google Scholar

[7] Tsai C C, Huang H C, Chan C K. Parallel Elite Genetic Algorithm and Its Application to Global Path Planning for Autonomous Robot Navigation. IEEE Trans Ind Electron, 2011, 58: 4813-4821 CrossRef Google Scholar

[8] Saska M, Macaš M, Pvreučil L, et al. Robot path planning using particle swarm optimization of Ferguson splines. In: Proceedings of IEEE International Conference on Emerging Technologies and Factory Automation (ETFA). New York: IEEE Press, 2006. 833--839. Google Scholar

[9] Raja P, Pugazhenthi S. On-line path planning for mobile robots in dynamic environments. NNW, 2012, 22: 67-83 CrossRef Google Scholar

[10] Chen X, Kong Y, Fang X. A fast two-stage ACO algorithm for robotic path planning. Neural Comput Applic, 2013, 22: 313-319 CrossRef Google Scholar

[11] Purcaru C, Precup R E, Iercan D, et al. Optimal robot path planning using gravitational search algorithm. Int J Artif Intell, 2013, 10: 1--20. Google Scholar

[12] Li P, Duan H B. Path planning of unmanned aerial vehicle based on improved gravitational search algorithm. Sci China Technol Sci, 2012, 55: 2712-2719 CrossRef Google Scholar

[13] Duan H, Qiao P. Pigeon-inspired optimization: a new swarm intelligence optimizer for air robot path planning. Int Jnl Intel Comp Cyber, 2014, 7: 24-37 CrossRef Google Scholar

[14] Rania H, Babak C, Olivier D. A comparison of particle swarm optimization and the genetic algorithm. In: Proceedings of the 46th AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics & Material Conference, Austin, 2005. 1--13. Google Scholar

[15] Qin Y Q, Sun D B, Li N, et al. Path planning for mobile robot using the particle swarm optimization with mutation operator. In: Proceedings of the 3rd IEEE International Conference on Machine Learning And Cybernetics, Shanghai, 2004. 2473--2478. Google Scholar

[16] Zhang Q, Guochang G, Zhang Q. Path planning based on improved binary particle swarm optimization algorithm. In: Proceedings of the 2008 IEEE Conference on Robotics, Automation and Mechatronics, Chengdu, 2008. 462--466. Google Scholar

[17] Gong D, Zhang J, Zhang Y. Multi-objective particle swarm optimization for robot path planning in environment with danger sources. J Comput, 2011, 6: 1554--1561. Google Scholar

[18] Juang C F, Chang Y C. Evolutionary-Group-Based Particle-Swarm-Optimized Fuzzy Controller With Application to Mobile-Robot Navigation in Unknown Environments. IEEE Trans Fuzzy Syst, 2011, 19: 379-392 CrossRef Google Scholar

[19] Chen X, Li Y. Smooth path planning of a mobile robot using stochastic particle swarm optimization. In: Proceedings of the 2006 IEEE International Conference on Mechatronics and Automation, Luoyang, 2006. 1722--1727. Google Scholar

[20] Geng N, Gong D W, Zhang Y. PSO-based robot path planning for multisurvivor rescue in limited survival time. Math Probl Eng, 2014. Google Scholar

[21] Zhang Y, Gong D, Zhang J. Robot path planning in uncertain environment using multi-objective particle swarm optimization. Neurocomputing, 2013, 103: 172-185 CrossRef Google Scholar

[22] Masehian E, Sedighizadeh D. A multi-objective PSO-based algorithm for robot path planning. In: Proceedings of the 2010 IEEE International Conference on Industrial Technology (ICIT), Valparaiso, 2010. 465--470. Google Scholar

[23] Wang X, Zhang G, Zhao J. A Modified Membrane-Inspired Algorithm Based on Particle Swarm Optimization for Mobile Robot Path Planning. INT J COMPUT COMMUN, 2015, 10: 732-745 CrossRef Google Scholar

[24] Mo H, Xu L. Research of biogeography particle swarm optimization for robot path planning. Neurocomputing, 2015, 148: 91-99 CrossRef Google Scholar

[25] Purcaru C, Precup R E, Iercan D, et al. Hybrid PSO-GSA robot path planning algorithm in static environments with danger zones. In: Proceedings of the 17th IEEE International Conference on System Theory, Control and Computing (ICSTCC), Sinaia, 2013. 434--439. Google Scholar

[26] Xu C, Duan H, Liu F. Chaotic artificial bee colony approach to Uninhabited Combat Air Vehicle (UCAV) path planning. Aerospace Sci Tech, 2010, 14: 535-541 CrossRef Google Scholar

[27] Min C L, Min G P. Artificial potential field based path planning for mobile robots using a virtual obstacle concept. In: Proceedings of the 17th IEEE/ASME International Conference on Advanced Intelligent Mechatronics, Kobe, 2003. 735--740. Google Scholar

[28] Mcisaac K A, Ren J, Huang X. Modifed Newton's method applied to potential field navigation. In: Proceedings of the 42nd IEEE Conference on Decision and Control, Maui, 2003. 5873--5878. Google Scholar

[29] Cleghorn C W, Engelbrecht A P. Particle swarm convergence: standardized analysis and topological influence. In: Proceedings of the 9th International Conference on Swarm Intelligence, Brussels, 2014. 134--145. Google Scholar

[30] Frans V D B, Engelbrecht A P. A convergence proof for the particle swarm optimiser. Fundam Inform, 2010, 105: 341--374. Google Scholar

[31] Li C, Yang S. An adaptive learning particle swarm optimizer for function optimization. In: Proceedings of the IEEE Congress on Evolutionary Computation, Trondheim, 2009. 381--388. Google Scholar

[32] Poli R, Kennedy J, Blackwell T. Particle swarm optimization. Swarm Intell, 2007, 1: 33-57 CrossRef Google Scholar

[33] Lin Q, Li J, Du Z. A novel multi-objective particle swarm optimization with multiple search strategies. Eur J Operational Res, 2015, 247: 732-744 CrossRef Google Scholar

[34] Li C, Yang S. An adaptive learning particle swarm optimizer for function optimization. In: Proceedings of the 2009 IEEE Congress on on Evolutionary Computation, Trondheim, 2009. 381--388. Google Scholar

[35] Elshamli A, Abdullah H A, Areibi S. Genetic algorithm for dynamic path planning. In: Proceedings of the IEEE Electrical and Computer Engineering, Niagara Falls, 2004. 677--680. Google Scholar

[36] Carlisle A, Dozier G. An off-the-shelf PSO. In: Proceedings of the Workshop on Particle Swarm Optimization, Indianapolis, 2001. 1--6. Google Scholar

[37] Liang J J, Qu B Y, Suganthan P N, et al. Problem Definitions and Evaluation Criteria for the CEC 2013 Special Session and Competition on Real-Parameter Optimization. Technical Report 201212. 2013. Google Scholar

[38] Tvrdík J. Competitive differential evolution. In: Proceedings of the 12th International Conference on Soft Computing, Brno, 2006. 7--12. Google Scholar

[39] Montemanni R, Gambardella L M, Rizzoli A E. Ant Colony System for a Dynamic Vehicle Routing Problem. J Comb Optim, 2005, 10: 327-343 CrossRef Google Scholar

[40] Zhi-Hui Zhan , Jun Zhang , Yun Li . Adaptive particle swarm optimization.. IEEE Trans Syst Man Cybern B, 2009, 39: 1362-1381 CrossRef PubMed Google Scholar

[41] Quigley M, Conley K, Gerkey B P, et al. ROS: an open-source robot operating system. In: Proceedings of the ICRA Workshop on Open-Source Software, Kobe, 2009. Google Scholar

[42] Gerkey B P, Vaughan R T, Howard A. The player/stage project: tools for multi-robot distributed sensor systems. In: Proceedings of the 11th International Conference on Advanced Robotics, Coimbra, 2003. 317--323. Google Scholar

  • Figure 1

    (Color online) The environment model for mobile robot path planning.

  • Figure 2

    The flowchart of SLPSO for mobile robot path planning.

  • Figure 3

    (Color online) The simulation environment for mobile robot path planning in Gazebo.

  • Figure 4

    (Color online) The path planning results of mobile robot using GA, PSO and SLPSO for different D. (a) Path length; (b) path collision risk degree; (c) path smoothness; (d) overall path cost.

  • Figure 5

    (Color online) The path planning results of mobile robot using GA, PSO and SLPSO for different D. (a) D= 5; (b) D= 10; (c) D= 15; (d) D= 20; (e) D= 25; (f) D= 30.

  • Figure 6

    (Color online) The overall path cost results of GA, PSO and SLPSO for mobile robot path planning with different D. (a) D= 5; (b) D= 10; (c) D= 15; (d) D= 20; (e) D= 25; (f) D= 30.

  • Figure 7

    (Color online) Turtlebot2 robot.

  • Figure 8

    (Color online) The practical environment for TurtleBot2 robot path planning.

  • Figure 9

    (Color online) The path planning results of TurtleBot2 robot using GA, PSO and SLPSO in the RVIZ.

  •   

    Algorithm 1 The SLPSO algorithm

    Initialize the parameters of SLPSO. Set the population size $N$, generate the initial particles with position and velocity, initialize the update frequency (${U_{\rm~f}}$), and set the generation counter k = 1.

    while $k~<~{\rm~Iter}_{\rm~max}$ do

    Calculate the inertia weight value by using (11).

    for ${i}=1$ to $N$

    if $k%~{U_{\rm~f}}==0$ then

    Update the selection ratio of each learning operator for particle i.

    end if

    Select the most suitable operator according to its selection ratio for particle i.

    Hand the boundary violation of velocity and position for particle i by using (16) and (17).

    Evaluate the objective function of particle i according to (7).

    Calculate the reward value, progress value and selection ratio of each operator of particle i for the iteration k+1 according to (12)–(15).

    if the updated particle i is better than its ${{\boldsymbol~X}_{\rm~pbest}^k}$ then

    Update ${{\boldsymbol~X}_{\rm~pbest}^k}$.

    end if

    if the updated particle i is better than ${{\boldsymbol~X}_{\rm~gbest}^k}$ then

    Update ${{\boldsymbol~X}_{\rm~gbest}^k}$.

    end if

    end for

    k=k+1.

    end while

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1