LMICSE: Lego Mindstorms in Computer Science Education

Prerequisite Knowledge

A basic understanding of how to control the Turtle's movements as well as using data structures and other fundamentals in java.

Materials

Standard Turtle robot with rotation sensors.

Gridded area for testing. See printable example.

Task One

The first thing that you're going to need to do, is modify the GridWalker class so that it can store the location of the goal cell, because all of the values recorded from the wavefront propagation are based off of where the goal cell is. This should be fairly simple. All you have to do is add a method that stores the goal cell's address to some instance variable.

You also need to create some sort of structure to store the wavefront values of each cell. It is recommended that you use a 2D array of bytes to conserve memory. Once the goal cell has been initiated and you have space to store the wavefront values, you are going to need to design a breadth-first search type implementation to assign values to the remaining cells in the grid. This can be done using a queue. The best way to do this, is to implement the queue with an array of cells, so as to save memory in the robot. To populate all of the cells inside the grid, the first step is to choose a starting cell, in this case the goal cell. Next, look at the values of the cells around the current cell (left, right, above, and below). If these are legal cell locations (not outside of the dimensions of our occupancy grid), and their value is greater than the value of the current cell +1, then you should modify that value and add that cell to the queue so that you can look at the cells surrounding it.

Since you're going to be comparing the wavefront values of the cells, you're going to want to initialize them with some value. This can either be a high value or a low value, just make sure that when you compare the cell values in the wavefront propagation, that you make the proper decision based upon what the cell values are initialized at. For example, if you initialize them to some high value, then you would want to check that the adjacent cells' value is that high value (meaning that it has not been updated).

Task Two

So now you have your goal cell specified and you can build the wavefront propagation values for each cell. But what about obstacles? Obstacles are going to change your wavefront values. There are two ways that you can work around this. One is to build the obstacles first, and then build the wavefront values after you declare the goal cell. This way, you only build the wavefront values once. Or, you can declare the goal cell before building any obstacles, and then, with each new obstacle, rebuild the wavefront values. Either way works fine, but the first way may help to save space in the RCX.

To specify a cell as being an obstacle, you are going to need to make it some value that stands out from all of the rest of the wavefront values, meaning that you don't want there to be any confusion as to whether or not a cell is an obstacle. This can be done similarly to initializing the cell values, in that you can either make the value some high (say 126 if the values are stored in a 2D byte array) value or some low value (say -1). If you chose to initialize the cell values to some high value, then you should probably set the obstacle cells to some low value, and vice versa so as to prevent any confusion.

Now, assuming that your wavefront propagation values are correct, all you have left to do to move through the grid is find the next cell with the lowest value and tell your GridWalker to move to that cell.

Task Three

The algorithm for moving through the grid should be fairly simple now. It should be something along the lines of: while the current cell is not the goal cell, look at the cells surrounding the current cell and move to one with a wavefront value that is less than that of the current cell. If there is more than one cell with a wavefront value less than the current cell, then these cells should have the same value, in which case it does not really matter which one the robot moves to because it will still take the same number of steps to get to the goal cell. If the there is more than one cell with a wavefront value less than the current cell, and the values of these cells are different, then there is something wrong with the code which assigns the wavefront values.

Additional Problem

Create a method which checks to see if the robot is stuck (in a cell for which there is no path to the goal cell). If the robot finds that it is stuck, it spins in a circle and then quits the program.

Conclusion

In this lab, you learned the following:

• The idea of wavefront propagation and some of its uses
• Expanded our knowledge on occupancy grids