Prerequisite Knowledge
A basic understanding of how to control the Turtle's movements as well as using data structures and other fundamentals in java.
Basic knowledge of exception handling and the system stack.
Building a Grid Walker
An occupancy grid is a discrete grid that represents an environment, where each cell in the grid is either empty (free to move into), or occupied by an obstacle. If any part of an obstacle is in a grid cell, then that cell is considered to be occupied. Grids which represent real world environments are typically very fine grained in that there are lots of cells in the occupancy grid.
However, if an occupancy grid is fine grained, it will use large amounts of memory, which is a problem on the RCX since we have very limited memory. On the other hand, if it is coursely grained, some environmental features may be lost, such as narrow passageways and openings.
To equate for this, design a GridWalker which, given some coordinates, will travel to that location in the grid no matter what its current location or orientation. Once this is down, the robot will, one cell at a time, randomly around the grid for a while, and then retrace its steps back to our starting point using a stack, assuming that the grid does not contain any obstacles. To do this, for each step that it takes, it's going to have to push a step in the opposite direction onto the stack, that way, once it reaches the end, it can just pop the appropriate actions off of the stack.
Materials
Standard Turtle robot with rotation sensors.
Gridded area for testing. See printable example.
Task One
There are really three ways in which you can implement your GridWalker. One is to hardcode values into the robot which relate to timing for turns and distances, however, timing depends on battery strength, so over time, this would become inexact.
Another implementation possibility is to use one of the two LejOS navigation classes, either the TimingNavigator, or the RotationNavigator. Using the TimingNavigator will create some of the same problems that were described above, so the best solution would be to have the GridWalker class extend LejOS's RotationNavigator class (this requires 2 rotation sensors).
So now, the heart of this project is going to be the definition of the GridWalker class. It contains a constructor that specifies the grid size, the starting point of the robot, the current point of the robot, as well as some specifics about the robot (wheel diameter in centimeters, wheel base in centimeters, gear ratio). Some of this information will need to be passed to the RotationNavigator's constructor. The grid walker will also need to contain a goto method that takes as a parameter a grid location and causes the robot to move from its current grid position to that location as well as convenience methods north, east, south, and west that move the robot one cell in the respective direction.
For more information on LejOS's RotationNavigator, look at the API.
Note: |
The majority of the work for navigating the robot around the world is already done for you in the RotationNavigator class. Really, all you need in the goto method is to call the RotationNavigator's gotoPoint(float x, float y) method, which recieves in the distance in centimeters to move in each direction based upon to our current location. This conversion is based on the distance in cells from robot's current location to the goal location, and the size of each cell. You will also need to update the robot's current location once it is done moving. |
Task Two
Now that you can navigate your robot around on a gridded area, it's time to start to incorporate the stack element of this lab. You should have a good understanding of stacks from one of the previous labs. With this lab, you will need to create a stack in your driving class, and push each move onto the stack. One way to do this is equate each possible move (north, south, east, and west) with an int (say 0, 1, 2, and 3). It is easy to create a random number between 0 and 3, so once you've got your number, you can perform the necessary move and push that number onto a stack of ints. Then, after the robot has completed the necessary number of moves, it can start popping ints off the stack and perform the opposite action as when it pushed them on the stack. So if the robot moved north when the random number was 1, then it should move south when it pops a 1 off of the stack.
Note: |
Some moves may not be legal, for example, if the robot is already at the top of our grid, and the next move is to go north. Therefore, you will need some feedback from our Gridwalker as to whether or not it was able to move to the location it was told to. This feedback should determine whether or not the move is pushed onto the stack. |
Rather than using a stack of ints, try coming up with your own idea for what kinds of objects the stack holds.
Conclusion
In this lab, you learned the following:
- How to develop your own grid navigator
- How to use a stack
© 2001, 2004 by Scott Anderson, Frank Klassner, Pam Lawhead,
and Myles McNally. This work is supported by NSF grants 0088884 and 0306096. Permission
to use, copy, adapt and modify this lab for instruction purposes is granted.
These materials can be obtained from our web site www.mcs.alma.edu/LMICSE. If you have suggestions
for improvement, please contact us via the web site; we would really appreciate
it. This file was last modified on
June 30, 2005.