research-article

An On-Line Method to Evolve Behavior and to Control a Miniature Robot in Real Time with Genetic Programming

Authors: Peter Nordin, Wolfgang BanzhafAuthors Info & Claims

Adaptive Behavior, Volume 5, Issue 2

Pages 107 - 140

https://doi.org/10.1177/105971239700500201

Published: 01 January 1997 Publication History

Abstract

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.

References

[1]

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 Learning Autonomous 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 Learning Autonomous 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 Learning Autonomous 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 Learning Autonomous 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 Learning Autonomous 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 Learning Autonomous 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 Learning Autonomous 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 II Cambridge, 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.

Cited By

Landi A(2024)Almost: Predicting “Natural" SequencesSN Computer Science10.1007/s42979-024-02647-15:3Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/s42979-024-02647-1
Sukarman FKita E(2023)Grammatical Evolution based Controller Design for Vehicle Robot Action LearningProceedings of the 2023 9th International Conference on Robotics and Artificial Intelligence10.1145/3637843.3637850(45-48)Online publication date: 17-Nov-2023
https://dl.acm.org/doi/10.1145/3637843.3637850
de Melo VVargas DBanzhaf WAuger AStützle T(2019)Batch tournament selection for genetic programmingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321793(994-1002)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321793
Show More Cited By

Index Terms

An On-Line Method to Evolve Behavior and to Control a Miniature Robot in Real Time with Genetic Programming
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Robotics
2. Computing methodologies
  1. Artificial intelligence

Index terms have been assigned to the content through auto-classification.

Recommendations

Engineering Online Evolution of Robot Behaviour: (Doctoral Consortium)
AAMAS '15: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems

Evolutionary computation techniques have been widely studied to automate the synthesis of behavioural control for robots. In online evolution, an evolutionary algorithm is executed on the robots themselves during task execution so as to continuously ...
Chaotic dynamics of a behavior-based miniature mobile robot: effects of environment and control structure

To study the regularity and complexity of autonomous behavior, the flow of sensory information obtained in autonomous mobile robots under various conditions was analyzed as a complex system. Sensory information time series X"n was collected from a ...
Robot Programming: A Guide to Controlling Autonomous Robots

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Adaptive Behavior - Animals, Animats, Software Agents, Robots, Adaptive Systems

Adaptive Behavior - Animals, Animats, Software Agents, Robots, Adaptive Systems Volume 5, Issue 2

Jan 1997

105 pages

ISSN:1059-7123

Issue’s Table of Contents

Publisher

Sage Publications, Inc.

United States

Publication History

Published: 01 January 1997

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Landi A(2024)Almost: Predicting “Natural" SequencesSN Computer Science10.1007/s42979-024-02647-15:3Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/s42979-024-02647-1
Sukarman FKita E(2023)Grammatical Evolution based Controller Design for Vehicle Robot Action LearningProceedings of the 2023 9th International Conference on Robotics and Artificial Intelligence10.1145/3637843.3637850(45-48)Online publication date: 17-Nov-2023
https://dl.acm.org/doi/10.1145/3637843.3637850
de Melo VVargas DBanzhaf WAuger AStützle T(2019)Batch tournament selection for genetic programmingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321793(994-1002)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321793
Tavafi ABanzhaf WBosman P(2017)A hybrid genetic programming decision making system for RoboCup soccer simulationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071194(1025-1032)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071194
Hamida SAbdelmalek WAbid F(2016)Applying Dynamic Training-Subset Selection Methods Using Genetic Programming for Forecasting Implied VolatilityComputational Intelligence10.1111/coin.1205732:3(369-390)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1111/coin.12057
Antunes LNunes DCoelho HBazzan AHuhns MLomuscio AScerri P(2014)The geometry of desireProceedings of the 2014 international conference on Autonomous agents and multi-agent systems10.5555/2615731.2617433(1169-1172)Online publication date: 5-May-2014
https://dl.acm.org/doi/10.5555/2615731.2617433
Fukunaga AHiruma HKomiya KIba H(2012)Evolving controllers for high-level applications on a service robotGenetic Programming and Evolvable Machines10.1007/s10710-011-9152-313:2(239-263)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1007/s10710-011-9152-3
García-Sánchez PEiben AHaasdijk EWeel BMerelo-Guervós J(2012)Testing diversity-enhancing migration policies for hybrid on-line evolution of robot controllersProceedings of the 2012t European conference on Applications of Evolutionary Computation10.1007/978-3-642-29178-4_6(52-62)Online publication date: 11-Apr-2012
https://dl.acm.org/doi/10.1007/978-3-642-29178-4_6
Laskowski M(2011)A Prototype Agent Based Model and Machine Learning Hybrid System for Healthcare Decision SupportInternational Journal of E-Health and Medical Communications10.4018/jehmc.20111001052:4(67-90)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.4018/jehmc.2011100105
Karafotias GHaasdijk EEiben ALanzi P(2011)An algorithm for distributed on-line, on-board evolutionary roboticsProceedings of the 13th annual conference on Genetic and evolutionary computation10.1145/2001576.2001601(171-178)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001576.2001601
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents