Problem 1: (100 pt) Consider the following simple
domain:
Initial State: A, B, C
Goal: C, D, E
Operator O1 Preconditions: A; Add Effects: F; Delete Effects: C
Operator O2 Preconditions: A; Add Effects: D; Delete Effects: B
Operator O3 Preconditions: B; Add Effects: C
Operator O4 Preconditions: F; Add Effects: D, E, G
A) Trace in detail how Graphplan finds a plan for this problem. (This
includes, for example, to show the planning graph in various stages
together with the mutexes.)
B) Show how the final planning graph can be converted to a SAT instance
using Kautz and Selman's ideas. What is the solution of this SAT
instance? How does it convert back to a solution for the planning
problem?
C) Trace in detail how a partial-order regression planner finds a plan
for this problem. (This includes, for example, to show the various
partial-order plans together with their ordering constraints and
causal links.)
D) Solve the same problem using integer programming techniques.Problem 2: (100 pt)
An agent has a large supply of eggs and its goal is to get the
contents of two(!) good eggs and no bad ones into one of two
bowls. Each egg is good with probability 50 percent. The agent can
pick up an egg and empty its contents into one of the bowls (= one
action execution). The agent can also empty a bown by either dumping
its content into a garbage can (= one action execution) or dumping
its
content into the other bowl (= one action execution). At any time,
the
agent can find out whether a bowl contains the contents of only good
eggs by smelling it (= one action execution).
A) Devise a CONFORMANT plan that maximizes the probability of solving
the task with 5(!) or fewer action executions (that is, parallel
actions are not allowed). A conformant plan is just an (unconditional)
sequence of actions.
B) Devise a CONDITIONAL plan that maximizes the probability of solving
the task with 5(!) or fewer action executions (that is, parallel
actions are not allowed). A conditional plan is one that can contain
sensing actions and where the execution of actions can be conditioned
on the information provided by sensors. To solve this problem, we
suggest that you do not consider the execution of actions that clearly
cannot be optimal, such as emptying the contents of an egg into a bowl
that contains already the contents of two(!) eggs.
In both cases, do not just give an optimal plan but also the reasoning
that shows that your plan is indeed optimal.