Artificial
Intelligence

8.8 Exercises

Exercise 8.1:

Consider the planning domain in Figure 8.1.

1. Give the feature-based representation of the MW and RHM features.
2. Give the STRIPS representations for the pick up mail and deliver mail actions.

Exercise 8.2:

Suppose the robot cannot carry both coffee and mail at the same time. Give two different ways that the CSP that represents the planning problem can be changed to reflect this constraint. Test it by giving a problem where the answer is different when the robot has this limitation than when it does not.

Exercise 8.3:

Write a complete description of the limited robot delivery world, and then draw a state-space representation that includes at least two instances of each of the blocks-world actions discussed in this chapter. Notice that the number of different arcs depends on the number of instances of actions.

Exercise 8.4:

Change the representation of the delivery robot world [Example 8.1] so that

1. the agent cannot carry both mail and coffee at the same time;
2. the agent 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).

Test it on an example that gives a different solution than the original representation.

Exercise 8.5:

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 only two rooms, the garage - which, if it is dusty, it is extra-dusty - 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.

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

• move: move to the other room,
• dust_lr: dust the living room (if the robot is in the living room and the living room is dusty),
• dust_gar: dust the garage (if the robot is in the garage and the garage is dusty),
• sweep_lr: sweep the living room floor (if the robot is in the living room), or
• sweep_gar: sweep the garage floor (if the robot is in the garage).

1. Give the STRIPS representation for dust_gar.
2. Give the feature-based representation for lr_dusty
3. Suppose that, instead of the two actions sweep_lr and sweep_gar, there was just the action sweep, which means to sweep whatever room the robot is in. Explain how the previous answers can be modified to handle the new representation or why they cannot use the new representation.

Exercise 8.6:

Suggest a good heuristic for a forward planner to use in the robot delivery domain. Implement it. How well does it work?

Exercise 8.7:

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

1. What is the effects list for this composite action?
2. What are the preconditions for this composite action? You can assume that the preconditions are specified as a list of Variable=value pairs (rather than as arbitrary logical formulas).
3. Using the delivery robot domain of Example 8.1, give the STRIPS representation for the composite action puc;mc.
4. Give the STRIPS representation for the composite action puc;mc;dc made up of three primitive actions.
5. Give the STRIPS representation for the composite action mcc;puc;mc;dc made up of four primitive actions.

Exercise 8.8:

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

1. Explain how to check if the precondition of an action is satisfied, given such a representation.
2. Explain how to do cycle detection 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 8.7) consisting of the first k or the last k actions at any stage.]

Exercise 8.9:

Explain how the regression planner can be extended to include maintenance goals, for either the feature-based representation of actions or the STRIPS representation. [Hint: Consider what happens when a maintenance goal mentions a feature that does not appear in a node.]

Exercise 8.10:

For the delivery robot domain, give a heuristic function for the regression planner that is non-zero and an underestimate of the actual path cost. Is it admissible?

Exercise 8.11:

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

Exercise 8.12:

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.

Exercise 8.13:

To implement the function add_constraint(A₀<A₁,Constraints) 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. Represent a partial ordering as a set of less-than relations that entail the ordering - for example, as the list [1<2,2<4,1<3,3<4,4<5].
2. Represent a partial ordering as the set of all the less-than relations entailed by the ordering - for example, as the list [1<2,2<4,1<4,1<3,3<4,1<5,2<5,3<5,4<5].
3. Represent a partial ordering as a set of pairs ⟨E,L⟩, 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 ⟨E,L⟩. An example of such a representation is [⟨1,[2,3,4,5]⟩, ⟨2,[4,5]⟩, ⟨3,[4,5]⟩, ⟨4,[5]⟩, ⟨5,[])⟩.

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?

Exercise 8.14:

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?

Exercise 8.15:

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

A ≠A₀  and  A ≠A₁  and (A  deletes  G  or  A  achieves  G ).

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.