COSC1127/1125 Artificial Intelligence
School of Computing Technologies Semester 2, 2021
Prof. ̃a
Tutorial No. 6 Automated Planning
PART1: Conceptual……………………………………………………………………… Explain informally but clearly and precisely.
(a) Closed world assumption.
(b) The frame problem. Provide two examples.
(c) The three components an action using the STRIPS language? Explain, in your own words, each each of the components are meant to define and capture. Give an example of a STRIPSaction.
(d) At least 2 limitations of STRIPS language to represent actions.
Solution: Cannot represent stochastic actions, or actions that have conditional effect.
(e) The differences and similarities between problem solving/search and planning.
(f) What is the difference between path/motion planning and automated planning.
(g) Explain what GraphPlan is and what is it used for.
Solution: The assumption that when a proposition cannot be proven true, it is taken as false (like in a relational database: if the tuple is not in the table, it is not true).
Solution:
The challenge of representing the effects of action in logic without having to represent explicitly a large number of intuitively obvious non-effects. See this entry in Stanford Encyclopedia of Philosophy.
Solution: A STRIPS action is built from three lists: precondition, add, and delete lists. Example here
Solution:
Both are concerned with getting from a start state to a goal using a set of defined operations or actions. In planning, however, we use a structured language to represent states, goals, and plans, which allows for generic solver algorithms that among other things can automatically extract heuristic functions. In search, we need to hard-code the heuristic function depending on which particular problem we are solv- ing.
Solution: Path planning is a domain dependent task: it is known what the problem is, namely, navi- gating from source to destination in a network (of roads, for example). Automated planning implies not knowing what the problem is, it could be a motion planning task or playing tic-tac-toe, or a robot collecting and delivering mail in a building.
1
COSC1127/1125 – AI Tutorial 6: Automated Planning Page 2 of 8
Solution: Graphplan is a technique to do planning by constructing a layered graph and is also used to obtain, automatically, domain-independent heuristics from a domain problem specification given in a certain factored representation (like STRIPS or PDDL).
PART2: BlocksWorld……………………………………………………………………. Consider the following blocks world scenario:
Suppose we use the following fluents (predicates in logic) to represent a states:
• OnT able(x): block x is on the table.
• On(x, y): block x is on top of block y.
• Clear(x): there is nothing on top of block x. • Gripping(x): the gripper is holding block x. • Empty: the gripper is not holding anything.
(a) Specify the initial state in logical representation, that is, using conjunction of atoms and relying on the close world assumption.
(b) WritetheSTRIPSrepresentationforoperatorspickup(x),putdown(x),stack(x,y),andunstack(x,y). Should a block be made clear stacking or putting it down?
Solution: (Note: this is a partial solution)
The initial state of the blocks world above may be represented by the following set of predicates:
OnT able(a) ∧ OnT able(c) ∧ …. ∧ On(b, a) ∧ On(e, d) ∧ Clear(b) ∧ Clear(c) ∧ Clear(e) ∧ ….
Solution: (Note: this is a partial solution)
pickup(x): Precondition:
Add List: Delete List:
Empty, Clear(x), OnT able(x) Gripping(x)
OnT able(x), Clear(x), Empty
RMITAI2021(Semester2)-SebastianSardin ̃a Exercise2continuesonthenextpage…
COSC1127/1125 – AI Tutorial 6: Automated Planning Page 3 of 8
putdown(x): Precondition:
Add List:
Delete List: stack(x, y):
Precondition: Add List: Delete List:
unstack(x, y): Precondition:
Add List:
Delete List:
Clear(x) implies that the block is clear to be stacked on; and one cannot stack something on top of something that is in the gripper. More importantly, unless equality constraints are used explicitly in the PDDL description, it could lead to an action that stack a block onto itself! Why? Consider a state such that Ontable(a) ∧ Clear(a) ∧ Gripping(b) ∧ Clear(b).
Gripping(x)
OnT able(x), Empty, Clear(x) Gripping(x)
Clear(y), Gripping(x) ….
Clear(y), Gripping(x)
Clear(x), Empty, On(x, y) ….
….
(c) What is the new state if we apply operator-action unstack(e, d) to the initial state. Solution:
OnT able(a)∧OnT able(c)∧OnT able(d)∧On(b, a)∧Gripping(e)∧Clear(b)∧Clear(c)∧Clear(d) (d) Explain in English what frame axioms would be required in this domain. Explain how those frame axioms
were respected in the question before when unstack(e, d) was executed.
Solution: In the above, we can see as a result of applying the new operator, new predicates have been added to the new state, whereas other predicates such as On(e, d) ∧ Empty have been deleted from the new state because they are no longer valid.
You will notice that predicates such as OnTable(a) ∧ OnTable(c) ∧ OnTable(d) continue to remain true in the new state, thus respecting the frame axioms one would have to model the domain.
Frame axioms encode the knowledge that the things that remain the same when not affected by an action. While this comes as common sense knowledge for humans, a formal model for automatic reasoning (as computers need) require that this knowledge is encoded.
The semantics of planning languages like STRIPS and PDDL already have built-in the frame axioms: if a predicate is not affected by an operator, then its truth value remains the same.
(e) Use the operators (and the implicit frame axioms) of the previous question to complete (by filling ?????) part of the search state space of the blocks world given in the figure above. The root of the tree should be the logical initial state representation and edges should represent application of ground operators.
RMITAI2021(Semester2)-SebastianSardin ̃a Exercise2continuesonthenextpage…
COSC1127/1125 – AI
Tutorial 6: Automated Planning
Page 4 of 8
OnT able(a), OnT able(c), OnT able(d), On(b, a), Gripping(e), Clear(b), Clear(c), Clear(d)
··· ···
?????????????
OnT able(a), OnT able(c), OnT able(d), On(b, a), On(e, d), Empty, Clear(b), Clear(c), Clear(e)
?????????????
?????????????
?????????????
··· ···
?????????????
Solution: (Note: this is a partial solution)
OnT able(a), OnT able(c), OnT able(d), On(b, a), Gripping(e), Clear(b), Clear(c), Clear(d)
··· ···
OnT able(a), OnT able(c), OnT able(d), On(e, d), On(b, c), Empty, Clear(b), Clear(e), Clear(a)
OnT able(a), OnT able(c), OnT able(d), On(b, a), On(e, d), Empty, Clear(b), Clear(c), Clear(e)
OnT able(a), OnT able(c), OnT able(d), On(e, d), Gripping(b), Clear(c), Clear(e), Clear(a)
….
….
··· ···
OnT able(a), OnT able(c),
OnT able(d), OnT able(b), On(e, d), Empty, Clear(b), Clear(c), Clear(e), Clear(a)
(f) Show an optimal plan that solves this problem: e
Initial state: a c m bdh
e Goal: d c ab
RMITAI2021(Semester2)-SebastianSardin ̃a Exercise2continuesonthenextpage…
pickup(c)
putdown(b)
pickup(c)
putdown(b)
stack(b, c)
unstack(e, d)
stack(b, c)
unstack(e, d)
unstack(b, a) stack(b, e)
unstack(b, a) stack(b, e)
COSC1127/1125 – AI Tutorial 6: Automated Planning Page 5 of 8
Solution:
There are multiple optimal solutions, here is one:
unstack(a, b), putdown(a), unstack(e, c), putdown(e), unstack(c, d), stack(c, b), pickup(e), stack(e, c), pickup(d), stack(d, a)
If you have not come up with one yourself and just read ours, now get one by yourself.
(g) How many solutions are there for the above question? How many optimal solutions?
(h) Is the goal state correctly defined? Explain either way.
(i) What would GraphPlan give as heuristic value for the initial state? To find out, build the planning graph starting from the initial state. Is the value of the heuristic less, equal, or greater than the true length of the plan you found in the previous question? Explain why.
Solution:
There are infinitely many solutions, as you can start by stacking and unstacking the same block repeat- edly before proceeding. There are only 8 optimal solutions (the first and last pairs of actions can be swapped independently, and for each of those 4 solutions, we can stack and unstack e with m instead of putting it on the table temporarily).
Solution: Yes, a goal is not a full state, it is a condition that any state should satisfy. Hence, in this condition it does not matter where blocks m and h end up being.
Said so, one could argue whether the goal picture specify whether blocks d and e should be clear or not. If block m ends up on top of block e, is it a goal state?
Solution:
Please check this video that explains this solution in more detail.
The optimal plan has 10 actions, but GraphPlan should give you a lower heuristic value because, among other things, it will be able to hold many blocks at the same time, put them on the table all at the same time, and the original sub-tower On(e, c) will always stay true!
We construct a GraphPlan graph by iteratively alternating proposition layers (Pi) and action layers (Ai). Starting with the set of initial propositions in P1, the graph can be constructed by the following rules:
• an action is in Ai iff all of its preconditions are in Pi; and,
• a proposition is in Pi+1 iff it is in the add list for an action in Ai (except for P1).
Here is the graph representing the GraphPlan algorithm process for the this blocksworld problem (to save space we will ignore blocks m and h, as they are not useful in this instance):
RMITAI2021(Semester2)-SebastianSardin ̃a Exercise2continuesonthenextpage…
COSC1127/1125 – AI Tutorial 6: Automated Planning Page 6 of 8
P1 P2 P3 P4 P5 A1 A2 A3 A4
Ontable(b) Ontable(d) On(a, b) On(c, d) On(e, c) Clear(e) Clear(a) E mpty
Ontable(b) Ontable(d) On(a, b) On(c, d) On(e, c) Clear(e) Clear(a) E mpty
Ontable(b) Ontable(d) On(a, b) On(c, d) On(e, c) Clear(e) Clear(a) E mpty Gripping(a) Clear(b) Gripping(e) Clear(c) Gripping(c) Clear(d) Gripping(b) Ontable(a) Ontable(e) On(a, c) On(a, e) On(e, b) On(e, a) Ontable(c) On(c, a) On(c, b) On(b, a) On(b, c) On(b, d) Gripping(d) On(d, a) On(d, b) On(d, c) On(d, e)
unstack(a, b) unstack(e, c)
unstack(a, b)
unstack(e, c)
unstack(c, d)
pickup(b)
putdown(a)
putdown(e)
stack(a, c)
stack(a, e)
unstack(a, b) unstack(e, c) unstack(c, d) pickup(b) putdown(a) putdown(e) stack(a, c) stack(a, e) stack(e, b) stack(e, a) putdown(c) stack(c, a) stack(c, b) stack(b, a) stack(b, c) stack(b, d) pickup(d)
Ontable(b) Ontable(d) On(a, b) On(c, d) On(e, c) Clear(e) Clear(a) E mpty
unstack(a, b) unstack(e, c) unstack(c, d) pickup(b) putdown(a) putdown(e) stack(a, c) stack(a, e) stack(e, b) stack(e, a) putdown(c) stack(c, a) stack(c, b) stack(b, a) stack(b, c) stack(b, d) pickup(d) stack(d, a) stack(d, b) stack(d, c) stack(d, e)
Ontable(b)
Ontable(d)
On(a, b)
On(c, d)
On(e, c)
Clear(e)
Clear(a)
E mpty
Gripping(a) Gripping(a) Gripping(a)
Clear(b)
Clear(b)
Clear(b)
stack(e, b)
stack(e, a)
Gripping(e) Gripping(e) Gripping(e)
Clear(c) Clear(c) Gripping(c)
Clear(d) Gripping(b) Ontable(a) Ontable(e) On(a, c) On(a, e) On(e, b) On(e, a)
Clear(c) Gripping(c) Clear(d) Gripping(b) Ontable(a) Ontable(e) On(a, c) On(a, e) On(e, b) On(e, a) Ontable(c) On(c, a) On(c, b) On(b, a) On(b, c) On(b, d) Gripping(d)
Now, as the goal is Ontable(a) ∧ Ontable(b) ∧ On(d, a) ∧ On(c, b) ∧ On(e, c) ∧ Clear(d) ∧ Clear(e), and all of those propositions are in layer P5 (indicated with black arrows), we can say the heuristic lower bound for the plan is 4.
Some actions, such as those that undo previous actions (e.g., unstack(x, y) → stack(y, x)) have been omitted to save space. You may have noticed that the number of propositions and actions monotonically increases with each layer. For very large planning problems, this can quickly blow up, beyond control (especially when doing it by hand!). Therefore, we can add an additional set of exclusion relations that are maintained throughout the process, which help to eliminate incompatible propositions and actions, hence reducing the graph size — but this is beyond the scope of this course.
RMITAI2021(Semester2)-SebastianSardin ̃a Exercise2continuesonthenextpage…
COSC1127/1125 – AI Tutorial 6: Automated Planning Page 7 of 8
(j) Suppose that each block has a new property of colour. All the rest of the domain remains the same. What would you change to your representation and corresponding STRIPS modeling?
(k) Suppose you want to represent the action of dropping an object. Its effect is that the object is on the floor and depending on whether it is fragile or not, it may or may not be broken. Can you represent such action in STRIPS representation? Either provide the representation or explain why not. Can you think of a way that you could work around this limitation by defining multiple actions?
Solution: Nothing. The new property of colour is not required for any preconditions of the operators. So it is irrelevant for the problem at hand and does not need to be taken into account.
Solution: It is not possible to represent such operator in STRIPS because it requires the ability to repre- sent so-called conditional effects, that is, effects that depend on the context of where the action is applied (in our case, whether the object is fragile or not, which is represented by predicate F ragile(x))
It is however possible to represent it in PDDL as PDDL supports conditional effects using the construct (when (condition effect))asfollows:
(:action drop
:parameters (?x)
:precondition (and (Holding ?x))
:effect (and (OnFloor(?x) (when (Fragile ?x) (Broken ?x)) )
If one wants to stick to STRIPS representations, the workaround is to use two actions dropF ragile(x) and dropNotFragile(x), then we could have preconditions on the fragility (or lack thereof) of the object x being dropped, so the effect is no longer conditional.
PART3: TimetocodeinPDDL!…………………………………………………………… In this question, you will code a problem in PDDL and let the automated planning system find the solution for you! To do so, you will use the planning.domain’s editor, where you can code your domain and a specific problem and use an online solver to get the plan (if any exists!).
Check the video that I did here to show you how to use planning.domain’s editor and its animation facility!
For PDDL, besides the book, you may want to check the PDDL quick tutorial notes here and here. Another useful material is this PDDL by Example pack of slides. Finally a nice web-based PDDL reference can be found here.
(a) First model the Blocks World domain we have seen above. Take the template file domain.pddl encoding the domain in PDDL and fill the gaps in the editor. You can just drag and drop the file and it will load it. Remember that the domain file only contains the fluents and operators. It is meant to be usable with any specific problem instance.
Solution: Here is the start of the domain file: (define (domain BLOCKS-AI20) (:requirements :strips) (:predicates (on ?x ?y)
(ontable ?x)
(clear ?x)
(empty)
(gripping ?x)
)
There is now very little to be filled…
RMITAI2021(Semester2)-SebastianSardin ̃a Exercise3continuesonthenextpage…
COSC1127/1125 – AI Tutorial 6: Automated Planning Page 8 of 8
(b) Next, encode the specific problem we saw above by completing the following template problem.pddl file. A problem file specifies what domain the problem is based on, the actual objects in the problem (in our case, what blocks there are), the initial state, and the condition for a state to be considered a goal state.
e Initial state: a c m bdh
e Goal: d c ab
Solution: Your turn!
(c) Find a solution by hitting the button Solve! in the web interface. If your domain and problem files are
OK, you should get the plan with 10 actions!
Solution:
(unstack a b)
(putdown a)
(unstack e c)
(putdown e)
(unstack c d)
(stack c b)
(pickup e)
(stack e c)
(pickup d)
(stack d a)
(d) Finally, animate it using the Planimation plugin using the blockworld AP.pddl animation file. Solution: Your turn!
(e) Are you still curious? Do you want to see more involved domains with larger plans? Check the par- cprinter domain, from a real-wrold case:
This domain models the operation of the multi-engine printer, for which one prototype is devel- oped at the Palo Alto Research Center (PARC). This type of printer can handle multiple print jobs simultaneously. Multiple sheets, belonging to the same job or different jobs, can be printed simultaneously using multiple Image Marking Engines (IME). Each IME can either be color, which can print both color and black&white images, or mono, which can only print black&white image. Each sheet needs to go through multiple printer components such as feeder, transporter, IME, inverter, finisher and need to arrive at the finisher in order. Thus, sheet (n + 1) needs to be stacked in the same finisher with sheet n of the same job, but needs to arrive at the finisher right after sheet n (no other sheet stacked in between those two consecutive sheets). Since IMEs are heterogeneous (mixture of color and mono) and can run at different speeds, optimizing the oper- ation of this printer for a mixture of print jobs, each of them is an arbitrary mixture of color/b&w pages that are either simplex (one-sided print) or duplex (two-sided print) is a hard problem.
Use this already prepared session to solve one problem instance. How many nodes did the planner ex- panded? How many did it generate but did not manage to expand? Post those stats in the forum!
End of tutorial worksheet
RMIT AI 2021 (Semester 2) – ̃a