Problem 1: (10 pt) Let the length of a plan be the total
number of steps in the plan,
independent of their ordering. Can you find an example where Graphplan
finds a plan with n steps (for any given n) while UCPOP finds a plan
of 2 steps and an example where UCPOP finds a plan with n steps while
Graphplan finds a plan with 2 steps (for any given n). In each case,
either give an example or argue that an example does not exist.
Problem 2: (10 pt) Adding additional clauses to
a Boolean formula makes it in general
harder to find an assignment that makes it true. Given this, why does
adding domain specific control knowledge seem to support faster
planning in Kautz and Selman's work? Do you think that such an
improvement is always possible given any type of domain knowledge?
Problem 3: (10 pt) Write the following piece of
domain knowledge for a blocksworld
problem in the language of TLPlan:
"The only reasonable places for a block during the execution of a good
plan are (1) the place where it is in the initial state, (2) being
held by the robot hand, (3) being on the table or (4) being in its
final position."
Problem 4: (10 pt) What is the nature of the information
computed by Graphplan's
memoizing phase? Is it useful in the absence of mutex propagation?
Problem 5: (10 pt) SATPlan first builds a SAT instance
for time horizon t=1 where the
goal holds at t=1 (short: g1) and tries to find a solution for it.
If
unsuccessful, it builds a SAT instance for time horizon t=2 where the
goal holds at t=2 (short: g2) and tries to find a solution for it,
and
so on, until time horizon t=tmax is reached. Suppose instead that it
builds a SAT instance for time horizon t=1 right away where the goal
is g1 OR g2 OR g3 ... OR gtmax.
Will this approach always return a plan if one exists with length less
than or equal to tmax?
Does this approach introduce any new spurious "solutions?"
Discuss how one might modify WALKSAT so that it finds short solutions
(if they exist) when given a disjunctive goal of this form.
Part II: Practice
The goal of this part of the assignment is to get familiar with two
real planners: UCPOP and Graphplan. Your task is to download and run the
two planners on the Blocks World problem.
Download:
Download the following tar file. It contains the code for the two planners. These file are the same as the ones given in the Planners link on the class's web page. However, the tar file contains some modifications so that PATH problems are resolved.
Where is lisp?
Lisp is available on the CoC network. The following should work on Sun
Machines 'lispworks'.
Save this configuration file to your home directory. (
.lispworks
)
Lisp is also available for other platforms but since graphplan is compiled
for Sun SPARC it is better
to stick to Suns for this assignment.
How to run?
UCPOP
lispworks
[ Start the lisp environment]
> (load "loader.lisp")
[ Stuff Happens ]
> (load-ucpop)
[Stuff Happens ]
;; Test on the Sussman's anomaly
(in-package "UCPOP")
(bf-control 'sussman-anomaly)
;;Testing with many domains
(load "testall.lisp")
(run-tests *all-tests*)
[ Note may take a long time]
New problems can be added to the file domains.lisp.
GRAPHPLAN
Read the the README file.
Domain: Blocks world (10 pt)
Use the Blocks World problem generator to construct problems with 5 blocks. Encode this problems in the format appropriate for the two planners and run them. Compare your solutions with the solution printed by the problem generator. Submit a printout of the results given by the two planners.
Here is a sample solution for a problem
with 4 blocks.