An Improved Robot Path Planning Algorithm

Xuesong Yan Xuesong Yan, Qinghua Wu Qinghua Wu, Hammin Liu

Abstract


Robot path planning is a NP problem. Traditionaloptimization methods are not very effective to solve it. Traditional genetic algorithm trapped into the local minimum easily. Therefore, based on a simple genetic algorithm and combine the base ideology of orthogonal design method then applied it to the population initialization, using the intergenerational elite mechanism, as well as the introduction of adaptive local search operator to prevent trapped into the local minimum and improvethe convergence speed to form a new genetic algorithm. Through the series of numerical experiments, the new algorithm has been proved to be efficiency.We also use the proposed algorithm to solve the robot path planning problem and the experiment results indicated that the new algorithm is efficiency for solving the robot path planning problems and the best path usually can be found.

Full Text:

PDF

References


A Yahja, S Singh, A Stentz. An Efficient on-line Path Planner for Outdoor Mobile Robots. Robotics and Autonomous Systems. Elsevier Science. 2000; 32: 129-143.

UNehmzow, COwen. Robot Navigation in the Real World: Experiments with Manchester’s Forty Two in Unmodified Large Environments.Robotics andAutonomous Systems.Elsevier Science.2000; 33: 223-242.

A Howard, H Seraji. Vision-Based Terrain Characterization and TraversabilityAssessment.Journal of Robotic Systems. Wileyperiodicals.2001; 18(10): 577-587.

DBGennery. Traversability Analysis and Path Planning for Planetary Rovers.Autonomous Robots. Kluwer, Academic Publishers.1999; 6: 131-146.

G Liu, T Li, Y Peng, X Hou. The ant algorithm for solving robot path planning problem. 3rd International Conf on Information Technology and Applications. IEEE Press.2005; 2: 25-27.

J Holland. Adaptation in natural and artificial systems. University of Michigan press.1975.

Leung Yiu-Wing, Wang Yuping. An orthogonal genetic algorithm with quantization for global numerical optimization. IEEE Transactions on Evolutionary Computation. 2001; 5(1): 41-53.

Latombe JC. Robot Motion Planning. Kluwer Academic Publishers. Boston.1991.

M Bracho de Rodríguez, J Ali Moreno. Heuristic Algorithm for Robot Path Planning Based on Real Space Renormalization. International Joint Conference, 7th Ibero-American Conference on AI: Advances in Artificial Intelligence table of contents, Lecture Notes in Computer Science, Springer-Verlag London, UK.2000: 379–388.

Barraquand J, Langlois B,Latombe JC. Numerical Potential FieldTechniques for Robot Path Planning. IEEE Transactions on System, Man and Cybernetic. 1992; 22(2): 224-241.

Durbin R, Willshaw D. An Analogue Approach to the Traveling Salesman Problem Using an Elastic NetApproach.Nature. 1987; 326(6114): 689-691.

XSYan, LSKang et.al.An Approach to Dynamic Traveling Salesman Problem.3rdInternational Conference on Machine Learning and Cybernetics.IEEE Press, Shanghai, 2004;2418-2420.

XSYan,AM Zhou, LS Kang et,al.TSP Problem Based on Dynamic Environment. 5thWorld Congress onIntelligent Control and Automation, IEEE press, Hangzhou,China.2004;2271-2274.

MJ. Rendas,WTetenoire.Definition of exploratory trajectories in roboticsusing genetic algorithms.10thInternational Conference in Industrial andEngineering Applications of Artificial Intelligence and Expert Systems.1997; 211-216.

JXiao, Z Michalewicz, L Zhang, K Trojanowski. Adaptive evolutionaryplanner/navigator for robots.IEEE Trans. on Evolutionary Computation.1997; 1(1): 18-28.

GengqianLiu, TiejunLi, YuqingPeng, XiangdanHou. The Ant Algorithm for Solving Robot Path Planning Problem.3rdInternational Conference on Information Technology and Applications, IEEE Press.2005; 2: 25-27.

XSYan, Hui Li et.al.A Fast Evolutionary Algorithm for Combinatorial Optimization Problems.4th International Conference on Machine Learning and Cybernetics.IEEE Press.2005; 3288-3292.

XSYan, Qing Hua Wu et.al.A New Optimizaiton Algorithm for Function Optimization.3rd International Symposium on Intelligence Computation & Applications, Lecture Notes in Computer Science.Springer Press.2009;144-150.

XS Yan, QH Wu. Function Optimization Based on Cultural Algorithms. Journal of Computer and Information Technology. Academy Publish.2012; 2: 152-158.

XS Yan, QH Wu, C Zhanget, al.An Improved Genetic Algorithm and Its Application.TELKOMNIKA Indonesian Journal of Electrical Engineering. 2012; 10(5): 1081-1086.

QH Wu, HM Liu et, al. Research of Function Optimization Algorithm. TELKOMNIKA Indonesian

Journal of Electrical Engineering. 2012; 10(4): 858-863.




DOI: http://doi.org/10.12928/telkomnika.v10i4.850

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

TELKOMNIKA Telecommunication, Computing, Electronics and Control
ISSN: 1693-6930, e-ISSN: 2302-9293
Universitas Ahmad Dahlan, 4th Campus
Jl. Ringroad Selatan, Kragilan, Tamanan, Banguntapan, Bantul, Yogyakarta, Indonesia 55191
Phone: +62 (274) 563515, 511830, 379418, 371120
Fax: +62 274 564604

View TELKOMNIKA Stats