PAReX Weblog Entries

A Maze Mapping Algorithm

Andy Michalicek,
PAReX, November 26, 2003

This is one of several maze mapping techniques you can find in the literature.  The advantage of this one is that it requires just a small amount of memory.  Also, mapping of the maze defines the return path that will be used in the competition, without requiring extra software.

In this approach, the maze is treated as a collection of squares or cells. In each cell, we will be recording where the walls are, and a history of where we move. Because the PAReX competition maze consists of multiples of 4’x 4’ sections, with walls placed on 12” boundaries, a 12”x12” cell is a natural choice. For a maze that is 4’x4’, sixteen bytes of storage are needed (4 x 4 = 16). For a maze that is 8’x8’, 64 bytes are needed. The maze then is mapped as a two dimensional array of bytes.

Recording the Cell Wall Configuration

We will use N, E, S, and W as absolute directions.  We can do this even if those directions are not the true compass directions, as an assumed convenience. We will assume that when the robot starts out, it is facing north. We will talk of the robot moving Forward (F), right (R), or left (L), where F is to move forward to the next cell, and R and L is to turn right or left and then move to the next cell in that direction. The robot needs to keep track of its heading, because walls within a cell are recorded per the side of the cell they are located: north, east, south, or west.

In addition to physical walls, the robot will deal with virtual walls. A robot does not distinguish between a physical and virtual wall when choosing which way to travel, both are valid blocks to its movement.  This comes into play where it has traveled along one path in a maze, has hit a dead end, and has had to backtrack. It will treat that path as if virtual walls existed, and not travel from that cell in that direction again.

As the robot moves through the maze, it analyzes the wall layout and records it in its map. It stores this in one byte per cell, where two bits are assigned to each wall. For each cell in the map the four walls are coded as follows:

Code	Binary	Meaning
0	00	Untraveled
1	01	Traveled
2	10	Not Used
3	11	Don’t Go There

‘Untraveled’ means that the robot has not traveled there. ‘Traveled’ says that the robot has already moved in that direction. ‘Don’t Go There’ can either mean that a wall is there, or that the robot has gone there already, but at some point ran into a dead end, and had to back track, and so it will never want to go there again. When entering a new cell, the robot will only have to look forward, to the right, and to the left. It will assume that in the direction behind it, it can mark the wall with a code of 1, for ‘Traveled’.

When the walls are analyzed and stored in the map, the robot does so using absolute directions of N, E, S, or W, rather than forward, left or right. This is because ‘forward’ for the robot can be any absolute direction at different time while searching through the maze.  The storage pattern for each cell is as follows:

| North | East |  South |  West  |

xx xx xx xx = 8 bits

In the starting square, it is facing North, and there are three walls located at east, south, and west, so it would record the starting square as:

00(N) 11(E) 11(S) 11(W) = 00 11 11 11 binary = 0333 quad

So at the start, the heading is N, and Map(0,0) = 0 3 3 3.

Movement Algorithm

For the PAReX maze competition, there are two modes: Search, and Return. In search, we are looking through the maze for a tennis ball, mapping the maze as we go. In return, we have found the tennis ball and want to take the most direct path back to the start.

We are now ready to start walking through the maze. Since there is a PAReX rule that the maze will be laid out in a tree structure without any cross-over paths, we can follow each branch of the maze till we find the tennis ball, or follow it to a dead end. If we find a dead end, we will backtrack to where we can start down another path. While we are backtracking, we will insert virtual walls behind us in the map so that we ‘Don’t Travel There’ again, just as if walls existed in those spots.

For convenience, we are referring to the passageway where a wall could exist as a wall. Below you will find the phrase “the wall the robot will travel through” or the phrase “the wall the robot just came through” not to mean the robot can pass through walls, but to mean the passageway where a wall would have existed. This was done for readability (of the author if nobody else).

Search Mode

In this mode, movement is always to a ‘0’ unless backtracking, in which case movement is to a ‘1’.

1.	Record the front, right, and left walls into the map.
2.	Check F, R, and L for a wall code of value 0. If F is 0, go there. Else if R is 0, go there. Else if L is 0, go there. The choice to look at R before L was arbitrary. If there are no 0 codes, find the ‘1’ and move there. This indicates you are backtracking. There will be only one ‘1’.
3.	Before the actual move in a ‘0’ direction, the wall the robot will travel through is changed from a 0 to a 1. Update the map.
4.	Move to the new cell and update the current heading and location.
5.	After arriving at a new cell, if the wall code behind the robot is a ‘0’, it is changed to a 1 (been there). If it is a ‘1’, it is changed to a 3 (virtual wall). Update the map.
6.	If three walls exist, then a dead end has been found, and the robot must backtrack. Turn around and go back to the previous cell.
7.	Repeat until the tennis ball is found. Normally we would now tap the ball to displace it, then enter Return mode.

Return Mode

For the PAReX maze, the search mode ends and the return mode begins when the tennis ball is found. We now look for ‘1’s, instead of ‘0’s, of which there should be only one per cell. We know we have returned home when all four walls are ‘3’.

1. All cells should only have one ‘1’. The other two walls can be either a ‘0’ or a ‘3’. Move in the direction of the ‘1’.

2. Update the current heading and location.

3. In the new cell’s map, the wall the robot just came through is marked with a code of 3. Update the map.

4. Repeat until all four walls are ‘3’s. Extra points are earned at this point if the robot indicates it knows that it has returned to the start. Update the map.

Example

In the example, the location of the robot will be indicated with: (x,y), where (x,y) is the current location. At the beginning of the search phase, this will read (0,0).

We will assume that the robot starts off in the south-west corner of an 3’x3’ maze, and is facing north. Cells are numbered from 0 to 2 for north-south, and 0 to 2 for east-west. The starting cell location is therefore (0,0). The current heading is north (N). There are walls: on the right (R), which is east (E); behind, which is south (S); and to the left (L), which is west (W), and so Map(0,0) = 0 3 3 3.

As a part of starting out, since it would have been done as the last step of the previous move, we assign a code of 3 (wall) to the location behind us. Now we can move.

Sample maze:

Walking through the maze:

Step 1

Location	(0,0) = 0 3 3 3
Mode	Search
Heading	North
Decision	Forward

The robot starts out in cell (0,0), facing north. The first motion will be forward. The south wall has been set to 3 as an initial condition.

Step 2

Location	(1,0) = 0 0 1 3
Mode	Search
Heading	North
Decision	Forward

Now in (1,0), the robot is still facing north. The north wall of (0,0) has been set to 1, and the south wall of (1,0) has been set to 1. The robot chooses to go forward.

Step 3

Location	(2,0) = 3 0 1 3
Mode	Search
Heading	North
Decision	Right

Now in cell (2,0), the north wall of (1,0) has been set to 1 and the south wall of (2,0) has been set to 1.Only one ‘0’ exists, and the robot turns right.

Step 4

Location	(2,1) = 3 3 3 1
Mode	Backtrack
Heading	West
Decision	Back

Dead end. The robot turns around and backtracks, The west wall is ‘1’, so it goes that way.

Step 5

Location	(2,0) = 3 3 1 3
Mode	Backtrack
Heading	West
Decision	Left

In (2,0), the robot has set the wall (east) it has just come through to a 3. It is still in Backtrack mode, so it follows the ‘1’ code of the south wall, and turns left.

Step 6

Location	(1,0) = 3 0 1 3
Mode	Search
Heading	South
Decision	Left

In (1,0), a code of 0 is found in the east wall, so the robot switches from backtrack to search. The north wall code of (1,0) has been set to a 3.

Step 7

Location	(1,1) = 3 0 3 1
Mode	Search
Heading	East
Decision	Forward

Searching again, the east wall of (1,0) has been set to a ‘1’, and the west wall of (1,1) has been set to a ‘1’. Continue forward.

Step 8

Location	(1,2) = 0 3 0 1
Mode	Search
Heading	East
Decision	Right

Still in search mode, the east wall of (1,1) has been set to a ‘1’, and the west wall of (1,2) has been set to a ‘1’.

Step 9

Location	(0,2) = 1 3 3 0
Mode	Search
Heading	South
Decision	Right

Still in search mode.

Step 10

Location	(0,1) = 3 1 3 3
Mode	Backtrack
Heading	West
Decision	Back

Another deadend, so backtrack.

Step 11

Location	(0,2) = 1 3 3 3
Mode	Backtrack
Heading	East
Decision	Left

Step 12

Location	(1,2) = 0 3 3 1
Mode	Search
Heading	North
Decision	Forward

Another code of ‘0’, so another branch starts here. Switch from backtrack to search mode.

Mode: Return Home

Step 13
Location	(2,2) = 3 3 1 3
Heading	North
Decision	Back
Step 14
Location	(1,0) = 0 0 1 3
Heading	South
Decision	Right
Step 15
Location	(1,0) = 0 0 1 3
Heading	West
Decision	Forward

Step 16

Location	(1,0) = 0 0 1 3
Heading	West
Decision	Right
Step 17 Completed
Location	(1,0) = 0 0 1 3
Mode	Complete
Heading	South
Decision	Stopped

Back to the starting square. Note the four '3's in the start cell, and that the other cells have a single '1'. All '1's lead back to the start.

PAReX 2004 Autonomous Event

The 2004 Event is on!!! Registration is now open for this event scheduled for Nov. 20th at the Challenger Learning Center. Here for more info,