15-887*/16-830: Planning, Execution, and Learning
Homework Assignments
Fall 2008
Policy on Collaboration
It is OK, and you are encouraged, to discuss the homework problems with
others. The readings and the class notes should provide the best resource
for solving the homework problems. You must write up your
own homework solutions. If you find that it is needed, you may write
the
names of anyone you discussed the problems with on your submission.
Reading papers not on the reading list and searching the web for related
topics may sometimes help you gain a better understanding of the ideas
involved. If some reference helps you directly with a problem, please
explain this in your solutions.
Homeworks
- Homework 1 (Classical Planning)
Out: Wednesday, September 17
Due: Wednesday, October 1, in class
Additional materials:
Rush Hour description,
PDDL description,
PDDL examples
Solutions:
Solution Problems 1 and 2;
Solution Problem 4.
- Homework 2 (Classical Planning and Learning)
Out: Monday, October 6
Due: Wednesday, October 22, in class
Reading for problem 5:
OBBD-based Universal planning for synchronized agents in non-deterministic
domains, Rune Jensen and Manuela Veloso, Journal of Artificial Intelligence Research, 13,
pages 189-226, 2000.
Comments:
- The second part of problem 1 is fine, and different from problem
4 in homework 1, as it mentions "an entire backwards search," meaning
that Graphplan would consider all the existing solutions in its
current planning graph.
- Some of you noticed that the GET-NEW(c,l) operator in Problem 3,
with its empty preconditions, could teleport any container to any
location. I fixed this problem by adding a precondition, not
In-Use(c), and an add effect of In-Use(c). A version of the
Homework2.pdf with this fix is posted (see above).
- Regarding problem 2, Prodigy has only MEA as an heuristic to
guide its search choices. Prodigy selects one goal at a time and then
selects an operator that adds that goal. You can consider that Prodigy
uses means-ends analysis (MEA) in two ways: (i) choosing one goal that
is not true in the current state; and (ii) if more than one operator
adds a goal, then choosing the one that has the least number of
preconditions not true in the current state. MEA does not reason, in
Prodigy in particular, about the delete effects of operators when
choosing an operator.
- You can easily solve problem 5. The class notes on BDD-based
planning are taken from the "OBBD-based universal planning" paper
above. You can solve this problem by studying the pages 195-198 for
the NADL example. You don't need to proceed studying the general
description of the semantics and syntax of NADL. And then you need to
study Section 6 for the algorithms, again as presented in class (pages
204-209).
Solutions:
Solutions Problems 1, 2, and 3;
Solution Problems 4, 5, and 6.
- Homework 3 (MDPs, Path Planning, POMDPs)
Out: Wednesday, October 29
Due: Wednesday, November 12, in class
Updated November 5
Solutions:
Solution Problem 3.
- Homework 4 (Planning, Execution,
Replanning, Learning)
Out: Monday, November 17
Due: Wednesday, December 3, in class
reids@cs.cmu.edu
December 4, 2008