Error on line 5 of Python tag (line 6 of source):
    from lib601.util import Point

ModuleNotFoundError: No module named 'lib601'

Files

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 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.

Check Yourself 1:

What Python expression could you write to compute \theta_d?

Note: You may find the documentation for the util.Point class helpful.

Check Yourself 2:

Under what conditions (in terms of current_angle and \theta_d) should the robot's rotational velocity be positive (or negative)? How could you test for these conditions in Python?

The brain contains code for a function angle_difference, which computes the difference between two angles and reports it in the range -\pi to \pi. How and why might this function be useful?

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.

Check Yourself 3:

Test your driving code in bigEmptyWorld.py. When you load (or "reload") the brain, the robot's planned path will be drawn. Do not close this window, as soar will draw dots representing the robot's position over time (a "breadcrumb" trail) as the robot moves, which can be helpful for analyzing the robot's performance.

Make sure your robot goes within 0.1m of the target points and stays within 0.15m of the specified linear path segments (these regions are indicated on the window). You should also make sure that your robot reaches the goal (and you click stop) within 60 seconds, and that it stops gracefully (without raising an exception) when it reaches the last point.

Checkoff 1:
Discuss your driving implementation with a staff member.

4) Real-World Coordinates

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.

Check Yourself 4:

Make sure you understand what the __init__ method of RobotMaze is doing. If you are having trouble, ask a staff member for help.

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.

Check Yourself 5:

Recall that, like instances of the Maze class, instances of RobotMaze will have attributes start and goal, representing the discrete starting and goal locations in the maze. How can you make use of these to determine the path the robot should follow?

• 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

• 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)

Checkoff 2:
Explain the relative merits of these four different search strategies. Which one would you want to use for future work on this problem?

6) Rollin' down the highway

Check Yourself 6:

Are there problems with this path or the robot's behavior? Think about what's going wrong and how you might fix it. Ask a staff member for help if you can't clearly see how to proceed.

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.

Checkoff 3:
Demonstrate that the robot can navigate through the entire maze, from start to goal, by showing the robot's planned path and breadcrumbs to a staff member.

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