CSEP 573: Applications
of Artificial Intelligence
Homework Assignment #1
Due: Before class time (6:30 pm) on Monday, January 25, 2010
Turn-in procedure: Use the dropbox: https://catalysttools.washington.edu/collectit/dropbox/afriesen/8677
to submit a folder containing a document with your answers to problems 1-4 below and all files requested in problem 5. Name the folder HW1_<LastnameFirstname>.
Reading: Chapters 1-5 in the textbook AIMA (3rd ed.).
Problems:
1. (10 points) Give a PEAS description of the task environment for each of the following agent:
a. Lawn mowing robot
b. Internet airline-ticket shopping agent
2. (15 points) Consider a state space where the start state is 1 and the successor function for state i returns three states: 3i, 3i+1, 3i+2.
a. Draw the state space from 1 to 53 (start from 1 and iterate to get a tree structure). Show only states reachable from the start state.
b. Suppose the goal state is 37. List the order in which nodes will be visited for: (i) breadth-first search, (ii) depth-limited search with depth limit 3, and (iii) iterative deepening search.
c. Describe how bidirectional search would work for this problem? Does this suggest a solution for getting to a goal state from state 1 with almost no search?
3. (10 points) Consider a best-first search algorithm with evaluation function:
f(n) = a1g(n)+a2h(n) where h is admissible.
a. What type of search does this algorithm perform when:
i. a1 = 1 and a2 = 0?
ii. a1 = 0 and a2 = 1?
iii. a1 = a2?
b. Let a1 = 1. For what values of a2 is the algorithm guaranteed to be optimal?
4. (15 points) Your boss woke up in the middle of the night with the bright idea of using local search algorithms for sorting N distinct integers, where N is a fixed number. You’ve been asked to test this idea. The state representation you have decided to use is simply a sequence of N integers; a successor of a state is obtained by swapping any two adjacent elements in the sequence. For example, two successors of (13, 12, 19, 2, 5) are (12, 13, 19, 2, 5) and (13, 19, 12, 2, 5).
a. Formulate an objective function (heuristic cost function) for this problem.
b. Does your objective function have any local maxima or just a global maximum? Explain your answer.
c. Let N = 5 and let the initial state be (5, 9, 3, 7, 2). Show a possible next state and a possible state after that next state, along with their objective function values, when using:
i. Hill climbing
ii. Simulated annealing (you get to choose a value for T)
5. (50 points) [Programming Assignment]
You are to implement the A* search algorithm to solve the 8-puzzle. The 8-puzzle consists of a 3x3 grid of squares, tiles numbered 1-8, and one blank space. For instance, an initial configuration of the puzzle might look like this:
|
2 |
3 |
6 |
|
|
4 |
5 |
|
8 |
1 |
7 |
The goal of your program is to get it into the following arrangement:
|
1 |
2 |
3 |
|
8 |
|
4 |
|
7 |
6 |
5 |
Note that the blank space is in the middle. A move consists of moving one of the tiles next to the blank space into the spot where the blank space is. This leaves the spot previously occupied by the tile blank. We will call the possible moves L, R, U, and D based on whether the blank space moves to the left, right, up or down respectively.
Your task is to write a Java program which takes a file describing an initial puzzle configuration, and uses the A* algorithm to search for a series of moves which will solve the puzzle.
Heuristic Function: Recall that A* evaluates nodes according to the path cost to the node plus the estimated path cost to the goal node. It expands the node with the smallest total first.
Your job is to implement and test any three (3) different
heuristic functions. At least one of these heuristics must be admissible,
and at least one must be non-admissible.
Also, one of the heuristics you implement should be the "
Program Specifics: You will write a file called HW1.java (notice the upper case) which has the calling convention:
java HW1 <input-file>
where <input-file> is the name of a file that
contains the initial state of the 8-puzzle in row-major-order (first row
followed by second row followed by third) with 0 representing the
location of the blank space. For example, the goal configuration depicted above
would represented as: 1 2 3
8 0 4 7 6 5
Your program should output:
1. Whether or not a solution is found
2. The number of nodes expanded during the search
3. The length of the solution (number of moves)
4. The solution itself (in the format: UDDL... meaning "Up, Down, Down, Left, ...")
It is okay to allow your program to take extra arguments
beyond the input file name to identify which of your heuristic functions to
use, but the "
Be careful about using random configurations to test your program. Not all 8-puzzle configurations are solvable. Your program should return "No solution" if there is indeed no solution to a given 8-puzzle configuration, but it will take quite a long time to search all of state space (several hours, for example). For debugging purposes, feel free to use the following configurations which are all solvable:
2 3 6 0 4 5 8 1 7
8 3 2 7 0 4 6 1 5
7 8 3 5 0 6 1 4 2
0 4 8 7 5 3 1 2 6
7 8 0 2 4 1 5 6 3
8 4 2 6 1 3 7 5 0
7 8 4 3 5 6 0 1 2
7 8 4 3 5 6 1 0 2
7 6 8 3 2 0 1 4 5
2 0 6 7 3 8 1 4 5
Although not required, feel free to write code for visualization, showing, for example, a movie of how the initial configuration was transformed move-by-move to the goal configuration.
What to turn in: