Harvey Mudd College
Computer Science 154 - Robotics
Assignment BB

Motion Planning

Part 1 -- Path Following

The key to all of the motion planning strategies we explored in class was to somehow transform the known (2d) environment into a graph of 1d connections. This graph then serves as a map from which the robot can navigate.

This first part of the project will provide the robot with the ability to follow paths. A path, in this context, is simply a list of (x,y) coordinates. For example,

 (0,0),  (1000,0),  (1000,1000),  (0,1000),  (0,0)

For this part of the assignment, you need to write a function that will navigate the robot along any (predefined) path. To do this, you should

• create a data structure with which you will represent paths -- you could use the built-in STL list and pair to represent the path and the individual points, respectively. Or, you could create your own data structure to do so.
  
  
• devise some method for inputting paths to your program, e.g., you could type points at a prompt from stdin, or you could read them from a file.
  
  
• be able to draw the path on the simulator window before traversing it. To accomplish this, you will want to use the API function

         draw_line(startx, starty, finishx, finishy, draw_mode);
         

  All of these arguments are integers -- the first two constitute the starting point; the second two are the ending point; the final argument indicates how to draw the line. If draw_mode == 1 draws the line in black on top of any existing structure. draw_mode == 2 draws the line in black, but XORs it with any existing pixels in the simulated world. Larger values of draw_mode draw the line in color (it is not documented which color is which), again using the XOR drawing mode.
  
  
• write code that will guide the robot along the path you've drawn.
  
  

Include in your explanation of this part a few snapshots of your robot navigating along a path (the square, above, or one of your own choosing). Feel free to include obstacles in the world (but not in the way of the path!) Also, include a link to your code and a short explanation of the choices you made (for representating and inputting the path).

Part 2 -- Implementing a motion-planning technique

This part of the assignment will actually generate a graph of points from the robot's environment and a designated goal point. To do this, you first need to be able to get at the information stored in a map of the environment. There are files (written by Bruce Maxwell of Swarthmore College) that will read in an environment map and will create a list of Obstacles (a certain C struct) from it. These files are called nomadmap.h and nomadmap.c and are in /cs/cs154/as/BB. A test environment is available in /cs/cs154/as/BB/environment.txt. (You will need to zoom out several times to see the whole thing.)

Note: to approximate expanding all obstacles by the robot's radius, I would suggest simply adding 100 to the larger of the x- and y- coordinates of each obstacle and subtracting 100 from the smaller x- and y- coordinates of each obstacle. (The robot radius is 90, so this is a bit conservative. In addition, it approximates the robot by a square, rather than a circle.) You may assume that the obstacles will all be rectangles with sides aligned with the coordinate axes.

The bulk of this part of the project, however, is creating a graph of points from the environment map. You may choose any technique we've talked about (or a variation):

• You can use visibility graphs (medium difficulty)
• You can use Voronoi diagrams (most difficult)
• You can use an exact trapezoidal decomposition (medium)
• You can use a regular 2D grid and an approximate decomposition (medium)
• You can use an adaptively-spaced 2D grid (least difficult)

In order to represent the free space as a graph, you will need to create or use a graph data structure. One resource for a C++ graph class is the GTL available at http://www.infosun.fmi.uni-passau.de/GTL/.

Once you have the ability (1) to read in environment files and (2) to create a free-space graph of points from such files, you need to add the start and goal points to your graph. To do this, simply add (0,0) and a command-line-specified goal point to the graph. Then, add at least one edge from those points to other points in the graph, e.g., to the center of the cell that contains them. You may add more than one edge, e.g., if you are implementing a visibility graph, but you'll need at least one to be able to get the robot from start to goal.

Write-Up

In your write-up of this part of the assignment, be sure to include the following

• link(s) to your code
• a general explanation of any problems you encountered and how you dealt with them
• a picture of the graph your code created in the test world /cs/cs154/as/BB/environment.txt

Part 3 -- Graph search and execution

Once you have parts 1 and 2 complete, only the search through the graph remains. The simplest search technique is breadth-first search through the graph. Alternatively, you can use the A* algorithm (which we will talk about in class after break), you can use that to find a path from the origin to the goal.

Once you can find a path from start to finish, your code from part 1 of this project should be able to get the robot there. In your results, show at least two runs of your own and the run from (0,0) to (-2000,5125) in the environment from /cs/cs154/as/BB/environment.txt.