We present a novel evolutionary approach to robotic control of a real robot based on genetic programming (GP). Our approach uses GP techniques that manipulate machine code to evolve control programs for robots. This variant of GP has several advantages over a conventional GP system, such as higher speed, lower memory requirements, and better real-time properties. Previous attempts to apply GP in robotics use simulations to evaluate control programs and have difficulties with learning tasks involving a real robot. We present an on-line control method that is evaluated in two different physical environments and applied to two tasks—obstacle avoidance and object following—using the Khepera robot platform. The results show fast learning and good generalization.
Atkin, M., & Cohen, P.R. (1994). Learning monitoring strategies: A difficult genetic programming application. In Proceedings of the 1994 IEEE World Congress on Computational Intelligence. Piscataway, NY: IEEE Press.
2.
Baluja, S. (1996). Evolution of an artificial neural network based autonomous land vehicle controller. IEEE Transactions Systems, Man and Cybernetics—Part B, Special Issue on LearningAutonomous Robots, 26, 450-463.
3.
Banzhaf, W., Francone, F., & Nordin, P. (1996). The effect of extensive use of the mutation operator on generalization in genetic programming using sparse data sets. In W Ebeling, I. Rechenberg, H.-P. Schwefel & M. Voigt (Eds.), Proceedings of Parallel Problem Solving from Nature IV. Berlin: Springer.
4.
Banzhaf, W., Nordin, P., & Olmer, M. (in press). Generating adaptive behavior using function regression within genetic programming and a real robot. In J. Koza et al. (Eds.) Proceedings of the Second Annual Conference on Genetic Programming . San Mateo, CA: Morgan Kaufmann .
5.
Braitenberg, V. (1984). Vehicles. Cambridge, MA: MIT Press.
6.
Brooks, R. (1992). Artificial life and real robots. In F.J. Varela and P. Bourgine (Eds.), Proceedings of the First European Conference on Artificial Life. Cambridge, MA: MIT Press.
7.
Cliff, D. (1991). Computational neuroethology: A provisional manifesto . In J.A. Meyer & S. Wilson (Eds.), From animals to animats: Proceedings of the First International Conference on Simulation of Adaptive Behavior. Cambridge, MA: MIT Press .
8.
Cliff, D., Harvey, I., & Husbands, P. (1993). Explorations in evolutionary robotics. Adaptive Behavior, 2, 73-110.
9.
Colombetti, M., Dorigo, M., & Borghi, G. (1996). Behavior analysis and training: A methodology for behavior engineering. IEEE Transactions Systems, Man and Cybernetics—Part B, Special Issue on LearningAutonomous Robots, 26, 365-380.
10.
Donnart, J., & Meyer, J. (1996). Learning reactive and planning rules in a motivationally autonomous animat. IEEE Transactions Systems, Man and Cybernetics—Part B, Special Issue on LearningAutonomous Robots, 26, 381-395.
11.
Edelman, G. (1987). Neural Darwinism. New York : Basic Books.
12.
Fitzpatrick, J.M., Grefenstette, J., & van Gucht, D. (1984). Image registration by genetic search. In Proceedings of IEEE Southeast Conference. Piscataway, NY: IEEE Press.
13.
Floreano, D., & Mondada, F. (1994). Automatic creation of an autonomous agent: Genetic evolution of a neural-network driven robot. In D. Cliff, P. Husbands, J.A. Meyer & S. Wilson (Eds.), From animals to animats III: Proceedings of the Third International Conference on Simulation of Adaptive Behavior. Cambridge, MA: MIT Press.
14.
Floreano, D., & Mondada, E. (1996). Evolution of homing navigation in a real mobile robot. IEEE Transactions Systems, Man and Cybernetics—Part B, Special Issue on LearningAutonomous Robots, 26, 396-407.
15.
Francone, F., Nordin, P., & Banzhaf, W. (1996). The effect of extensive use of the mutation operator on generalization in genetic programming using sparse data sets. In J. Koza, D. Goldberg, D. Fogel & R. Riolo (Eds.), Proceedings of the First Annual Conference on Genetic Programming . Cambridge, MA: MIT Press.
16.
Fraser, A.P., & Rush, J.R. (1994). Putting INK into a BIRo: A discussion of problem domain knowledge for evolutionary robotics. In Proceedings of the Workshop on Artificial Intelligence and Simulation of Behavior Workshop on Evolutionary Computing.
17.
Grefenstette, J., Ramsey, C., & Schultz, A. (1990). Learning sequential decision rules using simulation models and competition. Machine Learning, 5, 355-381.
18.
Greiner, R., & Isukapalli, R. (1996). Learning to Select Useful Landmarks. IEEE Transactions Systems, Man and Cybernetics - Part B, Special Issue on LearningAutonomous Robots, 26, 437-449.
19.
Handley, S. (1994). The automatic generation of plans for a mobile robot via genetic programming with automatically defined functions. In K. Kinnear (Ed.), Advances in genetic programming. Cambridge, MA: MIT Press.
20.
Harvey, I., Husbands, P., & Cliff, D. (1993). Issues in evolutionary robotics. In J. A. Meyer & S. Wilson (Eds.), From animals to animats 2: Proceedings of the Second International Conference on Simulation of Adaptive Behavior. Cambridge, MA: MIT Press.
21.
Kaelbling, L.P., Littman, M.L., & Moore, A.W. (1996). Reinforcement learning: A survey. Journal of Artificial Intelligence Research, 4, 237-285.
22.
Keith, M.J., & Martin, C.M. (1993). Genetic programming in C++: Implementation and design issues. In K. Kinnear (Ed.), Advances in genetic programming. Cambridge, MA : MIT Press.
23.
Koza, J. (1992). Genetic programming. Cambridge, MA: MIT Press.
24.
Kröse, B. (1995). Learning from delayed response. Robotics and autonomous systems, 15, 233-235.
25.
Lowerre, B.T., & Reddy, R.D. (1980). The Harpy Speech Understanding System. In W A. Lea (Ed.), Trends in speech recognition. New York: Prentice-Hall .
26.
MatariΛ, M.J. (1993). Designing emergent behaviors: From local interactions to collective intelligence. In J. A. Meyer & S. Wilson (Eds.), From animals to animats II: Proceedings of the Second International Conference on Simulation of Adaptive Behavior. Cambridge, MA: MIT Press.
27.
Meeden, L. (1996). An incremental approach to developing intelligent neural network controllers for robots. IEEE Transactions Systems, Man and Cybernetics— Part. B, Special Issue on LearningAutonomous Robots, 26, 474-484.
28.
del Millán, R.J. (1996). Rapid, safe, and incremental learning of navigation strategies. IEEE Transactions Systems, Man and Cybernetics—Part B, Special Issue on LearningAutonomous Robots, 26, 408-420.
29.
Mondada, F., Franzi, E., & Ienne, P. (1993). Mobile robot miniaturization: A tool for investigation in control algorithms. In Proceedings of the Third International Symposium on Experimental Robotics (ISER '93), Kyoto, Japan, October 1993.
30.
Nordin, P. (1994). A compiling genetic programming system that directly manipulates the machine-code. In. K. Kinnear (Ed.), Advances in genetic programming. Cambridge, MA: MIT Press.
31.
Nordin, P., & Banzhaf, W. (1995a). Complexity compression and evolution. In L. Eshelman (Ed.), Proceedings of the Sixth International Conference of Genetic Algorithms. San Mateo, CA: Morgan Kaufinann.
32.
Nordin, P., & Banzhaf, W. (1995b). Evolving turing complete programs for a register machine with self-modifying code. In L. Eshelman (Ed.), Proceedings of the Sixth International Conference of Genetic Algorithms. San Mateo, CA: Morgan Kaufimann.
33.
Nordin, P., & Banzhaf, W. (1995c). Real time evolution of behavior and a world model for a miniature robot using genetic programming (Tech. Rep. SysReport SYS-5/95) . Dortmund, Germany: Department of Computer Science, University of Dortmund.
34.
Nordin, P., & Banzhaf, W. (1996a). Image recognition and image encoding using paint primitives and genetic programming . Unpublished manuscript.
35.
Nordin, P., & Banzhaf, W. (1996b). Programmatic compression of images and sound . In J. Koza, D. Goldberg, D. Fogel & R. Riolo (Eds.), Proceedings of the First Annual Conference on Genetic Programming. Cambridge, MA: MIT Press.
36.
Nordin, P., Francone, F., & Banzhaf, W. (1996). Explicitly defined introns in genetic programming . In P. Angeline & K. Kinnear (Eds.), Advances in genetic programming IICambridge, MA: MIT Press.
37.
Olmer, M., Nordin, P., & Banzhaf, W. (1996). Evolving real-time behavior modules for a real robot with genetic programming. In J. Grefenstette & A. Shultz (Eds.), Proceedings of the International Symposium on Robotics and Manufacturing, Montpellier, France, 1996.
38.
Potter, M.A., De Jong, K.A., & Grefenstette, J. (1995). In L. Eshelman (Ed.), Proceedings of the Sixth International Conference of Genetic Algorithms. San Mateo, CA: Morgan Kaufinann.
39.
Reynolds, C.W. (1988). Not bumping into things. In: Notes_for the SIGGRAPH'88 Course Developments in Physically Based Modeling. ACM-SIGGRAPH .
40.
Reynolds, C.W. (1994). Evolution of obstacle avoidance behavior. In K. Kinnear (Ed.), Advances in genetic programming. Cambridge, MA: MIT Press.
41.
Rosenbloom, P. (1987). Best first search. In S. Shapiro (Ed.), Encyclopedia of artificial intelligence , (Vol. 2). New York: Wiley.
42.
Sims, K. (1994). Evolving 3D morphology and behavior by competition . In A. Brooks & P. Maes (Eds.), Proceedings in artificial life IV. Cambridge, MA: MIT Press .
43.
Sparc (1991). The SPARC architecture manual. Menlo Park, CA: SPARC International .
44.
Spencer, G. (1994). Automatic generation of programs for crawling and walking. In K. Kinnear (Ed.), Advances in genetic programming. Cambridge, MA : MIT Press.
45.
Syswerda, G. (1991). A study of reproduction in generational steady-state genetic algorithms. In G. J. E. Rawlings (Ed.), Foundations of genetic algorithms. San Mateo, CA: Morgan Kaufmann.
46.
Teller, A. (1994). The evolution of mental models. In K. Kinnear (Ed.), Advances in genetic programming . Cambridge, MA: MIT Press.
47.
Zapata, R., Lepinay, P., Novales, C., & Deplanques, P. (1993). Reactive behaviors of fast mobile robots in unstructured environments: Sensor-based control and neural networks. In J. A. Meyer & S. Wilson (Eds.), From animals to animats 2: Proceedings of the Second International Conference on Simulation of Adaptive Behavior. Cambridge, MA: MIT Press.
