Comparison of Metaheuristic Algorithms for Evolving a Neural Controller for an Autonomous Robot
Keywords:Evolutionary algorithm, Neural network, Robot simulation
Evolutionary algorithms are a possible way to automatically design the behavior of autonomous robots. In this paper we compare different evolutionary algorithms (EA), namely simple EA, two dimensional cellular EA, and random search, according to their performance in a simple simulation, where a phototaxis robot with two sensors of limited range has to find a light source in a closed area. In our experiments we studied the effects on performance of EA parameters, such as population size and number of generation. The results explain how the choice of the neural network (three-layered or fully-connected) may influence the quality of a final solution.Our findings indicate that acceptable results can be achieved using all EAs but not with random search. The utilization of a fully-connected neural network allows achieving better results for all EAs as compared to a three-layered neural network. Two dimensional cellular EA and simple EA evolve the best strategies for a robot’s behavior which allow the robot to reach the light source in almost all cases.
M. Berry and G. Linoff. Data Mining Techniques: For Marketing, Sales, and Customer Support. Database management / Wiley. Wiley, 1997.
A. Blum. Neural Networks in C++: An Object-Oriented Framework for Building Connectionist Systems. Wiley, 1 edition, 5 1992.
Z. Boger and H. Guterman. Knowledge extraction from artificial neural network models. In Systems, Man, and Cybernetics, 1997.
Computational Cybernetics and Simulation., 1997 IEEE International Conference, volume 4, pages 3030–3035 vol.4, 1997.
M. Caudill and C. Butler. Understanding Neural Networks; Computer Explorations. MIT Press, Cambridge, MA, USA, 1992.
D. Cliff, P. Husbands, and I. Harvey. Explorations in evolutionary robotics. Adaptive Behavior, 2(1):73–110, 1993.
A. Czarn, C. MacNish, K. Vijayan, B. Turlach, and R. Gupta. Statistical exploratory analysis of genetic algorithms. Evolutionary Computation, IEEE Transactions, 8(4):405–421, 2004.
K. A. De Jong. Analysis of the behavior of a class of genetic adaptive systems. 1975.
A. E. Eiben and J. E. Smith. Introduction to Evolutionary Computing. Springer, 2007.
W. Elmenreich and G. Klingler. Genetic evolution of a neural network for the autonomous control of a four-wheeled robot. In A. Gelbukh and A. F. Kuri Morales, editors, Sixth Mexican International Conference on Artificial Intelligence, pages 396–406. IEEE Computer Society, 2007.
D. Floreano and L. Keller. Evolution of adaptive behaviour in robots by means of darwinian selection. PLoS biology, 2010.
D. Fogel. What is evolutionary computation? Spectrum, IEEE, 37(2):26–28, 2000.
L. Fogel, A. Owens, and M. Walsh. Artificial Intelligence Through Simulated Evolution. John Wiley & Sons, 1966.
D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition, 1989.
J. He and X. Yao. From an individual to a population: An analysis of the first hitting time of population-based evolutionary algorithms. Evolutionary Computation, IEEE Transactions, 6(5):495–511, 2002.
J. H. Holland. Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press, 1975.
J. Kari. Theory of cellular automata: a survey. Theoretical Computer Science, 334(1):3–33, 2005.
A. L. Nelson, E. Grant, and T. C. Henderson. Evolution of neural controllers for competitive game playing with teams of mobile robots. Robotics and Autonomous Systems, (46):135–150, 2004.
A. Pinter-Bartha, A. Sobe, and W. Elmenreich. Towards the light – Comparing evolved neural network controllers and finite state machine controllers. In Proceedings of the Tenth International Workshop on Intelligent Solutions in Embedded Systems, pages 83–87, Klagenfurt, Austria, jul 2012.
J. D. Schaffer, R. A. Caruana, L. J. Eshelman, and R. Das. A study of control parameters affecting online performance of genetic algorithms for function optimization. In Proceedings of the third international conference on Genetic algorithms, pages 51–60. Morgan Kaufmann Publishers Inc., 1989.
M. Sipper, Y. Azaria, A. Hauptman, and Y. Shichel. Designing an evolutionary strategizing machine for game playing and beyond. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions, 37(4):583–593, 2007.
A. Sobe, I. Fehervari, and W. Elmenreich. FREVO: A tool for evolving and evaluating self-organizing systems. In Proceedings of the 1st International Workshop on Evaluation for Self-Adaptive and Self-Organizing Systems, Lyon, France, Sept. 2012.
K. Swingler. Applying Neural Networks: A Practical Guide. Morgan Kaufmann, pap/dsk edition, 5 1996.
M. Tomassini. Spatially structured evolutionary algorithms: artificial evolution in space and time (natural computing series). Springer-Verlag New York, Inc., 2005.
M. Schuster, and K. Paliwal. Bidirectional recurrent neural networks. Signal Processing, IEEE Transactions on 45, no. 11: 2673-2681, 1997.
R. Pascanu, T. Mikolov, Y. Bengio. On the difficulty of training recurrent neural networks. In Proceedings of the 30 th International Conference on Machine Learning, Atlanta, Georgia, USA, 2013