# Spring2007RobotLabAssignment3

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

=== Assignment 3: Path Planning

#### Description of Assignment

Your program should take in a text file called path_input.txt which will look like:

9 8 S,0,0,0,0,0,0,0,0 0,0,0,0,0,1,1,0,0 0,0,0,0,0,1,1,0,0 0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0 1,0,0,0,0,0,0,0,0 1,0,0,0,0,0,0,0,0 1,0,0,0,0,0,0,0,E

The first line tells how many rows (9), the second line tells how many columns (8) the map has. The starting point for the path will have an S, and the ending point will have an E. All obstacles will have a 1, and open cells will have a 0.

We will assume that your robot can move one square at a time in any direction (up, down, left, right, all four diagonals), as long as it does not go off the map or into an occupied cell. We also assume that your robot takes up 1 cell. To provide your robot with a buffer so that it does not run into an obstacle or a wall given the error in its path, you will add extra occupied cells to the map. You should first increase the size of all obstacles by the size of your robot in all directions by adding a 1 in all directions around all obstacles.

You will not turn this step in, but here is a representation so that you can see what the input map would look like after expanding the obstacles:

9 8 S,0,0,0,1,1,1,1,0 0,0,0,0,1,1,1,1,0 0,0,0,0,1,1,1,1,0 0,0,0,0,1,1,1,1,0 1,1,0,0,0,0,0,0,0 1,1,0,0,0,0,0,0,0 1,1,0,0,0,0,0,0,0 1,1,0,0,0,0,0,0,E

Next you will expand all walls by adding a 1 above the lower wall, to the right of the left wall, below the upper wall, and to the left of the right wall, do this for all cells that are not currently occupied and are not the start and end positions (i.e. for any cell that has a 0).

You will not turn this step in, but here is a representation so that you can see what the input map would look like after expanding the walls:

9 8 S,1,1,1,1,1,1,1,1 1,0,0,0,1,1,1,1,1 1,0,0,0,1,1,1,1,1 1,0,0,0,1,1,1,1,1 1,1,0,0,0,0,0,0,1 1,1,0,0,0,0,0,0,1 1,1,0,0,0,0,0,0,1 1,1,1,1,1,1,1,1,E

Now we perform the Wavefront algorithm. This is a breadth first search that starts at the end position, and expands out from there, noting how far every other cell is from the end position. You should replace the E (end position) with a 2, then until your algorithm encounters the S (but will not replace the S), you will expand out in a wave from the end position, setting all adjacent cells to 3, then the adjacent cells of the 3's to 4, etc.

You will turn this step in, so your program should output a file named wavefront_path_map.txt that looks like the following:

9 8 S,1,1,1,1,1,1,1,1 1,9,9,9,1,1,1,1,1 1,9,8,8,1,1,1,1,1 1,9,8,7,1,1,1,1,1 1,1,8,7,6,5,5,5,1 1,1,8,7,6,5,4,4,1 1,1,8,7,6,5,4,3,1 1,1,1,1,1,1,1,1,2

Finally you will calculate the path from the S to the 2, and this path should be of minimal distance. Note that this minimal distance path may not be unique. Your path will replace the S with an A, then increment through alphabet (B..Z, then AA, AB, AC..AZ if needed) with one letter per cell to indicate your path.

You will turn this step in, so your program should output a file named wavefront_path_plan.txt that looks like the following:

9 8 A,1,1,1,1,1,1,1,1 1,B,9,9,1,1,1,1,1 1,9,C,8,1,1,1,1,1 1,9,8,D,1,1,1,1,1 1,1,8,7,E,F,5,5,1 1,1,8,7,6,5,G,4,1 1,1,8,7,6,5,4,H,1 1,1,1,1,1,1,1,1,I

Note that there is an alternative path with F the cell below the displayed F, and then another choice for G, as all of these paths will have the same length.

#### Deliverables

You will be given the path_input.txt file, either on your own laptop, or on a departmental machine, and your code should execute on that input file, producing the two output files.

You should turn in: