PAReX Weblog Entries

Maze Mapping with your Robot.

Fred used mapping technics to propel himself into 1st place at the Nov 2nd 2002 PAReX Autonomous Event. This article details the technics he used to map the maze in his Mazimillian Smarticus II robot.

The maze-mapping mode includes options for left or right wall following to map the maze. When running that mapped maze, it can return to start along the shortest path or repeat the shortest path from start to finish.

This bot uses Path Mapping, not Maze Mapping. It works very well with a right or left following robot to map the Path as described below.

Path Mapping Algorithm Description

Look at 4x3 maze below. Each square is numbered, in this case starting at 1. A typical right wall following robot would start at location 1, and go through the following path 1, 5, 6, 2, 6, 7, 3, 7, 6, 5, 9, 10, 11, 12, 8 and then 4 to complete the maze.

In a computer algorithm you might call the first step in your path 1, and you are in square 1. Your second step in your path would be 2 and you would be in square 5. Or using a one-dimensional array called path ... Path(1) = 1 and Path(2) = 5. The first part of the path-mapping array would look like this:

Path	Square
1	1
2	5
3	6
4	2
5	6

So how does the path mapping help you? First lets define a value, CSIP (Current Square in Path). In the above example your CSIP might be 1 through 5 for the portion of the explored maze. You have already found one dead end, so how to account for it? Do the check on where you are now, and where your were two steps ago. Since Path(CSIP) = Path(CSIP-2) in the case where CSIP = 5, just eliminate this dead end by zeroing out the dead end in the array and setting CSIP back to CSIP - 2. The sample code is below.

    If CSIP > 2 Then
        If Path(CSIP) = Path(CSIP-2) Then
            Path(CSIP) = 0
            Path(CSIP-1) = 0
            CSIP = CSIP - 2
        End If
    End If

Obviously, if CSIP is 1 or 2, there is no way to shorten the path, so don't check those cases. This algorithm results in your array looking like this.

Path	Square
1	1
2	5
3	6
4	0
5	0

and CSIP = 3

Your robot will continue to right wall follow, giving you new Path(4) = 7. You run you mapping code, and nothing changes. Your robot will continue to right wall follow, giving you Path(5) = 3. You run you mapping code, and again, nothing happens.

Your robot will continue to right wall follow, returning you to Path(6) = 7.

Path	Square
1	1
2	5
3	6
4	7
5	3
6	7

and CSIP = 6

You then run you mapping code, and you get rid of another dead end, resulting in the following.

Path	Square
1	1
2	5
3	6
4	7
5	0

and CSIP = 4

You robot continues to right wall following, getting back to square 6. Your array looks like before running the mapping subroutine

Path	Square
1	1
2	5
3	6
4	7
5	6
6	0

and CSIP = 5

You then run you mapping code, and you get rid of another dead end, resulting in the following.

Path	Square
1	1
2	5
3	6
4	0
5	0

and CSIP = 3

And the true beauty is that now your bot is back to square 5, your array would look like this before running the algorithm

Path	Square
1	1
2	5
3	6
4	5
5	0

and CSIP = 4

After running the mapping subroutine you are down to:

Path	Square
1	1
2	5
3	0
4	0
5	0

and CSIP = 2

With your bot now moving up into new territory (square 9) and your path mapping knowing to ignore squares 2, 3, 6 and 7.

Your bot will now have a complete and short path back from start to finish. The path can be run from end to start (for our expert class maze mapping), or it can be used to run the advanced maze in a faster time for those configurations you choose to run twice. Obviously, when following the path (instead of mapping it) the bot needs to decide which way to turn based on the path, not just it simple right or left following mode used for path mapping.

Path Mapping Description Special Case Number 1

What if one wall was removed from the maze we used above, the wall between squares 2 and 3. Now your right wall following robot would follow a path of 1,5,6,2,3,7,6,5,9,10,11,12,8,4

The code used above wouldn't work, since you never hit a typical dead end. How do you handle that? Basically, just look to see if the bot backtracked ANYWHERE on its path. The code would look like this.

    If CSIP > 1 Then
      For P = CSIP to 2             ' Check to see if back tracking anywhere on path.
        If (Path(CSIP) = Path(P-2)) and (Path(P) <> 0) Then
          CSIP = P - 2              'Reset CSIP to eliminate dead ends
          For Q = (CSIP + 1) to 48  '48 is my assume maximum path length
             Path(P) = 0            'Set any back tracked portion of the maze back to zero
          Next
        End If
      Next
    End If

Path Mapping Description Special Case Number 2

There is a weakness with this algorithm. The maze must be a rectangular, treed maze. It can't find the shortest path in a non-treed maze. A non-treed maze is one with more than one path to the finish line, such as below.

A right wall following robot would follow the path 1,5,6,2,3,7,11,10,9,13,14,15,16,12,8,4. It would never be in the same space twice, , and would therefore not recognize the shorter path of 1,5,9,13,14,15,16,12,8,4 (i.e. skipping 6,2,3,7,11,10). Because you aren't directly mapping the walls, you don't realize that there is no wall between squares 5 and 9.

Details, Details, Details

So, using the above method for path mapping, how do you know when to run the maze algorithm? Obviously, every time you enter a new square. How do you know you are in a new square?

1. Every time you have to turn, you are in a new square. You know you have to turn when you see a new opening, or you can't go straight any more. Exception - You need to check to ensure you have traveled a minimum distance of about 3 inches to ensure you just aren't doing two turns in a dead end).
2. Every time you travel in a straight line with no openings for over about 14 inches. This ensures that you count a long corridor as more than one square.

You assign numbers to all squares, but you don't always know the size of the maze you will run. Also, you start point might not be the lower left corner. How do you attack this?

1. Assume you are in the middle of a really big maze, maybe location 12 and 12 of a 24 by 24 maze. Your starting location number would be X + (Y-1)*24 or 12 + (12-1)*24 or 276. The size of the maze matters very little. If you are heading right, your new square number is one greater than before. If you are heading left, your new square number is one less than before. If you are heading up, your new square number is 24 greater than before (assuming you use the numbers for a 24 x 24 maze). If you are heading down, your new square number is 24 less than before.
2. Assume a smaller maze and configure the starting location of the bot based on what the actual maze looks like.

How do you know what direction you are heading?

1. I assume I start facing up. If I turn left I must be facing left. If I turn left again I must be facing down. I use a compass module to help ensure I get full 90 degree turns.

By The Way

A display of some sort is essential in programming a bot of this type. I used a 2 line by 16 character LCD. You need to see information during your software development phase such as where the robot thinks it is, and which direction it thinks it is pointing, and any temporary error codes that you program in.