02285 AI and MAS, F23
Theory Assignment
Due: Monday 13 March at 20.00
Thomas Bolander, Mikkel Birkegaard Andersen
This assignment is individual. Your solution is to be handed in using the Quiz tool on DTU Learn.
You should first solve all the problems offline, entering your answers in this pdf (either by using the
annotation tools of your pdf viewer or by printing this pdf and filling it in by hand). When you do the
exercises, make sure to describe all your calculations and reasoning on a separate piece of paper. Many
of the questions refer back to previous questions, so you will need to be able to go back and look at the
details of your answers to those questions. Furthermore, many of the questions require a good deal of
thinking and computation, and will be almost impossible to answer correctly unless you make good and
well-structured notes on the side. Only when you have solved all the exercises should you go to the Quiz
tool, and then transfer your answers to that tool.
Filling in your answers online Some of the questions require you to enter a number. In the case
that number is ∞, just write infinity in letters. Other questions require you to fill in names of atoms
or actions. Your answer will only be counted as correct if you stick to these conventions:
• Write without whitespace, e.g. ColorOfBlock(b,red), not ColorOfBlock(b, red).
• Write without subscripts, e.g. Block(B1), not Block(B_1).
• Write with any combination of capital and non-capital letters, e.g. both block(B1) and Block(b1)
are valid when the name of the predicate is Block .
1 Painting domain: action schemas, state spaces, POP algorithm, do-
main independent heuristics
Consider the following painting planning domain. You’re given a number of cans of paint and a number
of brushes that can be dipped in the cans, after which they can be used to paint blocks. A planning
problem in this domain will contain an initial state describing a number of blocks, B1, . . . , Bb, a number
of brushes, R1, . . . , Rr, a number of cans, C1, . . . , Cc and a number of colors K1, . . . ,Kk. Each can
contains paint of a specific color, also described in the initial state. Hence the initial state will contain
the following literals:
• Block(Bi) for each block Bi
• Brush(Ri) for each brush Ri
• Can(Ci) for each can Ci
• IsColor(Ki) for each color Ki
1
• ColorInCan(Ci,Kj) when the color of the paint in can Ci is Kj
A goal in this domain will be any conjunction of ColorOfBlock(b, k) literals. The available actions are:
Action : DipBrush(r, c, k)
Precondition : Brush(r) ∧ Can(c) ∧ IsColor(k) ∧ ColorInCan(c, k)
Effect : CanPaint(r, k)
Action : Paint(b, r, k)
Precondition : Block(b) ∧ Brush(r) ∧ IsColor(k) ∧ CanPaint(r, k)
Effect : ColorOfBlock(b, k) ∧ ¬CanPaint(r, k)
Note that, by assumption, none of the ColorOfBlock(b, k) atoms are true in the initial state, hence all
blocks are initially uncolored. Also, none of the CanPaint(r, k) atoms are true in the initial state, so
initially none of the brushes can paint in any color.
1.1 Rigids
What are the rigid predicates of the planning domain? (cf. the weekly exercises). Mark the rigid
predicates below:
Block
Brush
Can
CanPaint
ColorInCan
ColorOfBlock
IsColor
1.2 Simplified action schemas
The preconditions of the action schemas above can be simplified. We can remove some of the precondition
literals without affecting the set of solutions that each planning problem in the domain has. Determine
all the precondition literals that can be removed without affecting the set of solutions of each planning
problem in the domain. Then mark below the precondition literals that still need to be included after
the simplification.
Action : DipBrush(r, c, k)
Precondition : Brush(r) ∧ Can(c) ∧ IsColor(k) ∧ ColorInCan(c, k)
Effect : CanPaint(r, k)
Action : Paint(b, r, k)
Precondition : Block(b) ∧ Brush(r) ∧ IsColor(k) ∧ CanPaint(r, k)
Effect : ColorOfBlock(b, k) ∧ ¬CanPaint(r, k)
In the rest of this exercise, assume that the original action schemas have been replaced by the simplified
ones.
2
1.3 State space
Consider a planning problem in the painting domain with initial state given by
s0 = Block(B1) ∧ Block(B2) ∧ Brush(R1) ∧ Can(C1) ∧ IsColor(Green) ∧ ColorInCan(C1, Green)
Draw the entire state space reachable from this initial state. Omit the rigids when drawing states. Re-
member to label all edges by their corresponding actions. Then answer the following questions concerning
the state space:
The total number of states is
The total number of loop edges (edges with the same start and end point) is
The total number of edges, including loop edges, is
The minimal number of outgoing edges from any state is
The maximal number of outgoing edges from any state (branching factor) is
1.4 Solutions to planning problems
Let A denote your simplified set of action schemas, let s0 be the initial state given above, and let
g = ColorOfBlock(B1, Green) ∧ ColorOfBlock(B2, Green).
Answer the following, using your state space of the previous question:
The length of an optimal solution to the planning problem (A, s0, g) is
The number of optimal solutions to the planning problem (A, s0, g) is
For any goal formula g′, the maximal number of optimal plans to the planning
problem (A, s0, g′) is
3
1.5 POP algorithm
Consider the same planning problem (A, s0, g) as above. The graph below is the skeleton of a partially
ordered plan resulting from a run of the POP algorithm on this planning problem. The graph includes
all the labelled ordering constraints (causal links), however not the unlabelled ones (the ones resulting
from conflict resolution). Fill in both the names of the states and the labels on the labelled ordering
constraints below. Three of the labels have already been filled in.
1:
2:
3:
4:
5:
6:
A: Brush(R1)
F: Brush(R1)
B:
C: Block(B1)
D:
E:
G:
H:
I:
J:
Now answer the questions below, where we define conflict as follows: An action D 6= B is said to
conflict with an ordering constraint A
c≺ B if D’s effect is inconsistent with c. A conflict is resolved by
adding either the constraint B ≺ D or D ≺ A, while making sure that the graph is still acyclic (so that
≺ is always a strict partial order).
How many conflicts are there in total in the partially ordered plan that you filled in
above?
How many distinct ways are there to resolve all conflicts in the partially ordered
plan?
Suppose you resolve all conflicts in the partially ordered plan. How many linearisa-
tions does your resulting partially ordered plan then have?
4
1.6 Domain-independent heuristics
We are now going to consider some of the different domain-independent heuristics for the planning
problem (A, s0, g) considered in Exercise 1.4. Determine the following heuristic values:
hgc(s0) =
hip(s0) =
h+(s0) =
hadd(s0) =
hmax(s0) =
hFF (s0) =
1.7 Modifying the domain
Consider the following action sequence:
DipBrush(R1, C1, Y ellow),Paint(B1, R1, Y ellow),
DipBrush(R1, C2, Blue),Paint(B2, R1, Blue).
The result will be that the block B1 becomes yellow, and block B2 blue. However, in real life, B2 might
become slightly greenish, as a bit of the yellow paint is bound to be still on the brush when it is dipped
into the blue can. Usually one would clean a brush whenever the brush has to be used for a new color.
The goal of this question is to describe action schemas for capturing this.
We call a brush unclean when it hasn’t been cleaned since last dipped in a can. We can modify the
action schemas so that an unclean brush can not be dipped in another color until it has been cleaned.
To capture this, we need the following modifications of the existing domain:
• We need to able to express that a brush is clean. For this we will use a unary predicate Clean.
• We need to be able to clean an unclean brush. For this we will introduce a new action schema
CleanBrush.
• We will require that an unclean brush can never be dipped into another color than the one it
previously had. Hence, we need to separate between dipping a clean and an unclean brush, as these
will have different preconditions. This is most easily done by having two separate action schemas,
DipCleanBrush and DipBrush. The first action is only applicable when the brush is clean, but
allows us to dip the brush in any can of any color. The second is only applicable when the color of
the brush is the same as the color in the can.
• So far we have used a literal CanPaint(r, k) to express that brush r can paint in color k. Now
things are slightly more complicated. After a brush has been used to paint, it is dry and can’t
paint before being dipped again—however, it still has a bit of color left, and can only be dipped in
the same color unless being cleaned first. This means we need to be able to assign colors to dry
brushes as well. We can do this by splitting CanPaint(r, k) into two atoms ColorOfBrush(r, k) and
5
CanPaint(r). Then ColorOfBrush(r, k) means that brush r has color k, and CanPaint(r) means
that the brush is wet (it has been dipped, but afterwards neither cleaned nor used to paint). A
dipped brush should then preserve its color even after having been used to paint, however it will
no longer be wet. The brush color only disappears when the brush is cleaned.
Fill in the preconditions and effects of the action schemas below such that the resulting schemas follow
the specifications provided above. Make sure to use a minimal number of literals, that is, never add
a precondition or effect literal that is not necessary to include. Superfluous literals will be counted as
mistakes. You can assume that the initial state and goal of any problem in the modified domain is as
for the original domain, except we suppose all brushes to be initially clean, i.e. we add Clean(r) for each
brush r to the initial state description.
Action : DipCleanBrush(r, c, k) // dip clean brush r in can c containing paint of color k
Precondition :
Effect :
Action : DipBrush(r, c, k) // dip brush r in can c containing paint of color k
Precondition :
Effect :
Action : Paint(b, r, k) // paint block b in color k using brush r
Precondition :
Effect :
Action : CleanBrush(r, k) // clean brush r having color k
Precondition :
Effect :
6
1.8 Optimal plans in modified domain
Provide an optimal plan using the action schemas from the previous question in the planning problem
having:
• Two brushes R1 and R2 (initially clean, by convention for initial states).
• A can C1 with Green paint, a can C2 with Red paint and a can C3 with Blue paint.
• Four blocks B1, . . . , B4.
• The goal is for blocks B1 and B2 to be green, block B3 to be red and block B4 to be blue.
Answer the following questions concerning the plan you found:
The length of the plan is
The number of DipCleanBrush actions in the plan is
The number of DipBrush actions in the plan is
The number of Paint actions in the plan is
The number of CleanBrush actions in the plan is
2 Hospital domain: Action schemas, state spaces, multi-agent conflicts
In this exercise we consider how to represent the hospital domain in PDDL. At first we consider only the
single-agent case. Assume we are given a specific single-agent level. We will now show how to represent
the configurations of this level as PDDL states, that is, conjunctions of literals. We choose constants to
denote the entities in the level as follows:
• 0 denotes the agent.
• B1, B2, . . . , Bb is an enumeration of the boxes in the level.
• G1, G2, . . . , Gg is an enumeration of the goals in the level.
• L1, L2, . . . , Ll is an enumeration of the locations (grid cells) in the level, excluding walls.
Then a state of the level is a conjunction of the form:
A ∧ B ∧ G ∧ F ∧ L1 ∧ L2 ∧N ,
where:
A = AgentAt(0, Li), where Li is the current location of agent 0
B = ∧{BoxAt(Bi, Lj) | box Bi is at location Lj}
G = ∧{GoalAt(Gi, Lj) | goal Gi is at location Lj}
F = ∧{Free(Li) | location Li is a free cell}
L1 =
∧{Type(Gi, α) | α ∈ {A,B, . . . , Z} is the type of goal Gi}
L2 =
∧{Type(Bi, α) | α ∈ {A,B, . . . , Z} is the type of box Bi}
N = ∧{Neighbour(Li, Lj) | Li and Lj are neighbours}
The initial state is the one in which A, B, G and F are defined by the initial locations of the agent, boxes,
goals, and free cells. The corresponding goal is:∧
i=1,...,g
GoalAt(Gi, xi) ∧ BoxAt(yi, xi) ∧ Type(yi, zi) ∧ Type(Gi, zi),
7
where all xi, yi and zi are variables. Note that by definition of PDDL, a goal formula is satisfied if
its existential closure is satisfied, that is, if there exists constants to instantiate the variables xi, yi
and zi such that the resulting formula is true in the state. Note also that role of the conjunctions
Type(yi, zi) ∧ Type(Gi, zi) is to make sure that boxes end up at goal cells of the correct type.
2.1 Action schemas for the hospital domain
Fill in the preconditions and effects of the action schemas below so that they formalise the actions
available in single-agent domains. We use the following naming conventions:
• agt is the agent (we are so far only considering single-agent levels, so this parameter can only be
instantiated with 0).
• agtfrom is the location of the agent before the action is executed.
• agtto is the location of the agent after the action is executed.
• box is the box to be moved (in the Push and Pull actions).
• boxfrom is the location of the box before the action is executed.
• boxto is the location of the box after the action is executed.
Note that we are not using the directions (W , E, S and N) as parameters in these action schemas. They
are not needed when we have the exact locations as parameters. The action schemas you design for
these three actions should of course match exactly how these are specified in the hospital domain, cf. the
description in hospital_domain.pdf. Make sure to use a minimal number of literals, that is, never add
a precondition or effect literal that is not necessary to include.
Action : Move(agt , agtfrom, agtto)
Precondition :
Effect:
Action : Push(agt , agtfrom, box , boxfrom, boxto)
Precondition :
Effect :
Action : Pull(agt , agtfrom, agtto, box , boxfrom)
Precondition :
Effect :
8
2.2 Computing plans in the hospital domain
Consider the following very simple level (left) and its corresponding location enumeration (right):
0
A
a L1
L2 L3
L4
A plan to solve the level is the following, using the action names above:
Move(0, L3, L2),Pull(0, L2, L3, B1, L4),Push(0, L3, B1, L2, L1).
Compute the sequence of states that the agent will pass through when executing this plan, using your
action schemas from the previous question. Some of the literals are rigid, that is, will never change as
the consequence of performing an action. These are the literals in G, L1, L2 and N . Check that the
state reached after having executed the entire plan satisfies the goal, using the goal formula given in the
beginning of the exercise. Mark below which atoms are true in which states (e.g. if AgentAt(0, L1) is true
after the Move action, you put a mark in the second column of the first row).
In initial state AfterMove action After Pull action After Push action
AgentAt(0, L1)
AgentAt(0, L2)
AgentAt(0, L3)
AgentAt(0, L4)
BoxAt(B1, L1)
BoxAt(B1, L2)
BoxAt(B1, L3)
BoxAt(B1, L4)
Free(L1)
Free(L2)
Free(L3)
Free(L4)
The goal formula has g = 1 in this case, since there is only one goal cell. This means the goal formula
contains three variables, x1, y1 and z1. As earlier mentioned, a goal state is one in which the existential
9
closure of the goal formula is satisfied, i.e., there has to be a way to instantiate all the variables so that
the resulting ground formula is true in the state. Enter below the constants that the variables have to
be instantiated with for the goal formula to be true in the state reached by the plan above.
The variable x1 of the goal formula has to be instantiated with the constant
The variable y1 of the goal formula has to be instantiated with the constant
The variable z1 of the goal formula has to be instantiated with the constant
2.3 Extending with colors
Now consider extending the problem definition to deal with levels containing multiple agents. At first,
consider only extending the domain to deal with actions composed asynchronously, that is, one agent
acting at a time. A has to specify initial location of all agents. We also have to add colors to the initial
state:
C =
∧
{Color(α, β) | α is agent or box and β is its color}.
Define the revised action schemas for Move, Push and Pull in the setting of multiple agents with only
one agent acting at a time. Then answer the following questions about the revised action schemas.
The original action schema for Move used 3 variables: agt, agtfrom and agtto. How
many additional variables does the revised action schema use?
How many additional precondition literals does the revised Move action have?
How many additional effect literals does the revised Move action have?
The original action schema for Push used 5 variables. How many additional variables
does the revised action schema use?
How many additional precondition literals does the revised Push action have?
How many additional effect literals does the revised Push action have?
The original action schema for Pull used 5 variables. How many additional variables
does the revised action schema use?
How many additional precondition literals does the revised Pull action have?
How many additional effect literals does the revised Pull action have?
2.4 Extending to synchronous actions
Now consider extending the problem definition to deal with multiple agents acting concurrently (MA
track). A joint action is of the form
a0 | · · · | an
where a0 is the action of agent 0, a1 is the action of agent 1, etc. This implies that a0 is an action having
0 in its first parameter, that is, of the form Move(0, . . . ), Push(0, . . . ) or Pull(0, . . . ). Similarly, a1 is an
action having 1 in its first parameter, etc. Note that this is different from the programming project in
which the agent parameter has been made implicit when joint actions are sent to the server.
Suppose in a given state, ai is an action of agent i and aj is an action of agent j, i 6= j. By definition,
the two actions are then conflicting if:
10
1. Actions ai and aj attempt to move two distinct objects (agents or boxes) into the same cell.
2. Actions ai and aj attempt to move the same box.
The goal of this question is to investigate whether it is possible to reduce the problem of checking
for conflict between two actions ai and aj to a condition expressed exclusively in terms of the logical
properties of the corresponding action schemas. Recalling the standard notions from logic, a conjunction
of literals A is inconsistent with a conjunction of literals B if some literal occurs positively in one of the
conjunctions and negatively in the other. In that case we also say that the two conjunctions are mutually
inconsistent. For each of the statements below concerning the relation between conflicts and the action
schemas of the individual actions, determine whether it is true or false. Mark the true statements.
Everywhere it is assumed that i 6= j and that ai and aj only range over the applicable actions.
For all actions ai and aj , if 1 holds, then the effects of the two actions are mutually
inconsistent.
For all actions ai and aj , if 1 holds, then the precondition of one of the actions is
inconsistent with the effect of the other.
For all actions ai and aj , if 2 holds, then the effects of the two actions are mutually
inconsistent.
For all actions ai and aj , if 2 holds, then the precondition of one of the actions is
inconsistent with the effect of the other.
For all actions ai and aj where the precondition of one is inconsistent with the effect
of the other, either 1 or 2 holds.
It is possible to reduce the problem of checking for conflict between two actions ai
and aj to a condition expressed exclusively in terms of consistency constraints on
the action schemas (whether precondition/effects are mutually inconsistent or not).