Mindstorm Mazes

(Experiments with the Lego Mindstorm Robots)

Between May and July 2000, a number of students visited the department from Lycees in France. These students were set the task of designing, building, and programming maze-following robots using the Lego Mindstorms system. The main objectives of this work were to:

Many thanks are due to these students for the hard work that they put into these projects. They all achieved impressive results, despite starting with no knowledge of the Mindstorms system.

The Maze

The students were all asked to build and program a robot to find a goal (a light source) in an aluminium-walled maze:

The maze was constructed from L-shaped wall sections, clipped together so that the layout of the maze could be changed easily (to make life more difficult for the robots).

The Reactive Approach

The first group of students were from Lycee St Gabriel, St Laurent sur Sevre:

The task for their robots was to implement a simple reactive algorithm that would detect collisions with walls, and then turn repeatedly until a clear path was found and the robot was able to move forwards. Because of the limited time available, no attempt was made at mapping the environment. Time-trials were held with the completed robots.

The following Quicktime movie (.MOV) files show the robots in action and the construction of the robot hardware.

  1. One of the robots successfully finds the goal. The robot's "whiskers" detect the wall and, if the wall is only on one side, turn away from it. If the wall is directly in front of the robot, it makes an arbitrary choice of trun direction. (This robot appears to prefer right turns.) Movie 1 (3.3Mb)
  2. A second reactive robot goes in search of the goal but, in this particular maze layout gets stuck revisiting a dead-end. (One problem with the reactive approach is the extent to which individual maze layouts are especially well or badly suited to a particular robot.) Movie 2 (2.4Mb)
  3. This maze layout was specifically designed by the onlookers to cause problems for this robot. Because the robot responds only to collisions, it does not detect the gaps on its left and does not venture into the interesting part of the maze. Instead it makes a quick exit! Movie 3 (1.1Mb)
  4. This clip gives an all-round view of the robots for those whos want to see how they were put together. (They're both based on one of the standard designs recommended by Lego. Movie 4 (10.5Mb)

Map-Building

The second group of students were from Lycee Chevrollier, Angers

Their task was to extend the functionality of the robot to include map-building and path planning. This robot adopted a "wall-following" approach to exploring the maze. The hardware was designed to include a touch sensor that maintained contact with the wall.

The robot built a grid map of the maze and iteratively marked as "closed" the cells with three closed sides. The robot effectively adds "virtual walls" to its map to close off the dead ends. It then finds its way to goal, again by wall-following, but this time following the virtual walls as well.

  1. The robot explores the environment and builds its map. The robot is clearly moving with much more "confidence". Notice how, by following the wall on its left, the robot takes a very circuitous route to the goal. Movie 1 (3.7Mb)
  2. By using its map, the robot can now plan a path that avoids all of the dead ends and goes directly to the goal. Movie 2 (0.3Mb)
  3. An all-round view of this robot. Movie 3 (2.9Mb)