The goal of this assignment is to use the search algorithms provided in the AIMA code base to solve a real world problem.
I have a homework assignment. Really.
And I want you to help me with my homework.
As part of a Forest Management class I took this summer, I need to go out to "randomly" predetermined plot points on my property and assess their condition.
This includes which plants and trees are present, how healthy they are, what is the true slope, soil depth, and any other interesting things I might step in.
Based on a process we went through in the forestry class, the points to assess were determined and placed on maps.
These maps have been translated into units of steps. (Really. One step = right leg forward, then left leg forward. I take 23 normal steps in 100 feet.)
Two map environments are provided, following the AIMA code base template for maps (with a few adjustments just to initialize everything.)
These are WiseRiver.java and TollMountain.java. The maps (not very clear, but still, maps) are in Maps.
This assignment is more like PacMan search than like finding the shortest route. I need to visit every point on the map, much like PacMan eating all the dots.
All of the points are fully connected. That is, you could travel between any two points, if you were a masochist.
I want you to find me a reasonably short / cost reduced path from a given start position until all the points have been visited.
Note that this is really a continuous environment. It has been discretized by the plot points, and this makes it almost do-able.
You might also notice that this is very much like the traveling salesperson problem, with the exception that there is no restriction on how many times I can retrace my steps if it makes it less costly.
That is, I can visit any point more than once, and the measure is cost, not strictly distance.
Part 1: Design a Cost Function
In the map environments I left the cost as simply straight line distance.
The cost should really combine the factors of slope and whether I consider a point a barrier or not.
On the Wise River terrain, there are two barrier points.
One is in the creek area. I really don't want to slog back and forth over the creek.
The second is in a swampy area where moosies hang out. Like the creek, I don't want to slog about in a swamp too much, nor do I wish to anger any moosies.
On the Toll Mountain terrain, there are no barriers! Yay! But it still has slope.
So how do you combine these things into a cost measure?
Think about if you were making the trek.
How much would you prefer not to go up and down a 40% slope? Is a 20% slope much better?
Mathematically, you can use these things along with distance to come up with a measure you feel comfortable with.
(You might even test it a couple of times to see if it gives results you are happy with.)
I know. You're saying "results I'm happy with? I just want a good grade".
But really, isn't that what a utility function is all about? And everyone has a different utility function for different things.
When you write your utility function, in the two map environment files, simply write a comment that describes why you did what you did.
Remember, a utility function is not the same as a heuristic function.
It determines the cost of the path, not the estimated cost to the goal.
You are welcome to use straight line distance as the utility function.
Part 2: Use the AIMA Code Base to Search for a Route
This part is harder.
Using parts of the AIMA code base, construct an agent that plans a (reasonable) route through the two maps.
Keep track of how many nodes were expanded during the search, the path which provides a solution, and the cost of that path.
I would strongly advise that you not use an uninformed search for this.
For the Wise River map, since it is fully connected, you would have to explore up to 21! nodes.
According to my calculator, that's 51,090,942,171,709,440,000 nodes.
I don't even know how to pronounce that number.
You can look at the AIMA code base for guidance on how to approach this.
Just like your last assignment, you will be required to dig through code and see how it is used, and then use it to create your own search agent and solution.
If your are using Eclipse, it can help you track down where a particular class or method is defined.
Not quite as good as having an API, but not so bad as a manual search.
(Note to self. Maybe next year's search assignment will be to search code bases for a particular definition. Hmmm...)
Submission.
Submit your search program, with all files required to make it run, via Moodle.
Please submit source files, not executables.
I want to look at the source and compile and run it myself.
Be sure each submitted source file has the required header with your name, and a description of the class/program.
If you are using java, I won't need the files from the code base.
If you are not using java, I will need whatever code files your code uses, plus instructions on how to compile and run.
