Uninformed Search Lab

Introduction

The goal of this lab is to implement and apply uninformed search algorithms and to become more familiar with Python. This lab was originally developed as part of the AI project at Berkeley University.

Resources

Useful API documents:

• Python Sets
• import queue
• from collections import namedtuple

Files

The required files for this lab are provided in uninformedSearch.zip . The files you will need to modify are:

• eightpuzzle.py (UNFINISHED) a representation of an eight piece sliding puzzle. You can directly run this file and watch your search problem solve an instance of the puzzle.

• search.py (UNFINISHED) A set of uninformed search functions that operate on SearchProblem instances

Instructions

Download the zip file above and complete eightpuzzle.py and search.py so that all functions conform to their Python docstrings. Test your completed files by running search_test.py .

Storing States Efficiently

Graph search methods need to track visited states to avoid getting into infinite loops (and wasting computing time and space).  You must utilize a python set object to store the visited/reached states.  Hashing in Python (whether into a set or a dictionary) utilizes the __hash__ and __eq__ member functions of the object being stored. 

Task: Augment the eightpuzzle.py to provide both the __hash__ and __eq__ functions for the class EightPuzzleState.  These are required for storing objects as keys in dictionaries and sets.

Hint: To hash something, one approach could first turn the object into a String and then use the Python hash function (which knows how to change a String into a hashcode).  For the eq function, think about what makes two puzzles equal?

DFS and BFS Graph Search

Task: Augment the search.py and complete the breadthFirstSearchStats, depthFirstSearchStats, and whateverFirstSearch functions so that they comply with their docstrings.

For the frontiers, a queue.LifoQueue object can be used as a stack and the queue.Queue object can serve as a queue. It is important that both types of frontiers share the same interface so that whateverFirstSearch does not need to distingish between them (they share the same member function names for most operations). The prototyped methods of depthFirstSearch and breadthFirstSearch must simply create the frontier and call whateverFirstSearch.  They literally should be 2 lines of code each. Each method should return the tuple returned by whateverFirstSearch (see the docstring in whateverFirstSeach).

Frontier Mangement

All of your functions must add items to the frontier data structure in the order that the successors function returns the actions.

Until now (and based on what we have read), you may have thought of the frontier as just storing which state to visit next.  But the goal of these methods is to construct PATHs from the start state to the goal state.  In the assigned reading, a search tree is used to encode the path. To do this, as we remove items from the frontier, we need to know the parent state (so we know where to append this node in the tree).  It is useful to think of this as a tree, but in Python, it is common to take another approach to this problem.  Let each entry in the frontier be a tuple that consists of three items:

1. the current state
2. a list which represents the ordered actions required to move from the start state to the current state (in other words, the path from start to current)
3. the cost of the actions taken from the root to the current node.  You might think you could compute this as the length of the list - 1, however, some problems do not have uniform cost actions like the 8 piece puzzle.  Notice that the getSuccessors function returns a tuple with the new state, the action taken, and the action cost.  Your cost should be the running sum of the action costs.  

For this lab, the “object” you push on the frontier must be a namedtuple.  Tuples are similar to lists in Python except they are immutable.  Using a namedtuple is nice and enables you to refer to items by name instead of just [0], [1], etc.  We will briefly discuss in class what items to place in the tuple.  

No additional Python imports

You may not add any imports to search.py or eightpuzzle.py. If you think that you need to import a library, post a question to Piazza or email me.

Testing Your Code

If you have trouble with your submission, you may find it helpful to look at the unittests: search_test.py .

Fun Tests with Pacman

You can use your uninformed search methods to find a path to the nearest dot in Pacman.

The Pacman board will show an overlay of the states explored, and the order in which they were explored (brighter red means earlier exploration). Is the exploration order what you would have expected? Does Pacman actually go to all the explored squares on his way to the goal? Does either method find the most efficient path to the dot?

python pacman.py -l mediumMaze -p SearchAgent -a fn=dfs

python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs

Hint: If Pacman moves too slowly for you, add the option --frameTime 0 (or some other value like 0.05 works well).

Rubric

Submitting

Submit your completed version of eightpuzzle.py and search.py through Gradescope. You have an unlimited number of submissions. Note that the autograder is not verifying your hasheq and namedtuple portions of the assignment.

Acknowledgements

I would like to thank the Berkeley AI team for developing the Pacman API and the scaffolding around this assignment.