Mazes for LEGO MindStorms NXT Robots
Here we will look at two types of mazes that are suitable for use with LEGO MindStorms NXT robots:-
1.0 Mazes with Walls, and
2.0 Line Mazes.
1.0 A Taste of Mazes Similar to International Rescue B Mazes.
There has been local interest in the new experimental International RoboCup "Rescue B" challenge introduced by the committee headed by Dr. Damien Kee. This was used as a demonstration event in the World RoboCup in Singapore in 2010, and I am told unofficially that it will be a competition event in Istanbul in RoboCup 2011. An important change from the traditional RoboCup Junior Rescue Challenge is the inclusion of a maze. In competition, this maze is reconfigurable, and hence can be a constantly changing new challenge to students.
This new Challenge has stirred interest by some teachers who have contacted me. Unfortunately the Rescue B competition arena is large, and not easily transportable (not in my small car anyway!) Hence we looked at making up mazes from reasonably robust stackable "tiles" that could be quickly placed adjacent to each other to form different mazes, that could be easily transported between schools, and yet would still preserve some of the taste of Rescue B. Successful use of these tiles could be regarded a precursor to constructing a full International Rescue B course.
The bases of the tiles are 30 cms. square to provide maneuvering spaces for robots that is similar to that provided in Rescue B. The height of the walls has been reduced both for stability of these maze components, and to allow the rest of the class to more easily see their robots going around the maze. The wall height selected is 13 cms., the same height as the 375 ml. soft drink can used in the Australian version of the RoboCup Junior Rescue competitions; hopefully this will assist transfer of robot construction expertise between this maze and the Australian RoboCup event. The tiles are painted white to imitate the preferred Rescue B maze colours. The tops of the vertical portions of the tiles have been colour coded to allow easy student maze assembly. To imitate Rescue B’s “forbidden” areas, squares of black cardboard can be placed over these tile bases.
Initial sketches are shown below. Tiles 0, 1 and 2L are mutually stackable, allowing both compact storage and easy transfer of these maze components between schools. Tiles 2H only stack with themselves, but this is not a problem because I have only had to use two. Tile 3 has not been found necessary, so far.
A video of this arena being assembled can be see here.
The tiles were cut from a light grade of MDF board using power hand tools with the board perched on a stone wall in my back yard (I did not then have access to a workbench). I later purchased a small workbench that made things much easier. A video of Grade 8 student Yaya Lu making some tiles (she wanted some more for a bigger maze), and of one of her robots going around a maze, can be seen on the web page here.
Given a stock of tiles, many maze and arena configurations are possible. Some of the possible maze and arena configurations are shown below. A summary of the tile requirements of the illustrated mazes and arenas can be seen by clicking here.
1.1 A First Stock of Tiles.
Let us consider a stock of one tile of type 0, seven tiles of type 1, and 6 tiles of type 2L. Mazes 1 to 8 and Arenas 1 and 2 can be constructed using these components; as shown below.
Maze 1. Maze 2a. Maze 2b
Maze 1 is just about the simplest possible maze. One of the traditional methods used by robots to solve mazes involves keeping an unbroken wall to the left (or to the right) of the robot all the way from the start of the maze to the end. This technique will solve many (but not all) mazes. So that neither left nor right wall-following robots have an advantage, robot competition mazes are often chosen to have the same number of left and right-hand wall components to pass on the way to the exit. Maze 1 fulfills this requirement. However for classroom use any type of maze is OK, and simpler ones are preferable for first student maze attempts. Summarizing; Maze 1 is 3x2 tiles, one of type 0, one of type 1, and four of type 2L. Between the start and the finish there are 4 wall segments to the left, and 4 wall segments to the right.
Maze 2a can be useful as a second maze in a class where there is a large disparity of abilities. It includes 90 degree turns to both the right and left of the robot, two dead ends, and a more difficult 180 degree turn. Maze 2a uses only one wall gap that serves as both the entrance and the exit to this Maze. The robot's path is longer than in Maze 1, with robots that follow either the left or the right walls passing eleven wall segments. Summarizing; Maze 2a is 3x2 tiles, two of type 1, and four of type 2L. Between the start and the finish there are 11 wall segments to the left or to the right.
Maze 2b is another small maze that can also be useful in a class where there is a large disparity of abilities. Robots following the left wall have a relatively easy path. The path for robots following the right wall is relatively much harder, including a 180 degree turn, and with the path also including a forbidden black zone of the type used in International RoboCup Rescue B. Hopefully Mazes 2a and 2b will be able to keep some of the best students occupied while the rest of the class solves Maze 1. Summarizing; Maze 2b is 3x2 tiles, one of type 0, one of type 1, and four of type 2L with one type 2L being covered by black cardboard to represent a forbidden area. Between the start and the finish there are 4 wall segments to the left, and the equivalent of 6 wall segments to the right.
Maze 3. Maze 4.
Maze 3 is harder than Maze 1, as both left and right wall-following paths include 180 degree turns. It is a suitable follow-up to Maze 1. Summarizing; Maze 3 is 3x3 tiles, one of type 0, two of type 1, and six of type 2L. Between the start and the finish there are 9 wall segments to the left, 9 wall segments to the right.
Maze 4 may be suitable as a follow-up for Maze 2 (for a class with varying abilities). The left wall-following path is shorter than that of Maze 3, but the right wall-following path includes a forbidden zone. Summarizing; Maze 4 is 3x3 tiles, two of type 0, one of type 1, and six of type 2L with black cardboard covering one of the 2L tiles to indicate a forbidden zone. Between the start and the finish there are 7 wall segments to the left, and the equivalent of 9 wall segments to the right.
Maze 5.
Maze 5 can be used as a larger follow-up to Maze 3. Summarizing; Maze 5 is 4x3 tiles, six of type 1, and six of type 2L. Between the start and the finish there are 12 wall segments to the left, and 12 wall segments to the right.
Maze 6.
Maze 6 could be used as an alternative to Maze 5 as a follow-up to Maze 3. Summarizing; Maze 6 is 4x3 tiles, seven of type 1, and five of type 2L. Between the start and the finish there are 11 wall segments to the left, and 11 wall segments to the right.
Maze 7
Maze 7 could be use as a follow-up to Maze 4, useful when the students have a wide range of abilities. A left-wall-following robot will have an easier time than a right-wall-following robot, because the latter has the added complication of encountering a forbidden zone. Summarizing; Maze 7 is 4x3 tiles, seven of type 1, and five of type 2L with black cardboard covering one of the 2L tiles to indicate a forbidden zone. Between the start and the finish there are 11 wall segments to the left, and the equivalent of 11 wall segments to the right.
Maze 8
Maze 8 could also be used as an alternative to Maze 7 as a follow-up to Maze 4, useful in classes where the students have a wide range of abilities. A right-wall-following robot will have an easier time than a left-wall-following robot, because the latter has the added complication of encountering a forbidden zone. Summarizing; Maze 8 is 4x3 tiles, one of type 0, six of type 1, and five of type 2L with black cardboard covering the 0 tile to indicate a forbidden zone. Between the start and the finish there are 11 wall segments to the right, and the equivalent of 11 wall segments to the left.
Arena 1
Arena 1 is an alternative closed arena layout that could be used with Challenges that incorporate robot races; e.g. www.DrGraeme.net Challenge 52 . It can be used to run the type of oval races run in the Roman coliseum or Indianapolis race track. Robots can be timed with the best time winning, or (more popularly in the classes I have assisted) two robots are placed in the arena starting at the positions indicated by the green dotted arrows, and the race ends when one robot catches up with the other. Summarizing; Arena 1 is 2x3 tiles plus 1; three of type 1, and four of type 2L. One lap of the arena passes 10 outside wall segments.
Arena 2
Arena 2 is an alternative that could be used instead of Arena 1 when there is more classroom space available. These arenas can be used with Challenges that incorporate robot races; e.g. www.DrGraeme.net Challenge 52 . It can be used to run the type of oval races run in the Roman coliseum or Indianapolis race track. Robots can be timed with the best time winning, or (more popularly in the classes I have assisted) two robots are placed in the arena starting at the positions indicated by the green dotted arrows, and the race ends when one robot catches up with the other. Summarizing; Arena 2 is 2x4 tiles plus 2; six of type 1, and four of type 2L. One lap of the arena passes 12 outside wall segments.
1.2 A More Versatile Stock of Tiles.
A more versatile stock of tiles that allows the construction of more complicated arenas and mazes (including one maze that can not be solved by left- or right-hand wall following) can be constructed from a stock of 3 tiles of type zero, 12 tiles of type 1, 9 tiles of type 2L, and 2 tiles of type 2H.
The two tiles of type 2H can also be usefully used as "entry" and "exit" tiles for many of the mazes.
Maze 9
Summarizing; Maze 9 is 4x4 tiles, eleven of type 1, and five of type 2L. Between the start and the finish there are 14 wall segments to the right, and 14 wall segments to the left.
Maze 9a
Summarizing; Maze 9a is 4x4 tiles, ten of type 1, and six of type 2L. Between the start and the finish there are 8 wall segments to the right, and 12 wall segments to the left.
Maze 10
Summarizing; Maze 10 is 4x4 tiles, two of type 0, six of type 1, and eight of type 2L. Between the start and the finish there are 15 wall segments to the right, and 15 wall segments to the left.
Maze 10a
Summarizing; Maze 10a is 4x4 tiles, one of type 0, eight of type 1, and seven of type 2L. Between the start and the finish there are 15 wall segments to the right, and 15 wall segments to the left.
Maze 11
Summarizing; Maze 11 is 4x4 tiles, one of type 0, eight of type 1, and seven of type 2L. Between the start and the finish there are 15 wall segments to the right, and 15 wall segments to the left.
Maze 12
Summarizing; Maze 12 is 4x5 tiles, one of type 0, ten of type 1, and nine of type 2L. Between the start and the finish there are 17 wall segments to the right, and 17 wall segments to the left. The right-hand following path has no sharp turns. The path taken by a right-hand wall follower is thus easier than the path for a left-hand wall follower.
Maze 14. The extra tiles allow the assembly of a much more elaborate maze, which has two alternate paths from the entrance to the exit. This is not a maze for beginners in robot construction, but should be a good challenge for an experienced roboticist. Summarizing; Maze 14 is 5x5 tiles, three of type 0, eleven of type 1, and nine of type 2L and two of type 2H. Between the start and the finish there are 17 wall segments to the right, and 17 wall segments to the left.
Maze 15. A search for an ice-cream in the center of the maze – 15 tile walls for right hand wall following robots, and 16 tile walls (including more difficult turns) for left hand wall following robots. Summarizing; Maze 15 is 5x5 tiles, three of type zero, eleven of type 1, and nine of type 2L, and two of type 2H. Between the start and the ice-cream there are 16 wall segments to the left, and 15 wall segments from the right to the ice cream.
Maze 16. A search for an ice-cream in the center of the maze – almost the same as maze 15, but with a "2L" tile being replaced by a "1" tile, making a "loop" or discontinuity between the walls around the edge of the maze and the center walls. This makes this treasure hunt much more difficult, because it is impossible for a purely wall-following robot to solve this maze. Hopefully this will keep the more advanced students occupied for a few moments while the rest of the class catches up! Summarizing; Maze 16 is a 5x5 assembly of tiles, three of type zero, twelve of type 1, and eight of type 2L, and two of type 2H.
Arena 3
Arena 3 is a longer version of Arena 2. It can be used to run the type of oval races run in the Roman coliseum or Indianapolis race track. Robots can be timed with the best time winning, or (more popularly in the classes I have assisted) two robots are placed in the arena, and the race ends when one robot catches up with the other after starting at the positions indicated by the dotted green arrows. Summarizing; Arena 3 is 5x2 tiles plus 3, nine of type 1, and four of type 2L. One lap of the arena passes 14 outside wall segments.
Arena 4
If Arenas 1 to 3 represent oval race tracks, Arena 4 could be said to represent a road-racing track - it has more corners, one of which turns the "other way". Robots can be timed with the best time winning, or (more popularly in the classes I have assisted) two robots are placed in the arena, and the race ends when one robot catches up with the other after starting at the positions indicated by the dotted green arrows. Summarizing; Arena 4 is 4x3 tiles, five of type 1, and seven of type 2L. One lap of the arena passes 16 outside wall segments.
Arena 5
Arena 5 is a bigger version of Arena 4, useful if you have room to use it in your classroom. Summarizing; Arena 5 is 4x4 tiles, nine of type 1, and seven of type 2L. One lap of the arena passes 18 outside wall segments.
Arena 6
If Arenas 4 & 5 represent a road course, Arena 6 represent a formula 1 course! This course is tough, many bends and direction changes. It should probably only be used with experienced students. Robots can be timed with the best time winning, or (more popularly in the classes I have assisted) two robots are placed in the arena, and the race ends when one robot catches up with the other after starting at the positions indicated by the dotted green arrows. Summarizing; Arena 5 is an irregular 6x4 group of tiles, two of type zero, ten of type 1, and eight of type 2L, and two of type 2H One lap of the arena passes 24 outside wall segments.
1.3 Rescue B Example Mazes
Maze 20. This maze is patterned after the top floor maze shown in the International RoboCup Rescue B rules. It can be set out using the "versatile" stock of tiles. Summarizing; Maze 20 is 4x4 tiles, nine of type 1, and seven of type 2L, with two type 2L and one type 1 tiles being covered by black cardboard to represent forbidden zones. To solve this maze, a robot would pass the equivalent of 14 "wall segments" to the left, 12 "wall segments" to the right.
Maze 21. This maze is patterned after the lower floor maze shown in the International RoboCup Rescue B rules. This maze requires a much larger set of tiles than the "versatile" set of tiles. Summarizing; Maze 21 is 10x4 tiles, three of type 0, twenty-one of type 1, and sixteen of type 2L, with six type 2L tiles being covered by black cardboard to represent forbidden zones. To solve this maze, a robot would pass the equivalent of 38 "wall segments" to the left, 30 "wall segments" to the right.
1.4 A Bigger Maze
Maze 17. This maze is just a little bigger than a Rescue B maze - which is usually either 4x4 (top floor, see Maze 20 above), or 10x4 tiles, (lower floor, see Maze 21 above). A wall-following robot has to navigate 50 interior walls to the left, or 50 interior walls to the right to solve this maze. Construction of this maze requires a very big stock of tiles, but since it of comparable complexity to a Rescue B maze, Rescue B robots should have the capability to able to solve this Maze. Summarizing; Maze 17 is 5x10 tiles, six of type 0, twenty-four of type 1, and twenty of type 2L.
2.0 A Line Maze
The mazes above have real, touchable, walls. A cheaper alternative is to use line mazes, where the maze is defined by the use of (e.g.) black tape on a white background. An example of this type of maze, made using black electrical tape on a white foam background, is shown below:
This maze above was constructed using interlocking foam tiles purchased from a local discount store, and black electrician's tape. The larger rectangular areas are used as the start and/or finish ends of the maze. Temporary mazes can be easily and quickly constructed using this method, see "advantages" below.
How to solve the maze using robots: Provided the line maze does not have "loops" of the type shown in maze 16 above, this type of maze allows robots to use light sensors to solve the maze by following either the left or right edges of the black lines.
Advantages: Can be constructed more quickly and cheaply than a walled maze. Even light-coloured masking tape on a dark classroom floor can function as an effective temporary maze. Although there is theoretically no restriction on the complexity of the mazes that can be constructed by either the walled or line maze methodologies, the restrictions imposed by classroom finances mean that in practice the line maze method can be used to construct more complex mazes in the classroom than the walled maze methodology.
This type of line maze can also be useful when coping with an advanced student, as it can be quickly constructed using masking tape on a classroom floor to keep a more advanced student occupied while the rest of the class catches up...
Disadvantages: In my experience, students don't seem to regard line mazes as "real mazes". They seem much more enthusiastic when their robotics challenge involves a walled maze rather than a line maze. Walled mazes are also more "forgiving" than line mazes. In my experience, the sharp ends of the lines in tape mazes are not easy to follow when the robots have been constructed by beginning students. It is not a coincidence that the Australian RoboCup Rescue mat (see here) has gentle curves, and very few sharp ends.
Line Maze Construction hints: The Pololu robotics site has some useful hints regarding construction of line mazes using black electrician's tape (but note that the comments on the bottom of the page regarding 3pi robots and QTR sensor arrays do not apply to our LEGO MindStorms robots). To see these construction hints, click here; (or if this web page is not available, the instructions as they were in February 2011 can be seen here.)
Running a LEGO NXT Robot through this Maze: Two LEGO light sensors were attached to ClareBot. The standard "line following" (actually it is "edge following") program supplied with RobotC was loaded. The light sensors were calibrated, and the motor speeds adjusted from 60 and 20 forwards, to 60 forwards and 30 backwards. To see what happened when the left light sensor was used to follow the left edge of the maze, click on one of these: [Video PCBig, PCSmall, apple]. To see what happened when the right light sensor was used to follow the right edge of the maze, click on one of these: [Video PCBig, PCSmall, apple]. The videos are speeded up. The actual time taken to wobble around this maze was about 2 1/2 minutes in both cases.
Solving More Complex Line Mazes: Some robotics competitions use a more advanced challenge. In this challenge, student's robots have to first find their way to the end of the line maze, and then have second run through the same maze. Their overall time is the sum of the two runs. The essence of this challenge is that the robot will "learn" the best path on the first run, and will ignore all the false side paths in the second run.
Programming our robot for this challenge can be quite complex. Hints for solving this type of challenge are available. If you ignore the reference to five light sensors (our LEGO robots will usually employ only three light sensors), some useful hints for solving this type of challenge can be seen by clicking here.
www.DrGraeme.net - LEGO NXT MindStorms - Free Tutorials - Maze Components (Google URL shortener http://goo.gl/5Fsc )