CIS630 Homework 2: Informed and Uninformed Search

Due to the tornado warning, the deadline is extended 24 hours to October 12th.

Due:October 12 at 11:59 P.M.
 1 point late penalty for each minute late

Part 1: Problems

  1. (10 points) Explain whether a bidirectional search could be employed to solve the following problems:
    1. The n-queens problem.
    2. The Kevin Bacon game: link any movie star to Kevin Bacon. To play this game, go to the Oracle of Bacon at UVA.
  2. (20 points) Describe the state variables, initial state, operators, and goal test for the 4-sudoku problem. In 4-sudoku, there is a 4x4 grid, with 4 inner grids in each corner. You start with a partially-filled in grid, and are only allowed to add numbers 1-4 to the grid so that no row, column, or inner grid has the same number.

    Example initial configuration:
    2 4
    _ 3
    _ _
    _ _
    _ _
    _ _
    4 _
    3 1

  3. (15 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 breadth-first search, what node would be expanded next?
    4. In a uniform-cost search, what node would be expanded next?
    5. In a depth first search, what node would be expanded next?
  4. (6 points) Prove each of the following:
    1. Breadth-first search is a special case of uniform-cost search.
    2. Breadth-first search, depth-first search, and uniform-cost search are special cases of best-first search.
    3. Uniform-cost search is a special case of A* search.
  5. (9 points) In the knapsack problem, you have objects weighing 1,3,4,7,8,10,11, and 13 pounds. You want to fit as much as possible into a knapsack that has a capacity of 40 pounds. Formulate this problem as a genetic algorithm search by describing a coding for individuals and the fitness function.

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).

Each agent must be a separate program, which will be called in the following manner: > DfsMarsTraveller -s A < hw2-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 both the search progress and 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, it's priority number (i.e, depth in BFS/DFS, cost in UCS, f-cost in A*) 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, and the total number of nodes enqueued. 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,...

Do not hard code any of this file; we may choose to grade using a different map. We will provide I/O and queue routines in the supported langauges (C++,Java, C) 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 (say 10) if the goal state hasn't been found. Please tell the grader which strategy you are employing.

Extra credit (up to +25 points):

Code up the 4-sudoku problem as a search problem, solving the example sudoku given. We may test with another sudoku, so tell us how to input this into your program.

Submission instructions:

The grader had some requests: 

- Please only submit things he can print from unix (pdf or txt files). If you can't do that, print out a hard copy and put it in Prof. Fosler-Lussier's mailbox (behind 395 Dreese)

- If you choose to print out, then you need to do one of two things:
A) Get it in Dr. F's mailbox by 5 pm.
B) Put it in Dr. F's mailbox tomorrow, but submit the files online in addition so that they are timestampped.

This will only apply to this homework because the message is coming out late. In future homeworks, you'll only be able to get paper submissions in by 5pm.

- Submit one file for all written answers, not a separate file for each.

-1 File if possible for individual programs. It is possible to have
multiple classes in C/C++ and Java without making me hunt for them.

-No sub folders please.

-Please include source codes only. This goes for MAKE scripts too, as I
have to make sure you aren't pulling source code from somewhere else.
Instructions for compile/parsing should be a command or set of commands.

-If you feel it necessary to include the compiled version of your code,
please make sure that you include the source code with it.
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 your code for part 2 and extra credit), and ONLY those files, in a directory on STDSUN, and 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.