HW#4 --- last modified November 14 2022 20:41:41.

Solution set.

Due date: Nov 18

Files to be submitted:
  Hw4.zip

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

Related Course Outcomes:

CLO2 -- Explain the advantages and disadvantages of the following techniques: (a) breadth-first search compared to depth-first search, (b) informed search compared to uninformed search, hill climbing, STRIPS/PDDL representations for planning.

CLO8 -- Students should be able to describe: (a) the frame problem, (b) Possible representations for time and for beliefs.

Specification:

Do the following problems and submit them in Hw4.zip.

1. Express each of the following as first order logic formula in the language with constant 0, function symbols MakeTree, LeftTree, RightTree and predicates Equals, and BinaryTree: (a) `0` is a binary tree, (b) if x, y are binary trees, then so is MakeTree(x,y), (c) z equals itself, (d) 0 is not equal to MakeTree(x,y), (e) if z equals MakeTree(x,y) then LeftTree(z) equals x and RightTree(z) equals y, (f) if x is a binary tree and x is not equal to 0, then LeftTree(x) and RightTree(x) are binary trees.
2. Using our Natural Deduction system extended by rules for First-order logic, assuming (a)-(f) of problem 1 as our knowledge base, give a formal proof of the formula `alpha` := there exists an `x` such that x is a binary tree and LeftTree(LeftTree(RightTree(x))) equals 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 your parents wants you to change the sheets on your king size bed with two pillows. Imagine all the different things you might need to choose between, put on, or remove from your bed to accomplish this daunting task. Model this as a PDDL problem. Then use the GraphPlan algorithm to find a solution.
5. Express the Yale Shooting Problem in PDDL and show your solution does not suffer from the frame problem.

Point Breakdown