Project 11 Solution

Objective




This assignment explores the connection between problem formulation and search strategies. You will need to implement and compare several search strategies on a few different puzzles and problems we’ve talked about in class.




Program Specification




Your program should be named “puzzlesolver.py” and it should take ​two mandatory input arguments plus one optional one​. The first argument is a configuration file for the puzzle your program has to solve (see the next section for more information). The second argument is a keyword that specifies which search algorithm to use to solve the puzzle: ​bfs​, ​dfs​, ​iddfs, unicost, greedy, astar, ​and ​idastar ​(​with the exception of the ​dfs​-based ones: ​dfs​, ​iddfs,​and idastar​, assume “graph-search”​). The optional third argument allows the user to specify different heuristic functions for ​greedy​, ​astar​, and ​idastar​search.




Your program should solve the input puzzle using the specified search algorithm and strategy.




Upon completion, it should output the following information:




the solution path (or “No solution” if nothing was found): print one state per line.



Time​: expressed in terms of the total number of nodes created.
Space​: expressed as the ​maximum​number of nodes kept in memory ​(approximately,, the biggest size that the ​frontier​list grew to) as well as the maximum number of states stored on the ​explored​list (if used). Please report these as two separate numbers​.



Puzzle Types




An important element of this assignment is to separate the puzzle specific parts from the generic search algorithm part. Make sure that your implementation of the search does not hard code in any puzzle specific details. For this assignment, your program will be working with three puzzles: the water jugs problem, the path planning problem, and one more to be revealed a week later. If you’ve kept the problem/search abstraction clean, when you get the new puzzle problem, you ought to be able to just code up the functions relevant to setting up that puzzle as a state space search (e.g., get-successor-states, and goal-test, etc.)






The Water Jugs Problem




We’ve previously talked about this problem in Lecture 2:




“You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring markers on it. There is a tap that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into the 4-gallon jug?”. (cf. ​Rich & Knight, 1991​)




In general, we could have more than two jugs of some other pre-specified volumes (For example, see ​this Wikipedia entry​for a version with 3 jugs). We will use the configuration file to specify the particular instance of the puzzle. It has the following format:

Line 1 is a keyword (​jugs​) that tells you this is the water jug problem




Line 2 is a tuple specifying the capacities of the jugs; e.g., (3, 4)




Line 3 is the initial state; e.g., (0, 0)




Line 4 is the goal state; e.g., (0, 2)




You may assume that we ​will not​stress test with bad inputs like negative capacities or impossible states, and we’ll keep to just two or three jugs.




The Path-Planning Problem




For this problem, we will read in a graph representation of a roadmap, where cities are nodes and roads between them are undirected edges with costs. We want to find a path from the starting city to the destination city with the lowest cost. Here is the format of the input configuration file:




Line 1 is a keyword (​cities​) that tells you that this is the path-planning problem. Line 2 is a list of the names and locations of the cities; e.g., [(“Arlington”,1,1),(”Berkshire”,2,3),(”Chelmsford”,1, 5)]




Line 3 is the name of the starting city




Line 4 is the name of the destination city




Each of the following lines specifies a connection between two cities and the cost of taking that route; e.g.,: (“Arlington”, “Chelmsford”, 4) specifies that it costs 4 units to go from Arlington to Chelmsford or vice versa (after one action).




You may assume that we ​will not​stress test with bad inputs like roads with negative or zero cost. We may try a large graph with this problem, however.




Timeline




Begin by implementing the uninformed search strategies (​bfs​, ​dfs​, ​iddfs, ​and ​unicost) for the two specified puzzle problems.



Next, implement the informed search algorithms (​greedy, astar, ​and ​idastar​) for the two specified puzzles. What would be a reasonable heuristic for each problem?



Remote commit what you’ve got by 9/18 (Tuesday) night. At this point, you should have completed the uninformed search strategies and gotten started on the informed strategies. You may still modify any part of the code you want during the second week;
we will not grade this first-week version for correctness, but we will check to see your early implementation decisions.



I will specify the 3rd puzzle on 9/20 (Wednesday). You will then have a week to complete the assignment and do a final commit by 11:59pm 9/26 (Wednesday).



What to commit




A transcript of running your program on the sample input file (on Linux or Mac Terminal or Cygwin on Windows, use the command “script” which will save your session into a text file. For DOS Prompt, you may have to find some workarounds (See: ​[1]​, ​[2]​)).
Your Python source code.



A README file that addresses the following:



the version of Python you used



List any additional resources, references, or web pages you've consulted.



List any person with whom you've discussed the assignment and describe the nature of your discussions.



Describe any component that is not working in your program



Grading Guideline



Assignments are graded qualitatively on a non-linear five point scale. Below is a rough guideline:




5 (100%): The program works as expected; has a clear README for the grader; includes a transcript; complete report with insightful observations.



4 (93%): The program works as expected, but possibly with some minor flaws; has a clear enough README for the grader; includes a transcript; complete report.



3 (80%): The program works for for at least two puzzle types, and there is a clear abstraction between the search and puzzle parts; OR, the program works for at least five search strategies for all three puzzle types; has a clear enough README for the grader; includes a transcript; cursory report.



2 (60%): The program works for at least four search strategies for at least two puzzle types; has a clear enough README for the grader; includes a transcript; cursory report. OR: has a better program but the report is missing.



1 (40%): The program has major problems, but a serious attempt has been made on the assignment; has a clear enough README for the grader.