Evolutionary robotics
Encyclopedia
Evolutionary robotics is a methodology that uses evolutionary computation
to develop controllers
for autonomous robot
s. Algorithms in ER frequently operate on populations of candidate controllers, initially selected from some distribution
. This population is then repeatedly modified according to a fitness function
. In the case of genetic algorithm
s (or "GAs"), a common method in evolutionary computation
, the population of candidate controllers is repeatedly grown according to crossover, mutation and other GA
operators
and then culled according to the fitness function
. The candidate controllers used in ER applications may be drawn from some subset of the set of artificial neural network
s, although some applications (including SAMUEL, developed at the Naval Center for Applied Research in Artificial Intelligence) use collections of "IF THEN ELSE" rules as the constituent parts of an individual controller. It is theoretically possible to use any set of symbolic formulations of a control laws (sometimes called a policies
in the machine learning
community) as the space of possible candidate controllers. Artificial neural network
s can also be used for robot learning
outside of the context of evolutionary robotics. In particular, other forms of reinforcement learning
can be used for learning robot controllers.
Developmental robotics
is related to, but differs from, evolutionary robotics. ER uses populations of robots that evolve over time, whereas DevRob is interested in how the organization of a single robot's control system develops through experience, over time.
In 1992 and 1993 two teams, a team surrounding Floreano
and Mondada
at the EPFL in Lausanne
and a research group at the COGS at the University of Sussex
reported experiments on artificial evolution of autonomous robots. The success of this early research triggered a wave of activity in labs around the world trying to harness the potential of the approach.
Lately, the difficulty in "scaling up" the complexity of the robot tasks has shifted attention somewhat towards the theoretical end of the field rather than the engineering end.
), reproducing psychological phenomena, and finding out about biological neural networks by studying artificial ones. Creating controllers via artificial evolution requires a large number of evaluations of a large population. This is very time consuming, which is one of the reasons why controller evolution is usually done in software. Also, initial random controllers may exhibit potentially harmful behaviour, such as repeatedly crashing into a wall, which may damage the robot. Transferring controllers evolved in simulation to physical robots is very difficult and a major challenge in using the ER approach. The reason is that evolution is free to explore all possibilities to obtain a high fitness, including any inaccuracies of the simulation . This need for a large number of evaluations, requiring fast yet accurate computer simulations, is one of the limiting factors of the ER approach .
In rare cases, evolutionary computation may be used to design the physical structure of the robot, in addition to the controller. One of the most notable examples of this was Karl Sims
' demo for Thinking Machines Corporation.
algorithms require a set of training examples
consisting of both a hypothetical input and a desired answer. In many robot learning applications the desired answer is an action for the robot to take. These actions are usually not known explicitly a priori, instead the robot
can, at best, receive a value indicating the success or failure of a given action taken. Evolutionary algorithms are natural solutions to this sort of problem framework, as the fitness function need only encode the success or failure of a given controller, rather than the precise actions the controller should have taken. An alternative to the use of evolutionary computation in robot learning is the use of other forms of reinforcement learning
, such as q-learning
, to learn the fitness of any particular action, and then use predicted fitness values indirectly to create a controller.
Evolutionary computation
In computer science, evolutionary computation is a subfield of artificial intelligence that involves combinatorial optimization problems....
to develop controllers
Controller (control theory)
In control theory, a controller is a device which monitors and affects the operational conditions of a given dynamical system. The operational conditions are typically referred to as output variables of the system which can be affected by adjusting certain input variables...
for autonomous robot
Autonomous robot
Autonomous robots are robots that can perform desired tasks in unstructured environments without continuous human guidance. Many kinds of robots have some degree of autonomy. Different robots can be autonomous in different ways...
s. Algorithms in ER frequently operate on populations of candidate controllers, initially selected from some distribution
Probability distribution
In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....
. This population is then repeatedly modified according to a fitness function
Fitness function
A fitness function is a particular type of objective function that is used to summarise, as a single figure of merit, how close a given design solution is to achieving the set aims....
. In the case of genetic algorithm
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
s (or "GAs"), a common method in evolutionary computation
Evolutionary computation
In computer science, evolutionary computation is a subfield of artificial intelligence that involves combinatorial optimization problems....
, the population of candidate controllers is repeatedly grown according to crossover, mutation and other GA
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
operators
and then culled according to the fitness function
Fitness function
A fitness function is a particular type of objective function that is used to summarise, as a single figure of merit, how close a given design solution is to achieving the set aims....
. The candidate controllers used in ER applications may be drawn from some subset of the set of artificial neural network
Artificial neural network
An artificial neural network , usually called neural network , is a mathematical model or computational model that is inspired by the structure and/or functional aspects of biological neural networks. A neural network consists of an interconnected group of artificial neurons, and it processes...
s, although some applications (including SAMUEL, developed at the Naval Center for Applied Research in Artificial Intelligence) use collections of "IF THEN ELSE" rules as the constituent parts of an individual controller. It is theoretically possible to use any set of symbolic formulations of a control laws (sometimes called a policies
Policy
A policy is typically described as a principle or rule to guide decisions and achieve rational outcome. The term is not normally used to denote what is actually done, this is normally referred to as either procedure or protocol...
in the machine learning
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
community) as the space of possible candidate controllers. Artificial neural network
Artificial neural network
An artificial neural network , usually called neural network , is a mathematical model or computational model that is inspired by the structure and/or functional aspects of biological neural networks. A neural network consists of an interconnected group of artificial neurons, and it processes...
s can also be used for robot learning
Robot learning
Robot learning is a subset of machine learning and robotics.Usually "robot learning" refers to learning to perform tasks such as obstacle avoidance, control and various other motion-related tasks. While machine learning is frequently used by computer vision algorithms employed in the context of...
outside of the context of evolutionary robotics. In particular, other forms of reinforcement learning
Reinforcement learning
Inspired by behaviorist psychology, reinforcement learning is an area of machine learning in computer science, concerned with how an agent ought to take actions in an environment so as to maximize some notion of cumulative reward...
can be used for learning robot controllers.
Developmental robotics
Developmental robotics
Developmental Robotics , sometimes called epigenetic robotics, is a methodology that uses metaphors from neural development and developmental psychology to develop the mind for autonomous robots. The focus is on a single or multiple robots going through stages of autonomous mental development...
is related to, but differs from, evolutionary robotics. ER uses populations of robots that evolve over time, whereas DevRob is interested in how the organization of a single robot's control system develops through experience, over time.
History
The foundation of ER was laid with work at the national research council in Rome in the 90s, but the initial idea of encoding a robot control system into a genome and have artificial evolution improve on it dates back to the late 80s.In 1992 and 1993 two teams, a team surrounding Floreano
Dario Floreano
Dario Floreano is director of the Laboratory of Intelligent Systems at the École Polytechnique Fédérale de Lausanne in Switzerland. He is one of the pioneers in evolutionary robotics, a research field in which robots are evolved using artificial evolution.Floreano received an M.A. in visual...
and Mondada
Francesco Mondada
Francesco Mondada is a Swiss researcher in artificial intelligence and robotics. He is one of the creators of the Khepera, the S-bot and the e-puck mobile robots. He got a Master's degree in Microengineering at the EPFL in 1991 and a Ph.D. degree in 1997.He was the director of from its creation...
at the EPFL in Lausanne
Lausanne
Lausanne is a city in Romandy, the French-speaking part of Switzerland, and is the capital of the canton of Vaud. The seat of the district of Lausanne, the city is situated on the shores of Lake Geneva . It faces the French town of Évian-les-Bains, with the Jura mountains to its north-west...
and a research group at the COGS at the University of Sussex
University of Sussex
The University of Sussex is an English public research university situated next to the East Sussex village of Falmer, within the city of Brighton and Hove. The University received its Royal Charter in August 1961....
reported experiments on artificial evolution of autonomous robots. The success of this early research triggered a wave of activity in labs around the world trying to harness the potential of the approach.
Lately, the difficulty in "scaling up" the complexity of the robot tasks has shifted attention somewhat towards the theoretical end of the field rather than the engineering end.
Objectives
Evolutionary robotics is done with many different objectives, often at the same time. These include creating useful controllers for real-world robot tasks, exploring the intricacies of evolutionary theory (such as the Baldwin effectBaldwin effect
The Baldwin effect, also known as Baldwinian evolution or ontogenic evolution, is a theory of a possible evolutionary processes that was originally put forward in 1896 in a paper, "A New Factor in Evolution," by American psychologist James Mark Baldwin. The paper proposed a mechanism for specific...
), reproducing psychological phenomena, and finding out about biological neural networks by studying artificial ones. Creating controllers via artificial evolution requires a large number of evaluations of a large population. This is very time consuming, which is one of the reasons why controller evolution is usually done in software. Also, initial random controllers may exhibit potentially harmful behaviour, such as repeatedly crashing into a wall, which may damage the robot. Transferring controllers evolved in simulation to physical robots is very difficult and a major challenge in using the ER approach. The reason is that evolution is free to explore all possibilities to obtain a high fitness, including any inaccuracies of the simulation . This need for a large number of evaluations, requiring fast yet accurate computer simulations, is one of the limiting factors of the ER approach .
In rare cases, evolutionary computation may be used to design the physical structure of the robot, in addition to the controller. One of the most notable examples of this was Karl Sims
Karl Sims
Karl Sims is a computer graphics artist and researcher, who is best known for using particle systems and artificial life in computer animation....
' demo for Thinking Machines Corporation.
Motivation for evolutionary robotics
Many of the commonly used machine learningMachine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
algorithms require a set of training examples
Training set
A training set is a set of data used in various areas of information science to discover potentially predictive relationships. Training sets are used in artificial intelligence, machine learning, genetic programming, intelligent systems, and statistics...
consisting of both a hypothetical input and a desired answer. In many robot learning applications the desired answer is an action for the robot to take. These actions are usually not known explicitly a priori, instead the robot
Robot
A robot is a mechanical or virtual intelligent agent that can perform tasks automatically or with guidance, typically by remote control. In practice a robot is usually an electro-mechanical machine that is guided by computer and electronic programming. Robots can be autonomous, semi-autonomous or...
can, at best, receive a value indicating the success or failure of a given action taken. Evolutionary algorithms are natural solutions to this sort of problem framework, as the fitness function need only encode the success or failure of a given controller, rather than the precise actions the controller should have taken. An alternative to the use of evolutionary computation in robot learning is the use of other forms of reinforcement learning
Reinforcement learning
Inspired by behaviorist psychology, reinforcement learning is an area of machine learning in computer science, concerned with how an agent ought to take actions in an environment so as to maximize some notion of cumulative reward...
, such as q-learning
Q-learning
Q-learning is a reinforcement learning technique that works by learning an action-value function that gives the expected utility of taking a given action in a given state and following a fixed policy thereafter. One of the strengths of Q-learning is that it is able to compare the expected utility...
, to learn the fitness of any particular action, and then use predicted fitness values indirectly to create a controller.
Main conferences
- Evolutionary Robotics
- GECCO
- IEEE Congress on Evolutionary ComputationIEEE Congress on Evolutionary ComputationThe IEEE Congress on Evolutionary Computation is one of the largest and most important conferences within Evolutionary computation , the other conferences of similar importance being Genetic and Evolutionary Computation Conference and Parallel Problem Solving from Nature .CEC, which is organized...
- European Conference on Artificial Life
- ALifeAlife-Other uses:* Artificial life* Artificial Life, Inc., , a mobile content and technology provider...
Academic institutes and researchers
- Chalmers University of TechnologyChalmers University of TechnologyChalmers University of Technology , is a Swedish university located in Gothenburg that focuses on research and education in technology, natural science and architecture.-History:...
: Peter NordinPeter NordinPeter Nordin is a Swedish computer scientist, entrepreneur and author who has contributed to artificial intelligence, automatic programming, machine learning, and evolutionary robotics.- Studies and early career :...
, The Humanoid Project - University of SussexUniversity of SussexThe University of Sussex is an English public research university situated next to the East Sussex village of Falmer, within the city of Brighton and Hove. The University received its Royal Charter in August 1961....
: Inman HarveyInman HarveyInman Harvey is a Senior Lecturer in Computer Science and Artificial Intelligence at the University of Sussex. His research interests largely centre on the development of artificial evolution as an approach to the design of complex systems. Application domains of interest include evolutionary...
, Phil HusbandsPhil HusbandsPhil Husbands is professor of Computer science and Artificial intelligence at the University of Sussex in Brighton near the East Sussex village of Falmer, near Brighton and Hove. He is head of the Evolutionary and Adaptive Systems group and co-director of the Centre for Computational Neuroscience...
, Ezequiel Di Paolo, Eric Vaughan, Thomas Buehrmann - CNRConsiglio Nazionale delle RicercheThe Consiglio Nazionale delle Ricerche or National Research Council, is an Italian public organization set up to support scientific and technological research. Its headquarters are in Rome.-History:The institution was founded in 1923...
: Stefano NolfiStefano NolfiStefano Nolfi is a director of research of the Institute of Cognitive Sciences and Technologies at the Consiglio Nazionale delle Ricerche and head of the Laboratory of Autonomous Robots and Artificial Life. He is one of the founders of Evolutionary robotics...
, Domenico Parisi, Gianluca Baldassarre, Vito Trianni, Onofrio Gigliotta, Gianluca Massera, Mariagiovanna Mazzapioda - EPFL: Dario FloreanoDario FloreanoDario Floreano is director of the Laboratory of Intelligent Systems at the École Polytechnique Fédérale de Lausanne in Switzerland. He is one of the pioneers in evolutionary robotics, a research field in which robots are evolved using artificial evolution.Floreano received an M.A. in visual...
- University of ZürichUniversity of ZurichThe University of Zurich , located in the city of Zurich, is the largest university in Switzerland, with over 25,000 students. It was founded in 1833 from the existing colleges of theology, law, medicine and a new faculty of philosophy....
: Rolf PfeiferRolf PfeiferRolf Pfeifer is professor of computer science at the , University of Zurich, and director of the Artificial Intelligence Laboratory. He has a Ph.D. in computer science from the Swiss Federal Institute of Technology in Zurich, Switzerland... - Cornell UniversityCornell UniversityCornell University is an Ivy League university located in Ithaca, New York, United States. It is a private land-grant university, receiving annual funding from the State of New York for certain educational missions...
: Hod LipsonHod LipsonHod Lipson is an American robotics engineer. He is the director of Cornell University's Creative Machines Lab , formerly known as Computational Synthesis Lab , at the Sibley School of Mechanical and Aerospace Engineering... - University of VermontUniversity of VermontThe University of Vermont comprises seven undergraduate schools, an honors college, a graduate college, and a college of medicine. The Honors College does not offer its own degrees; students in the Honors College concurrently enroll in one of the university's seven undergraduate colleges or...
: Josh BongardJosh BongardJosh Bongard is a professor at the University of Vermont and a 2010 PECASE awardee. He received his Bachelors degree in Computer Science from McMaster University, Canada, his Masters degree from the University of Sussex, UK, and his PhD from the University of Zurich, Switzerland... - Indiana UniversityIndiana University BloomingtonIndiana University Bloomington is a public research university located in Bloomington, Indiana, in the United States. IU Bloomington is the flagship campus of the Indiana University system. Being the flagship campus, IU Bloomington is often referred to simply as IU or Indiana...
: Randall BeerRandall BeerRandall D. Beer is a professor of cognitive science, computer science, and informatics at Indiana University. He was previously at Case Western Reserve University. His primary research interest is in understanding how coordinated behavior arises from the neurodynamics of an animal's nervous... - Center for Robotics and Intelligent Machines, North Carolina State UniversityNorth Carolina State UniversityNorth Carolina State University at Raleigh is a public, coeducational, extensive research university located in Raleigh, North Carolina, United States. Commonly known as NC State, the university is part of the University of North Carolina system and is a land, sea, and space grant institution...
: Eddie GrantEddie GrantEdward Grant may refer to:* Edward Grant * Edward Grant , , English cricketer* Eddy Grant , Guyanese-born musician and record producer...
, Andrew Nelson - University College LondonUniversity College LondonUniversity College London is a public research university located in London, United Kingdom and the oldest and largest constituent college of the federal University of London...
: Peter J. BentleyPeter J. BentleyDr Peter John Bentley is a British author and computer scientist based at University College London.Peter J. Bentley is an Honorary Reader and College Fellow at UCL and a Collaborating Professor at KAIST. He is also a popular science author and consultant...
, Siavash Haroun MahdaviSiavash Haroun MahdaviSiavash Haroun Mahdavi is an inventor and entrepreneur living and based in London. His work in the fields of Engineering and Design have revolutionized many products and design paradigms. His work in robotics resulted in the world's first intelligent robot that was able to autonomously recover... - University of EssexUniversity of EssexThe University of Essex is a British campus university whose original and largest campus is near the town of Colchester, England. Established in 1963 and receiving its Royal Charter in 1965...
: Simon Lucas - Brandeis UniversityBrandeis UniversityBrandeis University is an American private research university with a liberal arts focus. It is located in the southwestern corner of Waltham, Massachusetts, nine miles west of Boston. The University has an enrollment of approximately 3,200 undergraduate and 2,100 graduate students. In 2011, it...
: Jordan Pollack - IDSIAIDSIAThe Swiss institute for Artificial Intelligence IDSIA was founded in 1988 by the private Dalle Molle foundation...
and Technical University of MunichTechnical University of MunichThe Technische Universität München is a research university with campuses in Munich, Garching, and Weihenstephan...
: Juergen Schmidhuber's Robot Lab - University College of Skövde: Tom Ziemke
- U.S. Naval Research Laboratory's, Navy Center for Applied Research In Artificial Intelligence: Alan C. Schultz, Mitchell A. Potter, Kenneth De Jong
- University of Osnabrueck, Neurocybernetics Group: Frank Pasemann
- Evolved Virtual Creatures by Karl SimsKarl SimsKarl Sims is a computer graphics artist and researcher, who is best known for using particle systems and artificial life in computer animation....
(GenArts) - Ken Rinaldo artificial life robotics
- University of the Basque Country (UPV-EHU): Robótica Evolutiva, Pablo González-Nalda (in Spanish) PDF (in English)
- University of PlymouthUniversity of PlymouthPlymouth University is the largest university in the South West of England, with over 30,000 students and is 9th largest in the United Kingdom by total number of students . It has almost 3,000 staff...
: Angelo Cangelosi, Davide Marocco, Fabio Ruini, * Martin Peniak - Heriot-Watt University: Patricia A. Vargas
- Pierre and Marie Curie UniversityPierre and Marie Curie UniversityThe Paris VI University , or the Pierre and Marie Curie University , is a university located on the Jussieu Campus in the Latin Quarter of the 5th arrondissement of Paris, France....
, ISIR: Stephane Doncieux, Jean-Baptiste Mouret - Paris-Sud UniversityParis-Sud 11 UniversityUniversity of Paris-Sud or University of Paris-Sud or University of Paris XI is a French university distributed among several campuses in the southern suburb of Paris...
and INRIA, IAO/TAO: Nicolas Bredeche - RIKEN Brain Science InstituteRIKEN Brain Science InstituteRIKEN Brain Science Institute, often abbreviated as RIKEN-BSI, is a non-profit research institute focusing on neuroscience located in Wakō city, Saitama Prefecture in greater Tokyo area, Japan. It was established to lead the field of neuroscience in 1997 as one of institute in RIKEN...
: Fady Alnajjar - Karlsruhe Institute of TechnologyKarlsruhe Institute of TechnologyThe Karlsruhe Institute of Technology is a German academic research and education institution with university status resulting from a merger of the university and the research center of the city of Karlsruhe. The university, also known as Fridericiana, was founded in 1825...
, Institute of Applied Informatics and Formal Description Methods: Lukas Koenig
See also
- Artificial intelligenceArtificial intelligenceArtificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
- CyberneticsCyberneticsCybernetics is the interdisciplinary study of the structure of regulatory systems. Cybernetics is closely related to information theory, control theory and systems theory, at least in its first-order form...
- Cognitive roboticsCognitive roboticsa robot is a robot device that is built from inanimate matter. Its behavior in response to the environment is deterministic, based on how the robot was designed. Cognition is the process of acquiring and using knowledge about the world for goal-oriented purposes, such as survival...
- Evolutionary computationEvolutionary computationIn computer science, evolutionary computation is a subfield of artificial intelligence that involves combinatorial optimization problems....
- RoboticistRoboticistA roboticist designs, builds, programs, and experiments with robots. Since robotics is a highly interdisciplinary field, roboticists often have backgrounds in a number of disciplines including computer science, mechanical engineering, electrical engineering, and computer engineering...
- RoboticsRoboticsRobotics is the branch of technology that deals with the design, construction, operation, structural disposition, manufacture and application of robots...
- Robot kitRobot kitA robot kit is a special construction kit for building robots, especially autonomous mobile robots.Toy robot kits are also supplied by several companies...
- Universal DarwinismUniversal darwinismUniversal Darwinism refers to a variety of approaches that extend the theory of Darwinism beyond its original domain of biological evolution on Earth...