15-780: Grad AILecture 6: OptimizationGeoff Gordon (this lecture)Ziv Bar-Joseph TAs Geoff Hollinger, Henry LinAdmin2Wait listThere are still several students signed up on the wait list for 15-780If you are one of them, just let us know, and we will move you to the regular course roster3Review4FOLQuantifiers, models of FOL expressionsReasoning in FOLClause form, SkolemizationUnification and resolutionPropositionalizationHerbrand, Robinson5PlanningRepresentations of timePlanning languages like STRIPSoperators, preconditions, effects6Using FOL7Knowledge engineeringIdentify relevant objects, functions, and predicatesEncode general background knowledge about domain (reusable)Encode specific problem instancePose queries8Knowledge engineeringSadly, next step is also necessary:Debug knowledge baseSevere bug: logical contradictionsLess severe: undesired conclusionsLeast severe: missing conclusionsIn general, trace back chain of reasoning until reason for failure is revealed9Plan search10Plan searchGiven a planning problem (start state, operator descriptions, goal)Run standard search algorithms to find planDecisions: search state representation, neighborhood, search algorithm11Linear plannerSimplest choice: linear planner Search state = sequence of operatorsNeighbor: add an operator to end of sequenceBind variables as necessaryboth operator and binding are choice points12Linear plannerCan search forward from start or backward from goalOr mix the twoGoal is often incompletely specifiedExample heuristic: number of open literals13Goal: full(M)14STRIPS state examplefood(N)hungry(M)at(N, W)at(M, X)at(B1, Y)at(B2, Y)at(B3, Z)on(B2, B1)clear(B2)clear(B3)level(M, Low)level(N, High)15Linear planner exampleStart w/ empty plan [], initial world statePick an operator, e.g., Move(from, to)at(M, from), level(M, Low)at(M, to), ¬at(M, from)16Linear planner exampleBind variables so that preconditions match world statee.g., from: X, to: Ypre: at(M, X), level(M, Low)post: at(M, Y), ¬at(M, X)17Apply operatorfood(N)hungry(M)at(N, W)at(B1, Y)at(B2, Y)at(B3, Z)on(B2, B1)clear(B2)clear(B3)level(M, Low)level(N, High)at(M, X)at(M, Y)18Repeat…Plan is now [ move(X, Y) ]World state is as in previous slidePick another operator and bindingClimb(object, p), p: Yat(M, p), at(object, p), level(M, Low), clear(object)level(M, High), ¬level(M, Low)19Apply operatorfood(N)hungry(M)at(N, W)at(B1, Y)at(B2, Y)at(B3, Z)on(B2, B1)clear(B2)clear(B3)level(N, High)at(M, Y)level(M, Low)level(M, High)20And so forthGoal: full(M)A possible plan:move(X, Y), move(Y, Z), push(B3, Z, Y), push(B3, Y, X), push(B3, X, W), climb(B3, W), eat(N, W, High)DFS will try moving XYX, climbing on boxes unnecessarily, etc.21Partial-order plannerLinear planner can be wasteful: backtrack undoes most recent action, rather than one that might have caused failurePartial order planner tries to fix thisAvoids committing to details of plan until it has to (principle of least commitment)22Partial-order plannerSearch state:set of operators (partially bound)ordering constraintscausal links (also called guards)open preconditions23Set of operatorsMight include move(X, p) “I will move somewhere from X”, eat(target) “I will eat something”Also includes extra operators START, FINISHeffects of START are initial statepreconditions of FINISH are goals24Partial orderingSTART move(X, p)eat(N)FINISHpush(B3, r, q)25GuardsDescribe where preconditions are satisfiedSTART move(X, p)eat(N)FINISHpush(B3, r, q)at(M, X)full(M)26Open preconditionsAll unsatisfied preconditions of any actionUnsatisfied = doesn’t have a guardSTART move(X, p)eat(N)FINISHpush(B3, r, q)at(M, X)full(M)at(N, p)at(M, p)at(B3, r)level(M, Low)at(M, r)clear(B3)…27Partial-order plannerNeighborhood: plan refinementAdd an operator, guard, or ordering constraint28Adding an ordering constraintSTART move(X, p)eat(N)FINISHpush(B3, r, q)at(M, X)full(M)at(N, p)at(M, p)at(B3, r)level(M, Low)at(M, r)clear(B3)…29Adding an ordering constraintSTART move(X, p)eat(N)FINISHpush(B3, r, q)at(M, X)full(M)at(M, p)at(B3, r)at(M, r)clear(B3)…Wouldn’t ever add ordering on its own—but may need to when adding operator or guardlevel(M, Low)at(N, p)30Adding a guardSTART move(X, p)eat(N)FINISHpush(B3, r, q)at(M, X)full(M)at(N, p)at(M, p)at(B3, r)level(M, Low)at(M, r)clear(B3)…31Adding a guardMust go forward (may need to add ordering)Can’t cross operator that affects conditionSTART move(X, p)eat(N)FINISHpush(B3, r, q)at(M, X)full(M)at(N, p)at(M, p)at(B3, r)level(M, Low)at(M, r)clear(B3)…32Adding a guardMight involve binding a variable (may be more than one way to do so)START move(X, p)eat(N)FINISHpush(B3, r, q)at(M, X)full(M)at(N, W)at(M, p)at(B3, r)level(M, Low)at(M, r)clear(B3)…33Adding an operatorSTART move(X, p)eat(N)FINISHpush(B3, r, q)at(M, X)full(M)at(N, W)at(M, p)at(B3, r)level(M, Low)at(M, r)clear(B3)…34Adding an operatorSTART move(X, p)eat(N)FINISHpush(B3, r, q)at(M, X)full(M)at(N, W)at(M, p)at(B3, r)level(M, Low)at(M, r)clear(B3)…move(s, r)at(M, s)level(M, Low)35Resolving conflictSTART move(X, p)eat(N)FINISHpush(B3, r, q)at(M, X)full(M)at(N, W)at(M, p)level(M, Low)clear(B3)…move(s, r)at(B3, r)at(M, r)at(M, s)level(M, Low)36Recap of neighborhoodPick an open preconditionPick an operator and binding that can satisfy itmay need to add a new opor can use existing opAdd an ordering constraint and guardResolve conflicts by adding more ordering constraints or bindings37Consistency & completenessConsistency: no cycles in ordering, preconditions guaranteed true throughout guard intervalsCompleteness: no open preconditionsSearch maintains consistency, terminates when complete38ExecutionA consistent, complete plan can be executed by linearizing itExecute actions in any order that matches the ordering constraintsFill in unbound variables in any consistent way39Plan Graphs40Planning & model searchFor a long time, it was thought that SAT-style model search was a non-starter as a planning algorithmMore recently, people have written fast planners thatpropositionalize the domainturn it into a CSP or SAT problemsearch for a model41Plan graphTool for making good CSPs: plan graphEncodes a subset of the constraints that plans must satisfyRemaining constraints are handled during search (by rejecting solutions that violate them)42ExampleStart state: have(Cake)Goal: have(Cake) ∧ eaten(Cake)Operators: bake, eat43OperatorsBakepre: ¬have(Cake)post: have(Cake)Eatpre: have(Cake)post: ¬have(Cake),