public:t-622-arti-12-1:prog1
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
public:t-622-arti-12-1:prog1 [2012/01/26 17:12] – stephan | public:t-622-arti-12-1:prog1 [2024/04/29 13:33] (current) – external edit 127.0.0.1 | ||
---|---|---|---|
Line 1: | Line 1: | ||
====== Programming Assignment 1 - Search ====== | ====== Programming Assignment 1 - Search ====== | ||
+ | |||
+ | **Use the [[http:// | ||
===== Problem Description ===== | ===== Problem Description ===== | ||
Line 16: | Line 18: | ||
Your actions have the following costs: | Your actions have the following costs: | ||
- | * TURN_OFF: | + | * 1 + 15*D, if you TURN_OFF |
- | * 1 + 15*D, if the robot is in the home location and there are D dirty cells left | + | * 100 + 15*D, if you TURN_OFF |
- | | + | * 5 for SUCK, if the current location of the robot does not contain dirt |
- | * 5 for SUCK, if the current location of the robot does not contain dirt | + | * 1 for SUCK, if the current location of the robot contains dirt |
- | * 1 for all other actions | + | |
===== Tasks ===== | ===== Tasks ===== | ||
Line 28: | Line 30: | ||
* Implement methods to compute the legal moves in a state and the successor state resulting of executing an action. | * Implement methods to compute the legal moves in a state and the successor state resulting of executing an action. | ||
* Implement the goal test, i.e., a method telling you whether a certain state fullfills all goal conditions. | * Implement the goal test, i.e., a method telling you whether a certain state fullfills all goal conditions. | ||
- | - Assess the following blind search algorithms wrt. their completeness, | + | - Assess the following blind search algorithms wrt. their completeness, |
- Implement the three algorithms and make sure to keep track of the number of state expansions and the maximum size of the frontier. Run all the given environments with the three algorithms and compare the results wrt. | - Implement the three algorithms and make sure to keep track of the number of state expansions and the maximum size of the frontier. Run all the given environments with the three algorithms and compare the results wrt. | ||
* number of state expansions (time complexity) | * number of state expansions (time complexity) | ||
Line 40: | Line 42: | ||
===== Material ===== | ===== Material ===== | ||
- | * {{: | + | * {{: |
- | * {{: | + | * {{: |
The files in the archive are similar to those in the first lab. | The files in the archive are similar to those in the first lab. | ||
Line 51: | Line 53: | ||
- Setup the simulator as shown in this picture: | - Setup the simulator as shown in this picture: | ||
{{: | {{: | ||
- | | + | - If there is a second role called "Random" |
- | - Run the " | + | - Run the " |
- | | + | |
- Now push the " | - Now push the " | ||
- If the output of the simulator contains any line starting with " | - If the output of the simulator contains any line starting with " | ||
Line 62: | Line 63: | ||
For implementing your agent: | For implementing your agent: | ||
* Add a new class that implements the " | * Add a new class that implements the " | ||
- | * You have to implement the methods " | + | * You have to implement the methods " |
+ | * Implement a class " | ||
+ | * Distinguish between nodes of the search tree and states! Each node has an associated state, but there may be several nodes that have the same state associated. In addition to a state, a node contains a reference to is parent (unless it is the root node), the move that was taken to get to the node and (if necessary) the path cost associated for getting from the root node to the node. | ||
+ | |||
+ | For developing an admissible heuristics: | ||
+ | * Remember: The cost of the optimal solution of a relaxation of the problem is an admissible heuristics. How could you relax the problem, such that you instantly know the cost of the optimal solution? | ||
+ | * The maximum of two admissible heuristics is again admissible. The same holds for consistent heuristics. So, if you have two admissible heuristics you can simply take the maximum value of both and you will get an admissible heuristics that is at least as good. | ||
+ | |||
+ | ===== Handing In ===== | ||
+ | Please hand in a zip file containing: | ||
+ | * a short description of your heuristic and an explanation why it is admissible | ||
+ | * the results of the experiments and which conclusions you draw from them | ||
+ | * the source code and an executable jar file for your agent | ||
+ | To create the zip file you just edit the " | ||
+ | The deadline is Tuesday, 14.02.2012. You can still hand in after the deadline, but your grade will be lowered by 0.5 for each day your submission is late. |
/var/www/cadia.ru.is/wiki/data/attic/public/t-622-arti-12-1/prog1.1327597921.txt.gz · Last modified: 2024/04/29 13:32 (external edit)