Memetic Algorithm Based Path Planning for a Mobile Robot

Authors: Neda Shahidi, Hadi Esmaeilzadeh, Marziye Abdollahi, Caro Lucas

Abstract:

In this paper, the problem of finding the optimal collision free path for a mobile robot, the path planning problem, is solved using an advanced evolutionary algorithm called memetic algorithm. What is new in this work is a novel representation of solutions for evolutionary algorithms that is efficient, simple and also compatible with memetic algorithm. The new representation makes it possible to solve the problem with a small population and in a few generations. It also makes the genetic operator simple and allows using an efficient local search operator within the evolutionary algorithm. The proposed algorithm is applied to two instances of path planning problem and the results are available.

Keywords: Path planning problem, Memetic Algorithm, Representation.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1331165

References:

[1] Ashiru I.: Czarnecki C.: Optimal Motion Planning for Mobile Robots Using Genetic Algorithms. In Proc. of the 1995 International Conference on Industrial Automation and Control (1995).
[2] Sugihara, K., Smith J.: Genetic Algorithms for Adaptive Motion Planning of an Autonomous Mobile Robot. In Proc. of the IEEE International Symposium on Computational Intelligence in Robotics and Automation (1997) 138-146.
[3] Gerke M.: Genetic Path Planning for Mobile Robots. In Proc. of the American Control Conference (1999).
[4] Tu J., Yang S.X.: Genetic Algorithm Based Path Planning for a Mobile Robot. In Proc. of the 2003 IEEE Intern. Conference on Robotics & Automation (2003) 1221-1226.
[5] Hu Y., yang S.X.: Knowledge Based Genetic Algorithm for Path Planning of a Mobile Robot. In Proc. of the 2004 IEEE Intern. Conference on Robotics & Automation (2004) 4350-4355.
[6] Hart W. E.: Adaptive Global Optimization with Local Search. Ph. D. Thesis, University of California, San Diego (1994).
[7] Shahidi N., Esmaeilzadeh H. Abdollahi M., Lucas C.: Self-adaptive Memetic Algorithm: An Adaptive Conjugate gradient approach. IEEE Conference of Cybernetic and Intelligent Systems (CIS'2004), in press.
[8] Baldwin J. M.: A New Factor in Evolution. The American Naturalist 30 (1896), 441-451, 536-553.
[9] Ong Y. S., Keane A. J.: Meta-Lamarckian Learning in Memetic Algorithms, IEEE Transactions on Evolutionary Computation, Vol. 8, No. 2 (2004).
[10] Krasnogor N.: A Memetic Algorithm with Self-adaptive Local Search; TSP as a Case Study. In Proc. of the 2000 International Genetic and Evolutionary Computation Conference (GECCO 2000).
[11] Land, M. W. S.: Evolutionary Algorithms with Local Search for Combinatorial Optimization. Ph. D. Thesis, University of California, San Diego, 1998.
[12] Principe J. C., Euliano N. R., Lefebvre W. C.: Neural and Adaptive Systems. Jone Wiley & Sons, Inc., 2000.