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.
BLOCK WORLD PROBLEM CONCEPT IN PROLOG PLUS
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 kommentar(er)
