1. Consider the vacuum-cleaning problem outlined below:

Here we have a vacuum-cleaning agent that can sense the environment and perform actions to move around and vacuum-clean dirty squares.

We make the following assumptions:

We assume a 3 by 3 grid world known to the agent. The environment is fully observable: the percepts give complete information about the Dirty/Clean status of every square and the agents location.

The environment is deterministic: A clean square remains clean and a dirty square remains dirty unless the agent cleans it up.

The actions available for the agent are: Left, Right, Up, Down, Suck. Each action takes place in one time "step".

The actions and percepts are perfectly reliable.

Each of the actions will incur a penalty of -1 point.

The agent will get a penalty of -2 points per dirty square per time step,

The agents performance is measured by the sum of negative points received on reaching a state with all squares in the environment being "Clean". As usual, a rational agent should maximize its performance score.

(a) Define the vacuum-cleaning problem as a state-space search problem. Specify the states, actions, the transition model, and the goal state(s). The initial state could be any of the states in the state space.

You should also specify a cost function COST (n, a, n) > 0, which defines the cost of one step transition from node n to node n by applying action a, such that the cost of a path in the search tree should be exactly the absolute value of the sum of penalty points due to dirty square(s) and moves.

(Hint: COST (n, a, n) should be related to w, the number of dirty squares at the state s for node n, and related to the fact whether the action a is "Suck", and the current square is dirty or not).

(b) Which of the algorithms would be appropriate for this problem? Should the algorithm use tree search or graph search?

(c) You are asked to define an admissible (hopefully also consistent) heuristic function h to be used with the A* algorithm for solving the problem of searching for an optimal sequence of moves that maximize the agents performance score.

(Hint: your h(n) should be related to w, the number of dirty squares at the state for node n, namely hdominates h_2.

(d) Show the first level of search tree starting from the initial state in which the top 3 squares, and the 3 right-most squares are dirty, and the agent is at the left bottom corner square. The frontier nodes at the first level should consist of three nodes, one is obtained from the initial state (root node) by the action Up, one is obtained by the action Right , and one is obtained by the action Suck. Write the actions as well as the edge cost along each edge from the root node to a frontier node. Then write down below each frontier node n: g(g), h(n) and h₂(n).