Informed Search Lab

Introduction

In this lab, you will write uniform cost search (UCS) and A* search methods in Python.
You will construct heuristics for A* specifcally for the eightpiece puzzle problem (the two that were discussed in lecture). This lab introduces priority queue objects in Python.

NOTE Technically UCS is an uninformed search method since it does not use knowledge about the goal location, but it is part of this lab so that we can compare how it performs against A*.

Resources

Useful API documents:

• queue.PriorityQueue

Files

Copy your Lab 1 files over to a new directory for this lab. You will need your search methods and the modified eightpuzzle.py file with the hash functions added for this lab.

• eightpuzzle.py (UNFINISHED) a representation of an eight piece sliding puzzle. You will add the two heuristic functions discussed in lecture.

• search.py (UNFINISHED) A set of search functions that operate on SearchProblem instances. You will complete the UCS method by adapting whateverFirstSearch to work with this.

• plot_search_performance.py (UNFINISHED) Python code to plot the results of your searchs on the 6 benchmark puzzles

• informed_search_test.py A unittest file to test your code.

Instructions

1. Copy the entire set of files from Lab 1

2. Complete the aStarSearchStats method within search.py so that it conforms to its Python docstring. NOTE: Completing the aStarSearchStats method enables uniformCostSearchStats to use the call it and utilize the nullHeuristic function.

It is required that UCS be unchanged and that it just calls aStarSearchStats. You could change whateverFirstSearch to handle all 4 searches (although this is not a requirement). HINT: It is a good idea to use a namedtuple that stores f(x), g(x), and h(x) separately.

1. Complete the tilesEightPuzzleHeuristic and manhattenEightPuzzleHeuristic methods inside of eightpuzzle.py. These methods compute heuristics for the eight piece puzzle. The requirements of each method are detailed in their Python docstrings. When called directly, the eightpuzzle.py module will generate a random eight piece puzzle and use your code to solve it. As coded, it calls BFS, but you can change it to call UCS or A* so that you can test your code.

2. Showcase the performance (expanded state count) between the different searches by creating a plot in python. This single plot needs to show the 6 puzzles on the X axis (the ones built by and used by informed_search_test.py), the Y axis for each of these 6 points is the number of expand operations performed. You need to plot a line for each search: UCS, A* w/tiles, A* w/manhatten). An example of creating a plot with two lines is provided in the plot_search_performance.py .

Priority Queues in Python and Frontier Management

A* and UCS both required a priority queue. The priorityQueue object accepts a tuple (with any number of elements) and uses all the element in the tuple for creating the “key” that it will use for extracting the minimum value. For example, if all the first elements were distinct values, it would never need to access the other elements (which it would only use to break a tie). You might try storing a tuple with (f(x), node). However, since it is likely that more than 1 node in the priority queue will have the same f(x) value, which would require the priority queue to compare the second element in the tupe to break the tie, which is a node object. Since node is a namedtuple, it does not have a comparison method and thus, Python throws an error.

While several solutions exist for this situation, including adding comparative methods and or wrapping the item in a class as suggested in the PriorityQueue documentation. Here is a solution that works well in practice in Python. Given two elements on the priority queue with the same f(x), the A* algorithm does not care which one is extracted. Therefore, just store an extra element within the tuple stored on the priority queue, where the first element is f(x), the second element is some counter value (unique by construction), and then any remaining elements. Since each counter value is unique, it breaks all ties when the f(x) values are the same, and the elements that follow are never evaluated for key order.

In your A* method, you can create a counter at the beginning of your function (count is imported from itertools):

from itertools import count

unique = count()

An example of adding a new item to the priority queue is:

pq.put((f(x), next(unique), node))

where node is a namedtupled that should contains 4 items:

1. the state
2. a list of actions to get from the start state to this state
3. the cost so far so get to this state (g(x))
4. the heuristical cost to get from this state to the goal (h(x))

While having items 3 and 4 (g(x) and h(x)) is redundant (since f(x) is already the first element), it greatly helps with debugging your code and is highly recommended.

Working with the EightPuzzle for heuristic computation

It may be helpful to have the puzzle in a 1d type structure (instead of the 2d array). You can use the following call to “flatten” the data into a 1d structure:

from itertools import chain
list(chain.from_iterable(state.cells))

Shorter Paths

Is it possible that a state/node appears in the priority queue more than once with A* search? If so, how do you handle this? Think about this question and the reached data structure used with graph search. The good news is that you can deal with this, but can you explain how your code will deal with this situation?

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 that are provided in the informed_search_test.py file.

Fun Tests with Pacman

You can use your informed search methods to find paths with different agents and cost functions 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 bigMaze -z .5 --frameTime 0.04 -p SearchAgent -a fn=ucs

python pacman.py -l bigMaze -z .5 --frameTime 0.04 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic

Notice that the two paths have the same cost (they are both optimal). However the UCS should have expanded more nodes than A* (showing that it took UCS more computations to find an optimal path).

Rubric

Submitting

Submit your completed version of search.py, eightpuzzle.py and a PDF containing your plots named searchPlots.pdf through Gradescope. You have an unlimited number of submissions. Note that the autograder is not verifying your plots and namedtuple portions of the assignment (these will be manually evaluated).