Download Presentation
## For Friday

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**For Friday**• No new reading • Logic and Resolution Homework**Program 2**• Any questions?**Resolution**• Propositional version. {a Ú b, ¬b Ú c} |- a Ú c OR {¬aÞ b, b Þ c} |- ¬a Þ c Reasoning by cases OR transitivity of implication • Firstorder form • For two literals pj and qk in two clauses • p1Ú ... pj ... Ú pm • q1Ú ... qk ... Ú qn such that q=UNIFY(pj , ¬qk), derive SUBST(q, p1Ú...pj1Úpj+1...ÚpmÚq1Ú...qk1 qk+1...Úqn)**Implication form**• Can also be viewed in implicational form where all negated literals are in a conjunctive antecedent and all positive literals in a disjunctive conclusion. ¬p1Ú...Ú¬pmÚq1Ú...ÚqnÛ p1Ù... Ù pmÞ q1Ú ...Ú qn**Conjunctive Normal Form (CNF)**• For resolution to apply, all sentences must be in conjunctive normal form, a conjunction of disjunctions of literals (a1Ú ...Ú am) Ù (b1Ú ... Ú bn) Ù ..... Ù (x1Ú ... Ú xv) • Representable by a set of clauses (disjunctions of literals) • Also representable as a set of implications (INF).**Example**Initial CNF INF P(x) Þ Q(x) ¬P(x) Ú Q(x) P(x) Þ Q(x) ¬P(x) Þ R(x) P(x) Ú R(x) True Þ P(x) Ú R(x) Q(x) Þ S(x) ¬Q(x) Ú S(x) Q(x) Þ S(x) R(x) Þ S(x) ¬R(x) Ú S(x) R(x) Þ S(x)**Resolution Proofs**• INF (CNF) is more expressive than Horn clauses. • Resolution is simply a generalization of modus ponens. • As with modus ponens, chains of resolution steps can be used to construct proofs. • Factoring removes redundant literals from clauses • S(A) Ú S(A) -> S(A)**Sample Proof**P(w) Q(w) Q(y) S(y) {y/w} P(w) S(w) True P(x) R(x) {w/x} True S(x) R(x) R(z) S(z) {x/A, z/A} True S(A)**Refutation Proofs**• Unfortunately, resolution proofs in this form are still incomplete. • For example, it cannot prove any tautology (e.g. PÚ¬P) from the empty KB since there are no clauses to resolve. • Therefore, use proof by contradiction (refutation, reductio ad absurdum). Assume the negation of the theorem P and try to derive a contradiction (False, the empty clause). • (KB Ù ¬P Þ False) Û KB Þ P**Sample Proof**P(w) Q(w) Q(y) S(y) {y/w} P(w) S(w) True P(x) R(x) {w/x} True S(x) R(x) R(z) S(z) {z/x} S(A) False True S(x) {x/A} False**Resolution Theorem Proving**• Convert sentences in the KB to CNF (clausal form) • Take the negation of the proposed theorem (query), convert it to CNF, and add it to the KB. • Repeatedly apply the resolution rule to derive new clauses. • If the empty clause (False) is eventually derived, stop and conclude that the proposed theorem is true.**Conversion to Clausal Form**• Eliminate implications and biconditionals by rewriting them. p Þ q -> ¬p Ú q p Û q > (¬p Ú q) Ù (p Ú ¬q) • Move ¬ inward to only be a part of literals by using deMorgan's laws and quantifier rules. ¬(p Ú q) -> ¬p Ù ¬q ¬(p Ù q) -> ¬p Ú¬q ¬"x p -> $x ¬p ¬$x p -> "x ¬p ¬¬p -> p**Conversion continued**• Standardize variables to avoid use of the same variable name by two different quantifiers. "x P(x) Ú$x P(x) -> "x1 P(x1) Ú $x2 P(x2) • Move quantifiers left while maintaining order. Renaming above guarantees this is a truthpreserving transformation. "x1 P(x1) Ú $x2 P(x2) -> "x1$x2 (P(x1) Ú P(x2))**Conversion continued**• Skolemize: Remove existential quantifiers by replacing each existentially quantified variable with a Skolem constant or Skolem function as appropriate. • If an existential variable is not within the scope of any universally quantified variable, then replace every instance of the variable with the same unique constant that does not appear anywhere else. $x (P(x) Ù Q(x)) -> P(C1) Ù Q(C1) • If it is within the scope of n universally quantified variables, then replace it with a unique nary function over these universally quantified variables. "x1$x2(P(x1) Ú P(x2)) -> "x1 (P(x1) Ú P(f1(x1))) "x(Person(x) Þ$y(Heart(y) Ù Has(x,y))) -> "x(Person(x) Þ Heart(HeartOf(x)) Ù Has(x,HeartOf(x))) • Afterwards, all variables can be assumed to be universally quantified, so remove all quantifiers.**Conversion continued**• Distribute Ù over Ú to convert to conjunctions of clauses (aÙb) Ú c -> (aÚc) Ù (bÚc) (aÙb) Ú (cÙd) -> (aÚc) Ù (bÚc) Ù (aÚd) Ù (bÚd) • Can exponentially expand size of sentence. • Flatten nested conjunctions and disjunctions to get final CNF (a Ú b) Ú c -> (a Ú b Ú c) (a Ù b) Ù c -> (a Ù b Ù c) • Convert clauses to implications if desired for readability (¬a Ú ¬b Ú c Ú d) -> a Ù b Þ c Ú d**Sample Clause Conversion**"x((Prof(x) Ú Student(x)) Þ($y(Class(y) Ù Has(x,y)) Ù$y(Book(y) Ù Has(x,y)))) "x(¬(Prof(x) Ú Student(x)) Ú($y(Class(y) Ù Has(x,y)) Ù$y(Book(y) Ù Has(x,y)))) "x((¬Prof(x) Ù ¬Student(x)) Ú ($y(Class(y) Ù Has(x,y)) Ù$y(Book(y) Ù Has(x,y)))) "x((¬Prof(x) Ù ¬Student(x)) Ú ($y(Class(y) Ù Has(x,y)) Ù$z(Book(z) Ù Has(x,z)))) "x$y$z((¬Prof(x)Ù¬Student(x))Ú ((Class(y) Ù Has(x,y)) Ù (Book(z) Ù Has(x,z)))) (¬Prof(x)Ù¬Student(x))Ú (Class(f(x)) Ù Has(x,f(x)) Ù Book(g(x)) Ù Has(x,g(x))))**Clause Conversion**(¬Prof(x)Ù¬Student(x))Ú (Class(f(x)) Ù Has(x,f(x)) Ù Book(g(x)) Ù Has(x,g(x)))) (¬Prof(x) Ú Class(f(x))) Ù (¬Prof(x) Ú Has(x,f(x))) Ù (¬Prof(x) Ú Book(g(x))) Ù (¬Prof(x) Ú Has(x,g(x))) Ù (¬Student(x) Ú Class(f(x))) Ù (¬Student(x) Ú Has(x,f(x))) Ù (¬Student(x) Ú Book(g(x))) Ù (¬Student(x) Ú Has(x,g(x))))**Sample Resolution Problem**• Jack owns a dog. • Every dog owner is an animal lover. • No animal lover kills an animal. • Either Jack or Curiosity killed Tuna the cat. • Did Curiosity kill the cat?**In Logic Form**A) $x Dog(x) Ù Owns(Jack,x) B) "x ($y Dog(y) Ù Owns(x,y)) Þ AnimalLover(x)) C) "x AnimalLover(x) Þ ("y Animal(y) Þ ¬Kills(x,y)) D) Kills(Jack,Tuna) Ú Kills(Cursiosity,Tuna) E) Cat(Tuna) F) "x(Cat(x) Þ Animal(x)) Query: Kills(Curiosity,Tuna)**In Normal Form**A1) Dog(D) A2) Owns(Jack,D) B) Dog(y) Ù Owns(x,y) Þ AnimalLover(x) C) AnimalLover(x) Ù Animal(y) Ù Kills(x,y) Þ False D) Kills(Jack,Tuna) Ú Kills(Curiosity,Tuna) E) Cat(Tuna) F) Cat(x) Þ Animal(x) Query: Kills(Curiosity,Tuna) Þ False**Search**• What are characteristics of good problems for search? • What does the search know about the goal state? • Consider the package problem on the exam: • How well would search REALLY work on that problem?**Search vs. Planning**• Planning systems: • Open up action and goal representation to allow selection • Divide and conquer by subgoaling • Relax the requirement for sequential construction of solutions**Planning in Situation Calculus**PlanResult(p,s) is the situation resulting from executing p in s PlanResult([],s) = s PlanResult([a|p],s) = PlanResult(p,Result(a,s)) Initial stateAt(Home,S_0) Have(Milk,S_0) … Actions as Successor State axioms Have(Milk,Result(a,s)) [(a=Buy(Milk) At(Supermarket,s)) Have(Milk,s) a ...)] Querys=PlanResult(p,S_0)At(Home,s)Have(Milk,s) … Solutionp = Go(Supermarket),Buy(Milk),Buy(Bananas),Go(HWS),…] • Principal difficulty: unconstrained branching, hard to apply heuristics**The Blocks World**• We have three blocks A, B, and C • We can know things like whether a block is clear (nothing on top of it) and whether one block is on another (or on the table) • Initial State: • Goal State: A B C A B C**Situation Calculus in Prolog**holds(on(A,B),result(puton(A,B),S)) : holds(clear(A),S), holds(clear(B),S), neq(A,B). holds(clear(C),result(puton(A,B),S)) : holds(clear(A),S), holds(clear(B),S), holds(on(A,C),S), neq(A,B). holds(on(X,Y),result(puton(A,B),S)) : holds(on(X,Y),S), neq(X,A), neq(Y,A), neq(A,B). holds(clear(X),result(puton(A,B),S)) : holds(clear(X),S), neq(X,B). holds(clear(table),S).**neq(a,table).**neq(table,a). neq(b,table). neq(table,b). neq(c,table). neq(table,c). neq(a,b). neq(b,a). neq(a,c). neq(c,a). neq(b,c). neq(c,b).**Situation Calculus Planner**plan([],_,_). plan([G1|Gs], S0, S) : holds(G1,S), plan(Gs, S0, S), reachable(S,S0). reachable(S,S). reachable(result(_,S1),S) : reachable(S1,S). • However, what will happen if we try to make plans using normal Prolog depthfirst search?**Stack of 3 Blocks**holds(on(a,b), s0). holds(on(b,table), s0). holds(on(c,table),s0). holds(clear(a), s0). holds(clear(c), s0). | ? cpu_time(db_prove(6,plan([on(a,b),on(b,c)],s0,S)), T). S = result(puton(a,b),result(puton(b,c),result(puton(a,table),s0))) T = 1.3433E+01**Invert stack**holds(on(a,table), s0). holds(on(b,a), s0). holds(on(c,b),s0). holds(clear(c), s0). ? cpu_time(db_prove(6,plan([on(b,c),on(a,b)],s0,S)),T). S = result(puton(a,b),result(puton(b,c),result(puton(c,table),s0))), T = 7.034E+00**Simple Four Block Stack**holds(on(a,table), s0). holds(on(b,table), s0). holds(on(c,table),s0). holds(on(d,table),s0). holds(clear(c), s0). holds(clear(b), s0). holds(clear(a), s0). holds(clear(d), s0). | ? cpu_time(db_prove(7,plan([on(b,c),on(a,b),on(c,d)],s0,S)),T). S = result(puton(a,b),result(puton(b,c),result(puton(c,d),s0))), T = 2.765935E+04 7.5 hours!**STRIPS**• Developed at SRI (formerly Stanford Research Institute) in early 1970's. • Just using theorem proving with situation calculus was found to be too inefficient. • Introduced STRIPS action representation. • Combines ideas from problem solving and theorem proving. • Basic backward chaining in state space but solves subgoals independently and then tries to reachieve any clobbered subgoals at the end.**STRIPS Representation**• Attempt to address the frame problem by defining actions by a precondition, and add list, and a delete list. (Fikes & Nilsson, 1971). • Precondition: logical formula that must be true in order to execute the action. • Add list: List of formulae that become true as a result of the action. • Delete list: List of formulae that become false as result of the action.**Sample Action**• Puton(x,y) • Precondition: Clear(x) Ù Clear(y) Ù On(x,z) • Add List: {On(x,y), Clear(z)} • Delete List: {Clear(y), On(x,z)}**STRIPS Assumption**• Every formula that is satisfied before an action is performed and does not belong to the delete list is satisfied in the resulting state. • Although Clear(z) implies that On(x,z) must be false, it must still be listed in the delete list explicitly. • For action Kill(x,y) must put Alive(y), Breathing(y), HeartBeating(y), etc. must all be included in the delete list although these deletions are implied by the fact of adding Dead(y)**Subgoal Independence**• If the goal state is a conjunction of subgoals, search is simplified if goals are assumed independent and solved separately (divide and conquer) • Consider a goal of A on B and C on D from 4 blocks all on the table**Subgoal Interaction**• Achieving different subgoals may interact, the order in which subgoals are solved in this case is important. • Consider 3 blocks on the table, goal of A on B and B on C • If do puton(A,B) first, cannot do puton(B,C) without undoing (clobbering) subgoal: on(A,B)**Sussman Anomaly**• Goal of A on B and B on C • Starting state of C on A and B on table • Either way of ordering subgoals causes clobbering**STRIPS Approach**• Use resolution theorem prover to try and prove that goal or subgoal is satisfied in the current state. • If it is not, use the incomplete proof to find a set of differences between the current and goal state (a set of subgoals). • Pick a subgoal to solve and an operator that will achieve that subgoal. • Add the precondition of this operator as a new goal and recursively solve it.**STRIPS Algorithm**STRIPS(initstate, goals, ops) Let currentstate be initstate; For each goal in goals do If goal cannot be proven in current state Pick an operator instance, op, s.t. goal Î adds(op); /* Solve preconditions */ STRIPS(currentstate, preconds(op), ops); /* Apply operator */ currentstate := currentstate + adds(op) dels(ops); /* Patch any clobbered goals */ Let rgoals be any goals which are not provable in currentstate; STRIPS(currentstate, rgoals, ops).**Algorithm Notes**• The “pick operator instance” step involves a nondeterministic choice that is backtracked to if a deadend is ever encountered. • Employs chronological backtracking (depthfirst search), when it reaches a deadend, backtrack to last decision point and pursue the next option.**Norvig’s Implementation**• Simple propositional (no variables) Lisp implementation of STRIPS. #S(OP ACTION (MOVE C FROM TABLE TO B) PRECONDS ((SPACE ON C) (SPACE ON B) (C ON TABLE)) ADDLIST ((EXECUTING (MOVE C FROM TABLE TO B)) (C ON B)) DELLIST ((C ON TABLE) (SPACE ON B))) • Commits to first sequence of actions that achieves a subgoal (incomplete search). • Prefers actions with the most preconditions satisfied in the current state. • Modified to to try and re-achieve any clobbered subgoals (only once).**STRIPS Results**; Invert stack (good goal ordering) > (gps '((a on b)(b on c) (c on table) (space on a) (space on table)) '((b on a) (c on b))) Goal: (B ON A) Consider: (MOVE B FROM C TO A) Goal: (SPACE ON B) Consider: (MOVE A FROM B TO TABLE) Goal: (SPACE ON A) Goal: (SPACE ON TABLE) Goal: (A ON B) Action: (MOVE A FROM B TO TABLE)**Goal: (SPACE ON A)**Goal: (B ON C) Action: (MOVE B FROM C TO A) Goal: (C ON B) Consider: (MOVE C FROM TABLE TO B) Goal: (SPACE ON C) Goal: (SPACE ON B) Goal: (C ON TABLE) Action: (MOVE C FROM TABLE TO B) ((START) (EXECUTING (MOVE A FROM B TO TABLE)) (EXECUTING (MOVE B FROM C TO A)) (EXECUTING (MOVE C FROM TABLE TO B)))**; Invert stack (bad goal ordering)**> (gps '((a on b)(b on c) (c on table) (space on a) (space on table)) '((c on b)(b on a))) Goal: (C ON B) Consider: (MOVE C FROM TABLE TO B) Goal: (SPACE ON C) Consider: (MOVE B FROM C TO TABLE) Goal: (SPACE ON B) Consider: (MOVE A FROM B TO TABLE) Goal: (SPACE ON A) Goal: (SPACE ON TABLE) Goal: (A ON B) Action: (MOVE A FROM B TO TABLE) Goal: (SPACE ON TABLE) Goal: (B ON C) Action: (MOVE B FROM C TO TABLE)**Goal: (SPACE ON B)**Goal: (C ON TABLE) Action: (MOVE C FROM TABLE TO B) Goal: (B ON A) Consider: (MOVE B FROM TABLE TO A) Goal: (SPACE ON B) Consider: (MOVE C FROM B TO TABLE) Goal: (SPACE ON C) Goal: (SPACE ON TABLE) Goal: (C ON B) Action: (MOVE C FROM B TO TABLE) Goal: (SPACE ON A) Goal: (B ON TABLE) Action: (MOVE B FROM TABLE TO A)**Must reachieve clobbered goals: ((C ON B))**Goal: (C ON B) Consider: (MOVE C FROM TABLE TO B) Goal: (SPACE ON C) Goal: (SPACE ON B) Goal: (C ON TABLE) Action: (MOVE C FROM TABLE TO B) ((START) (EXECUTING (MOVE A FROM B TO TABLE)) (EXECUTING (MOVE B FROM C TO TABLE)) (EXECUTING (MOVE C FROM TABLE TO B)) (EXECUTING (MOVE C FROM B TO TABLE)) (EXECUTING (MOVE B FROM TABLE TO A)) (EXECUTING (MOVE C FROM TABLE TO B)))**STRIPS on Sussman Anomaly**> (gps '((c on a)(a on table)( b on table) (space on c) (space on b) (space on table)) '((a on b)(b on c))) Goal: (A ON B) Consider: (MOVE A FROM TABLE TO B) Goal: (SPACE ON A) Consider: (MOVE C FROM A TO TABLE) Goal: (SPACE ON C) Goal: (SPACE ON TABLE) Goal: (C ON A) Action: (MOVE C FROM A TO TABLE) Goal: (SPACE ON B) Goal: (A ON TABLE) Action: (MOVE A FROM TABLE TO B) Goal: (B ON C)**Consider: (MOVE B FROM TABLE TO C)**Goal: (SPACE ON B) Consider: (MOVE A FROM B TO TABLE) Goal: (SPACE ON A) Goal: (SPACE ON TABLE) Goal: (A ON B) Action: (MOVE A FROM B TO TABLE) Goal: (SPACE ON C) Goal: (B ON TABLE) Action: (MOVE B FROM TABLE TO C) Must reachieve clobbered goals: ((A ON B)) Goal: (A ON B) Consider: (MOVE A FROM TABLE TO B)**Goal: (SPACE ON A)**Goal: (SPACE ON B) Goal: (A ON TABLE) Action: (MOVE A FROM TABLE TO B) ((START) (EXECUTING (MOVE C FROM A TO TABLE)) (EXECUTING (MOVE A FROM TABLE TO B)) (EXECUTING (MOVE A FROM B TO TABLE)) (EXECUTING (MOVE B FROM TABLE TO C)) (EXECUTING (MOVE A FROM TABLE TO B)))