Intel Lego

Description

A Lego Mindstorms finds its way through the Maze of Wiering and Schmidhuber.

Intellego Simulator

1. If you only want to use the simulator, you can skip this step. Otherwise download Lejos, read the documentation on how to install it. Make sure the environment variable LEJOS_HOME is set to the path where Lejos is installed.
2. Get our improved version of Intellego.
3. Adjust settings.properties according to your installation path of Intellego
4. run it: java -cp lib/classes.jar:build/java intellego.Intellego (use a ';' instead of ':' for Win32 machines)
5. Have fun!

Simulation of the Maze of Wiering and Schmidhuber with a Finite State Automaton Using Evolution

Primitives

• Forward
• Backard
• Turn Left 90°
• Turn Right 90°

Transition triggers

• Bump sensor Left
• Bump sensor Right
• Metal stripe sensor
• Turn-timeout (only for Turn left or right)

Genome

• A genome is a finite state automaton with n states. Each state has an associated primitive action. For all triggers there is a leaving transition (deterministic) out any state; some states additionally have an associated timeout to trigger a state transition.
• A gene is a state of the automaton, plus the defined transitions to other states.

Genetic parameters for the simulation

• Population size
• Genome size
• Evaluation function (end position, time to get to there, progress rate, ...)
• Initial genomes (random, ...)
• Crossing (rate, in function of evaluation (e.g. crossing among strong individuals), ...)

Ideas for a genetic algorithm to develop a controller (obsolete!)

Terms used here derive from two areas: genetics (bold-faced) and informatics/robotics (in italics).

• A genome of some length represents the robot's controller; it is a sequence of genes each of which represents a state of the robot's controller: some working and some - possibly implicit - event (sensor input or timeout) that interrupts the work and induces a transition to the next state in the sequence.

• The following primitives might be considered

  • forward_l: fowarding until front sensor is activated; when bumping into the wall on the left hand, move a bit backward, turn a bit right, go on; when bumping into the wall on the right hand, move a bit backward, turn left, go on.
  • forward_r: (analogous)
  • turn left (see below, time related parameters)
  • turn right

• These primitives have the following main goals

  • to be as much time-independent as possible;
  • a gene should represent a subgoal/a step in the maze, tolerating some (small) variations.

• Genes can be represented by integer constants.
• A population is then simply represented by a set of genomes.
• Evolution of the fixed-size population is simulated by the means of crossing and mutation.
• An evaluation function estimates each individual in the population with respect to its capacities, in our case how well it does find its way through the maze.

• Time independent parameters

  • Population size
  • Genome size
  • Evaluation function (end position, time to get to there, progress rate, ...)
  • Initial genomes (random, ...)
  • Crossing (rate, in function of evaluation (e.g. crossing among strong individuals), ...)
  • Mutation (rate, in function of evaluation (e.g. mutate weak individuals - perhaps it helps - by chance), ...)

• Time dependent parameters (might be different in simulation and in the mindstorm)

  • Delta backward time (just enough to free the robot when bumped into a wall?)
  • Delta turn time (say about 5°)
  • Turn time (say about 20°)

Links

LeJOS related

• leJOS, Lego Java OS
• Intellego Visual Mindstorms simulator (using leJOS)
• improved leJOS API
• rcxcomm, a communication API for leJOS
• leJOS Eclipse-Plugin

Java related

• The basics of Java class loaders

Misc

• Mindstorms internals
• GNU cross compiler for the Hitachi H8/300HS
• Java2HTML source code highlighter