CSE 473:
Artificial Intelligence
Assignment #2
Due: Monday, October 23, 2006
Reading Assignment: Read Chapters 4 and 6.
1. (20 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?
2. (25 points) You’ve just joined the internet search company Gargle, Inc. Your boss wants you to try out the bright idea of using local search algorithms for the problem of sorting N distinct integers, where N is a fixed number. The state representation you will use is simply a sequence of N integers and 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. How many unique successor states does a particular state have for some fixed N?
b. Formulate an objective function (heuristic cost function) for this problem. Assume the goal is to minimize the objective function. Your function should be based on comparing pairs of elements in a state.
c. Does your objective function have any local minima or just a global minimum? Explain your answer.
d. 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)
e. Consider using Genetic Algorithms for this problem, where the initial population is comprised of the initial state and all successors of the initial state. Let N = 5 and assume the input numbers are between 1 and 9. Let the string representing the initial state (5, 9, 3, 7, 2) be 59372. Starting from the initial population, show one iteration of the genetic algorithm using a figure similar to Figure 4.15 in the textbook, showing selection, crossover, and mutation. (Assume a mutation swaps the characters in two randomly selected locations in a string).
3. (55 points) [Programming Assignment] (original design: K. Noto).
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. (If you wish to use a different programming language, please consult the instructor).
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:
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 hand in: