Smooth Path Planning Method Based on Dynamic Feedback A* Ant Colony Algorithm

HUANG Chen, FEI Jiyou, LIU Yang, LI Hua, LIU Xiaodong

Abstract

A smooth path planning method for mobile robot with A* ant colony optimization was proposed based on dynamic feedback for mobile robot. First of all, in order to overcome the disadvantage about slow convergence speed of ant colony algorithm, simplified A* algorithm was presented to optimize the initial pheromone settings, which was able to solve the blindness of the first search. In this step, the planning path with the minimum value of the valuation function was obtained by the evaluation function of A* algorithm. And the presented multi-evolutionary strategy mechanism which could increase search space was used to strengthen the global search ability of the algorithm. Secondly, in order to further improve the adaptability of algorithm about the problem of local minimum and stagnation in the path planning, the key parameters of the algorithm were systematically analyzed and the closed-loop feedback idea was adopted to adjust the parameters of ant colony optimization algorithm dynamically. Finally, combining with the cubic B spline curve method, the planning path was smoothed to meet the practical movement route of mobile robot. The simulation experiment results showed that compared with traditional ant colony (AC), A* ant colony optimization based on dynamic feedback could reduce 10.4% of the average path cost and shorten 65.8% of the computing time in average. In addition, compared with ant colony system (ACS), the average path cost could be reduced by 5.9%, the calculation time could be shortened by 52.6%. The improved ant colony optimization algorithm could plan a smooth and high quality path in both the dynamic and static environments.

 

Keywords: path planning, ant colony algorithm, dynamic feedback, A* algorithm, B spline curve

 

Download Full Text:

PDF


References


ZHU Daqi, YAN Mingzhong. Survey on technology of mobile robot path planning[J]. Control and Decision, 2010, 25(7) ; 961 - 967. (in Chinese)

ZHU Q, HU J, CAI W, et al. A new robot navigation algorithm for dynamic unknown environments based on dynamic path re- computation and an improved scout ant algorithm[ J ]. Applied Soft Computing, 2011 , 11(8) : 4667 -4676.

HAN Yong, LIU Guodong. Mobile robot motion planning based on potential field in dynamic environment [ J ]. Robot, 2006, 28 ( 1 ) : 45 -49. (in Chinese)

MANIKAS W, ASHENVVI K, WAINWRIGHT R. Genetic algorithms for autonomous robot navigation[ J]. IEEE Instrumentation & Measurement Magazine, 2008, 10(6); 26-31.

NI B, CHEN X. New approach of neural network for robot path planning[ С ] //2004 IEEE International Conference on Systems, Man and Cybernetics, 2004; 735 -739.

WU Xianxiang, GUO Baolong, WANG Juan. Mobile robot path planning algorithm based on particle swarm optimization of cubic splines[J]. Robot, 2009, 31(6): 556 -560. (in Chinese)

GARRO В A, SOSSA II, VAZQUEZ R A. Evolving ant colony system for optimizing path planning in mobile robots[C]// IEEE Electronics, Robotics and Automotive Mechanics Conference, 2007; 444 -449.

WANG Y, YANG Y, YUAN X, et al. Autonomous mobile robot navigation system designed in dynamic environment based on transferable belief model [ J ]. Measurement, 201 1 , 44(8) ; 1389 - 1405.

http:// www. j-csam. org/jcsam/ch/reader/view _ abstract, aspx? file_no = 20150903&flag = 1. DOI; 10. 6041/j. issn. 1000- 1298.2015.09.003. LIU Jianhua, YANG Jianguo, LIU Huaping, et al. Robot global path planning based on ant colony optimization with artificial potential field [ J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(9) ; 18 -27. (in Chinese)

WANG Peidong, FENG Zuhong, HUANG Xin. An improved ant colony algorithm for mobile robot path planning[J]. Robot, 2008, 30(6) ; 554 -560. ( in Chinese)

ZHAO Juanping, GAO Xianwen, FU Xiuhui, et al. Improved ant colony algorithm of path planning for mobile robot [J]. Control Theory & Application, 201 I , 28(4) : 457 -461. (in Chinese)

12 DORIGO M, GAMBARDELLA L M. Ant colony system; a cooperative learning approach to the traveling salesman problem [J ]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53 -66.

http:// www. j-csam. org/jcsam/ch/reader/view_ abstract, aspx? flag = l&file_no = 20160751 & journal _ id = jcsam. DO 1:10. 6041 /j. issn. 1000-1298. 2016. 07. 051. GUO Zonghuan, XIE Zhijiang, SONG Daiping, et al. Error optimization of pitching mechanism motion in wind tunnel test based on improved ant colony algorithm [ J/OL ]. Transactions of the Chinese Society for Agricultural Machinery, 2016 ,47 ( 7 ) :375 - 38 1. ( in Chinese)

http// www. j-csam. org/jcsam/ch/reader/view_abstract. aspx? file_no = 20150748&flag = 1. 1)01; 10. 6041/ j. issn. 1000-1298.2015.07.048. WU Xiaoyong, XIE Zhijiang, SONG Daiping, et al. Forward kinematics of 3 — PPR parallel mechanism based on improved ant colony algorithm [J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2015,46(7) ; 339 -344. ( in Chinese)

WANG Dianjun. Indoor mobile-robot path planning based on an improved A* algorithm [ J ]. Journal of Tsinghua University; Science and Technology, 2012, 52(8) ; 1085 - 1089. (in Chinese)

http;//www. j-csam. org/jcsam/ch/reader/view_ahstract. aspx? file_no = 20151243&flag = 1. DOI: 10. 6041/j. issn. 1000- 1298. GU Qing, DOU Fengqian, MA Fei. Energy optimal path planning of electric vehicle hast'd on improved A algorithm [J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46( 12) ; 316 -322. ( in Chinese)

http:// www. j-csam. org/jcsam/ch/ reader/view_abstract. aspx? file_no = 20150743 & flag = 1. DOI: 10. 6041/jissn. 1000-1298.2015.07.043. MA Fei, YANG Haoshen, GU Qing, el al. Navigation path planning of unmanned underground LHD based on improved A* algorithm [J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(7) ; 303 -309. (in Chinese)

I)U Pengzhen, TANG Zhenmin, SUN Van. An object-oriented multi-role ant colony optimization algorithm lor solving TSP problem [J]. Control and Decision, 2014( 10) : 1729 - 1736. (in Chinese)

http: // www. j-csam. org/jcsam/ch/reader/view„abstract, aspx? file_no = 20140609&flag = 1. DOI: 10. 6041/j. issn. 1000-1298.2014.06.009. Sill Knxiu, CHEN Minmin, I.I Jun, et al. Research on method of global path-planning for mobile robot based on ant-colony algorithm [J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2014, 45(6) ; 53 -57. ( in Chinese)

Tong, LU Qiang, ZHANG Hui, et al. High-speed real-time interpolation of cubic uniform B-spline curve[J]. Computer Integrated Manufacturing Systems, 2008, 14(9) ; 1830 - 1836. (in Chinese)


Refbacks

  • There are currently no refbacks.