CSSE413 Artificial Intelligence
Fall 2005-2006
Programming Homework 3 -- Search
(Please put in your turnin folder, labeled as HW3)
Due as described on the assignment webpage
Sliding credit scale for
turning in this assignment:
(as discussed in class Thurs, 9-22-05)
|
Turned in by: |
Counts as: |
|
Friday, Sep 23, 11:59 PM |
110% of �actual grade� |
|
Monday, Sep 26, 11:59 PM |
100% |
|
Friday, Sep 30, 11:59 PM |
80% |
|
Monday, Oct 3, 11:59 PM |
50% -- �Last chance� |
New Info -- Thurs, 9-15-05
FYI -- There are solutions to last year's HW 3 shown here (Java) and here (Scheme). Last year, the problem was longer -- not only requiring two different domains, but also asking for 3 different searches! Both of these examples show an A* search, however, and both also show the standard TSP as an example (versus the version of the TSP outlined below for this year).
The other domain they used was one called "blocks world," where a mechanical arm has to restack blocks into a different goal state. Obviously, don't use that as your second domain to which you apply your own search.
Use these similar programs as you like to get ideas, but please make your own solution look different, in your own style and including your own ideas.
Intro Discussion
The goal of this lab assignment is for you to gain expertise in using intelligent search 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 Scott and I can read your source code and test your programs in either Petit Scheme or JCreator, respectively.� For comments on Java alternatives, see the footnote.[1]
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 domain, some forethought on that will help in the long run.
You�ll 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 this particular search method.
Additionally, consider how you want the problems to be described, as input to your programs, to minimize the effort for that. 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!
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 or extend the deadline. However, this is about the right size for you to end-up feeling like you really designed software with some general search capability.
Detailed description
1. Pick an intelligent search method from Ch 4, whatever one you find most interesting.
1a.� If you want to �warm up� with an unintelligent search from Ch 3, that�s fine.� If it really runs, you can include that in what you turn in for some small amount of extra credit.
2. The two domains
are as follows:
a. Modified TSP.� The TSP you
know about from class and it is described in your book on p. 68.� 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
.� (This of course is for the standard TSP.) A few more notes on the
TSP are at the bottom of this assignment.
The modifications are as
follows:� You may visit a city more than
once!� And Not all the cities have to be
connected. Could be there�s no direct road between here and
b. Some other domain you would like to search. �Use your imagination.� The only requirement is that it not look like anything else � not like the TSP, not like anything standard in the literature nor like anything out on the internet.� Something you make up on your own, like I altered the TSP, above.� For full credit, the domain should look about as challenging as the TSP, a domain which is NP-hard, say.
3. In both domains, your goal is to do an optimal search (or close to optimal).� It should end up looking like it finds intelligent solutions to these problems.
Further comments on the Modified 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 mountains and winding roads between some of the cities! Note also, not all the cities have to be connected.
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.
[1] For example, if you are using a Java tool other than JCreator, such as Eclipse, give me the source code, and also wrap the java code into a jar file which will run by clicking on it from Windows.� In this case, you�d also need to have your test problems given as some kind of data you read from a file or enter through the keyboard, since recompiling may not be an option.