برنامه ریزی AI

صفحه 1:


صفحه 2:
The planning problem ا لش ‎Inputs:‏ © ‎A description of the world state‏ .1 ‎The goal state description‏ .2 ‎A set of actions‏ .3 © Output: A sequence of actions that if applied to the initial state, transfers the world to the goal state 

صفحه 3:
An example - Blocks world << ‏لل‎ ‎" Blocks on a table " Can be stacked, but only one block on top of another " A robot arm can pick up a block and move to another position * On the table * On another block © Arm can pick up only one block at a time * Cannot pick up a block that has another one on it 

صفحه 4:
STRIPS Representation ‎١‏ شخ ‎State is a conjunction of positive ground‏ 5 ‎literals‏ ‎On(B, Table) A Clear (A)‏ ‎Goal is a conjunction of positive ground‏ " ‎literals‏ ‎Clear(A) A On(A,B) A On(B, Table)‏ ‎STRIPS Operators‏ © ‎Conjunction of positive literals as preconditions‏ * ‎* Conjunction of positive and negative literals as effects 

صفحه 5:
More on action schema ‏ليسي ا‎ ©" Example: Move (b, x, y) * Precondition: Block(b) A Clear(b) A Clear(y) A On(b,x) A (b # x) A(b # y) A (y # x) * Effect: =Clear(y) A ~On(b,x) A Clear(x) A On(b,y) سپس سسپست Deets best (Bet best " An action is applicable in any state that satisfies its precondition 

صفحه 6:
STRIPS assumptions ۳ © Closed World assumption * Unmentioned literals are false (no need to explicitly list out) © STRIPS assumption * Every literal not mentioned in the “effect” of an action remains unchanged 5 Atomic Time (actions are instantaneous) 

صفحه 7:
STRIPS expressiveness "_______ ‏ا‎ ‎“Literals 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 actions 5 No disjunctive goals: On(B, Table) V On(B, C) No conditional effects: On(B, Table) if -On(A, Table) 

صفحه 8:
Planning algorithms —_ _ _ _ © Planning algorithms are search procedures = Which state to search? * State-space search ™ Each node is a state of the world ™ Plan = path through the states * Plan-space search ™ Each node is a set of partially-instantiated operators and set of constraints = Plan = node 

صفحه 9:
State search 5* ‏[آ[آ[كك سس سي‎ © Search the space of situations, which is connected by operator instances " The sequence of operators instances = plan © We have both preconditions and effects available for each operator, so we can try different searches: Forward vs. Backward 

صفحه 10:
Planning: Search Space 6 1 B ۱۱ (B Aj |B IA] |C B 0 2 A 0 ‏عالظالفا‎ 6 B 2 A} |B Al ‏ع6‎ ‎AI 2 ‏اظ‎ BI |C اهاس تداع 

صفحه 11:
Forward state-space search 211592 ay ° Progression 5 Initial state: initial state of the problem © Actions: » Applied to a state if all the preconditions are satisfied * Succesor state is built by updating current state with add and delete lists = Goal test: state satisfies the goal of the problem 

صفحه 12:
Progression (forward م77 لوعتقعع ProgWS(world-state, goal-list, PossibleActions, path) If world-state satisfies all goals in goal-list, 1. Then return path. 2. Else Act = choose an action whose precondition is true in world-state ) If no such action exists Then fail Else return ProgWS( result(Act, world- state), goal-list, PossibleActions, concatenate(nath. Act) ) 

صفحه 13:
Forward search in the Blocks world CS | es 35 و _ Ie ta Ho / 

صفحه 14:
Forward state-space search a ‏ل‎ ‎cs ‎5 Advantages * No functions in the declarations of goals J] search state is finite * Sound * Complete (if algorithm used to do the search is complete) 5 Limitations * Irrelevant actions {j not efficient * Need heuristic or pruning procedure 

صفحه 15:
Backward state-space search (1) a © Regression © Initial state: goal state of the problem 5 Actions: * Choose an action that = Is relevant; has one of the goal literals in its effect set = Is consistent; does not negate another literal * Construct new search state = Remove all positive effects of A that appear in goal ™ Add all preconditions, unless already appears © Goal test: state is the initial world state 

صفحه 16:
Regression (backward path) 1 If initial-state satisfies all of current-goals 2. Then return path 3. Else Act = choose an action whose effect matches one of current-goals If no such action exists, or the effects of Act contradict some of current-goals, then fail ». G = (current-goals - goals-added- by(Act)) + preconds(Act) If G contains all of current-goals, then fail Return RegWS(initial-state, G, PossibleActions, concatenate(Act, path)) 

صفحه 17:
Backward state-space search (2) 7 5 Advantages * Consider only relevant actions J much smaller branching factor 5 Limitations * Still need heuristic to be more efficient 

صفحه 18:
Comparing ProgWS and EE ° Both algorithms are * sound (they always return a valid plan) * complete (if a valid plan exists they will find one) | Running time is O(b") where b = branching factor, n = number of “choose” operators 

صفحه 19:
Blocks world: STRIPS wy OS OS ‏سا7‎ 5 Pickup(x) © OvGraok(x,y) Pre: on(x, Table), ret va(x, v), oe clear(x), ae et: va(x, y), oF Del: on(x, Table), ae ‏ل اك‎ (v) Add: holding(x) "G x, “ Putdown(x) er vleur(v) Pre: holding(x) Oet: kokdicrey(x), chear(v) Del: holding(x) Odd: va(x, y), 3 Add: on(x, Table), ae 

صفحه 20:
STRIPS Planning ‏لها‎ 5 [o] ۲ [1 © Current state: * on(A,table), on(C, B), on(B,table), on(D,table), clear(A), clear(C), clear(D), ae. = Goal » on(A,C), on(C,D) 

صفحه 21:
STRIPS Planning lan: Goalstackoniasc).onio.a) ‏ا‎ on(A,C) Stack(A, C) holding(A), clear(C) holding(A) Pickup(A) on(A,Table), clear(A), ae جا وله ۲ jtable), on(C, B), on(B,table), on(D,table), clear(A), clear(C), clear(D), ae irrent State 

صفحه 22:
STRIPS Planning Plan: Goalstackoniac),onto.a) fl on(A,C) Stack(A, C) Pickup(x) holding(A), clear(C) Pre: on(x,Table), clear(x), ae holding(A) Pickup(A) Del: on(x, Table), ae, Add: holding(x) جا وله ۲ (0)) له , (۱))انه ,)ان ,)9 ننه ‎con((D)‏ , (ها هر )۳۲ ,((۳ ‎ibg(A), on(C,,‏ irrent State 

صفحه 23:
STRIPS Planning Plan: Goalstackoniac,onto.a) fl Pickup(A) on(A,C) Stack(A, C) Stack(x, y) Pre: holding(x), clear(y) Del: holding(x), clear(y) Add: on(x, y), ae 0 ۳1 inGIAdNG( G) BONdB (Ebab)leo nD (fbicled adeGr| AdjadesDICheclear(D). irrent State 

صفحه 24:
STRIPS Planning Pickup(A) on(D, A) Stack(A, C) Stack(D,A) holding(D), clear(A) holding(D) Pickup(D) on(D,Table), clear(D), ae “he ۳1 AD) ond CE) oon ‏اجه اه [( راهن تلاصا و3‎ )0( ae. irrent State 

صفحه 25:
STRIPS Planning Plan Goalstackaniac).onio.a fl Pickup(A) on(D, A) Stack(A, C) Stack(D,A) Pickup(D) holding(D), clear(A) holding(D) 0 1 ۳1 M6) con{(C, EB), con( ER tedts), hen DIlecdeGk|Adeclear(D) irrent State 

صفحه 26:
STRIPS Planning: Getting it Wrong! on(D,A) Stack(D, A) holding(D), clear(A) holding(D) Pickup(D) on(D,Table), clear(D), ae جا وله ۲ .table), on(C, B), on(B,table), oo BitahD3), clen(), cisen(O), cltsan(), a€ irrent State 

صفحه 27:
STRIPS Planning: Getting it Wrong! Plans GoalstackoniA.c),onto.a) Pickup(D) on(D,A) Stack(D, A) Hi ۳221 ١ Herts), con((C, EB), cov( EB Heidt), Fooling LD | ‏(۲)0هع۱ععع] هه که له‎ irrent State 

صفحه 28:
STRIPS Planning: Getting it Wrong! Plans Goalstackoniasc).onio.a) ‏ا‎ Pickup(D) Stack(D, A) Now What? — We chose the wrong goal first — Ais no longer clear. — stacking D on A messes up the preconditions for actions to accomplish on(A, C) SNS — either have to backtrack, or else we must undo ga the previous actions ۳221 \,table), on(C, B), on(B,table), on(D,A), clear(C), clear(D), ae. irrent State 

صفحه 29:
STRIPS planning (Goalstack planning) شش يفك ‎Works on one subgoal at a time‏ " ‎Insists on completely achieving that‏ 5 ‎subgoal before considering other subgoals‏ ‎May have to backtrack:‏ | * If it chooses the wrong order to work on the subgoals * If it chooses the wrong action to achieve a subgoal | Searches backwards from goal - uses goal to guide choice of actions 

صفحه 30:
Limitation of state-space search © Linear planning or Total order planning = Example * Initial state: all the blocks are clear and on the table * Goal: On(A,B) A 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 plans ‏ص‎ ‎© Nodes 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:
Partial Order Plans: Total Order Plans: Start Start| |Start||Start| |Start|/Start| |Start 2 1 1 1 1 1 1 ‏عم ]| تحونظ | غطونعا‎ | [Left |[Right ]/ Lett Left Right Sock | | Sock || Sock | | Sock |] Sock || Sock Sock Sock | | | | | | Left ]/ Left | [Right |[Right ] [Right] Left ‎on Right Sqckon | Sock || Sock |_| Sock || Sock | | Shoe | Shoe‏ دي ‎Left Right 1 | 1 J‏ ‎Shoe Shoe‏ ‎ ‎ ‎ ‎ ‎Right] [Left |[Right]/ Left ] [Left |[Right Shoe| | Sock || Shoe || Shoe | | Sock || Sock ‎ ‎ ‎ ‎ ‎Left ] [Right]/ Left ||Right|) Left | Right Shoe| | Shoe || Shoe || Shoe || Shoe | Shoe ‏لا 1 ] | ‎Finish Finish Finish Finish Finish Finish ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 33:
P.O. plans in POP 211101111111111 = Plan = (A, O, L), where * Ais the set of actions in the plan * Ois a set of temporal orderings between actions * Lis a set of causal links linking actions via a literal Causal 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- b 

صفحه 34:
Threats to causal links <<) ‏آذآ‎ Step At threatens link —— if: 1. At has (~Q) as an effect 2. At could come between Ap and Ac, i.e., 0 is consistent with Ap < At < Ac 

صفحه 35:
Threat Removal " Threats must be removed to prevent a plan from failing © Demotion adds the constraint A, < A, to prevent clobbering, i.e. push the clobberer before the producer 4 Promotion adds the constraint A, < A, to prevent clobbering, i.e. push the clobberer after the consumer 

صفحه 36:
Initial (Null) Plan © Initial plan has ~A={A,A} -O={A, <A} *L={} 4 A, (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 algorithm 1 If agenda is empty, return (A, O, L) 2. Pick (Q, An) from agenda 3. Ad = 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 If 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. s. For every action At that threatens any like —— > Pe 1. Choose to add At < Ap or Ac > At to O. If neither choice is consistent, fail. «. POP((A, O, L), agenda, PossibleActions) 

صفحه 38:
Sussman Anomaly ‏ا اط‎ Po (oO ®) ‏فا و‎ (cher O) (cer ®) ‎(os ®) ) 0 0(‏ روصم ‎© ‎3 

صفحه 39:
Work on open precondition (on B C) Po (oO ®) ‏فا و‎ (cher O) (cer ®) (cer ®) (cea ©) ‏یی‎ B) 0: wove 0 ‏مس‎ © -(ownble ®) {ele ©) (vg 0) (okt ©) — (ex ®®) (a OO) © 3 

صفحه 40:
Work on open precondition (on A B) ‎(ce ©) (eer)‏ ی سس وم ‎(cea ®) (cer) — (ote ®) ‎2: wove © Prow Dab ® Loy end) 4 3 eee) ‏(ماحطع‎ OO), 0: wove © Prow Poble i 0 ‎orb) -(cear ©) (oa ® OC) ‎(orkbeO) (oa) (a BO) ‎© ‎3 

صفحه 41:
Work on open precondition (on-table C) (or ‏یی (ه‎ ©( (2M. ©) (dew 0( (clear ®) (0 ®) ‏سم‎ 0( 9: wore O Prow © ۵ Publ (orth ©) (oa ®) (ck ®) (cher @) (clear ®) (oerteble ©( (cea ®) (cea ©) ‏یی‎ ©( OO: wre O Prow Table to © —_————O1: woe © Prow Doble by O شنت 7° )® جام )® ‎“(ort‏ (orb ©) (oa) (a BO) © 3 

صفحه 42:
Analysis my |" POP 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., 7 is larger but 6 is smaller! 

صفحه 43:
More analysis a ۲7 Does POP make the least possible amount of commitment? © Lifted POP: Using Operators, instead of ground actions, 5 Unification is required 

صفحه 44:
POP in the Blocks world a PutOn(x,y) C(x), Cl(y), On(x,y), Cx), On(x,z) ~Ci(y), ~On(x,z) PutOnTable(x) On(x, z) On(x,Table), 0100 Cl(x), ~On(x,z) 

صفحه 45:
POP in the Blocks world as (On(A) OmA, Table) CKB) OMB, Table) CHC) On(AB) 6980 FINISH 

صفحه 46:
POP in the Blocks world yy ۳ On{C,A) On(A, Table) CB) On(B, Table) CXC) START Puton(B,c) گام _ دامن FINISH 

صفحه 47:
POP in the Blocks world On(C,A) On(A, Table) ChB) On(B Table) CC) ۳ Puon(AB) Clobbers ‏رها‎ ‏تست‎ ‎2 ‏«هله_«‎ 40 ‎OntAz) CIB)‏ اس ‎ ‎ ‎ ‎-| Purons,c) ‎ ‎ ‏سا هبو [ ۳:۸ ‎۱ ‏واه _ همه ‎ ‎BEE ‎FINISH ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 48:
POP in the Blocks world (On(C.A) OniA, Table) CNB) On(B. Table) C1/C) 2 9:6 PutOn(A.8) clobbers CHB) SSorder after PutOn(E.c) PuOnTable(c) ‏وه‎ لي 0001 واه عجامه واه 5 بح ره مه ره .008نم ۳ PutOA.B) ١ onda.) onc) FINISH 

صفحه 49:
Example 2 ‏سس اا‎ 5 Ay: Start » At(Home) Sells(SM,Banana) Sells(SM,Milk) Sells(HWS, Drill) oA, : Finish * Have(Drill) Have(Milk) Have(Banana) At(Home) Buy (y,x) GO (x,y) At(x), Sells(x,y) | Have(y) At(x) At(y) ~At(x) 

صفحه 50:
POP Example 1521 ‏ع ات‎ start 1 finish 

صفحه 51:
POP Example 2 start Sells(SM, M) Sells(SM,B) At(H) 1 Have(M)} Have(B) finish 

صفحه 52:
POP Example Sells(SM, M) Sells(SM,B) At(H) ١ At(x,) Sells(x,,M) Buy (M,x,) Have(M) Have(M)} Have(B) finish 

صفحه 53:
POP Example ۲ ‏تسه‎ start Sells(SM, M) Sells(SM,B) At(H) ١ At(x,) Sells(x,,M) Buy (M,x,) Have(M) Have(M)} Have(B) finish 

صفحه 54:
POP Example 2 start Sells(SM, M) Sets(SM,B) At(H) | 7 7 7 2 7 At(x,) Sells(x,,M) »” Buy (M,x,) Have(M) ۰ ۰ ۰ ۷2۷۵ Have(B) finish 

صفحه 55:
POP Example 5 ‏مح‎ start Sells(SM, M) Sets(SM,B) At(H) | 7 7 7 2 7 At(x,) Sells(x,,M) Ke At(x,) Sells(x,, B) Buy (B,x2) Have(B) Buy (M,x,) Have(M) ۰ ۰ ۰ ۷2۷۵ Have(B) finish 

صفحه 56:
POP Example 211101111111111 start Sells(SM, M) Sefs(SM,B) At(H) 7 0 ‏َه‎ ۰ ۰ ۰ 7 7 2 7 ۰ At(x,) Sells(x,,M) Ke S\At(x,) Sells(x,, B) Buy (B,x2) ‏*م‎ _Have(B) 2 2 2 ۳2/۵ saves) finish Buy (M,x,) Have(M) 4 ۰ ١ ١ ١ ١ I 1 ١ ١ 1 1 ۰ 1 ١ 

صفحه 57:
POP Example go xX, = SM start Sells(SM, M) seinem.) At(H) 5 ۰ ۰ ۰ ۰ ۰ ۰ S\At(x,) Sells(x,, B) 7 7 3 5 7 At(x,) Sells(x,,M) »” Buy (B,x2) Have(B) Buy (M,x,) Have(M) + ۰ Sy FavetMy saves) finish 2 2 

صفحه 58:
POP Example ۲: xX, = SM x,=5M start Sells(SM, M) sea 8) At(H) Sy 1 7 1 ۰ At(x,) Sells(x,,M) »” 1 ‏0اه‎ “Sells(x,, B) 1 Buy (M,x,) ۱ Buy (B,x,) ۱۲۷۵۷۵۲۷ +. ۱ Have(B) . i 3 0 FavetMy saves) finish 

صفحه 59:
POP Example 211101111111111 eg xX, = SM x, = SM stale At(x,) Sells(SM, M) sea B) At(H) GO (x,5M) 5 3 ۱ = At(SM) 9 ۰ 5 1 2 i \ At(x,) Sells(x,,M) 2 At(x,) ‏,یل)کااع5‎ 8( Buy (M,x,) ۱ Buy (B,x,) ۱۲۱۵۷۵) 7+. ۱ Have(B) . i 7 1 FavetMy saves) finish 

صفحه 60:
POP Example xX, = SM x, = SM stat At(x;) Sells(SM, M) Sefs(SM.B) At(H) GO (x,,5M) ‘ 0 ۰ --77 7 At(SM) 4 ۰ At(x,) Sells(x,,M) acc om: ! SV At(x# 2 ells(x,, B) Buy (M,x,) ۱ Buy (B,x,) ۱۲۷۵۷۵۲۷ +. ۱ Have(B) ۰ i er 1 Tan sete 

صفحه 61:
‎ells(x,, B)‏ ۳ ل ‎ ‎Buy (B,x2) 77 _Have(B) ‎ ‎start ‎ ‎ ‎POP Example ‎ ‎3 ‎. ‎ ‎ ‎۰ ‎ ‎ ‎xX, = SM xX, = SM ‎ ‎At(x,) Sells(x;,M) g2-- 7 ‎ ‎Buy (M,x,) Have(M) ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 62:
POP Example ey tart 1 x, = SM Stal 14 At) x= Sells(SM, M) S€FXSWB) AH) GO (x,,SM) Zh At(x,) Sells(x,,M) acc ar SV At(x# 2 ells(x,, B) Buy (B,x2) ‎_Have(B)‏ *م ‎Buy (M,x,) Have(M) 4 ۰ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 63:
POP Example xX, = SM fait x = SM sta ” ‏لس‎ At(x,) Sells(x,,M) acc ar SV At(x# 2 ells(x,, B) Buy (B,x2) ‎_Have(B)‏ *م ‎Buy (M,x,) Have(M) 4 ۰ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎