CMSC 341 Spring 2011
Project 3

Assigned

Sunday, Apr 3, 2011

Due

11:59pm, Sunday, Apr 24, 2011

Update

1.      Due date is moved to 11:59pm, Tuesday, Apr 26, 2011

2.      Dead-state was mentioned in best-first algorithm, however, for the 8-puzzle problem specified in this project dead state will never occur.

Objectives


Description

In this project, you are asked to implement a search method, called best-first, to solve the 8-puzzle problem. This search method is supported by a priority queue.

Search

Search has been used as an effective method to solve complex problems whose solutions are within a huge space. A search typically starts with the initial state S0 that satisfies the initial conditions and continuously generates new states from S0 and its descendents until a goal state Sg that satisfies the conditions is generated. A new state Sj is generated from a known state Si (initially only S0 is known) by an applicable generation operator, and Sj is a child of Si. A state is called an open state if none of its children has been generated, a closed state if all of its children have been generated, and a dead state if it is not a goal state and it does not have a child (i.e., no generation operator is applicable to that state). The path from S0 to Sg is a solution to the problem.

One of the search methods that guarantees to find the optimal solution (i.e., the one with the shortest solution path) is called best-first search. Best-first search requires that each state has a merit value measuring how likely it is to be on an optimal solution path. The search can be outline as follows:

openQ = {S0}    //the set of open states, initially contains S0 only

while openQ is not empty

   { Sk = the state in openQ with the best merit;  // this is why it is called best-first

     openQ = openQ – {Sk}; //remove Sk from openQ;

     if Sk is a goal, a solution is found and exit;

     if Sk is a dead state, do nothing;

        else generate all children of Sk, calculate their merits, and put them to openQ.

         // Sk is closed, since all of its children are open

   }

Some details of this method such as how to generate the solution path once a goal state is reached and what is required for a good merit function are not descried here since they are not relevant to this project. But it is clear that if we treat the merit value of each state as its priority, then priority queue is naturally a good fit for openQ.         

8-puzzle

Given an initial configuration of 8 numbered tiles, 1, 2,…, 8, on a 3 x 3 board (initial state S0), move the tiles in such a way so as to produce a desired goal configuration (goal state Sg) of the tiles.

Generation operators

At each time, one of the numbered tiles adjacent to the blank tile either vertically or horizontally ca be moved to the blank tile (and its previous position becomes blank). These moves are the legal generation operators, and each move generates a new configuration, a child state. An easier way to encode the operators is to allow the blank tile to move up, down, left, or right one cell unless it hits the boundary. Depending on where the blank tile is located, a state can have 2, 3, or 4 children. The average number of children a state has is 2.67 (why?).

Figure 1 below is an example showing how child states are generated. Note that the initial state (at the top) has the blank tile on a corner, so it has two children. The child on the left has three children, one of which is the initial state. For efficiency, your implementation should NOT allow any state to generate its parent state as its child.

In this figure, there are two closed states (internal nodes) and three open states (leaf nodes) with path lengths from the initial state 2, 2, 1 (from left to right).

Figure 1

Merit value

Merit of each state is measured by a cost function (the smaller the better). The cost function consists of two parts

cost(Si) = g(Si) + h(Si), where

·         g(Si) is the length of the path from S0 to state Si created during the search, measuring the costs from S0 to Si. Note that if Sj is generated from Si then g(Sj) = g(Si) +1.

·         h(Si) is a heuristic that estimates how much it will cost going from Si to a goal state. In particular, h(Sg) = 0 and h(dead-state) = ∞.

There are a number of good heuristics for 8-puzzle problem, for this project, we use one of the simplest (and least efficient), which is the number of misplaced tiles in Si comparing with their goal positions in Sg. For example, for the goal state in Figure 2 below, the h value for the open state at the lower-left of Figure 1 is 7 (only tile 7 is in the goal position), and the total cost is 2 + 7 = 9. [Note that h(.) does not count the blank tile because when all 8 numbered tiles are in their goal positions, the blank tile shall also in its goal position.]

 

Figure 2. A goal state

When the goal state is reached at the end of a successful search, cost(Sg) = g(Sg), the length of the solution path found from S0 to Sg. This value can be viewed as a measure of the time complex of this problem since the number of states generated is in O(2^ g(Sg)). The size of openQ increases when search progresses. Since there is no dead-state for 8-puzzle as described here (why?), openQ will never shrink before the goal state is removed. The size of openQ thus can be viewed as the measure of the space complexity.


Your Tasks

You will have the following tasks:

·         Implement Priority Queue ADTs. You can base your implementation on Priority Queue lecture slides and author’s code of min binary heap.

·         Implement the best-first search method as outlined in the pseudo code earlier. You MUST use priority queue for openQ.

·         Your code will read in a pair of state configurations from the data file, the first is the initial state, the second is the goal state. After the goal state is reached by best first search, you will output

­   The first five state configurations in the order they are removed from openQ, together with their cost, h, and g values

­   The solution cost (the length of the path you found from the initial state to the goal).

­   The size of openQ at the end of the search process.

Implementation notes

·         Use the cost value as the priority for each state in openQ. Different states may have the same cost value, for uniformity, you should generate children of a state in the following order (if applicable): moving the blank tile up, left, down, right.

·         The same configuration can be generated from different paths, and thus with different cost values. You do NOT need to check if any has been generated before except that one state cannot have its parent as its child as stated earlier.


Command Line and Data File

Project 3 will be invoked with a command line with a single argument which is the name of the full path of the data file that contains a pair of state configurations. Following is an example of the command line:

 
  ant -Dargs="/afs/umbc.edu/users/y/p/ypeng/pub/cs341s11/Proj3/test1.txt" run

You must check command line arguments to ensure that they are valid, and the command file can be opened, and throw an exception if an error is found.

The data file consists of 6 lines of 3 integers each. The first three lines form the initial state, the next three the goal state. Integers are 0, 1, 2… 8 where 0 represents the blank tile, the other 8 are the numbered tiles. Integers on each line are separated by 1 single space. You can assume the data file is free of syntax error. The following is an example of a data file.

1 3 4

8 6 2

7 0 5

1 2 3

8 0 4

7 6 5

The format of printout for a state may look like the following:

1 3 4

8 6 2

7 0 5

cost = 4

g = 0

h = 4

 


Files to Be Submitted

Submit the following files:

  1. build.xml
  2. all your source code (including Proj3.java), your source code must be organized in the way that is consistent with your build file, otherwise it won’t compile and run
  3. README (optional)

You must use CVS to check out your module in the Proj3 repository and to check in your code. That must include an ant build.xml file and javadoc. See the projects page for more information on all of these topics. The repository location for this project is:

 
      /afs/umbc.edu/users/y/p/ypeng/pub/cs341s11/Proj3

If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your submittals. Make sure they work. Do this before the due date.