Chris Pollett > Old Classes > CS156
( Print View )

Student Corner:
  [Submit Sec2]
  [Grades Sec2]

Lecture Notes]

  [Discussion Board]

Course Info:
  [Texts & Links]
  [Outcomes Matrix]
  [HW/Quiz Info]
  [Exam Info]
  [Additional Policies]

HWs and Quizzes:
  [Hw1]  [Hw2]  [Hw3]
  [Hw4]  [Hw5]  [Quizzes]

Practice Exams:
  [Mid 1]  [Mid 2]  [Final]


HW#4 --- last modified Wednesday, 08-Nov-2017 16:09:03 PST.

Solution set.

Due date: Nov 21

Files to be submitted:

Purpose: To gain experience with first-order reasoning and planning algorithms.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO9 -- Students should be able to explain the advantages and disadvantages of the PDDL representation for planning.

LO10 -- Students should be able to describe the frame problem.


Do the following problems and submit them in

  1. Express each of the following as first order logic formula: (a) `epsilon` is a binary string, (b) if x is a binary string, then so are One(x) and Zero(x), (c) the length of the `epsilon` is 0, (d) the length of One(x) and the length of Zero(x) is 1 plus the length of x.
  2. Using our Natural Deduction system extended by rules for First-order logic, assuming (a)-(d) of problem 1 as our knowledge base, give a formal proof of the formula `alpha` := there exists an `x` that is a binary string of length `1+1+0`.
  3. Let the formulas of Problem 1 be our KB and `alpha` be as in Problem 2. Skolemize the formulas in KB and `neg alpha`, convert the result to CNF, and then clauses. Finally, find a resolution refutation. For at least one place where you needed to do unification carefully show the steps the algorithm from class would use.
  4. Pretend you are going all out to get dressed for a night out. Imagine all the different things you might put on or have to choose between. Model this as a PDDL problem. Then use the GraphPlan algorithm to find a solution.
  5. Briefly explain how PDDL solves the frame problem. Give some disadvantages to formulating problems in PDDL.

Point Breakdown

Each problem is worth 2pts unless, otherwise stated graded according to: 0 - didn't do or way off track, 1 partially correct 2 fully correct. 10pts