CSSE413 Artificial Intelligence
Fall 2004-2005
Programming Homework 3 -- Search
(Please put in your turnin folder, labeled as HW3)
Due Mon night, Sep 20th
(10% Bonus for
making it by the original deadline!)
The goal of this lab assignment is for you to gain expertise in using multiple search tools in more than one domain.
You will have two development environments to choose from, you can pick which one is right -- for you -- for this task.�� Namely, you can use either Scheme or Java.� So long as Clint and I can read your source code and test your programs in either Petit Scheme or JCreator, respectively.
You may want to spend a little time designing how you want your solution to be put together. Since it is to use more than one search method on more than one domain, some forethought on that will help in the long run.
As discussed in class, you want to decide what a �node� will look like, in general, and a �state� of each kind of problem at that node, and how you might need to remember �paths� so you can report what a �solution� looks like after a successful search.� And how to parse the list of �open nodes� with one or another search method.
Additionally, consider how you want the problems to be described, as input to your programs, to minimize the effort for that. Like we showed in class for Blocks World.�� Or, alternatively, include some way of generating randomized problems of some suitable variety for your program. Your instructor will be open to alternative ideas on these, so long as it�s feasible for him to test your program!
1. Pick three different search methods from Ch. 3 and 4 (total). At least 1 must be �intelligent� � from Ch. 4. Unless you want to be especially challenged, it is suggested that you pick 3 fairly simple methods. Say, breadth first search or depth first search from Ch. 3, and A* or hill-climbing from Ch. 4. More adventuresome solutions will be rewarded, but only if it looks like you had some success with them!
2. The two domains are as follows:
a. Simplified Blocks World.� This one you know about from class.� See your notes from Thurs & Fri, Sep 9 & 10.
b. Either the Traveling Salesperson Problem (TSP) or some other domain you get my permission to do instead.� We�ll talk about the TSP in class, and it is described in your book on p. 68, and you can either invent your own heuristic for testing, or else look up how to use the MST (Minimum Spanning Tree). See, for example, the explanation of this at http://www.ics.uci.edu/~eppstein/161/960206.html �.� A few more notes on the TSP are at the bottom of this assignment.
Note: It would be useful to take a crack at this early � If it turns out to be too much, I�ll revise the assignment downward, as noted at top. However, this is about the right size for you to end-up feeling like you really designed software with some general search capability.
Further comments on
the TSP:
Feel free to define any kind of TSP spaces you want for this, such as, say, 5 cities, A, B, C, D, E, with
A to B = 50 miles
A to C = 70
A to D = 80
A to E = 100
B to C = 50
B to D = 40
B to E = 30
C to D = 10
D to E = 20
These don't have to be realistic things you can plot on a 2-D graph.� After all, there could be winding roads between some of the cities!
Beyond this, I'm hoping you'll represent the data in some obvious way so that I can enter a different problem (which also will work!).� Or, better yet, if your problems are in a separate, editable, clearly identified data file (like a text file), I can just go in and modify your data in some obvious way to run other tests.
And if you know any limits, like "Don't try more than 10 cities or it blows up on my PC," let me know.