Dustin Stevens-Baier
Comp 569
Assignment #3
1. Find the shortest path for the example given in Assignment #3. If there is more than one shortest path, present them all.
The shortest path is D to the table , B to table, E to final state, F to its final state, C to its final state, A to table, G to final state, A to final state, D to its final state for a total of 10 moves. All most be moved once.
2. Show that the following heuristic will create valid, but not necessarily optimal, solutions: Use these rules: If any available block (any block at the top of a stack in the initial state) can me moved directly to its final position in the goal state then do it. If not, then take the block on the top of the largest stack and move it to the table (if there are two largest stacks then break ties by using the first stack as counted left to right). Iterate in this fashion until the goal state is achieved. Show that this method can produce an optimal solution in some cases, but suboptimal in others (give an example of each).
Optimal:
If we start with one stack ordered top to bottom = {W, X,Y,Z} and another stack = {A,B,C} and our goal state is
{A,W,X,B,Y,C} and {Z}
A to final, W to final, X to final, B to final, Y to final, C to final, Z to final
Sub optimal
If we start with the stack ordered top to bottom = {W,X,Y,Z} and {C,B,A} and our goal is {A,W,X,Y,Z,} {C,B}
following rules:
W table, X table, C table, B final, A final, W final, X final,Y final, Z final
shortest path:
C table, B final, A final, W final, X final, Y final, Z final, C final
You can see one less move.
3. Explain why, in an optimal solution, no block more should be moved more than twice.
Best case a block is palced directly in final state since every block has to be moved (1 Move)
Otherwise a block can be placed on the table and then from the table to final state. If a block is moved more than two times you can always eliminate the moves in the middle because you can just leave the block on the table until it can go into its final state.
4. Explain why finding the shortest path reduces to deciding which blocks will be moved twice and which ones will be moved only once.
The goal is to eliminate as many of the table moves as possible, you will always have as many final state moves as there are blocks. This means that we have to decide which ones to move to the table and minimize this number, this is deciding which ones are two moves, once we have minimized this number the rest will be 1 move.
5. Explain how the concept of "deadlock" applies to this problem. Give examples.
The concept of deadlock in this case is described in the paper, "On the Complexity of Blocks-World Planning." The difficulty in dealing with these deadlocks is that there can be an enabling condition interaction. This is when an action invoked to achieve a final state can have an unforseeen side effect of making it easier to achieve other goals. This makes it hard to create a heuristic that can predict the best possible outcome, without comparing all the outcomes.
6. Create a computer simulation of this blocks world problem (graphical display is extra credit). Implement the heuristics described above: H1: all blocks go to the table, then moved into final positions; H2: described in 2 above. Invent a better heuristic if you can.
I did the above heuristics using the examples in the assignment. I set up the code to deal with just the two initial and final stacks. Although they could be any size, under ten (which could be adjusted easily) . I did not allow for user input, but that could be easily adjusted as long as the constraints of only two starting stacks and two final stacks where met.
7. a) Create a graphical representation of this problem using a directed graph with nodes that correspond to the blocks and arcs that indicate a constraint created by the initial or goal state configurations.
I tried to implement the graph using the terminology in Gupta's paper. This is a little confusing to me as I believ that an initial state is any place that a block starts in so a block would be indentified as being intial if is already in its final state to begin with.
b) Research the Feedback Arch Set problem. This problem boils down to finding the fewest arcs to remove from a directed graph that will make it acyclic (no more cycles), and it is known to be NP complete. Explain how EBW reduces to the Feedback Arc Set problem, and thereby show that EBW is NP complete. (This is actually difficult, so I am not expecting perfect answers, just some rationale -- make an attempt to understand the Feedback Arc Set problem, and then try to tie it together with the graphical representation you came up with in part a). All of this shows that this simple blocks world planning problem is of equal complexity to the better-known traveling salesman problem.
Researching the problem shows that the feedback arch set problem is reduced to ebw by removing all deadlocks. this is graphical represented by the simple cycle, per lemma 3 in "On the Complexity of Blocks-World Planning." The biggest diffculty to me is understanding how to make the above graphical representation.