Find a good plan for the vacuum cleaner agent. The Environment is still the same as in the first lab: It is a rectangular grid of cells each of which may contain dirt or an obstacle. The agent is located in this grid and facing in one of the four directions: north, south, east or west. The agent can execute the following actions:

• TURN_ON: This action initialises the robot and has to be executed first.
• TURN_RIGHT, TURN_LEFT: lets the robot rotate 90° clockwise/counter-clockwise
• GO: lets the agent attempt to move to the next cell in the direction it is currently facing.
• SUCK: suck the dirt in the current cell
• TURN_OFF: turns the robot off. Once turned off, it can only be turned on again after emptying the dust-container manually.

However, the agent now has complete information about the environment. That is, the agent knows where it is initially, how big the environment is, where the obstacles are and which cells are dirty. The goal is to clean all cells, return to the initial location and turn off the robot.

Your actions have the following costs: * 5 for sucking at a cell which is already clean * -15 for cleaning a cell * 25 for turning the agent off in a position different from the home location * 1 for all other actions

1. Develop a model of the environment. What constitutes a state of the environment? What is a successor state resulting of executing an action in a certain state? Which action is legal under which conditions? Maybe you can abstract from certain aspects of the environment to make the state space smaller.
2. Implement the model:
   • Create a data structures for states.
   • 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.
3. Assess the following blind search algorithms wrt. their completeness, optimality, space and time complexity in the given environment:
   • Depth-First Search,
   • Breadth-First Search, and
   • Uniform-Cost Search

If one of the algorithms is not complete, how could you fix it?

1. 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
   • the maximum size of the frontier
   • quality (cost) of the solution

To make it a bit easier you can use the following assumptions:

• 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.
• 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.

• java project for the agent development
• some environment descriptions (one fixed and two with a random initial location)

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 zip file also contains the description of an example environment (vacuumcleaner.gdl) a simulator (gamecontroller-gui.jar). To test your agent:

1. Start the simulator (execute gamecontroller-gui.jar with either double-click or using the command “java -jar gamecontroller-gui.jar” on the command line).
2. Setup the simulator as shown in this picture:

1. 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 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.

1. 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.

You can see 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.

For implementing your agent:

• 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.
• Before you start programming a complicated strategy, think about it. The things your agent has to do are:
  1. execute TURN_ON
  2. visit every cell and suck up any dirt it finds on the way
  3. return to the initial location
  4. TURN_OFF
• 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.

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.