The goal of this assignment is to write a generic tree search algorithm and then provide different strategies to the algorithm to modify the type of search.
You will apply your search algorithm and strategies to a "visit all points" problem and report the results of each in terms of how many nodes were expanded and the
length (in terms of cost) of the solution found by each algorithm.
You will use the agent you created in our first assignment.
It will take in a description of the environment as its percepts.
Internally it must create a tree of the environment states and then use this tree to find a solution.
The output of your agent will be its solution, the cost of the solution, and the number of nodes expanded in order to reach that solution.
The Problem
You will be given a list of (x,y) points and your job is to figure out a route through these points such that all points are visited.
This is much more like the "eat-all-dots" goal for PacMan than the "find the least cost route", although, of course, you do want to find a more cost effective path than simply a random one.
Part 1: Design (and Code) the Input Module
You will read the input from a file. The person running the program should be able to choose which file to ru.
The format of the file is that the first number (an integer) tells you haow many points there are.
The rest of the numbers are pairs of doubles that represent a point on a cartesian plane.
You can assume that all points are completely connected - that is, you can travel from any point to any other point.
The cost to get from one point to another is its Euclidean distance (d = sqrt((x1-x2)(x1-x2) + (y1-y2)(y1-y2))).
Rather than finding a path to a single goal, the idea here is to hit all of the points (sounds like the TSP, doesn't it?).
You must decide how you will represent this as a tree, and you should be careful not to allow cycles in your tree.
A handful of input files are in GreedyPath.zip.
If you are using java, the StdDraw and DrawPath java files that are included in the zip are a way of getting graphical output of your path.
You are not required to use these, however.
Part 2: Design (and Code) the Generic Tree Search Module
The generic tree search module should follow the generic algorithm in your text and also in the slides.
This way you can simply manipulate your handling of the fringe/frontier in order to control search order (and implement a particular search strategy).
Part 3: Design (and Code) the Strategy Modules
Implement two of the search strategies we talked about. One must be uninformed, such as depth first, breadth first, etc.
The second must use a heuristic function, and can be either greedy or A*.
You will need to think about what kind of heuristic function to use.
As your search proceeds, you should keep track of how many nodes were expanded.
You also need to report the total cost of the path your algorithm chose.
Part 4: Design (and Code) the Output Module
The output should report:
0. The algorithm used.
1. The path that takes you through all the nodes.
2. The cost of that path.
3. The total number of nodes expanded while searching.
Note: If you'd like, you can write a driver program that uses both search methods in succession.
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.
As with the last programming assignment, please write up instructions on how to compile and run your program.
