Suppose you must solve planning problems for cleaning a house.

Various rooms can be dusted (making the room dust-free) or swept (making the room have a clean floor), but the robot can only sweep or dust a room if it is in that room. Sweeping causes a room to become dusty (i.e., not dust-free). The robot can only dust a room if the dustcloth is clean; but dusting rooms that are extra-dusty, like the garage, cause the dustcloth to become dirty. The robot can move directly from any room to any other room.

Assume there are only two rooms, the garage – which, if it is dusty, is extradusty – and the living room – which is not extra-dusty. Assume the following features:

• Lr dusty is true when the living room is dusty.

• Gar dusty is true when the garage is dusty.

• Lr dirty floor is true when the living room floor is dirty.

• Gar dirty floor is true when the garage floor is dirty.

• Dustcloth clean is true when the dust cloth is clean.

• Rob loc is the location of the robot, with values {garage, lr}.

Suppose the robot can do one of the following actions at any time:

• move: move to the other room

• dust: dust the room the robot is in, as long as the room is dusty and the dustcloth is clean

• sweep: sweep the floor the robot is in.

(a) Give the STRIPS representation for dust. [Hint: Because STRIPS cannot represent conditional effects, you may need to use two separate actions that depend on the robot’s location.]

(b) Give the feature-based representation for lr dusty.

(c) Suppose that the initial state is that the robot is in the garage, both rooms are dusty but have clean floors and the goal is to have both rooms not dusty.

Draw the first two levels (with two actions, so the root has children and grandchildren) of a forward planner with multiple-path pruning, showing the actions (but do not give the state descriptions). Show explicitly what nodes are pruned through multiple-path pruning.

(d) Pick two of the states at the second level (after two actions) and show what is true in those states.

(e) Suppose that the initial state is that the robot is in the garage, both rooms are dusty but have clean floors, and the goal is to have both rooms not dusty.
Draw the first two levels (with two actions, so the root has children and grandchildren) of a regression planner, showing the actions but do not show what the nodes represent.

(f) Pick two of the nodes at the second level (after two actions) and show what the subgoal is at those nodes.
(g) Draw the CSP for a planning horizon of two. Describe each constraint in English by specifying which values are (in)consistent.
(h) In designing the actions, the above description made one choice of what to include as preconditions of the actions. Consider the choices of whether to have the room is dusty as a precondition for cleaning the room, and whether to have the floor is dirty as a precondition for sweeping. Do these choices make a difference to (i) the shortest plan, (ii) the size of the search space for a forward planner, or (iii) the size of the search space for a regression planner?