CSE630 Homework 2: Informed and Uninformed Search

DUE DATE: October 16 at 04:00 a.m.
1 point late penalty for each minute late

Part 1: Problems

(10 points) Explain whether a bidirectional search could be employed to solve the following problems:
1. Checkers
2. The Kevin Bacon game: link any movie star to Kevin Bacon. To play this game, go to the Oracle of Bacon at UVA.
(10 points) Suppose you were given two URLs and you had to write a program to find a sequence of links to get from one to the other, if such a path exists. Remember that links are one-directional operators. A) What kind of search would you implement for this problem? B) What is the successor function? C) Can you think of a heuristic to use to order the successor state expansion?
(15 points) Describe the state variables, operators, and goal test for the Towers of Hanoi problem with 3 spindles. Make sure to state the goal test in terms of the state variables you defined. For a problem instance with 3 blocks, all of which are starting on spindle 1, and with spindle 2 and 3 empty, draw the state space graph for the states reachable in 3 moves from the starting state. For guidance, look at the vacuum cleaner state space graph in Figure 3.3. If you're doing this problem in a text editor, you can describe the state with a little box diagram as long as you provide a key, for example:
------------- | L | M | S | ------------- Means that the left-hand spindle has the large block, the middle spindle has the medium block, and the right-hand spindle has the small block. One possible successor for that state is:
------------- | S | | | | L | M | | -------------
(10 points) Consider the following graph. The shaded nodes have already been visited and expanded.
1. Draw the search tree that corresponds to this graph, where the search has started from "A", has just expanded "R", and can visit a node in the graph more than once.
2. Indicate the fringe of the search tree.
3. In a depth first search, what node would be expanded next?
4. In a breadth-first search, what node would be expanded next?
5. In a uniform-cost search, what node would be expanded next?
(15 points) For a genetic algorithm search for the 4-color map problem, describe a coding for individuals and the fitness function The 4-color map problem is that you are given a set of regions to color such that adjoining regions cannot use the same color. There are a max of 4 colors to use.

Part 2: The Mars Rover Agent gets Wheels!

(40 points) In this problem you will build a tree search agent that plans routes on the Martian surface. As in the first assignment, you can build the agent in the programming language of your choice. The purpose of this assignment is for you to become familiar with the concept of search, state spaces, and node expansion.

Coding

You may write your agent from scratch or utilize the objects in the code repository provided with the textbook. Once again, it is a good idea to utilize the pseudocode in the book to help design your agent. If you use the step names in the book such as ExpandNode and QueueingFunction, it will be easy to extend your agent with new capabilities. Your program will be graded on whether it accepts input in the specified format and writes output in the format below that is appropriate to the testing file we use. We will not grade your programming style or design skills.

We will test your program on the CSE dept unix computers, so make sure that the program you turn in is built to run on Solaris. As in the first assignment, turn in either source + the executable, or just source for interpreted languages.

The problem

The agent is armed with a map, and space onboard to carry three samples. The agent's task is to return to base with three different samples (of type 1, 2, and 3). The map carries information about what samples are available in each location (gathered through previous probes). You can assume the agent is able to detect where it is and relate that to a point on the map.

Your job is to design four different agents (which will differ slightly).

DfsMarsTraveller: a depth-first search agent
BfsMarsTraveller: a breadth-first search agent
UcMarsTraveller: a uniform-cost search agent
AstarMarsTraveller: an A* search agent

Each agent must be a separate program, which will be called in the following manner:
> DfsMarsTraveller -s A < ass2-data1.txt

The "-s A" means that you start from point A; you should be sure that you can start from any point on the map. The agent will always be trying to reach the point "Base".

Cost function: in a traditional path-planning problem, the cost may be the distance travelled; in this case you will want to incorporate information about the number of samples collected. For every link to a non-goal node, the cost should be the link distance. However, for links into the goal node, the cost should be:
link distance + 100 * (3 - #ofSamplesCollected)

A* search: for the heuristic function, use the straight-line distance between the node and the base.

Your program should output information about the solution found using breadth-first search, depth-first search, uniform-cost search, and A* search. Your program will earn 10 points for each technique implemented. For each search type, and for every search step, output each search node that is taken off the queue, and the name of the next state on the queue. At the conclusion of the search, output the sequence of states traversed to get from the start to the end city, the distance in kilometers of the path found, the total number of nodes enqueued, and the number of nodes considered by GoalTest.

The distances between points and possible operations from each point is already in the data file located here . The format of this file is:

Node,Sample#,XCoordinate,YCoordinate,NeighborNode1,Distance1,NeighborNode2,Distance2,...

Node: the name of the node (place)
Sample#: the number of the soil sample that can be found there
XCoordinate, YCoordinate: the location of the node
NeighborNodeN: name of the neighboring node (place)
DistanceN: distance to the neighboring place

We will provide I/O and queue routines in the supported languages (C++,LISP, Java,Perl, C, python ) to facilitate programming.You might also want to look at the javadoc of the classes (even if you're coding in c++).

Make sure your depth-first search does not go into an infinite loop. You can prevent this by checking for repeated states, implementing iterative deepening search, or automatically timing out after a certain number of nodes if the goal state hasn't been found.

Submission instructions:

Write up all of your answers to the questions (1 through 5) in a text editor so that it can be submitted electronically. Put all of the files you want to submit (answers to the questions plus the code for part 2), and ONLY those files, in a directory on STDSUN. The code directory needs to include all of the files needed to compile/run your code (including the code we supplied or any code you copied from the book's code repository), not just the program that you yourself wrote. Use the submit command to send the files to the grader. The syntax of the submit command is:

> submit c630aa lab2 (lab2_dir)

Where lab2_dir is the directory containing the files you want to submit. You can learn about using the submit command by typing man submit at a unix command prompt. If you cannot get the submit command to work, you can email your files to the grader, but please don't use this option unless you're having trouble with submit.