The vacuum cleaner problem is a well$-$known agent$-$based search problem. In this problem, there

are two rooms whose shape is given in the below figure. Assume the vacuum cleaner agent is

presented in any one of these rooms. There is dirt in both the rooms and the purpose of

deploying the agent is to clean both the rooms.

Figure: Shape of Two Rooms

i$)$Formulate the given problem as a search space problem by specifying the state space graph

with the problem formulation steps. $(6$ Marks$)$

ii$)$Assume that the initial state as two rooms having dust and the goal state as two rooms clean.

Show a simple search strategy that would create a search tree to find a path from the initial state

to the goal state. $(4$ Marks$)$