Assignment 3: Heuristic Search |
CSE 415: Introduction to Artificial Intelligence The University of Washington, Seattle, Spring 2019 |
The reading for this assignment is
Search
in The Elements of Artificial Intelligence with Python.
|
Due Wednesday, April 24 (date corrected)
at 11:59 PM. This is an individual-work assignment and students must work independently
on the actual coding and reports.
|
Introduction
This assignment is about the A* algorithm and its use. It's partly about implementing an A* search algorithm, and then mainly about the design and testing of heuristics that can make a search more intelligent. You'll apply it to a route-finding problem and then to various instances of the Eight Puzzle. |
Working with the Starter Code
In Assignment 2 you completed coding up a file to implement the graph-search algorithm known as Uniform-Cost Search. Assuming you followed the guidelines for that assignment, you can run your UCS.py program on the French cities route-finding problem by typing the following on a command line in Darwin, Linux, Cygwin: python3 UCS.py FranceWithCostsIf you just put all the files in the same folder and use IDLE or PyCharm, that should work. If you have any trouble with this please see a TA or post in Piazza. 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. The starter code is here. |
Implementation and Testing
Do the following tasks.
|
Optional Extra Credit (up to 15 points)
This is probably a lot more work per point than in the rest of the assignment, but it's a fun exercise if you have time. (a -- 5 points) Create a formulation of the 2x2x2 Rubik cube that works with UCS.py. You can limit the operators to these six: F (front), B (back), U (upper), D (down-side), L (left), R (right). Each operator rotates the indicated face by 90 degrees clockwise. That's clockwise looking at the cube from the outside, as if that face is facing you. (b -- 5 points) Implement two heuristic evaluation functions for the 2x2x2 Rubik cube. One should be a Hamming distance similar to that used in the Eight Puzzle; given a state, it will return the number of faces that are not where they need to be in the goal. The other is one that you should design yourself. It should be more informed, but you should design it to be admissible. One way to approach this is to consider what a Manhattan-like distance would be for cubie faces in this puzzle. (c -- 5 points) Evaluating Your Custom Heuristics ... Create a report item: "Evaluating my Custom Heuristic." (a) First explain how your heuristic works, and the thinking behind it. (b) Second tell whether it actually outperforms any of the other heuristics in terms of lowering the number of expanded states while still solving the problem. (c) Finally, discuss how you believe the computational cost of computing your heuristic compares with the cost of computing the others. |
Notes about Grading
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 that gives, on the first line, your name and UWNetID. It should identify the file (name and purpose), and explain if it is a modified version of starter code in CSE 415 or is a new file you created from scratch. 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. |
Files to Turn In
Here is a list of the files to include in your Canvas turn-in. AStar.py EightPuzzleWithHamming.py EightPuzzleWithManhattan.py A3_Report.pdf optional: Rubik2Cube.py optional: Rubik2WithHeuristics.py |
Updates and Corrections
On April 21, the due date was corrected from Wed. April 25 to Wed. April 24.
Also, a couple of filenames were given incorrectly as uwnetid_AStar.py rather than
AStar.py.
On April 19 at 2:00 PM, the link to this quarter's starter code was corrected.
If necessary, additional updates and corrections will be posted here and/or mentioned in class or on
Piazza
|
Acknowledgments:
The Fifteen Puzzle image is courtesy of Wayne Schmidt (http://waynesthisandthat.com/15puzzle.htm). The Eight Puzzle image comes from https://cs.stackexchange.com/questions/16515/reachable-state-space-of-an-8-puzzle. The remaining contents of this webpage and the starter code are Copyright by S. Tanimoto and the University of Washington, 2019. |