Lab 0: Maze Search

Lab 0: Maze Search
Due January 25th by midnight

 □ ■ ■ ■ □ □ □        □ ■ ■ ■ ▿ ◃ ◃       * ■ ■ ■ □ □ □
 □ □ □ ■ □ ■ □        ▵ ◃ ◃ ■ ▿ ■ ▵       * * * ■ □ ■ □
 ■ ■ □ ■ □ ■ □        ■ ■ ▵ ■ ▿ ■ ▵       ■ ■ * ■ □ ■ □
 □ □ □ □ □ ■ □        ▹ ▹ ▵ ◃ ◃ ■ ▵       * * * □ □ ■ □
 □ ■ ■ ■ ■ ■ □        ▵ ■ ■ ■ ■ ■ ▵       * ■ ■ ■ ■ ■ □
 □ ■ □ □ □ ■ □        ▵ ■ ▿ ◃ ◃ ■ ▵       * ■ * * * ■ □
 □ □ □ ■ □ □ □        ▵ ◃ ◃ ■ ▵ ◃ ◃       * * * ■ * * *

Starting point code

Unlike subsequent labs in the class, you must complete this lab individually. The following steps will to set up your directory for this lab.

First you need to run setup63 to create a git repository for the lab:
```
setup63-Lisa labs/00
```

Next, copy over the starting point code:

cd ~/cs63/labs/00
cp -r /home/meeden/public/cs63/labs/00/* .

Finally, add all of the files to your git repo, commit, and push:
```
git add *.py mazes/*.txt
git commit -m "lab0 start"
git push
```

You are now ready to start the project. Two of the files you copied are executable: Queues.py and MazeSearch.py. You can run them as you would have in CS21, for example:

python Queues.py

Alternatively, because the first line of these files tells bash where to find your python executable, you can simply run them with the path to the file, for example:

./Queues.py

However, these are the files you will be modifying, and they will just print error messages if you run them right away.

Introduction

The objectives of this lab are to:

(re)acquaint you with Python
(re)acquaint you with uninformed search
help you start thinking about search as an AI problem

For this lab you will implement three variants of a queue data structure:

FIFO: first-in-first-out (a classic queue)
LIFO: last-in-first-out (also known as a stack)
Random: elements are removed in random order

You will test these queues and then use them to implement three methods of uninformed search through an ASCII grid maze:

Breadth-first search
Depth-first search
Random order search

Queues

Your first task is to implement three versions of a queue. The file Queues.py defines a base class _Queue, and three subclasses: FIFO_Queue, LIFO_Queue, and Random_Queue. Each type of queue needs three methods implemented:

__init__() creates an empty queue
add() puts an item into the queue
get() removes an item from the queue and returns it

Some of these functions will be the same for all three types of queues and should therefore be implemented in the parent class. Others will differ across queue types and should be implemented by the child classes. The three types of queue differ in which item is returned by get():

FIFO_Queue.get() returns the oldest item in the queue
LIFO_Queue.get() returns newest item in the queue
Random_Queue.get() returns an item chosen uniformly at random

For functions that you implement in _Queue, you should remove the overriding definition in the child classes. For functions implemented in the child classes, change the parent-class error message to be more informative.

Testing

If you run the program Queues.py from the command line, the test_queues() function gets called. You should use this function for incremental testing while you implement your queue classes. By the time you have finished implementing all three classes, you should have tests to ensure that all three queues correctly support all six required functions (__init__, add, get, __len__, __repr__, and __contains__). You should also have tests that add and remove enough items to demonstrate that the the queues give proper ordering. Finally, as you work on MazeSearch.py consider what corner cases could come up and whether they need to be handled. Examples of corner cases could include empty queues and duplicate items.

When you submit Queues.py, your test_queues() function should print out explanations of each test so that a user could run the program, know what it is testing, and be convinced that it works correctly.

Maze Search

Input

A Python class representing a grid maze has been provided for you in the file MazeClass.py. Take a look at this class but do not modify it. One thing to note is the use of a set instead of a list to represent the walls. Sets are like dictionaries, but without values (only keys); they use a hash table to give O(1) lookup. See section 5.7 of the Python library docs for more information about sets.

You have been provided several .txt files containing example mazes. The maze at the top of this page is in 7x7_two_paths.txt. Before you can solve a maze, you need to read in the maze file, which means implementing the read_input() function. This function should check for valid command line input in sys.argv and print an error message if the input is invalid. Valid input is a path to a maze file and a search mode: BFS, DFS, or RND, for example:

./MazeSearch.py mazes/5x5_possible.txt BFS

Given valid input, you should parse the maze file and initialize a Maze object. A maze file has the following format:

one line with a single integer giving the number of rows in the maze
one line with a single integer giving the number of columns in the maze
some number of lines with pairs of integers specifying the (row, col) locations of walls in the maze

The __init__() function for the Maze class expects a number of rows, a number of columns, and a list of (row, col) pairs where walls are located. For the maze file 5x5_possible.txt, this would be:

rows = 5
cols = 5
walls = [(1,0),(1,1),(1,2),(1,3),(3,1),(3,2),(3,3),(3,4)]

read_input() should return the initialized Maze object as well as the mode string specifying the type of search. You can test your read_input() function by calling the display() method on the Maze object you return.

Searching

The SearchAgent class implements a search through a Maze object and stores the results of that search. The search starts from the Maze object's start state and seeks the goal state. The start is always the top-left cell of the grid and the goal is the bottom-right cell, but both can be accessed as named fields of the Maze object. The class's search() method should implement the following general algorithm:

add start to frontier
add start to parents
while frontier not empty
    get state from frontier
    if state is a wall
        add state to  walls 
    else
        add state to free
        if state is goal return
        for each neighbor of state
            if neighbor not in parents
               set neighbor's parent to state
               add neighbor to frontier
    end if
end while

If the while loop terminates because the goal was found, then the maze is solved; if the loop terminates because of an empty frontier, the maze is impossible. The search() function has no return value because all relevant information is stored in the SearchAgent class. For example, whether the maze can be solved is checkable by whether the goal is in parents. If the maze is solvable, a solution can be found by tracing parents backwards from the goal. You will implement this in the path_to() function.

Our search algorithm uses four data structures:

walls needs to support adding elements and containment testing with in
free needs to support adding elements and containment testing with in
parents needs to map states to parents by indexing with []
frontier should be one of your queue classes, depending on mode

You should decide what data structure to use for each of these and set them up in the __init__() function for the SearchAgent class.

Path Finding

Once search() has been called, the parents field of the SearchAgent can be used to construct a path from the start to any state reached by the search. If a state is in free, we can retreive its parent, and its parent's parent and so on back to the start state. The path_to() function should implement this, returning a list of states in order along the path (including start and end states). If the state is known to be a wall or was not reached, an empty list should be returned.

Testing

The folder mazes/ which you copied along with the starting point code contains several examples on which you can test your MazeSearch.py program. Try out all three types of search on these mazes. Then think about what other functionality needs testing and create your own mazes to exercise it. The following links have some sample output, but you should run a lot more tests than these:

Submitting your code

Before submitting, ensure that you have added your name to the top-level comments. To submit your code, you need to use git to add, commit, and push the files you modified. Only Queues.py and MazeSearch.py will be graded; other files added to your repository will be ignored.

cd ~/cs63/labs/00
git add Queues.py MazeSearch.py
git commit
git push

Lab 0: Maze SearchDue January 25th by midnight

Starting point code

Introduction

Queues

Testing

Maze Search

Input

Searching

Path Finding

Testing

Submitting your code

Lab 0: Maze Search
Due January 25th by midnight