| Next revision | Previous revision |
| public:t-622-arti-12-1:prog1 [2012/01/26 14:59] – created stephan | public:t-622-arti-12-1:prog1 [2024/04/29 13:33] (current) – external edit 127.0.0.1 |
|---|
| ====== Programming Assignment 1 - Search ====== | ====== Programming Assignment 1 - Search ====== |
| | |
| | **Use the [[http://ruclasses.proboards.com/index.cgi?board=arti2012&action=display&thread=104|forum]] or email me, if you have any questions or problems with the assignment. Start early, so you still have time to ask in case of problems!** |
| |
| ===== Problem Description ===== | ===== Problem Description ===== |
| |
| Your actions have the following costs: | Your actions have the following costs: |
| * 5 for sucking at a cell which is already clean | * 1 + 15*D, if you TURN_OFF the robot in the home location and there are D dirty cells left |
| * -15 for cleaning a cell | * 100 + 15*D, if you TURN_OFF the robot, but not in the home location and there are D dirty cells left |
| * 25 for turning the agent off in a position different from the home location | * 5 for SUCK, if the current location of the robot does not contain dirt |
| * 1 for all other actions | * 1 for SUCK, if the current location of the robot contains dirt |
| | * 1 for all other actions |
| |
| ===== Tasks ===== | ===== Tasks ===== |
| * 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, optimality, space and time complexity in the given environment: | - Assess the following blind search algorithms wrt. their completeness, optimality, space and time complexity in the given environment: Depth-First Search, Breadth-First Search, Uniform-Cost Search. If one of the algorithms is not complete, how could you fix it? **Note: Do this step first before you implement the algorithms, so you know what to expect when you run the algorithms. Otherwise you might be very surprised.** |
| * Depth-First Search, | |
| * Breadth-First Search, and | |
| * Uniform-Cost Search | |
| If one of the algorithms is not complete, how could you fix it? | |
| - 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 | * number of state expansions (time complexity) |
| * the maximum size of the frontier | * maximum size of the frontier (space complexity) |
| * quality (cost) of the solution | * quality (cost) of the found solution |
| | * computation time for finding a solution. |
| To make it a bit easier you can use the following assumptions: | - Think of a good (admissible) heuristic function for estimating the remaining cost given an arbitrary state of the environment. Make sure, that your heuristics is really admissible! |
| * The room is rectangular. It has only 4 straight walls that meet at right angles. There are no obstacles in the room. That is, the strategy "Go until you bump into a wall then turn right and repeat" will make the agent walk straight to a wall and then around the room along the wall. | - Implement A*-Search with an evaluation function that uses your heuristics. Run your agent with all the given environments and compare the results with those of the blind search methods. |
| * The room is fairly small, so that 100 actions are enough to visit every cell, suck all the dirt and return home given a halfway decent algorithm. | - Post the results (number of state expansions, maximum size of the frontier, cost of the found solution) [[http://ruclasses.proboards.com/index.cgi?action=display&board=arti2012&thread=104|here]]. |
| | - Try to improve your heuristics, but make sure that it does not increase the overall runtime of search algorithm. You can easily create a heuristics that tells you the optimal costs but is as expensive as a blind search. Try to avoid this. |
| |
| ===== Material ===== | ===== Material ===== |
| * {{:public:t-622-arti-12-1:vacuumcleaner.zip|java project for the agent development}} | * {{:public:t-622-arti-12-1:vacuumcleaner_utility_agent.zip|java project for the agent development}} |
| * {{:public:t-622-arti-12-1:gdls.zip|some environment descriptions (one fixed and two with a random initial location)}} | * {{:public:t-622-arti-12-1:bigger_worlds.zip|some bigger test environments}} (updated 14.02.2012, see the worlds.txt file to see how big the state spaces are) |
| |
| The file contains code for implementing an agent in the src directory. The agent is actually a server process which listens on some port and waits for the real robot or a simulator to send a message. It will then reply with the next action the robot is supposed to execute. | The files in the archive are similar to those in the first lab. |
| |
| The zip file also contains the description of an example environment (vacuumcleaner.gdl) a simulator (gamecontroller-gui.jar). To test your agent: | The first file contains code for implementing an agent in the src directory. The agent is actually a server process which listens on some port and waits for the real robot or a simulator to send a message. It will then reply with the next action the robot is supposed to execute. |
| | |
| | The zip file also contains the description of some example environments (vacuumcleaner*.gdl) and a simulator (gamecontroller-gui.jar). To test your agent: |
| - Start the simulator (execute gamecontroller-gui.jar with either double-click or using the command "java -jar gamecontroller-gui.jar" on the command line). | - Start the simulator (execute gamecontroller-gui.jar with either double-click or using the command "java -jar gamecontroller-gui.jar" on the command line). |
| - Setup the simulator as shown in this picture: | - Setup the simulator as shown in this picture: |
| {{:public:t-622-arti-12-1:gamecontroller-settings.png?nolink&|}} | {{:public:t-622-arti-12-1:gamecontroller-settings.png?nolink&|}} |
| - Run the "Main" class in the project. If you added your own agent class, make sure that it is used in the main method of Main.java. You can also execute the "ant run" on the command line, if you have [[http://ant.apache.org/|Ant]] installed. | - If there is a second role called "Random" in the game, leave it as "Random". |
| The output of the agent should say "NanoHTTPD is listening on port 4001", which indicates that your agent is ready and waiting for messages to arrive on the specified port. | - Run the "Main" class in the project. If you added your own agent class, make sure that it is used in the main method of Main.java. You can also execute the "ant run" on the command line, if you have [[http://ant.apache.org/|Ant]] installed. The output of the agent should say "NanoHTTPD is listening on port 4001", which indicates that your agent is ready and waiting for messages to arrive on the specified port. |
| - Now push the "Start" button in the simulator and your agent should get some messages and reply with the actions it wants to execute. At the end, the output of the simulator tells you how many points your agent got: "Game over! results: 0". In the given environment you will only get non-zero points if you manage to clean everything, return to the initial location, and turn off the robot within 100 steps. If the output of the simulator contains any line starting with "SEVERE", something is wrong. The two most common problems are the network connection (e.g., due to a firewall) between the simulator and the agent or the agent sending illegal moves. | - Now push the "Start" button in the simulator and your agent should get some messages and reply with the actions it wants to execute. At the end, the output of the simulator tells you how many points your agent got: "Game over! results: 0". Those points correspond more or less with negated costs. That is, more points means the solution had lower costs. |
| | - If the output of the simulator contains any line starting with "SEVERE", something is wrong. The two most common problems are the network connection (e.g., due to a firewall) between the simulator and the agent or the agent sending illegal moves. |
| |
| You can see [[http://130.208.241.192/ggpserver/public/view_state.jsp?matchID=vacuum_cleaner_1.1326993828477&stepNumber=2&role=RANDOM|here]], what the example environment looks like. Of course, you shouldn't assume any fixed size, initial location or locations of the dirt in your implementation. This is just an example environment. | Of course, you shouldn't assume any fixed size, initial location or locations of the dirt in your implementation. All this information will be given to your agent but is not fixed. |
| |
| ===== Hints ===== | ===== Hints ===== |
| For implementing your agent: | For implementing your agent: |
| * Add a new class that implements the "Agent" interface. Look at RandomAgent.java to see how this is done. | * Add a new class that implements the "Agent" interface. Look at RandomAgent.java to see how this is done. |
| * You have to implement the method "nextAction" which gets a collection of percepts as input and has to return the next action the agent is supposed to execute. | * You have to implement the methods "init" and "nextAction". "init" will be called once at the start and should be used to run the search while "nextAction" gets a collection of percepts as input (which you do not actually need here) and has to return the next action the agent is supposed to execute. So, if you found a solution in "init" you have to store it somewhere and than execute it step by step in "nextAction". |
| * Before you start programming a complicated strategy, think about it. The things your agent has to do are: | * Implement a class "State" that contains all the information about a state that you need to keep track of. The State class should have a method that returns a list of all moves that are legal in the state and a method that takes a move and returns the state that results from executing the move. |
| - execute TURN_ON | * 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. |
| - visit every cell and suck up any dirt it finds on the way | |
| - return to the initial location | For developing an admissible heuristics: |
| - TURN_OFF | * 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? |
| * For this your agent needs an internal model of the world. Figure out, what you need to remember about the current state of the world. Ideally, you create an object "State" that contains everything you need to remember and update this object depending on which action you executed and which percepts you got. Then you can implement rules that say which action should be executed depending on what properties the current state has. | * 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. |
| |
| As a last and general hint: "Days of programming can save you minutes of thinking." Think of a strategy, the rules to implement it and the information you need to decide on the actions **before** you start implementing it. | ===== 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 "student" property in the build.xml and call the "zip" target using ant (execute "ant zip" in the directory containing the build.xml). |
| |
| | 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. |
