Files

This lab description is available as a PDF file here. The code distribution may be downloaded (in zip format) here, or by running athrun 6.01 getFiles from an Athena machine or a 6.01 lab laptop.

Goals

1) Getting started

Get this week's files by running athrun 6.01 getFiles from the command line, or by downloading the zip file from the link above.

2) Representing Mazes

We have provided text representations for four mazes in maze.py. For example, the previous maze is described by the text shown below:

Cells are represented by single characters: '.' for passable, '#' for blocked, 'S' for start, and 'G' for goal. Each of the test mazes is represented by a list of strings, where the first string represents the cells in the top row (row 0), the second string represents the cells in row 1, and so forth.

For example, the following maze

########
#S...###
##.#...#
##.##.##
#..#.###
##...#G#
##.#...#
########

['########','#S...###','##.#...#','##.##.##',
 '#..#.###','##...#G#','##.#...#','########']

• a method called __init__, which takes a single argument, which is a list of strings that describes the maze (one of the variables defined at the top of the file, or one of your own) and sets up the following instance variables:
  • height and width, which are integers that represent the number of cells in the vertical and horizontal directions, respectively; and
  • start and goal, which are tuples of the form (r,c) representing the start cell and goal cell, respectively. The variable r represents the row number (0 at top), and the variable c represents the column number (0 at left).
• a method called is_passable, which takes a tuple of the form (r,c) as input, and returns True if cell (r,c) is passable and False otherwise. Note that out of bounds cells are not passable, and that the start and goal cells should be considered passable.

Implement these features in the Maze class. You should develop your code in maze.py and debug it using idle3.

3) Search over Mazes

Next, we wish to search the maze for the shortest path from start to goal. As discussed in lecture, our search procedure will organize the search by constructing a tree to represent paths through the maze. The root node represents the beginning of all paths, at the start cell. Each node in the tree is associated with a particular cell. However, a node is not the same as a cell. As part of the tree, a node also contains all of the information necessary to determine the entire path from the starting cell to the current cell. Branching of the tree occurs at decision points, where one cell (the parent) is adjacent to two or more passable cells (children)¹. An example of one such tree is shown in the Appendix below.

We will define the search domain (which will allow our search procedure to construct this tree) by specifying a successor function, which takes as input a single state s as argument, and returns a list of states directly reachable from s². In this particular problem, our successor function must be aware of the locations of the walls of the particular maze over which we are searching, and so we will have to add one more layer of complexity.

Now add a method to the Maze class called make_successor_function. This method should take no arguments, and should return an appropriate successor function for searching in that maze.

For example, the following should print [(1,2)]:

m = Maze(small_text)
f = m.make_successor_function()
print(f((1,1)))

Enter your code for the Maze class below. Don't attempt to debug your code here; debug it using IDLE on your machine.

class Maze: pass #Your code here

4) Results

Determine the length (including the start and goal cells) of the shortest path through all of the provided mazes.

Note that some implementations might have trouble finding the shortest path in huge_maze. If your code is taking more than 5 seconds to find the path in huge_maze, you may wish to discuss with a staff member.

Enter your results below:

Length of shortest path in small_maze:

Length of shortest path in medium_maze:

Length of shortest path in large_maze:

Length of shortest path in huge_maze:

5) Appendix: small_maze.txt

¹Note that diagonals are not considered adjacent in this context. (click to return to text)

²It does not matter whether your procedure includes children that revisit parental cells: these will be filtered out by the search algorithm if they are included. (click to return to text)