Problem

The blocksWorld is a well-known problem in AI searching area. A description can be found at https://en.wikipedia.org/wiki/Blocks_world. We have several stacks and blocks. Each blocks is assigned a unique letter. The goal state this program wants to achieve is that all blocks are in the first stack and in alphabetical order.

Program

Code

The code can be found at https://github.com/melonskin/blocksWorldAstarSearch.

Compile

Since I am using maven, the easiest way to compile and run it is using IDE (I use IDEA). However, we can always compile and run it in command line. The steps are as follows.

1. cd to the project folder
2. cd src
3. javac com/tangshijin/blocksWorld/*.java

Run

To run the program, execute following command with the arguments of your own choice.

java -cp . com.tangshijin.blocksWorld.Main no_blocks no_stacks no_iter

The user-defined arguments are

• no_blocks: number of blocks in this case
• no_stacks: number of stacks
• no_iter: maximum number of iterations allowed

Output examples

An output example is shown as below.

$ java -cp . com.tangshijin.blocksWorld.Main 6 4 100
initial state:
1 | A 
2 | E 
3 | F B D 
4 | C 

iter = 0, queueSize = 0, f = -1, depth = 0
iter = 1, queueSize = 11, f = 8, depth = 1
iter = 2, queueSize = 19, f = 7, depth = 2
iter = 3, queueSize = 27, f = 6, depth = 3
iter = 4, queueSize = 32, f = 5, depth = 4
iter = 5, queueSize = 37, f = 6, depth = 4
iter = 6, queueSize = 45, f = 6, depth = 5
iter = 7, queueSize = 50, f = 6, depth = 5
iter = 8, queueSize = 54, f = 6, depth = 5
iter = 9, queueSize = 55, f = 6, depth = 5
iter = 10, queueSize = 59, f = 6, depth = 5
iter = 11, queueSize = 64, f = 6, depth = 3
iter = 12, queueSize = 68, f = 6, depth = 6
success! depth = 6, total_goal_tests = 12, max_queue_size = 69
solution path:
1 | A 
2 | E 
3 | F B D 
4 | C 

1 | A 
2 | E D 
3 | F B 
4 | C 

1 | A B 
2 | E D 
3 | F 
4 | C 

1 | A B C 
2 | E D 
3 | F 
4 | 

1 | A B C D 
2 | E 
3 | F 
4 | 

1 | A B C D E 
2 | 
3 | F 
4 | 

1 | A B C D E F 
2 | 
3 | 
4 | 

Heuristic function

My heuristic function is basically the summation of the number of moves to move single block to its target position for all blocks.

At the target state, all blocks will be in order in the first stack. At other states, for the first stack, there are actually two case. One is the current block is above the target position. The measurement is number of moves that we takes all blocks above the target position(inclusive) away and put the current blocks. The other is current block is under the target position. The heuristic function valus is number of moves that taking all blocks above the current block (inclusive) away, and filling blocks back until reaching target position, then putting current block back.

For other stacks, the distance is actually the summation of the number of blocks above the target position in the first stack and the number of blocks above the current position in the current stack, plus one. That is to say, number of moves if we move all blocks above current position (exclusive) and target position (inclusive) to other position, and then move current block to the target position.

Furthermore, to improve the heuristic function, we may consider adding weight parameter to each block. Obviously, getting “A” in place first is better than getting “B” in place first then dealing with “A”. Because we don’t need to touch “A” any longer. Therefore, we can improve our heuristic function by add addtional term to the number of moves of every blocks to make sure “A” is placed in the right position first and so on.

If admissible?

This heuristic function is not admissible. Because during experiment, decreasing f(n) values are observed sometimes. However, for admissible heuristic functions, A* explore nodes in the order of increasing f(n) values. This function will overestimate true distance to goal. Taking fewer steps other than what has been described is totally possible.

Experiments

Performance metrics for the first heuristic

15 cases are chosen to run. Every case is repeated for 20 times. Max number of iteration is set to be 20000. The table below shows the mean performance.

Performance metrics for the second heuristic

For second heuristic function, larger cases are chosen to run.

Discussion

From the table of performance metrics, we can observe that this heuristic function works well. The mean path depths are far more less than corresponding numbers of initial moves we made.

For every case with 3 stacks, all 20 repeated tests succeeded with a mean depth less than or almost 10 and relatively small number of iterations and frontier size. Even for the difficult case with 3 stacks and 10 blocks, this program performs well.

For the cases with 10 blocks and more than 3 stacks, this program has about 90% chance to succeed. The mean depth is still reasonable, far less than the number of initial moves. Compared with the benchmark depth 18 of the case with 5 stacks and 10 blocks, our mean depth is around 16. However, the number of iterations and frontier size will increasing dramatically as the number of stacks rises.

As the number of stacks goes up, the branching parameter will increasing exponentially. We also have more initial random moves so that the depth of potential goal is very likely to be large. Therefore, the problem will be harder to solve. As we can observe in the table, for the initial heuristic function, case with 20 blocks and 7 stacks has the largest mean number of iterations and frontier size. It has 20% chance to find the goal, less than other cases. Meanwhile, since the cases with more blocks and stacks will have more initial moves, it can also make the problem harder.

The largest problem is considered th be the most computationally difficult. Therefore, it should be the case with large number of stacks, which means large branching parameter and more initial random moves. The largest problem we could solve is the case with 10 blocks and 8 stacks for initial heuristic functions. It will be slow when we have 9 stacks. For more difficult problem, the program has the risk running out of memory.

The second one performs better on large problems since the corresponding number of iterations and maximum frontier size are less than the cases with the initial heuristics. As we can see, the goals it can reach are far deeper than those with initial heuristic function. It can deal with the cases with more blocks (35) and more stacks (11) with less iterations and frontier size.

As mentioned above, our mean path depth for the case with 10 blocks and 5 stacks is pretty similar to the benchmark optimal depth provided. The depth is also far more smaller than the number of initial random moves.

To improve the heuristic function, we may consider modify the weight for every letter more precisely based on performance.