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 lecture.

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 the Tower 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 the Fox, 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 the Missionaries 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 addition.

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 calculus.

Suppose we have two fluents: A1 (John is ahead) and A2 (Bill is ahead).

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 calculus.

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, etc.

Hand-in Instructions

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.

Back to class home page.