Read "Streaming Systems" 1&2, Streaming 101 Read "F1, a distributed SQL database that scales" Read "Zanzibar, Google’s Consistent, Global Authorization System" Read "Spanner, Google's Globally-Distributed Database" Read "Designing Data-intensive applications" 12, The Future of Data Systems IOS development with Swift Read "Designing Data-intensive applications" 10&11, Batch and Stream Processing Read "Designing Data-intensive applications" 9, Consistency and Consensus Read "Designing Data-intensive applications" 8, Distributed System Troubles Read "Designing Data-intensive applications" 7, Transactions Read "Designing Data-intensive applications" 6, Partitioning Read "Designing Data-intensive applications" 5, Replication Read "Designing Data-intensive applications" 3&4, Storage, Retrieval, Encoding Read "Designing Data-intensive applications" 1&2, Foundation of Data Systems Three cases of binary search TAMU Operating System 2 Memory Management TAMU Operating System 1 Introduction Overview in cloud computing 2 TAMU Operating System 7 Virtualization TAMU Operating System 6 File System TAMU Operating System 5 I/O and Disk Management TAMU Operating System 4 Synchronization TAMU Operating System 3 Concurrency and Threading TAMU Computer Networks 5 Data Link Layer TAMU Computer Networks 4 Network Layer TAMU Computer Networks 3 Transport Layer TAMU Computer Networks 2 Application Layer TAMU Computer Networks 1 Introduction Overview in distributed systems and cloud computing 1 A well-optimized Union-Find implementation, in Java A heap implementation supporting deletion TAMU Advanced Algorithms 3, Maximum Bandwidth Path (Dijkstra, MST, Linear) TAMU Advanced Algorithms 2, B+ tree and Segment Intersection TAMU Advanced Algorithms 1, BST, 2-3 Tree and Heap TAMU AI, Searching problems Factorization Machine and Field-aware Factorization Machine for CTR prediction TAMU Neural Network 10 Information-Theoretic Models TAMU Neural Network 9 Principal Component Analysis TAMU Neural Network 8 Neurodynamics TAMU Neural Network 7 Self-Organizing Maps TAMU Neural Network 6 Deep Learning Overview TAMU Neural Network 5 Radial-Basis Function Networks TAMU Neural Network 4 Multi-Layer Perceptrons TAMU Neural Network 3 Single-Layer Perceptrons Princeton Algorithms P1W6 Hash Tables & Symbol Table Applications Stanford ML 11 Application Example Photo OCR Stanford ML 10 Large Scale Machine Learning Stanford ML 9 Anomaly Detection and Recommender Systems Stanford ML 8 Clustering & Principal Component Analysis Princeton Algorithms P1W5 Balanced Search Trees TAMU Neural Network 2 Learning Processes TAMU Neural Network 1 Introduction Stanford ML 7 Support Vector Machine Stanford ML 6 Evaluate Algorithms Princeton Algorithms P1W4 Priority Queues and Symbol Tables Stanford ML 5 Neural Networks Learning Princeton Algorithms P1W3 Mergesort and Quicksort Stanford ML 4 Neural Networks Basics Princeton Algorithms P1W2 Stack and Queue, Basic Sorts Stanford ML 3 Classification Problems Stanford ML 2 Multivariate Regression and Normal Equation Princeton Algorithms P1W1 Union and Find Stanford ML 1 Introduction and Parameter Learning

Solve blocksWorld problem with A* Search

2017-09-24

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.

No. blocks No. stacks Mean depth Inital moves No. successes Mean No. iterations Mean max frontier size
5 3 5.45 15 20/20 8.60 18.75
6 3 6.40 18 20/20 11.10 27.85
7 3 8.75 21 20/20 43.45 86.05
8 3 10.00 24 20/20 57.65 140.45
9 3 10.40 27 20/20 364.45 910.15
10 3 8.80 30 20/20 34.40 89.35
10 4 13.45 40 20/20 752.90 3544.25
10 5 16.25 50 20/20 2104.50 14121.90
10 6 17.26 60 19/20 1660.74 12332.37
10 7 18.81 70 16/20 5657.13 52990.88
10 8 18.80 80 10/20 6306.90 70438.80
15 7 23.40 105 5/20 5196.80 52627.40
20 7 22.50 140 4/20 7635.00 70571.50
25 7 NaN 175 0/20 NaN NaN
30 7 19.00 210 1/20 1189.00 11662.00

Performance metrics for the second heuristic

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

No. blocks No. stacks Mean depth Inital moves No. successes Mean No. iterations Mean max frontier size
5 3 6.30 15 20/20 9.95 21.05
6 3 6.35 18 20/20 10.10 24.80
7 3 8.50 21 20/20 15.80 38.50
8 3 8.20 24 20/20 15.85 40.30
9 3 7.70 27 20/20 14.95 38.05
10 3 10.40 30 20/20 17.85 47.45
10 4 13.70 40 20/20 178.85 885.65
10 5 13.40 50 20/20 300.35 1999.80
10 6 17.89 60 18/20 1640.50 11468.22
10 7 17.88 70 16/20 2950.56 22574.31
11 7 20.56 77 18/20 3351.78 27974.33
15 7 26.50 105 10/20 7602.10 70549.70
20 7 28.71 140 7/20 7256.29 67380.14
25 7 32.00 175 4/20 7061.25 65670.75
30 7 31.50 210 2/20 6359.00 57032.50
35 7 34.00 245 3/20 12145.00 96536.67
15 8 18.33 120 3/20 5763.67 64798.67
15 9 14.00 135 1/20 2366.00 33107.00
15 10 24.00 150 1/20 2233.00 31626.00
15 11 35.00 165 1/20 12504.00 197140.00

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.


Creative Commons License
Melon blog is created by melonskin. This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
© 2016-2019. All rights reserved by melonskin. Powered by Jekyll.