15-381 Artificial IntelligenceSearchPlanning: Parameterized OperationsSlide 3Slide 4Slide 5Means-Ends AnalysisControl Rules for MEASlide 8Constraint-Based SearchConstraint-Based SearchConstraintsSlide 12(Dis)Advantages of Constraints15-381 Artificial IntelligenceMeans-Ends Analysis and Constraint PropagationJaime Carbonell24 January 2002Topics Covered:Homework 1 (generalized state-space search)Means-Ends Analysis (backchaining)Search Control Rules in MEAConstraint-Based SearchSearchPlanning: Parameterized OperationsMulti-State TransitionsInstead of: Opi,j: Si Sj, We have Opk,l: {Sk}{ Sl}Preconditions and Post-ConditionsConjunctive set of first-order predicatesArguments can be constants or (typed) variablesIntentional description of subset of all statesPre-image {Sk} states where preconditions are truePost-image {S1} states where post-conditions are trueRequires Consistent variable bindings within and across preconditions and post-conditionsSearchPlanning: Parameterized OperationsFirst ExampleOPERATOR DRIVE-CAR(<car>, <driver>, <keys>, <loc-1>)[PRE: (AT <car> <loc-1>)(AT <driver> <loc-1>)(CONTAINS-GAS <car>)(HAVE <keys> <driver>)(CORRESPOND <keys> <car>)][POST: (AT <car> <loc-2>)(AT <driver> <loc-2>)(NOT (AT <car> <loc-1>))(NOT (AT <driver> <loc-1>))]]SearchPlanning: Parameterized OperationsSecond Example(Previous example: LISP-style, Current one: PROLOG-style)OPERATOR: move-robot(r,x,y)TYPE: ROBOT(r) & LOC(x) & LOC(y)PRE: AT(r,x) & EMPTY(y) & CONNECTED(x,y)POST: AT(r,y), NOT(AT(r,x))OPERATOR: pick-up(r,z)TYPE: ROBOT(r) & LOC(x) & LOC(y)PRE: AT(r,x) & AT(z,y) & NEXT-TO(x,y) & NOT(holding(r,w,))POST: HOLDING(r,z)NOT(AT(z,y))SearchPlanning: Parameterized OperationsInterpretationA plan is an o-path: S0 followed by a sequence of instantiated operators which result in the goal state.Variables match objects in state of specified types only for which the preconditions hold at plan execution time.Planning can proceed by forward or backward (or any other) search method.More on Planning expected from Veloso (later lecture)Means-Ends AnalysisBackchaining/Subgoaling Search1. Let Scurr:= S02. If Scurr = SG, then go to next goal (or DONE)3. Let OPSapp := match(SG {POST(Opi)}) 4. If OPSapp= empty, then FAIL • Else Select OP OPSapp, (save alt's) 1. If match(PRE(OP), Scurr),a. let Scurr:= apply(OP, Scurr)b. Go to step 22. Else (i.e. if NOT(match(PRE(OP), Scurr)))a. MEA(SG):= {unmatched(PRE(OP))}, SI := Scurr)b. If fail, go to step 4c. If succeed, apply OP as aboveControl Rules for MEAChoice Points in MEAChoose Operator, if several applicableChoose Goal, if > 1 subgoals pendingChoose Variable Bindings, if > 1 tupleTypes of Control RulesSelect – choose an alternative and eliminate other contendersReject – Reject an alternative and retain other contendersPrefer – Try one alternative first and retain others for possible backtrackingControl Rules for MEAExampleCONTROL-RULE: Carry-before-moveTYPE: SELECTPRE: Goals(Move(r,x,y), Pick-up(r,z,v)))POST: Pick-up(r,z)CONTROL-RULE: Don’t polish before machiningTYPE: REJECTPRE: Goals(Mill(p,f), Drill(p,l,d,s), Polish(p))POST: Polish(p)Constraint-Based Search Satisfiability problemsFind consistent bindings to a set of variablesConsistent = satisfy all constraintsExample: (X v Y) & (~X v ~Y) Example: Match applicants to positionsTwo families of search methods applyState-space search on bindingsSatisfiability-search on constraintsConstraint-Based SearchExample: How fast can you solve this?Find a way to fit components (1,2,3,4) into slots (A,B,C,D) such that:Each slot only takes one componentSlots are in LEFT-RIGHT sequence A, B, C, DSlots A and C are T-shapedSlots B and D are I-shapedComponents 1,2, are 3-prongedComponents 3,4 are 2-pronged2-pronged fit into T-shaped or I-shaped3-pronged fit only into T-shapedComponent 3 must be LEFT of component 2ConstraintsLeast Commitment Method1. For each Variable find all legal unary-constrained assignments.2. If no assignments possible, return FAILURE3. Assign most-constrained unassigned variable.4. If all variables assigned, return SUCCESS5. If the assigned variable is a member of a binary constraint, propagate instantiation6. Delete all residual un-viable assignments7. Go to 2Constraint-Based SearchA = {1,2,3,4}B = {3,4}C = {1,2,3,4}D = {3,4}A = {1,2,4}C = {1,2,4}D = {4}A = {1,2}C = {1,2}C = {2}A = {1}SUCCESSA = {1,2,3}C = {1,2,3}D = {3}FAILUREB4D3A1C2D4B3(Dis)Advantages of ConstraintsReduce the search spaceEarly failure (upon constraint violation)Generate minimal-uncertainty step (least commitment strategy)Only applicable to satisfiability problemsFinds an answer, not necessarily optimalNot all problems can be cast as constraints to
View Full Document
Unlocking...