برنامه ریزی AI

برنامه ریزی AI

اسلاید 1: 107فصل دهمبرنامه ریزی AIAlireza yousefpouryousefpour@shomal.ac.ir

اسلاید 2: The planning problem2Inputs:1. A description of the world state2. The goal state description3. A set of actionsOutput:A sequence of actions that if applied to the initial state, transfers the world to the goal state

اسلاید 3: An example – Blocks world3Blocks on a tableCan be stacked, but only one block on top of anotherA robot arm can pick up a block and move to another positionOn the tableOn another blockArm can pick up only one block at a timeCannot pick up a block that has another one on it

اسلاید 4: STRIPS Representation4State is a conjunction of positive ground literalsOn(B, Table) Λ Clear (A)Goal is a conjunction of positive ground literals Clear(A) Λ On(A,B) Λ On(B, Table)STRIPS Operators Conjunction of positive literals as preconditionsConjunction of positive and negative literals as effects

اسلاید 5: More on action schema5Example: Move (b, x, y)Precondition: Block(b) Λ Clear(b) Λ Clear(y) Λ On(b,x) Λ (b ≠ x) Λ (b ≠ y) Λ (y ≠ x)Effect: ¬Clear(y) Λ ¬On(b,x) Λ Clear(x) Λ On(b,y)An action is applicable in any state that satisfies its preconditionDelete listAdd list

اسلاید 6: STRIPS assumptions6Closed World assumptionUnmentioned literals are false (no need to explicitly list out)STRIPS assumptionEvery literal not mentioned in the “effect” of an action remains unchangedAtomic Time (actions are instantaneous)

اسلاید 7: STRIPS expressiveness7Literals are function free: Move (Block(x), y, z)operators can be propositionalized Move(b,x,y) and 3 blocks and table can be expressed as 48 purely propositional actionsNo disjunctive goals: On(B, Table) V On(B, C)No conditional effects: On(B, Table) if ¬On(A, Table)

اسلاید 8: Planning algorithms8Planning algorithms are search proceduresWhich state to search?State-space searchEach node is a state of the worldPlan = path through the statesPlan-space searchEach node is a set of partially-instantiated operators and set of constraintsPlan = node

اسلاید 9: State search9Search the space of situations, which is connected by operator instancesThe sequence of operators instances = planWe have both preconditions and effects available for each operator, so we can try different searches: Forward vs. Backward

اسلاید 10: Planning: Search Space10ACBABCACBCBABACBACBCACABACBBCAABCABCABC

اسلاید 11: Forward state-space search (1)11ProgressionInitial state: initial state of the problemActions:Applied to a state if all the preconditions are satisfiedSuccesor state is built by updating current state with add and delete listsGoal test: state satisfies the goal of the problem

اسلاید 12: Progression (forward search)12ProgWS(world-state, goal-list, PossibleActions, path)If world-state satisfies all goals in goal-list,Then return path.Else Act = choose an action whose precondition is true in world-stateIf no such action existsThen failElse return ProgWS( result(Act, world-state), goal-list, PossibleActions, concatenate(path, Act) )

اسلاید 13: Forward search in the Blocks world13……

اسلاید 14: Forward state-space search (2)14AdvantagesNo functions in the declarations of goals  search state is finiteSoundComplete (if algorithm used to do the search is complete)LimitationsIrrelevant actions  not efficientNeed heuristic or pruning procedure

اسلاید 15: Backward state-space search (1)15RegressionInitial state: goal state of the problemActions:Choose an action thatIs relevant; has one of the goal literals in its effect setIs consistent; does not negate another literalConstruct new search stateRemove all positive effects of A that appear in goalAdd all preconditions, unless already appearsGoal test: state is the initial world state

اسلاید 16: Regression (backward search)16RegWS(initial-state, current-goals, PossibleActions, path)If initial-state satisfies all of current-goalsThen return pathElse Act = choose an action whose effect matches one of current-goalsIf no such action exists, or the effects of Act contradict some of current-goals, then failG = (current-goals – goals-added-by(Act)) + preconds(Act)If G contains all of current-goals, then failReturn RegWS(initial-state, G, PossibleActions, concatenate(Act, path))

اسلاید 17: Backward state-space search (2)17AdvantagesConsider only relevant actions  much smaller branching factorLimitationsStill need heuristic to be more efficient

اسلاید 18: Comparing ProgWS and RegWS18Both algorithms are sound (they always return a valid plan)complete (if a valid plan exists they will find one)Running time is O(bn)where b = branching factor, n = number of “choose” operators

اسلاید 19: Blocks world: STRIPS operators19Pickup(x)Pre: on(x, Table), clear(x), aeDel: on(x, Table), ae Add: holding(x)Putdown(x)Pre: holding(x)Del: holding(x)Add: on(x, Table), ae UnStack(x,y)Pre: on(x, y), aeDel: on(x, y), aeAdd: holding(x), clear(y) Stack(x, y)Pre: holding(x), clear(y)Del: holding(x), clear(y)Add: on(x, y), ae

اسلاید 20: STRIPS Planning20Current state:on(A,table), on(C, B), on(B,table), on(D,table), clear(A), clear(C), clear(D), ae.Goalon(A,C), on(C,D)ACBDCAD

اسلاید 21: STRIPS Planning21on(A,C), on(D,A)on(A,table), on(C, B), on(B,table), on(D,table), clear(A), clear(C), clear(D), ae.Current StatePlan:Goalstack:on(A,C)Stack(A, C)holding(A), clear(C)holding(A)Pickup(A)on(A,Table), clear(A), ae ACBDCAD

اسلاید 22: STRIPS Planning22on(A,C), on(D,A)on(A,table), on(C, B), on(B,table), on(D,table), clear(A), clear(C), clear(D), ae.Current StatePlan:Goalstack:on(A,C)Stack(A, C)holding(A), clear(C)holding(A)Pickup(A) ACBDCADPickup(x)Pre: on(x,Table), clear(x), aeDel: on(x, Table), ae, Add: holding(x)holding(A), on(C, B), on(B,table), on(D,table), clear(A), clear(C), clear(D).

اسلاید 23: STRIPS Planning23holding(A), on(C, B), on(B,table), on(D,table), clear(A), clear(C), clear(D).on(A,C), on(D,A)Current StatePlan:Goalstack:on(A,C)Stack(A, C) ACBDCADStack(x, y)Pre: holding(x), clear(y)Del: holding(x), clear(y)Add: on(x, y), aePickup(A)on(A,C), on(C, B), on(B,table), on(D,table), clear(A), clear(D), ae.

اسلاید 24: STRIPS Planning24on(A,C), on(D,A)on(A,C), on(C, B), on(B,table), on(D,table), clear(A), clear(D), ae.Current StatePlan:Goalstack:on(D, A)Stack(D,A)holding(D), clear(A)holding(D)Pickup(D)on(D,Table), clear(D), ae ACBDCADon(A,C), on(C, B), on(B,table), holding(D), clear(A), clear(D)on(A,C), on(C, B), on(B,table), on(D,A), clear(A), aeStack(A, C)Pickup(A)

اسلاید 25: STRIPS Planning25on(A,C), on(D,A)Current StatePlan:Goalstack:on(D, A)Stack(D,A)holding(D), clear(A)holding(D)Pickup(D) ACBDCADon(A,C), on(C, B), on(B,table), holding(D), clear(A), clear(D)on(A,C), on(C, B), on(B,table), on(D,A), clear(A), aeStack(A, C)Pickup(A)

اسلاید 26: STRIPS Planning: Getting it Wrong!26on(A,C), on(D,A)on(A,table), on(C, B), on(B,table), on(D,table), clear(A), clear(C), clear(D), ae.Current StatePlan:Goalstack:on(D,A)Stack(D, A)holding(D), clear(A)holding(D)Pickup(D)on(D,Table), clear(D), ae ACBDCADon(A,table), on(C, B), on(B,table), holding(D), clear(A), clear(C), clear(D)

اسلاید 27: STRIPS Planning: Getting it Wrong!27on(A,table), on(C, B), on(B,table), holding(D), clear(A), clear(C), clear(D)on(A,C), on(D,A)on(A,table), on(C, B), on(B,table), on(D,A), clear(C), clear(D), ae.Current StatePlan:Goalstack:on(D,A)Stack(D, A)Pickup(D) ACBDCAD

اسلاید 28: STRIPS Planning: Getting it Wrong!28on(A,C), on(D,A)on(A,table), on(C, B), on(B,table), on(D,A), clear(C), clear(D), ae.Current StatePlan:Goalstack:Stack(D, A)Pickup(D) ACBDCADNow What?We chose the wrong goal firstA is no longer clear.stacking D on A messes up the preconditions for actions to accomplish on(A, C)either have to backtrack, or else we must undo the previous actions

اسلاید 29: STRIPS planning (Goalstack planning)29Works on one subgoal at a timeInsists on completely achieving that subgoal before considering other subgoalsMay have to backtrack:If it chooses the wrong order to work on the subgoalsIf it chooses the wrong action to achieve a subgoalSearches backwards from goal – uses goal to guide choice of actions

اسلاید 30: Limitation of state-space search30Linear planning or Total order planningExampleInitial state: all the blocks are clear and on the tableGoal: On(A,B) Λ On(B,C)If search achieves On(A,B) first, then needs to undo it in order to achieve On(B,C)Have to go through all the possible permutations of the subgoals

اسلاید 31: Search through the space of plans31Nodes are partial plans, links are plan refinement operations and a solution is a node (not a path).This can be powerful if the plan representation and refinements change the search space.POP creates partial-order plans following a “least commitment” principle.

اسلاید 32: 32Left SockStartFinishRight ShoeLeft ShoeRight SockStartRight SockFinishLeftShoeRightShoeLeft SockStartStartStartStartStartRight SockRight SockRight SockRight SockRight SockLeft SockLeft SockLeft SockLeft SockLeft SockLeft SockRightShoeRightShoeRightShoeRightShoeRightShoeLeftShoeLeftShoeLeftShoeLeftShoeFinishFinishFinishFinishFinishLeft Shoe onRight Shoe onLeft Sock onRight Sock onPartial Order Plans:Total Order Plans:

اسلاید 33: P.O. plans in POP33Plan = (A, O, L), whereA is the set of actions in the planO is a set of temporal orderings between actionsL is a set of causal links linking actions via a literalCausal link means that Ac has precondition Q that is established in the plan by Ap.move-a-from-b-to-table move-c-from-d-to-bApAcQ(clear b)

اسلاید 34: Threats to causal links34Step At threatens link if:At has (~Q) as an effectAt could come between Ap and Ac, i.e., O is consistent with Ap < At < AcApAcQ

اسلاید 35: Threat Removal35Threats must be removed to prevent a plan from failingDemotion adds the constraint At < Ap to prevent clobbering, i.e. push the clobberer before the producerPromotion adds the constraint Ac < At to prevent clobbering, i.e. push the clobberer after the consumer

اسلاید 36: Initial (Null) Plan36Initial plan has A = { A0, A¥} O = {A0 < A¥} L = {} A0 (Start) has no preconditions but all facts in the initial state as effects. A¥ (Finish) has the goal conditions as preconditions and no effects.

اسلاید 37: POP algorithm37POP((A, O, L), agenda, PossibleActions):If agenda is empty, return (A, O, L)Pick (Q, An) from agendaAd = choose an action that adds Q.If no such action exists, fail.Add the link Ad Ac to L and the ordering Ad < Ac to OIf Ad is new, add it to A.Remove (Q, An) from agenda. If Ad is new, for each of its preconditions P add (P, Ad) to agenda.For every action At that threatens any link Choose to add At < Ap or Ac < At to O.If neither choice is consistent, fail.POP((A, O, L), agenda, PossibleActions)QApAcQ

اسلاید 38: Sussman Anomaly38A0(on C A)(on-table A)(on-table B)(clear C)(clear B)A ¥(on A B)(on B C)(on-table C)

اسلاید 39: Work on open precondition (on B C)39A0(on C A)(on-table A)(on-table B)(clear C)(clear B)A ¥(on A B)(on B C)A1: move B from Table to C(on B C)-(on-table B)-(clear C)(clear B)(clear C)(on-table B)(on-table C)

اسلاید 40: Work on open precondition (on A B)40A0(on C A)(on-table A)(on-table B)(clear C)(clear B)A ¥(on A B)(on B C)A1: move B from Table to C(on B C)-(on-table B)-(clear C)(clear B)(clear C)(on-table B)A2: move A from Table to B(clear A)(clear B)(on-table A)(on A B)-(on-table A)-(clear B)(on-table C)

اسلاید 41: Work on open precondition (on-table C)41A0(on C A)(on-table A)(on-table B)(clear C)(clear B)A ¥(on A B)(on B C)A1: move B from Table to C(on B C)-(on-table B)-(clear C)(clear B)(clear C)(on-table B)A2: move A from Table to B(clear A)(clear B)(on-table A)(on A B)-(on-table A)-(clear B)A3: move C from A to Table(clear C)(on C A)-(on C A)(on-table C)(clear A)(on-table C)

اسلاید 42: Analysis42POP can be much faster than the state-space planners because it doesn’t need to backtrack over goal orderings (so less branching is required).Although it is more expensive per node, and makes more choices than RegWS, the reduction in branching factor makes it faster, i.e., n is larger but b is smaller!

اسلاید 43: More analysis43Does POP make the least possible amount of commitment?Lifted POP: Using Operators, instead of ground actions,Unification is required

اسلاید 44: POP in the Blocks world44On(x,y), Cl(x), ~Cl(y), ~On(x,z)PutOn(x,y)Cl(x), Cl(y), On(x,z)PutOnTable(x)On(x, z) Cl(x)On(x,Table), Cl(x), ~On(x,z)

اسلاید 45: POP in the Blocks world45

اسلاید 46: POP in the Blocks world46

اسلاید 47: POP in the Blocks world47

اسلاید 48: POP in the Blocks world48

اسلاید 49: Example 249A0: StartAt(Home) Sells(SM,Banana) Sells(SM,Milk) Sells(HWS,Drill)A¥ : FinishHave(Drill) Have(Milk) Have(Banana) At(Home) Have(y)Buy (y,x) At(x), Sells(x,y)GO (x,y)At(x)At(y) ~At(x)

اسلاید 50: POP Example50finishstart

اسلاید 51: POP Example51finishstartHave(M) Have(B)Sells(SM, M) Sells(SM,B) At(H)

اسلاید 52: POP Example52finishstartHave(M)Buy (M,x1) At(x1) Sells(x1,M)Have(M) Have(B)Sells(SM, M) Sells(SM,B) At(H)

اسلاید 53: POP Example53finishstartHave(M)Buy (M,x1) At(x1) Sells(x1,M)Have(M) Have(B)Sells(SM, M) Sells(SM,B) At(H)

اسلاید 54: POP Example54finishstartHave(M)Buy (M,x1) At(x1) Sells(x1,M)Have(M) Have(B)Sells(SM, M) Sells(SM,B) At(H)

اسلاید 55: POP Example55finishstartHave(B)Have(M)Buy (M,x1) At(x1) Sells(x1,M)Buy (B,x2)Have(M) Have(B)At(x2) Sells(x2, B)Sells(SM, M) Sells(SM,B) At(H)

اسلاید 56: POP Example56finishstartHave(B)Have(M)Buy (M,x1) At(x1) Sells(x1,M)Buy (B,x2)Have(M) Have(B)At(x2) Sells(x2, B)Sells(SM, M) Sells(SM,B) At(H)

اسلاید 57: POP Example57finishstartHave(B)x1 = SMHave(M)Buy (M,x1) At(x1) Sells(x1,M)Buy (B,x2)Have(M) Have(B)At(x2) Sells(x2, B)Sells(SM, M) Sells(SM,B) At(H)

اسلاید 58: POP Example58finishstartHave(B)x1 = SMHave(M)x2 = SMBuy (M,x1) At(x1) Sells(x1,M)Buy (B,x2)Have(M) Have(B)At(x2) Sells(x2, B)Sells(SM, M) Sells(SM,B) At(H)

اسلاید 59: POP Example59finishstartHave(B)x1 = SMHave(M)x2 = SMGO (x3,SM)At(x3)At(SM)Buy (M,x1) At(x1) Sells(x1,M)Buy (B,x2)Have(M) Have(B)At(x2) Sells(x2, B)Sells(SM, M) Sells(SM,B) At(H)

اسلاید 60: POP Example60finishGO (x3,SM)startHave(B)x1 = SMHave(M)x2 = SMAt(x3)At(SM)Buy (M,x1) At(x1) Sells(x1,M)Buy (B,x2)Have(M) Have(B)At(x2) Sells(x2, B)Sells(SM, M) Sells(SM,B) At(H)

اسلاید 61: POP Example61finishGO (x3,SM)startHave(B)x1 = SMHave(M)x2 = SMAt(x3)At(SM)Buy (M,x1) At(x1) Sells(x1,M)Buy (B,x2)Have(M) Have(B)At(x2) Sells(x2, B)Sells(SM, M) Sells(SM,B) At(H)

اسلاید 62: POP Example62finishGO (x3,SM)startHave(B)x1 = SMHave(M)x2 = SMAt(x3)At(SM)x3 = HBuy (M,x1) At(x1) Sells(x1,M)Buy (B,x2)Have(M) Have(B)At(x2) Sells(x2, B)Sells(SM, M) Sells(SM,B) At(H)

اسلاید 63: POP Example63finishGO (x3,SM)startHave(B)x1 = SMHave(M)x2 = SMAt(x3)At(SM)x3 = HBuy (M,x1) At(x1) Sells(x1,M)Buy (B,x2)Have(M) Have(B)At(x2) Sells(x2, B)Sells(SM, M) Sells(SM,B) At(H)