***************************** * CSCE 625 - AI * * Project #1 * * Due: Tues, Sept 29, 2009 * ***************************** The overall goal of this assignment is to develop and test heuristics for a specific search problem. The problem involves stacking blocks (a variant of the classic "Blocksworld" micro-domain). In any language you choose, you are to write a program to solve random instances of this problem using your own implementation of A* search. The focus of the project, however, is to use your intuitions to develop a heuristic that will make solving various instances of this problem efficient. Description of the problem -------------------------- This task involves stacking blocks. The blocks are labeled by integers. There can be a variable number of blocks, but there are only three stacks. Here is an example: 8 7 6 3 1 2 4 5 ----------- The state can be represented as a list of 3 lists, one for each stack. The lists are read such that left-to-right is top-to-bottom. For example, the state above could be represented as: [[3 2] [4] [8 7 6 1 5]]. The operators in this problem can pick up the top portion of any stack and move it to any other. For example, the 8 above could be moved on top of the 3 or the 4, and the substack of [8 7] could be moved onto the second stack to create [8 7 4], etc. In this domain, there are unit operator-costs, so each move costs 1, regardless of how many blocks are being moved. The goal is to take an initial, arbitrary configuration of blocks (could be 4, 5, or 6, etc.) and move them all to the right-hand stack in sorted order from top down. For example, given the 6 blocks in the above example, the goal would be [[] [] [1 2 3 4 5 6 7 8]]. Developing a heuristic ---------------------- This problem is fairly challenging for search because there is a fairly high branching factor of around 8, and the average depth of a solution for some intitial states can be as high as 10 moves. Your objective is to develop a heuristic that can be used with A* search to make the search efficient. One way to do this is to run an example problem with the simple heuristic, look at the order in which nodes are pulled out of the queue, identify situations in which it could have made an "obviously" better choice, and then use this to construct a calculation that assigns such states a higher (worse) heuristic score. You should try to keep the heuristics you develop admissible, though this is not always easy (if you can't guarantee admissibility, at least try to to design your heuristics to approximate the number of steps remaining to reach the goal state, even if they might be over-estimates). If your heuristics are not optimal, A* will not be guaranteed to find optimal solutions (i.e. of minimal depth). However, in this case, we are more concerned with using the heuristic as a guide to find any solution sequence at all. You might want your A* algorithm to be designed to have a built-in limit of a fixed number of goal tests, such as a few hundred, at which point it will give up. Then your job would be to find a heuristic that will allow it to find solutions to example problems as fast as possible within the time allotted. You should write your own random problem generator (easy) to develop and test your algorithm and heuristics. You might want to start by implementing a trivial default heuristic for comparison, such as one (let's call it h0) that returns 0 for any state (a drastic under-estimate of the distance to the goal, but should simulate breadth-first search within A*). Most of the problems will not be able to be solved within a limit of several hundred goal-tests by this heuristic. Your job is to implement a new heuristic function that allows your A* search to solve as many of the problems in as few goal-tests as possible. Feel free to invent other problems to test and develop your heuristic, such as easy problems with one block out of place, like [[] [1] [2 3]]. Also, a hint is to develop a series of more and more accurate heuristics by adding new calculations onto old ones as you think of them (e.g. h1, h2, h3=h1+h2... but what is the effect on admissibility?). Implement your code in a general way, so that it could be run on problems with an arbitrary number of blocks (e.g. more than 8). What you have to turn in ------------------------ The main thing you have to turn in is a written report that presents a brief overview of the problem, a discussion of the solution (your heuristics and the reasoning behind them), and a table of results showing the number of goal-tests required to solve the example problems (and any others you wish). Show some examples of problem solutions. You should compare the performance of several different heuristics you develop, or evaluate their accuracy (correlate estimates to true distance to goal). You will probably want to run multiple experiments with randomly generated starting configurations to collect statistics on average run-time for various algorithms/heuristics. Perhaps even show a plot of how it scales up with number of blocks... The report is important; you should spend a good deal of time writing an intelligent discription of your heuristics and analysis of your experimental results. You should include a general discussion that comments on how easy or hard it was to come up with the heuristics, what the challenges were, known limitations of your heuristic, other possible ideas that might have worked, etc. One interesting question you might address in the discussion is how often your heuristic leads A* to come up with an optimal solution, versus a sub-optimal one with extra moves that are unnecessary. Turn in your report in hard-copy format (print-out), along with the source code attached to it (as an appendix).