Design Lab 12: Maze Runner

The questions below are due on Thursday May 02, 2019; 09:55:00 PM.
 

Partners: You have not yet been assigned a partner for this lab.

Files

This lab description is available as a PDF file here. Code is available here, or by running athrun 6.01 getFiles.

1) Getting Started

You should do this lab with your assigned partner. The graphics in this lab have shown questionable performance on both Windows and Mac, so you should use one of our lab laptops for this lab.

Get today's files by running

$ athrun 6.01 getFiles

2) Overview

Today we are going to program the robot to navigate a maze. We have provided a template file called mazeBrain.py. Please use this file to develop your code, since it provides templates for the classes and functions that you will need. The template file will automatically load staff versions of the Maze class from Software Lab from mazeAnswers.pyc, which is included in the distribution.

If you added new attributes or methods to your Maze class implementation in software lab that you want to take advantage of later in the lab, you can set the brain up to import your code instead. Ask a staff member if you need help with that.

3) Driving

The file mazeBrain.py contains a skeleton for a brain that finds a path through a maze and then navigates along that path. The on_load function creates an instance of the RobotMaze class and determines an appropriate path. Notice that the path is stored in robot, which is an instance of a generic class that is provided for storage of global variables.

We will start by programming the robot to follow a path that is specified by a list of possibly widely-spaced points: the robot's actual path should come within 0.1m of the specified points and not deviate more than 0.15m from the line segment connecting each pair of points as it moves between them. By the end of the lab, we will be using the search functions we used in software lab to generate the paths that the robot will follow, but for now we will have the robot follow an "S"-shaped path through an empty world.

mazeBrain.py also contains code to display the robot's planned path graphically. Open the soar Simulator in the bigEmptyWorld.py world, and load the mazeBrain.py brain. You should see an empty world with an "S"-shaped curve representing the path we want the robot to follow.

Your job is to make the robot systematically work its way from one point to the next along its intended path, which is represented as a list of instances of util.Point and stored in a variable robot.path¹. Notice that the brain will need to know the robot's starting location, which is saved in robot.initial_location, to translate the robot's odometry readings (which always start at location (0,0)) into map coordinates. On each step, the robot should:

• determine which point on the path it should move toward, and then
• adjust its forward and rotational velocities to move itself closer to that point.

The robot should start by moving to the first point in the path. In general, it will take multiple steps to get to that point. After it gets close enough to that point, it should move on to the next point in the path, and finally stop when it is close enough to the last point.

The first few lines of on_step calculate current_point (in meters) and current_angle (in radians), which are the current position and angle of the robot measured in the global coordinate frame, with 0 radians to the right. Then, it calls a function drive to compute the desired forward and rotational velocities for this step. The drive function takes as input the desired path and the robot's current location and orientation. Now, we can think about how to implement drive.

Implement the drive function in mazeBrain.py. It will need to decide which point on the path the robot should be aiming at, and determine what velocities will bring it closer to that point. One strategy is to first turn to face the point (without driving forward), and then to drive toward the point.

If you need to store information so that it can be shared across multiple calls to the drive function, you can make use of Python's global keyword.

4) Real-World Coordinates

The robot navigates through a world that is described in meters. For example, the sonar sensors report distances in meters, and the forward velocity of the robot is set in meters/second. However, the mazes from earlier in the lab are described by integers that represent row and column numbers. In order to use the machinery we have built to interact with the robot, we will need to associate cells in the maze with positions in the robot's world.

For the rest of this lab, we will use tuples of integers (r, c) to represent discrete grid cells, and we will use instances of a class util.Point to represent real-world coordinates (in meters). You can find out more about util.Point from the lib601 documentation.

The relation between the discrete locations (in terms of tuples (r,c)) and util.Points (in meters) is not trivial. Remember that row numbers start at the top and grow downward, while the y direction on a map starts at the bottom and grows upward. Column numbers start at the left, as does the x direction.

In order to facilitate conversion between these two coordinate systems, it will be convenient to add some new instance variables and methods to the Maze class. Instead of modifying the Maze class, we have simply defined a new subclass of Maze called RobotMaze in the file mazeBrain.py. From here on out, you should not modify the Maze class directly. Rather, any new features for using our mazes with the robot should be implemented in the RobotMaze class.

The __init__ function of RobotMaze takes a text representation of a maze as input (as did the Maze class). It also takes four numbers that define the size of the map in meters (in the following order): x0 and y0 are the minimum values of x and y, and x1 and y1 are the maximum values of x and y. The __init__ method stores these values in instance variables x0, y0, x1, and y1.

It also defines instance variables start, goal, height, and width, as in the Maze class. Note that it does not re-implement the code that determines the appropriate values of height, width, start, and goal, but rather makes use of Maze's __init__ method to define them.

Here is an example of a world with height 4, width 4, and real-world bounds $x_0$, $y_0$, $x_1$, and $y_1$:

The RobotMaze class also provides two new methods:

• point_to_indices converts a location that is described by an instance of util.Point to a tuple (r,c) that represents the row and column (both integers) of the cell that contains the input point.

• indices_to_point takes a tuple (r,c) and returns the center of that cell (in meters) as an instance of util.Point.

5) Finding a path

Next, we will combine our search functions with your driver to make the robot navigate to the goal point in a maze.

Notice that the robot's path is computed by a function called get_path, which is defined in mazeBrain.py. The function get_path takes two inputs (the name of the world we are working in and an instance of RobotMaze representing the maze) and returns a list of util.Point instances (in meters) representing the robot's path through the physical world.

Implement the get_path function so that it uses the provided search function to find a shortest path through the maze.

To test your code:

• In soar, click "Load World" and choose dl12World.py. Note that this file is located in this week's code distribution, not with the other soar worlds.
• Comment out the line in mazeBrain.py that sets worldname = 'bigEmptyWorld' (so that worldname is 'dl12World')
• Click "Reload Brain and World." A plotting window will appear, which will show the robot's planned path through the world (made using the get_path function you modified). Do not close this window, and do not press start!

The default search strategy used by the provided search function is breadth-first with dynamic programming. In this section, we will experiment with some alternative search strategies (you should not run the robot yet; in this section, we are only interested in the path planning process). To make it clear how the searches are working in this domain, we will start by adding the ability for the search process to color in grid cells on the map when they are first expanded.

The brain has a function color_cell defined in it. It takes three arguments: an instance of RobotMaze, a discrete location in the maze, and a color. When called, it will color in the appropriate square of the maze.

Modify the successor function returned by make_successor_function so that it colors in a cell (in a color of your choosing) whenever it is expanded.

Now, experiment with four different searches:

1. Breadth-first with dynamic programming
2. Depth-first with dynamic programming
3. Breadth-first without dynamic programming
4. Depth-first without dynamic programming

The provided `search` function (from `search.py`, **which is not identical to the one in `lib601`**) takes two optional arguments, which you can use to run these experiments:

• dfs will run depth-first search if True (has value False by default)
• dp will use dynamic programming if True (has value True by default)

6) Rollin' down the highway

Now, once your code seems to be finding a good path, try to get the robot to follow it. Click "Start" and observe the robot's behavior.

Implement your solution to the problem we hope you just noticed. If you need to make changes, make those changes in RobotMaze rather than modifying the Maze class directly.

 

---

Footnotes

¹See the documentation for util.Point for information. (click to return to text)