Assignment 2: State-Space Search |
CSE 415: Introduction to Artificial Intelligence The University of Washington, Seattle, Winter 2020 |
Due Wednesday, January 22
at 23:59 PM.
|
Introduction
This assignment covers state-space search in single-agent, deterministic environments. Later we will consider multi-agent search in environments with stochastic dynamics. We start by introducing a framework for the classical theory of problem solving. Then we examine heuristic search. Note that this assignment is an "individual work" assignment, and should not be done in partnerships or groups. (When the graders find evidence of academic misconduct such as plagiarism, these cases are reported to the administration.) Along with various Python files, you'll be submitting two separate report files, one called BlindSearches.pdf and one called HeuristicSearches.pdf. |
Procedure
1. Next, download the starter code for this assignment. Un-tar it using a standard file archiving tool such as tar, WinZip, Windows Compressed Folders, etc. |
2. Examine each of the two problem formulation files provided.
One is the Missionaries and Cannibals problem. The other is the
Towers of Hanoi problem.
An additional file is provided, Farmer_Fox.py, and you will be writing one new
problem formulation in that file.
In the given formulation files, pay particular attention to how the State class is defined and how the operators are established. We will be talking about this code in class. |
3. An interactive solving client is provided. This is implemented
in the file Int_Solv_Client.py.
Optional but recommended:
Try running the client with Towers of Hanoi by using the following
command in a Linux, Darwin, or Cygwin command shell.
To do this,
issue the
command:
python3 Int_Solv_Client.py TowersOfHanoi 3If you are not comfortable working in Linux, Darwin, or Cygwin, you may wish to simply create a working folder with the Interactive Solving Client in it, and all the problem formulation files in it, and edit the importing code of the Interactive Solving Client so that it simply imports the problem formulation of your choice, and then run the program from IDLE, PyCharm, or other IDE you might be using. |
4. Create your own problem formulation for the
"Farmer, Fox, Chicken, and Grain" problem covered in class.
Then do either option 4a or 4b below to produce a session transcript
for your formulation.
Option 4a: Using the interactive solving client, demonstrate the use of your formulation to create a solving-session log. You can simply capture your screen to show the log. If you capture the screen as a text file, name the file FFCG-log.txt ,
If you capture it as an image, name the file FFCG-log.jpg, FFCG-log.png , or
FFCG-log.gif , depending on the image file format.
Option 4b: Use the starter-code program ItrDFS.py (described in item 5 below) to create output with your formulation. Capture that output and name the file as in option 4a. |
5. Starting with the starter-code file ItrDFS.py, which implements a loop-based depth-first search method ("DFS" in the following), implement BFS (Breadth-First Search) as it is specified in the lecture slides. Make sure that these implementations keep track of "predecessor" links (also known as back links), and they can report a shortest path from start to goal, for whatever problem they are applied to. (You can implement these links using a hash table, i.e., dictionary, that maps each state other than the initial state to its parent state. The initial state should be mapped to a special value such as None, or -1, which is up to you.) |
6. Compare DFS and BFS on the following problems: (i) Missionaries and Cannibals, (ii) Farmer, Fox, Chicken, and Grain, and (iii) 4-Disk Towers of Hanoi. For each combination of algorithm and problem, report the following: (a) the path found from start to goal, (b) the length of the path, (c) the number of nodes expanded (i.e., removed from OPEN and had successors generated). Create a file BlindSearches.pdf that contains a table showing these results in a clear, easy-to-read manner. Your Towers-of-Hanoi paths can be shown outside the table, since they can be relatively long. This file can be created with Microsoft Word, Google Docs, or similar tool. |
7. The starter-code file UCS.py ,
provides an implemention of the Uniform-Cost Search algorithm. This file also provides you with
an implementation of a special kind of priority queue which supports not only
the standard insert and delete_min operations, but also
a method called contains , which returns True if a given element is
in the priority queue. It also allows accessing and updating the priority value
of any element in the priority queue. See the
documentation for more information.
This priority queue is not just adequate for
implementing Uniform-Cost Search, but is particularly helpful in
implementing the A* Search algorithm.
The main difference between Breadth-First Search and Uniform-Cost Search (UCS) is that UCS works with problem formulations that have different costs associated with different moves. In terms of graph search, there are edge costs, and they are not necessarily assumed to be all equal to 1 as they essentially are in Breadth-First Search.
The starter code includes a new problem formulation for you to use with UCS; it's the
French Cities network in which the problem is to find a shortest route from the initial-state
city to the goal-state city. These are, by default, RENNES and AVIGNON. (These could easily
be changed by editing the formulation file's line defining STARTING_CITY, etc.)
This formulation is in the file For the default initial state and goal state, the results are ['Rennes', 'Nantes', 'Limoges', 'Lyon', 'Avignon']for the SOLUTION_PATH variable and
1041.0for the TOTAL_COST variable.
Page 184 in the reading shows the state space for this problem, with the distances on the graph edges. When you run the code you should get a solution path of 4 edges (5 cities) and total distance 1041: [’Rennes’, ’Nantes’, ’Limoges’, ’Lyon’, ’Avignon’]. It might be formatted differently in the printout. The map is also shown below:
Map showing French cities (which serve as the states of this problem) and distance values on roads (represented as graph edges) between them. Implement an A* search program by modifying a copy of the UCS.py file, renamed AStar.py. Develop your A* program to work with the heuristic function defined in the file FranceWithDXHeuristic.py. Your program will be operated as follows: python3 AStar.py FranceWithDXHeuristicWhen it is working, it should find the same path that UCS does, but it should have only expanded 12 states instead of 15. Here are some hints about how to modify UCS.py to implement A*. Change the names of the file and the algorithm in the code and the comments. After the code that imports the Problem, globally assign h = Problem.h, so that you can call the heuristic function easily in your algorithm. Within the search algorithm, any time UCS uses gs or new_g as a priority value, you should compute f (or call it fs or new_f, depending on the context), and use the f value as the priority. When checking the CLOSED list, don't necessarily delete the new state if the same city is already on CLOSED, but look at the priority, and if the new state has a lowever priority value, delete the state on CLOSED and put the new one on OPEN. |
8. The Eight Puzzle is a simplified version of the popular Fifteen Puzzle. A photo
of one commercial model of the Fifteen Puzzle is given below on the left,
and a picture of the Eight Puzzle is on the right. (For image credits, see
the acknowledgments at the bottom of this page.)
Try to solve some instances of the Eight Puzzle using UCS.py. There is a default instance you should try first. You can do it with the command line: python3 UCS.py EightPuzzleThere is an easy way to try more instances. Simply provide a string on the command line that represents the initial state in list form. python3 UCS.py EightPuzzle '[[3, 1, 2], [4, 5, 0], [6, 7, 8]]'Another way is to create a file that first imports EightPuzzle's definitions and then overwrites the definition of CREATE_INITIAL_STATE. This is illustrated in the file puzzle_rotate_2.py. To run UCS.py on such a puzzle, type this: python3 UCS.py puzzle_rotate_2This instance of the Eight Puzzle is named this way, because the solution requires moving all the outside pieces "around" the middle square a distance of two steps each. The lowest-cost path for this instance should have total cost 14.0, since there are seven tiles that move, and they each move twice. Note, if you prefer to do your testing by creating extra files like puzzle_rotate_2, DO NOT turn those files in with your solutions. Just report the results you get as part of your report file HeuristicSearches.pdf. Example puzzles to try: # Puzzle A. (should be very fast) python3 UCS.py EightPuzzle '[[3,0,1],[6,4,2],[7,8,5]]' # Puzzle B. (should not take long) python3 UCS.py EightPuzzle '[[3,1,2],[6,8,7],[5,4,0]]' # Puzzle C. (May take a few minutes) python3 UCS.py EightPuzzle '[[4,5,0],[1,2,8],[3,7,6]]' # Puzzle D. (May take several minutes) python3 UCS.py EightPuzzle '[[0,8,2],[1,7,4],[3,6,5]]' |
9.
Implement the following two pre-defined (i.e., fairly standard) heuristics for the Eight Puzzle.
(a) Hamming Distance (count the number of tiles out of place, but not the blank, in order to maintain
admissibility), and (b) Total of Manhattan distances for the 8 tiles.
Each of these should be in a separate file. If you look at the starter code
file FranceWithDXHeuristic.py, it shows you how your file should import the
basic problem formulation module (EightPuzzle) and then define the heuristic
function h. When you are ready to test your Hamming distance heuristic, for
example, you will type something like this to test it out.
# Test with Puzzle A: python3 AStar.py EightPuzzleWithHamming '[[3,0,1],[6,4,2],[7,8,5]]'If your A* algorithm and heuristics are working correctly, then you should see some rather noticeable improvements in the search speed and statistics. |
10.
Comparing Heuristics and Writing the Report:
Test these heuristics on the four previously given instances of the Eight Puzzle, and record
the results. Also, compare them with "no heuristic" (straight Uniform Cost Search).
You'll be turning in a report for this part of the assignment in addition to your code (see below). Create a section of your report called "Heuristics for the Eight Puzzle". Compare the performance of these heuristics on each of the example puzzles (given above). For each puzzle-heuristic pair, report (a) whether the puzzle was successfully solved, (b) length of the solution path found, in number of edges, (c) total cost of the path found, (d) number of states expanded, and (d) MAX_OPEN_LENGTH. Put this information into the table, described below.
The table should have a row for each puzzle instance and heuristic (e.g., "(Puzzle A, Hamming)",
and columns for the following:
puzzle instance permutation (e.g., [3,0,1,6,4,2,7,8,5]; this flattened list is OK here), success (yes/no), count of expanded nodes,
aborted (yes/no).
If it takes more than 5 minutes to solve a particular problem with a particular
heuristic then note that; you may abort such runs.
You are welcome to use the format for your report:
shown in the starter-code file named |
Keep in Mind
Here are some ideas to keep in mind for this assignment. The problem format we are using not only permits the "manual solving" that you do with the Interactive Solving Client. It also permits automatic solving, such as with DFS, and BFS. Thus it is important that you follow the problem structure correctly. Certain methods are required in the State class, including __init__, __eq__, __hash__, __str__, and copy. The operators must have the correct structure, as well. The nice thing about the Interactive Solving Client is that it provides a pretty good means to test whether your formulation will be OK. Even if you are familiar with Python, there may be some constructs in the formulation files that you are not familiar with. You can read up on list comprehensions (p.31 of the first reading) and lambda expressions (pp. 47-52 of that reading). We'll also cover them in class. The staff is planning to autograde parts of your code. To do this, it is likely that your files will be imported as modules by the autograder. Your search should not automatically start running when the module is imported. See the starter code UCS.py for how it uses the test "if __name__ == '__main__' " near the bottoom of the file to avoid running the search automatically if it is being imported, but still run automatically if it is the main program. You'll be fine if you simply carry over this feature from UCS.py when you create your copy of it to turn it into your implementation of A*. The autograder will be comparing the solutions and statistics found by your code with expected solutions, by calling functions in your code and examining the values of global variables in your code. These globals are generally already in place for you in the starter code UCS.py. So you should not rename variables like SOLUTION_PATH or any of the other global variables.. |
Commenting your Code
Each of your Python files should begin with a multiline string (more details are shown below.) Follow reasonable commenting practice in your code. The comments in the starter code can serve as examples of the commenting style that we consider appropriate. |
What to Turn In
Turn in eight files, but NOT zipped up, because that will interfere with the grading workflow. (As an incentive for compliance, the staff will deduct 4 points if the files are zipped.) The eight files are the following: Farmer_Fox.py FFCG-log.txt or FFCG-log.jpg or FFCG-log.png or FFCG-log.gif BFS.py BlindSearches.pdf AStar.py EightPuzzleWithHamming.py EightPuzzleWithManhattan.py HeuristicSearches.pdf |
Updates and Corrections
If needed, updates and corrections will be posted here, and/or in ED.
|