Devise a plan for a robot to clean a kitchen. Consider the following:
Write a set of STRIPS-style operator that might be used. When you describe the operators, take into consideration the information listed above (1-6). For each operator include the associated description (preconditions, delete list, add list).
The term "stove" is ambiguous. In general, a stove consists of two parts: a range and an oven. For the purposes of these sentences, since oven is anything that is taken to be true for a stove is also taken to be true for the range or oven.
Stove(x) ∧ Condition(x) ⇒
(Range(x) ∨ Oven(x)) ∧
Condition(x)
Planning in predicates are designed to be optional. It isn't possible to break the specification of actions across various predicates. For example, it would be convenient to do:
Cleaning the stove or the refrigerator causes the floor to get dirty.
Action(Clean(d)
Precond:
(Stove(d) ∨ Refrigerator(d))
∧ IsDirty(d)
Effect: IsClean(d)
∧ ¬IsDirty(d))
Cleaning the refrigerator creates garbage and messes up the counters.
Action(Clean(d)
Precond: Refrigerator(d)
∧ Garbage(g) ∧ Counter(c)
Effect: IsClean(d) ∧
¬IsEmpty(g) ∧ IsDirty(c))
A system could theoretically combine and apply all applicable preconditions and effects, but that is beyond the expected complexity of a STRIPS planner. Another solution is to insert interim goals between IsDirty and IsClean to capture the different prerequisites. This would create an arbitrary ordering of requisites and effects which shouldn't preclude any otherwise achievable goals, but which would complicate the logistical structure.
Another option is, rather than convert each sentence into a single predicate, first preprocess all of them to properly collect the prerequisites and effects for the cleaning of each element.
For all elements it is assumed that IsDirty is a cleaning prerequisite and (IsClean ∧ ¬IsDirty) as an effect.
| Phrase | Kitchen Object | Cleaning Prerequisites | Cleaning Effects |
|---|---|---|---|
| Cleaning the stove or the refrigerator causes the floor to get dirty. (This is split across the range and oven since it holds true for both.) | Stove(d) ∨ Refrigerator(d) |
Floor(f) |
IsDirty(f) |
Oven(d) ∨ Range(d) ∨
Refrigerator(d)
|
Floor(f) |
IsDirty(f) |
|
| To clean the oven, it is necessary to lock the oven shut and then set the dial to "clean." | Oven(d) |
IsLocked(d) ∧ Setting(d, 'clean') |
|
| Cleaning the refrigerator creates garbage and messes up the counters. | Refrigerator(r) |
Garbage(g) ∧ Counter(c) |
¬IsEmpty(g) ∧ IsDirty(c) |
| Washing the counters or the floor gets the sink dirty. | Counter(d) ∨ Floor(d) |
Sink(s) |
IsDirty(s) |
| Before the floor can be washed, it must be swept. (Washing is used as synonymous with cleaning for this situation.) | Floor(f) |
IsSwept(f) |
|
| Cleaning any previously unlisted objects doesn't dirty anything else. (Added for completeness.) | Sink(d) |
The first step in condensing this table is to duplicate rows with ∨ed objects
| Kitchen Object | Cleaning Prerequisites | Cleaning Effects |
|---|---|---|
Refrigerator(d) |
Floor(f) |
IsDirty(f) |
Oven(d) |
Floor(f) |
IsDirty(f) |
Range(d) |
Floor(f) |
IsDirty(f) |
Oven(d) |
IsLocked(d) ∧ Setting(d, 'clean') |
|
Refrigerator(r) |
Garbage(g) ∧ Counter(c) |
¬IsEmpty(g) ∧ IsDirty(c) |
Counter(d) |
Sink(s) |
IsDirty(s) |
Floor(d) |
Sink(s) |
IsDirty(s) |
Floor(f) |
IsSwept(f) |
|
Sink(d) |
Next, rows with the same object are combined by ∧ing their prerequisites and effects:
| Kitchen Object | Cleaning Prerequisites | Cleaning Effects |
|---|---|---|
Refrigerator(d) |
Floor(f) ∧ Garbage(g)
∧ Counter(c)
|
IsDirty(f) ∧ ¬IsEmpty(g)
∧ IsDirty(c)
|
Range(d) |
Floor(f) |
IsDirty(f) |
Oven(d) |
Floor(f) ∧ IsLocked(d) ∧
Setting(d, 'clean')
|
IsDirty(f) |
Counter(d) |
Sink(s) |
IsDirty(s) |
Floor(d) |
Sink(s) ∧ IsSwept(d) |
IsDirty(s) |
Sink(d) |
Each row in that table can be used to produce a Clean action by ∧ing the required object with the other prerequisites, and adding in the omitted IsDirty prerequisite and (IsClean ∧ ¬IsDirty) effects. For example, the first one is:
Action(Clean(d)
Precond: Refrigerator(d) ∧ IsDirty(d)
∧ Floor(f) ∧ Garbage(g)
∧ Counter(c)
Effect: IsDirty(f) ∧
¬IsEmpty(g) ∧ IsDirty(c)
∧ IsClean(d) ∧ ¬IsDirty(d))
The mapping to actions is straightforward enough that the listings for other objects is omitted. In addition to the Clean predicates, a few additional predicates are needed to provide for creating necessary states of the world:
Before the floor can be swept, the garbage must be taken out. (This is the original statement, however the actual meaning of the sentence is: "Before the floor can be swept, the garbage must be empty." It would not make sense to take out an empty garbage can.)
Action(Sweep(f)
Precond: Floor(f)
∧ Garbage(g) ∧ IsEmpty(g)
Effect: IsSwept(f))The garbage is emptied by taking it out.
Action(TakeOut(g)
Precond: Garbage(g)
∧ ¬IsEmpty(g)
Effect: IsEmpty(g))Locking the oven is an atomic action.
Action(Lock(o)
Precond: Oven(o)Effect: IsLocked(o))Setting the oven to "clean" is an atomic action.
Action(Set(o, 'clean')
Precond: Oven(o)Effect: Setting(o, 'clean'))Write a description of an initial state with a kitchen that has a dirty stove, dirty refrigerator, dirty counters and dirty floor. You can assume that the sink is clean and the garbage has been taken out. Also write a description of the goal state. The goal state should ensure that everything is clean and the garbage has been taken out.
The ambiguity of "stove" has already been discussed. For this example, saying the stove is dirty is taken to mean the oven and range are both dirty.
Initial State:
Oven('O') ∧ IsDirty('O') ∧Range('N') ∧ IsDirty('N') ∧Refrigerator('R') ∧ IsDirty('R') ∧Counter('C') ∧ IsDirty('C') ∧Floor('F') ∧ IsDirty('F') ∧Sink('S') ∧ IsClean('S') ∧Garbage('G') ∧ IsEmpty('G')Goal State:
Oven('O') ∧ IsClean('O') ∧Range('N') ∧ IsClean('N') ∧Refrigerator('R') ∧ IsClean('R') ∧Counter('C') ∧ IsClean('C') ∧Floor('F') ∧ IsClean('F') ∧Sink('S') ∧ IsClean('S') ∧Garbage('G') ∧ IsEmpty('G')Give a solution plan to the problem that a STRIPS system might produce (working forward from the initial state to the goal state). Write your solution in the tree-like representation that was used for illustrating the blocks world problem in class.
Derive a plan using a regression planning approach. Again, write your solution using the tree-like representation that we used for the blocks world problems in class.
From the lecture notes for CS360 at Vanderbilt, the algorithm for STRIPS is:
STRIPS(γ)
To increasing the readability of the tree, the following immutable identity predicates that are present in both the start and goal will be omitted from the state descriptions: Oven, Range, Refrigerator, Counter, Floor, Sink, and Garbage.
It is obvious to a human planner that in order to achieve an IsClean for the oven that the Clean action with Oven as a prerequisite must be chosen. STRIPS however only looks at one condition at a time and would not consider both IsDirty and Oven simultaneously. It will try each Clean action in turn and they would each eventually fail to bind and the algorithm will backtrack until the appropriate Clean action is chosen.
The tree structure described in class is difficult to use at times because it makes it difficult to represent the continually changing nature of the current state, S. Cleaning the counters, for example, dirties the sink. In the tree format from class the top level goal is divided into subgoals and the goal to work on is chosen only from those goals. In the description of the algorithm however, it says that the task chosen is one that exists in the goal but not the current state.
Derive the plan using the partial order planning scheme discussed in class.
Consider the problem of putting on one's shoes and socks:
Init()Goal(RightShoeOn ∧ LeftShoeOn)Action(RightShoeOn)
Precond: RightSockOnEffect: RightShoeOnAction(RightSock)
Effect: RightSockOnAction(LeftShoeOn)
Precond: LeftSockOnEffect: LeftShoeOnAction(LeftSock)
Effect: LeftSockOnApply Graphplan to this problem and show the solution obtained.
One can see that the pattern between S2 and S3, and between S3 and S4 is the same, meaning the graph has stabilized. Since there are no actions which remove a shoe or sock and it is not possible to put on a shoe or sock twice, any path through the graph that takes an action each time for four actions will arrive at a solution. So, Graphplan finds all six solutions.
Add actions for putting on a coat and a hat. Show the partial order plan that is a solution.
Show there are 180 different linearizations of the partial-order plan.
There are six positions to be filled with different actions. If they could be in any order then the number would simply be the number of permutations, n! = 6! = 720. Two of the pairs of elements however must be ordered.
Knowing that there are 180 valid permutations it means that 3/4 of the permutations are invalid, so a probable solution will reduce the number by 1/2 twice. There are two ordered sets. I'm pretty sure that if all permutations are considered then half of them will put LeftShoe before LeftSock which removes those. Of the remaining ones, half will have RightShoe before RightSock which reduces the number to the known 180 valid linearlizations.
What is the minimum number of different planning graph solutions needed to represent all 180 linearizations?
Each planning graph level, Ai, a new action is added. There are six actions to be added in total so the graph will need six levels.
We saw that planning graphs can handle only propositional actions. What if we want to use planning graphs for a problem with variables in the goal such as At(P1,x) ∧ At(P2,x), where x ranges over a finite domain of locations? How could such a problem be encoded to work with planning graphs? (Recall the Finish action from POP planning. What preconditions should it have?)
A simple solution is to flatten the variables into a set of propositional predicates with one element for each possible value of the variable. {At(Pi,Xj)} ∀ 1 ≤ i ≤ |P|; 1 ≤ j ≤ |X|.
For the example, it would create nk predicates for n Pis and |x| = k, but the growth of storage is linear (mnk for a planning graph of depth m) rather than polynomial, and so should be manageable unless m, n or k is extremely large.
A set of actions for going between each pair, Xi and Xj ∋ i ≠ j for each Pk would need to be added as well.
A consumable resource is a resource that is partially used up by an action. For example, attaching engines to cars requires screws. Once screws are used, they are not available for other attachments.
Given the following representation of a car assembly process:
Init(Chassis(C1) ∧
Chassis(C2) ∧
Engine(E1,C1,30) ∧
Engine(E2,C2,60) ∧
Wheels(W1,C1,30) ∧
Wheels(W2,C2,15) ∧
EngineHoists(1) ∧
WheelStations(1) ∧
Inspectors(2))
Goal(Done(C1) ∧
Done(C2))
Action(AddEngine(e,c))
Precond:
Engine(e,c,d) ∧
Chassis(c) ∧
¬EngineIn(c)
Effect:
EngineIn(c) ∧
Duration(d)
Resource:EngineHoists(1)
Action(AddWheels(w,c))
Precond:
Wheels(w,c,d) ∧
Chassis(c) ∧
EngineIn(c) ∧
¬WheelsOn(c)
Effect:
WheelsOn(c) ∧
Duration(d)
Resource:WheelStations(1)
Action(Inspect(c))
Precond:
EngineIn(c) ∧
WheelsOn(c)
Effect:
Done(c) ∧
Duration(10)
Resource:Inspectors(1)
Explain how to modify the following representation to contain:
The + and - function symbols may be used in effect literals for resources.
There simply needs to be an identity predicate Screws that represents the current number of screws. Screws(100) would be added to Init. The definition of Engine would be expanded to represent the number of screws required:
Engine(E1,C1,30,40)Engine(E1,C1,60,50)Action(AddEngine(e,c))
Precond:
Engine(e,c,d,s) ∧
Chassis(c) ∧ Screws(w) ∧
≥(s,w) ∧
¬EngineIn(c)
Effect:
EngineIn(c) ∧
Duration(d) ∧
¬Screws(w) ∧
Screws(w - s)
Resource:EngineHoists(1)
Explain how the definition of conflict between causal links and actions in partial-order planning must be modified to handle consumable resources.
A causal link in partial order planning asserts that a given action A provides a prerequisite, p, for another action B. An action conflicts with a causal link if it is inserted between A and B and has ¬p in its effects list. With consumable items, the effects that are protected are inequalities such as ≥(s,w). This characteristic does not become false simply by being negated, but by an action that affects the identity predicates that define the quantities s and w.
The logic for determining if a conflict has occurred would be required to examine the predicates that bound the values in the inequality and see if inserting a given action between A and B would invalidate that inequality.
Some actions — for example resupplying the factory with screws or refueling a car — can increase the availability of resources. A resources is monotonically non-increasing if no action increases it. Explain how to use this property to prune the search space.
A non-increasing property allows for removing all nodes that require a quantity of a given resource greater than the available quantity. All actions that depend on that action could be removed from consideration as well. Each time the quantity is reduced more nodes would be eliminated.
Some people say an advantage of Hierarchical Task Network (HTN) planning is that it can solve problems like "take a round trip from Los Angeles to New York and back" that are hard to express in non-HTN notations because the start and goal states would be the same (At('LA')). Can you think of a way to represent and solve this problem without HTNs?
Encoding discrete time steps into the world and allowing inequalities would be a possible solution, for example a requirements specification such as:
At('LA',i) ∧ At('NY',j) ∧ At('LA',k) ∧
<(i,j) ∧ <(j,k)
The Go action would then increment the step number:
Action(Go(f,t)
Precond: At(f,i)Effect: At(t,i + 1))The predicates then go from being a representation of the current state to being a representation of all states up to the current one.