Transcript Slide 1

An EA for Box Pushing with a
LEGO Mindstorms Robot
By
Sara L. Skroh
December 5, 2003
Introduction
• What is a LEGO Mindstorms Robot?
– LEGO parts & RCX (Robotic Command
eXplorer)
– Hitachi H8 CPU
– 32KB of RAM
– Light sensor
– Push sensor
– 2 motors
Research Questions
• How can an EA be used to optimize box
pushing?
– An EA can be used to optimize weights of a neural
network controller
• Can an EA for optimizing box pushing be
implemented on a LEGO Mindstorms robot?
– Not with just the software that is shipped with the
LEGO Robotics Invention System
– Thanks to Daniel Berger (Max Planck Institute for
Biological Cybernetics [7] it can be done
Motivation
• To perform low-level functions needed in
more complex applications
• To better understand what goes into
developing high-level robotic functionality
• Robot Soccer
• Military Applications
• etc.
Background
• Spronck et al. [4,5] using a simulated robot with
eight proximity sensors compared a feedforward
neural network design with a recurrent neural
network design evolving the connectivity of the
networks and found that the recurrent neural
network works better.
• Sprinkhuizen-Kuyper et al. [3] explore several
fitness functions that use global vs. local and
external vs. internal fitness measures. They
found that a a global, external measure
performed the best for box pushing.
Background (contd.)
• Montana and Davis [1] developed a
genetic algorithm to train a feedforward
neural network that outperformed
backpropagation on their data.
Methodology
• EA to optimize weights of a neural network
• Neural Network – simple feedforward
architecture
– 2 inputs (light sensor & push sensor) [0, 1023]
– 3 hidden nodes
– 2 outputs (left motor & right motor) [-8, 8]
The EA
• Population of individuals representing weight
matrices for the neural network
• Fitness function
– sets an individual's fitness value based on the amount
of time it takes the robot to reach the goal pushing the
box using the weight represented by the individual.
• Genetic Operators
– Cross-over – elements in parent weight arrays
– Mutation – add, subtract, multiply, or divide elements
in the child by a random factor
Parameters
•
•
•
•
•
Chance of cross-over
Frequency of crossover
Chance of mutation
Frequency of mutation
Population size
Results / Conclusions
• NN results
• No EA results yet
• Can’t conclude much without results
References
•
•
•
[1] Training Feedforward Neural Netwrks Using Genetic Algorithms
Montana, David J., Davis, Lawrence;
Proceedings of the Eleventh International Joint Conference on Artificial Intelligence,
Volume: 1, Aug. 1989
Pages(s): 762-767
[2] Evolutionary Learning of a Robot Controller: Effect of Neural Network Topology
Sprinkhuizen-Kuyper, I.G., Postma, E.O., and Kortmann, R.
BENELEARN 2000, Proceedings of the Tenth Belgian-Dutch Conference on
Machine Learning,
Tilburg University, Tilburg,
Page(s): 55-60.
[3] Fitness functions for evolving box-pushing behaviour
Sprinkhuizen-Kuyper, I.G., Kortmann, R., and Postma, E.O.
Proceedings of the Twelfth Belgium-Netherlands Artificial Intelligence
Conference 2000,
Page(s): 275-282.
References (contd.)
•
•
•
•
•
[4] Evolutionary Learning of a Neural Robot Controller
Spronck, P.H.M., Sprinkhuizen-Kuyper, I.G., and Postma, E.O.
International Conference on Computational Intelligence for Modelling, Control and
Automation - CIMCA'2001, ISBN: 0-858-89847-0
Page(s): 511-519.
[5] Evolutionary Learning of a Box-pushing Controller
Spronck, Pieter, Sprinkhuizen-Kuyper, Ida, Postma, Eric and Kortmann, Rens
Computational Intelligence in Control. Idea Group Publishing 2002
Page(s): 96-113. ISBN 1-59140-037-6.
[6] Mindstorms: not just a kid's toy
Wallich, P.;
Spectrum, IEEE , Volume: 38 Issue: 9 , Sept. 2001
Page(s): 52-57
[7] http://www.kyb.tuebingen.mpg.de/bu/people/berger/mindstorms.html
[8] http://mindstorms.lego.com/eng/default.asp
Questions?