من فضلكم تساعدوني

[أبو خضره]

In this programming assignment, you will use the A* algorithm to solve instances of the Rush Hour puzzle. This will involve implementing a graph-search version of A*, along with three heuristics, and testing your implementation on several Rush Hour puzzles.

Rush Hour puzzle
This assignment focuses on Rush Hour puzzle such as the following:



2665cars.doc

In Rush Hour puzzle, the red car is stuck in traffic and is trying to escape. Cars can be moved up and down or left and right. They are allowed to move more than one square in a single move, but cannot move over or through other cars. The goal is to clear a path so that the red car can escape past the yellow arrow.
A* and heuristics for Rush Hour
One of the main parts of this project is implementing A* and three heuristics for solving Rush Hour puzzles. Your implementation of A* should check to be sure that it is not re-exploring parts of the search space that have already been explored. The goal of the search is to solve the puzzle in the fewest moves possible, so the cost of a search path should simply be the number of legal moves made.
Here are the three heuristics that you should implement and test A* on:
1. The trivial zero heuristic whose value is equal to zero in all states. Note that using A* with this heuristic is equivalent to breadth-first search.
2. The blocking heuristic which is equal to zero at any goal state, and is equal to one plus the number of cars blocking the path to the exit in all other states. For instance, in the state above, there are two cars (namely, the two green ones) on the path between the red car and the exit. Therefore, in this state, the blocking heuristic would be equal to three.
3. A third, advanced heuristic of your own choosing and invention. You should aim for a heuristic that will be at least as effective as the blocking heuristic. A trivial heuristic, comparable to the zero heuristic in triviality, would not be appropriate.
You should submitt an additional written report, you should include a clear and precise description of the advanced heuristic that you chose to implement. You also should include a brief but convincing argument of why both the blocking heuristic and your advanced heuristic are consistent, and therefore appropriate for use with A* search.
Note that every car is constrained to only move horizontally or vertically. Therefore, each car has one dimension along which it is fixed, and another dimension along which it can be moved.
Your A* implementation will take as input a heuristic (1-3) and a string representing the names of the text file containing the initial state. The output should contain:
1. the solution as a sequence of operations; for example:
Move car # 3 down 3 squares
Move car # 1 down 1 square
…
2. The depth of the goal state found
3. The number of nodes expanded
4. The branching factor
5. The cost of the solution found

Locations on the grid of a Rush Hour puzzle are identified by their (x, y) coordinates, where the upper left corner is square (0,0). For instance, in the puzzle above, the red car occupies squares (1,2) and (2,2). The goal is to move the red car so that it occupies squares (5,2) and (6,2).
The goal car (the one we are trying to move to the exit) is always assigned index 0. The remaining cars are indexed 1,2,4, …
Puzzles should be read from a file into memory and they must be encoded as in the following example representing the puzzle above:

6
0 1 2 h 2
1 2 0 v 2
2 4 0 h 2
3 3 1 v 3
4 4 1 v 2
5 4 3 h 2
The first line "6", gives the size of the grid, i.e., this puzzle is defined on a 6x6 grid. The next line, "0 1 2 h 2", gives a description of the red car. The first number is the car ID. The second two numbers (1,2) give the (x, y) coordinates of the upper left corner of the car. The "h" indicates that the car is horizontally oriented ("v" would have indicated vertical orientation). The last number "2" indicates that the car has size (i.e., length) 2. The next line, "1 2 0 v 2" describes the pink car, and so on.
For this assignment, you can assume that the puzzle is a 6x6 grid, that the goal car always horizontally oriented.
You may notice that the results you achieve for the number of nodes searched are different, and frequently better, than the sample ones above. The number of nodes searched can vary pretty widely, even among "correct" implementations, due to slight variations involving the handling of nodes in the fringe that have the same cost. The results above were achieved for an implementation in which such ties are broken in a FIFO order, i.e., the node that was placed in the OPEN earliest is removed first, an approach that actually appears to be suboptimal. In any case, any way you choose to handle ties is acceptable and the potential variation in results will be taken into account when grading your assignments. (However, see the note below under "debugging tips".)
Note that in general we will not provide full-scale "reference solutions" for the programming assignments. Being able to thoroughly test and then debug computer programs is an important and often challenging task (especially for AI programs) requiring skill that is well worth developing. A good way to test your program is to run it on a variety of small problem instances where you know what the correct behavior should be. Also, sometimes the answer can be computed in two different ways; for instance, on this problem, we know that the search depth of the optimal solution should be the same regardless of which heuristic is used.
What to turn in
Using email: [email protected] you should turn in the following:
• The source code ready to compile and run. The subject must AI PROJECT and student names
• If appropriate, a readme.txt file explaining briefly how your code is organized, what data structures you are using, or anything else that will help the TA understand how your code works.
In addition, you should turn in a hard-copy to the instructor including the following:
• A clear and precise description of the advanced heuristic that you implemented.
• A convincing argument as to why your advanced heuristic and the blocking heuristic are both consistent.
What you will be graded on
We will automatically test your code on Rush Hour puzzles, possibly different from those that we provided. Your grade will depend largely on getting the right answers. In addition, your code should be efficient enough to run reasonably fast (easily running in not more than a few minutes on all forty puzzles and all three heuristics on a typical PC) and without running out of memory. Your code should not terminate prematurely with an exception (unless given bad data, of course); code that does otherwise risks getting no credit for the automatic testing portion of the grade. As always, you should follow good programming practices, including documenting your code enough for the TA's to be able to read and understand it. Creativity in the design of the advanced heuristic will be one factor in your overall grade.
Your write-up should be clear, concise, critical, thoughtful and perceptive.
This programming assignment will be worth about 15 points (about 12 for a correct implementation of all the algorithms, documentation and good programming practice, and 3 points for the report.

موعد تسليمو 1-12 وانا عندي مشروع تخرج غير هاد الواجب ومشغوله في
فيا ريت تساعدوني ازا ممكن تعرفو حد يحلو او عالاقل بعض الكودات تساعدني