Back to Blog
Block world problem code in python7/22/2023 The following graph is the same as the above except that it is a plot of the number of blocks against time taken to solve the problem, in seconds. The y-axis is the number of nodes expanded. The x-axis of the graph below is the number of blocks in the problem. Due to time constraints, we stopped a heuristic from continuing on a problem if it had already expanded 3000 nodes. ![]() Each heuristic was tested on the same problems. The following graph shows the number of nodes expanded in running each algorithm over twenty random problems of different a varying number of blocks. We found that Simulated Annealing does not produce good results and takes a long time to run, so we didn't include it in the graph. Heuristic 6 - This heuristic is a combination of heuristics 4 and 5, except when there is a block that must be moved twice (heuristic 4) and is also one of the blocks in a mutual prevention (heuristic 5), we don't add anything for this mutual prevention. This heuristic works the same way as heuristic 3, but adds 2 for each case of mutual prevention. Heuristic 5 - If blocks A and B are preventing each other from being moved to their goal positions, we call this a case of mutual prevention. A block that must be moved twice is a block that is currently on the block upon which it must be placed in the goal state, but that block is a block that must be moved or if there exists a block that must be moved twice somewhere below it (in the same pile). A block that must be moved once is a block that is currently on a block different to the block upon which it rests in the goal state or a block that has such a block somewhere below it in the same pile. Heuristic 4 - this heuristic is twice the number of blocks that must be moved once plus four times the number of blocks that must be moved twice. Heuristic 3 - This heuristic adds 2 for every block that is not currently directly on top of the block on which it has to be in the goal state or if there is such a block somewhere below it (in the same pile). If Block A in the goal state is supposed to be on top of Block B and under Block C and in the current state it is neither on top of B or under C, then we add 2 to the heuristic. It calculates the difference between the current state and the goal state, but looks at the details of each block. Heuristic 2 - this heuristic is similar to Heuristic 1. We do not count a block if it is currently in the arm of the crane. Heuristics description: Heuristic 1 - this heuristic calculates the number of blocks that are currently not in the correct 'position'. We used six different heuristics to solve the problem using A*. ![]() These include DFS, BFS, UCS, A* and simulated annealing. We used a number of algorithms to solve the problem. The blocks world is a NP-hard problem and we wanted to find smart solution to solve it. The program was created by Terry Winograd and is a limited-domain natural-language system that can understand typed commands and move blocks around on a surface. The blocks world is one of the most famous planning domains in artificial intelligence.
0 Comments
Read More
Leave a Reply. |