15-381/681 Homework 5
Part I: Planning Problems
Download and the
file planning-files.zip and
extract its contents. It contains a copy of graphplan.py, an
implementation of the GraphPlan algorithm, plus several sample
planning problems, including the rocket problem discussed in
Read the file rocket.py and make sure you understand it.
Run the file rocket.py and make sure you understand the output.
Read and run the fixit.py and blocks.py demos as well.
Note that there is special handling of the predicates 'equal' and 'not_equal'.
This will be useful to in solving the problems below.
Q1 (15 pts). Create a file hanoi.py that uses GraphPlan to solve
of Hanoi problem with three disks. Your solution should
require just one operator, Move.
Q2 (20 pts). Create a file fox.py that uses GraphPlan to solve
Goose, and Beans puzzle. Your solution should use no more than 5 operators;
our solution uses 3.
Q3 (30 pts). Create a file mandc.py that uses GraphPlan to solve
and Cannibals Problem. Note: although we don't have
arithmetic in our GraphPlan implementation, you don't need a
full arithmetic capability, just a handful of facts about
Part II: The Planning Graph
Q4 (15 pts). Draw the planning graph for the rocket problem,
showing all propositions, all actions including noops, and a
representative set of mutex links showing that you understand
the different types of mutex relations. (There were five types
described in lecture.) Use different colors for the different
types of mutex links. Note: you will want to do this in
PowerPoint or some other drawing program; doing it by hand will
be too messy.
Part III: Event Calculus
Consider the conditions of a 100 meter race between two people.
There are two racers: John and Bill, a starting gun, and a finish
line. We want to describe the progress of this race using event
Suppose we have two fluents: A1 (John is ahead) and A2 (Bill is
Q5 (10 pts). The event we want to determine is the
winning of the race. State the inference rules that would allow
us to determine who wins the race using the predicates of event
Q6 (10 pts). Suppose at time t1, John is ahead. Then, at
time t2, Bill takes the lead. At time t3, John takes the lead
again, and crosses the finish line at time t4. Create the
knowledge base of sentences corresponding to this situation.
Then, using your inference rules from Q5 and the axioms of event
calculus, show your work in determining who won the race. Note:
you should assume that there are no other events beyond those
described here, e.g., there are no additional "takes the lead"
events, neither John nor Bill was eaten by a velociraptor,
Create a zip archive containing exactly these files: (1)
hanoi.py, fox.py, and mandc.py, (2) an answers.pdf file
containing your planning graph from Q4 and your answers to the
written questions Q5 and Q6, and (3) a README.txt file with your
name and Andrew id. Note: do not use other archive formats such
as tar, rar, or bz2; you must submit a zip file.
Submit your zip file via Autolab.