Consider the planning domain in Figure 6.1.

1. (a)

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

2. (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 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 than is better than the heuristic of Example 6.10.

1. (a)

   For each of the forward and regression planners, test how efective 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.

2. (b)

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

3. (c)

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

An implementation of the heuristic can be found in stripsHeuristic.py in http://artint.info/AIPython/aipython.zip

Suppose we 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.

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

2. (b)

   Give the feature-based representation for $lr\mathrm{\_}dusty$

3. (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 you do not have to show the states). Show explicitly what nodes are pruned through multiple-path pruning.

4. (d)

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

5. (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 you do not have to show what the nodes represent.

6. (f)

   Pick two of the nodes at the second level (after two actions) and show what the subgoal is at those nodes.

7. (g)

   Draw the CSP for a planning horizon of two. Describe each constraint in English by specifying which values are (in)consistent.

8. (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?

Suppose you have a STRIPS representation for actions $a_1$ and $a_2$, and you want to define the STRIPS representation for the composite action $a_1;a_2$, which means that you do $a_1$ then do $a_2$.

1. (a)

   What are the effects for this composite action?

2. (b)

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

3. (c)

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

4. (d)

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

5. (e)

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

6. (f)

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

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

1. (a)

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

2. (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) consisting of the first $k$ or the last $k$ actions at any stage.]

Explain how the regression planner can be extended to include maintenance goals, for the STRIPS representation. Assume a maintenance goal is a disjunction of assignments of values to variables.

For the delivery robot domain, give a nontrivial admissible heuristic function for the regression planner. A nontrivial heuristic function is nonzero for some nodes, and always nonnegative. 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 discusion 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.

1. (a)

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

2. (b)

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

3. (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?

The selection algorithm used in the partial-order planner is not very sophisticated. It may be sensible to order the selected subgoals. For example, in the robot world, the robot should try to achieve a $carrying$ subgoal before an $at$ subgoal because it may be sensible for the robot to try to carry an object as soon as it knows that it should carry it. However, the robot does not necessarily want to move to a particular place unless it is carrying everything it is required to carry. Implement a selection algorithm that incorporates such a heuristic. Does this selection heuristic actually work better than selecting, say, the last added subgoal? Can you think of a general selection algorithm that does not require each pair of subgoals to be ordered by the knowledge engineer?

The SNLP algorithm is the same as the partial-order planner presented here but, in the $protect$ procedure, the condition is

This enforces systematicity, which means that for every linear plan there is a unique partial-ordered plan. Explain why systematicity may or may not be a good thing (e.g., discuss how it changes the branching factor or reduces the search space). Test the different algorithms on different examples.