• Exercise 6.1.

  Consider the planning domain in Figure 6.1.

  • (a)

    Give the STRIPS representations for the pick up mail ($pum$) and deliver mail ($dm$) actions.

  • (b)

    Give the feature-based representation of the $MW$ and $RHM$ features.

Change the representation of the delivery robot world of Example 6.1 so that the robot cannot carry both $mail$ and $coffee$ at the same time. Test it on an example that gives a different solution than the original representation.

Suppose the robot cannot carry both $mail$ and $coffee$ at the same time, but the robot can carry a box in which it can place objects (so it can carry the box and the box can hold the mail and the coffee). Suppose boxes can be picked up and dropped off at any location. Give the STRIPS representation for the resulting problem and test it on the problem of starting from the lab with mail waiting; the robot must deliver coffee and the mail to Sam’s office.

This exercise involves designing a heuristic function that is better than the heuristic of Example 6.10.

• (a)

  For each of the forward and regression planners, test how effective each of the individual parts of the heuristic for Example 6.10 is, as well as the maximum. Explain why the results you observed occurred.

• (b)

  Give an admissible heuristic function for the forward planner that expands fewer nodes than the forward planner does with that heuristic.

• (c)

  Give an admissible heuristic function for the regression planner that expands fewer nodes than the regression planner does with that heuristic.

AIPython (aipython.org) has an an implementation of the heuristic that can be modified.

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 extra-dusty – and the living room – which is not extra-dusty. Assume the following features:

• –

  $Lr\mathrm{\_}dusty$ is true when the living room is dusty.

• –

  $Gar\mathrm{\_}dusty$ is true when the garage is dusty.

• –

  $Lr\mathrm{\_}dirty\mathrm{\_}floor$ is true when the living room floor is dirty.

• –

  $Gar\mathrm{\_}dirty\mathrm{\_}floor$ is true when the garage floor is dirty.

• –

  $Dustcloth\mathrm{\_}clean$ is true when the dust cloth is clean.

• –

  $Rob\mathrm{\_}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\mathrm{\_}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?

Given a STRIPS representation for actions $a_1$ and $a_2$, define the STRIPS representation for the composite action $a_1;a_2$, which means that the agent does $a_1$ then does $a_2$.

• (a)

  What are the effects for this composite action?

• (b)

  When is the composite action impossible? (That is, when is it impossible for $a_2$ to be immediately after $a_1$?)

• (c)

  Assuming the action is not impossible, what are the preconditions for this composite action?

• (d)

  Using the delivery robot domain of Example 6.1, give the STRIPS representation for the composite action $puc;mc$.

• (e)

  Give the STRIPS representation for the composite action $puc;mc;dc$ made up of three primitive actions.

• (f)

  Give the STRIPS representation for the composite action $mcc;puc;mc;dc$ made up of four primitive actions.

In a forward planner, a state can be represented in terms of the sequence of actions that lead to that state.

• (a)

  Explain how to check whether the precondition of an action is satisfied, given such a representation.

• (b)

  Explain how to do cycle pruning in such a representation. You can assume that all of the states are legal. (Some other program has ensured that the preconditions hold.)

[Hint: Consider the composite action (Exercise 6.6) consisting of the first $k$ or the last $k$ actions at any stage.]

For the delivery robot domain, give a non-trivial admissible heuristic function for the regression planner. A non-trivial heuristic function is non-zero for some nodes, and always non-negative. Does it satisfy the monotone restriction?

Explain how multiple-path pruning can be incorporated into a regression planner. When can a node be pruned? See the discussion earlier.

Give a condition for the CSP planner that, when arc consistency with search fails at some horizon, implies there can be no solutions for any longer horizon. [Hint: Think about a very long horizon where the forward search and the backward search do not influence each other.] Implement it.

To implement the function used in the partial-order planner, you have to choose a representation for a partial ordering. Implement the following as different representations for a partial ordering:

• (a)

  Represent a partial ordering as a set of less-than relations that entail the ordering – for example, as the list .

• (b)

  Represent a partial ordering as the set of all the less-than relations entailed by the ordering – for example, as the list .

• (c)

  Represent a partial ordering as a set of pairs , where $E$ is an element in the partial ordering and $L$ is the list of all elements that are after $E$ in the partial ordering. For every $E$, there exists a unique term of the form . An example of such a representation is , , , , .

For each of these representations, how big can the partial ordering be? How easy is it to check for consistency of a new ordering? How easy is it to add a new less-than ordering constraint? Which do you think would be the most efficient representation? Can you think of a better representation?