1PlanningR&N Chap. 11(and a tiny snippet of Chap. 8-9)Limitations of Prop. Logic• Not very expressive: To represent the fact that a flight can originate from any of nairports, we need n symbols: FlyFromPITT, FlyFromSFO, FlyFromORC,…• Instead we would like to use more expressive sentences like:For any airport x, FlyFrom(x) First order logic (FOL)2FOL (The extremely short version!!)• Same as before, plus:– Quantifiers: – Variables: x, y, z– Predicates: P(x,y) = logical expression with value True/False– Functions: F(x)),Sibling(),Parent(),Parent(,, yxyzxzzyx⇒∧∀∃∀,FOL• Substitution: Replace a part of the sentence by another one.SUBST({x/John}, Rich(x)) Rich(John)• Unification: Find parts of two sentences that are identical after some substitution UNIFY(SameCountry(F(x), y), SameCountry(John,Mary)) = {F(x)/John, y/Mary}3FOL Inference: Resolution• Resolution: Resolution can be extended to FOL, but more complicated),UNIFY(),SUBST(22112121mlmlmmll¬=∨∨∨θθ}/{)UnHappy()Rich()Rich()UnHappy(JohnxJohnJohnxx=¬∨θAfter some substitution, l2and ¬m2are the sameFOL Inference: Chaining• Chaining: Forward/backward chaining idea can be extended to KBs with sentences of the form:• A1^ A2^ A3…. => B)(RoomSecure)(DoorLocked)ked(WindowsLoc xxx⇒∧4Summary• FOL provides more compact way of representing KBs• CNF, resolution and forward/backward chaining concepts exists in FOL• Properties of soundness, completenessA Simple Task• Task: Find a sequence of moves that will go from the configuration with 3 blocks on the table to a configuration with the 3 blocks stacked on top of each other in the A,B,C order.ABCABC5A Simple Task• Task: Find a sequence of moves that will go from the configuration with 3 blocks on the table to a configuration with the 3 blocks stacked on top of each other in the A,B,C order.ABCABC1. Move B from the table and stack it on top of A2. Move C from the table and stack it on top of BABCABCDescribe the startingconfiguration by a KB:On(A,Table) ^ On(B,Table) ^ On(C,Table) ^ Clear(A) ^ Clear(B) ^ Clear(C)Describe the goalconfiguration by a KB:On(A,Table) ^ On(B,A) ^ On(C,B)6ABCABCDescribe the startingconfiguration by a KB:On(A,Table) ^ On(B,Table) ^ On(C,Table) ^ Clear(A) ^ Clear(B) ^ Clear(C)Describe the goalconfiguration by a KB:On(A,Table) ^ On(B,A) ^ On(C,B)Predicates representing the constraints on the components of the environmentsSymbolsrepresenting the constraints on the components of the environmentsABCABCDescribe each possible action by a pair Precondition/Effect:Action: PutOn(r, x, y)PRECONDITION:On(r,x) ^ Clear(r) ^ Clear(y)EFFECT:On(r,y) ^ Clear(x) ^ ¬ On(r,x) ^ ¬ Clear(y) In words: Move block rfrom top of x to top of y7ABCABCDescribe each possible action by a pair Precondition/Effect:Action: PutOnTable(r, x)PRECONDITION: On(r,x) ^ Clear(r)EFFECT: On(r,Table) ^ Clear(x) ^ ¬ On(r,x)In words: Move block r from top of xto table Planning Problem as SearchOn(A,Table) ^ On(B,Table) ^ On(C,Table) ^ Clear(A) ^ Clear(B) ^ Clear(C)PutOn(B, Table, A)On(B,A) ^ On(C,Table) ^ ¬ Clear(A) ^ Clear(B) ^ Clear(C)On(B,A) ^ On(C,B) ^ ¬ Clear(A) ^ ¬ Clear(B) ^ Clear(C)PutOn(C, Table, B)On(C,A) ^ On(B,Table) ^ ¬ Clear(A) ^ Clear(B) ^ Clear(C)PutOn(C, Table, A)8Planning Problem as SearchOn(A,Table) ^ On(B,Table) ^ On(C,Table) ^ Clear(A) ^ Clear(B) ^ Clear(C)PutOn(B, Table, A)On(B,A) ^ On(C,Table) ^ ¬ Clear(A) ^ Clear(B) ^ Clear(C)On(B,A) ^ On(C,B) ^ ¬ Clear(A) ^ ¬ Clear(B) ^ Clear(C)PutOn(C, Table, B)On(C,A) ^ On(B,Table) ^ ¬ Clear(A) ^ Clear(B) ^ Clear(C)PutOn(C, Table, A)Each state is a knowledge base describing the configuration of the worldStates are linked by actions. An action links two states if the precondition of the action is satisfied in the starting state and the effect is consistent with the end state.Planning Problem as Search• States: KBs representing the possible configurations of the world• Arcs: actions allowed between states• Any of the previous search techniques can be used for planning in this graph (defined implicitly)• Forward planning: Search from the start configuration until the goal configuration is reached• Backward planning: Search backward from the goal configuration until the start configuration is reachedSTARTGOALS1S2SiSjaijaijis a valid action ifSisatisfies PRECONDITION(aij)Sjsatisfies EFFECT(aij)9Notation• Describing the actions is actually quite tricky. • Frame problem: Should we represent the effect of “PutOn” on the other variables? If we do, we need to enumerate explicitly all of the variables in the world!• One solution: It is implicitly assumed that any symbol not mentioned in the EFFECT remains untouched.• The particular notation used here (which uses this approach) is called the STRIPS notation (named after a famous Stanford system.)PutOn(r, x, y)PRECONDITION:On(r,x) ^ Clear(r) ^ Clear(y)EFFECT:On(r,y) ^ Clear(x) ^ ¬ On(r,x) ^ ¬ Clear(y)Forward planning can be stupidSTARTGo to Chem. SectionGo to NSH 1500Go to AirportGo to BookstoreGo to Movie TheaterGo to WeH7500Go to CS SectionECE SectionLooking forward from the START state, there is no way to anticipate which actions are relevant to reaching the goal Need to explore a large number of completely irrelevant actionsGOAL= Buy AI book10Heuristics• Search is in general inefficient. Can we use heuristics to speed up the search?• General heuristics: Try to guess a lower bound on the number of actions necessary to achieve the goal.• Example (relaxed problems): First assume that the actions have no preconditions and find a set of the actions leading to the goal configurations (easier problem) Provides a lower bound on the number of actions to reach the goal• A* and related search techniques can be used to take advantage of heuristics. Another way to look at planning• Instead of searching through the graph of possible world states linked by actions, we could do the opposite: Search through the set of possible plans = (informally) sequences of actions• In fact, in many cases we can find partial plans that can be combined into a complete plan (hopefully) more efficient search• Formally: Partial-Order Planning (POP)Move Block B On AMove Block A On BMove Block B On AMove Block C On BMove Block A On BMove Block C On AEmptyPlan11Example• The nodes are now actions instead of world states• START and FINISH are dummy nodes• Two nodes A and A’ are linked if the effect of A is a precondition
View Full Document
Unlocking...