Description

At(Home, S0) ^ ~Have(Milk, S0) ^ ~ Have(Bananas, S0) ^ ~Have(Drill, S0) ... no milk, banana, and Drill, Sells(HWS, Drill), Sells(SM, Milk), Sells(SM, Banana) ...

Transcripts

Arranging Chapter 11.1-11.3 Some material received from notes by Andreas Geyer-Schulz and Chuck Dyer

Planning issue Find a succession of activities that accomplishes a given objective when executed from a given starting world state . That is, given an arrangement of administrator portrayals (characterizing the conceivable primitive activities by the specialist), an underlying state depiction, and an objective state portrayal or predicate, compute an arrangement, which is a grouping of administrator examples, such that executing them in the underlying state will change the world to a state fulfilling the objective state depiction. Objectives are normally determined as a conjunction of objectives to be accomplished

Planning versus critical thinking Planning and critical thinking strategies can frequently take care of the same sorts of issues Planning is all the more intense on account of the representations and techniques utilized States, objectives, and activities are disintegrated into sets of sentences (for the most part in first-arrange rationale) Search regularly continues through arrangement space instead of state space (however there are additionally state-space organizers) Subgoals can be arranged freely, decreasing the intricacy of the arranging issue

Typical presumptions Atomic time: Each activity is inseparable No simultaneous activities are permitted (however activities don\'t should be requested as for each other in the arrangement) Deterministic activities: The aftereffect of activities are totally decided—there is no vulnerability in their belongings Agent is the sole reason for change on the planet Agent is omniscient: Has complete learning of the condition of the world Closed World Assumption: everything known not valid on the planet is incorporated into the state depiction. Anything not recorded is false.

B A C TABLE Blocks world The squares world is a miniaturized scale world that comprises of a table, an arrangement of pieces and a robot hand. Some area requirements: Only one piece can be on another square Any number of pieces can be on the table The hand can just hold one square Typical representation: ontable(a) ontable(c) on(b,a) handempty clear(b) clear(c)

Major methodologies GPS/STRIPS Situation analytics Partial request arranging Hierarchical deterioration (HTN arranging) Planning with limitations (SATplan, Graphplan) Reactive arranging

General Problem Solver The General Problem Solver (GPS) framework was an early organizer (Newell, Shaw, and Simon) GPS produced activities that lessened the distinction between some state and an objective state GPS utilized Means-Ends Analysis Compare what is given or known with what is wanted and select a sensible thing to do next Use a table of contrasts to distinguish strategies to decrease sorts of contrasts GPS was a state space organizer: it worked in the space of state space issues determined by an underlying state, some objective states, and an arrangement of operations

Situation math arranging Intuition: Represent the arranging issue utilizing first-arrange rationale Situation analytics gives us a chance to reason about changes on the planet Use hypothesis demonstrating to "demonstrate" that a specific grouping of activities, when connected to the circumstance describing the world state, will prompt a sought result

Situation math Initial state : a coherent sentence about (circumstance) S 0 At(Home, S 0 ) ^ ~Have(Milk, S 0 ) ^ ~ Have(Bananas, S 0 ) ^ ~Have(Drill, S 0 ) Goal state : ( s) At(Home,s) ^ Have(Milk,s) ^ Have(Bananas,s) ^ Have(Drill,s) Operators are depictions of how the world changes as an aftereffect of the specialist\'s activities: (a,s) Have(Milk,Result(a,s)) <=> ((a=Buy(Milk) ^ At(Grocery,s)) (Have(Milk, s) ^ a~=Drop(Milk))) Result(a,s) names the circumstance coming about because of executing activity an in circumstance s. Activity arrangements are additionally valuable: Result\'(l,s) is the consequence of executing the rundown of activities (l) beginning in s: ( s) Result\'([],s) = s ( a,p,s) Result\'([a|p]s) = Result\'(p,Result(a,s))

Situation math II An answer is an arrangement that when connected to the underlying state yields a circumstance fulfilling the objective inquiry: At(Home,Result\'(p,S 0 )) ^ Have(Milk,Result\'(p,S 0 )) ^ Have(Bananas,Result\'(p,S 0 )) ^ Have(Drill,Result\'(p,S 0 )) Thus we would expect an arrangement (i.e., variable task through unification, for example, p = [Go(Grocery), Buy(Milk), Buy(Bananas), Go(HardwareStore), Buy(Drill), Go(Home)]

Situation analytics: Blocks world Here\'s a case of a circumstance math standard for the pieces world: Clear (X, Result(A,S)) [Clear (X, S) ((A=Stack(Y,X) A=Pickup(X)) (A=Stack(Y,X) (holding(Y,S)) (A=Pickup(X) (handempty(S) ontable(X,S) clear(X,S))))] [A=Stack(X,Y) holding(X,S) clear(Y,S)] [A=Unstack(Y,X) on(Y,X,S) clear(Y,S) handempty(S)] [A=Putdown(X) holding(X,S)] English interpretation: A square is clear if (an) in the past state it was clear and we didn\'t lift it up or stack something on it effectively , or (b) we stacked it on something else effectively , or (c) something was on it that we unstacked effectively , or (d) we were holding it and we put it down . Whew!!! There\'s gotta be a superior way!

Situation analytics arranging: Analysis This is fine in principle, yet recollect that critical thinking (inquiry) is exponential in the most pessimistic scenario Also, determination hypothesis demonstrating just finds a proof (arrangement), not as a matter of course a decent arrangement So we confine the dialect and utilize an extraordinary reason calculation (an organizer) as opposed to general hypothesis prover

Basic representations for arranging Classic approach initially utilized as a part of the STRIPS organizer around 1970 States spoke to as a conjunction of ground literals at(Home) ^ ~have(Milk) ^ ~have(bananas) ... Objectives are conjunctions of literals, however may have variables which are thought to be existentially evaluated at(?x) ^ have(Milk) ^ have(bananas) ... Try not to need to completely indicate state Non-determined either couldn\'t care less or accepted false Represent numerous cases in little stockpiling Often just speak to changes in state as opposed to whole circumstance Unlike hypothesis prover, not looking for whether the objective is valid, but rather is there an arrangement of activities to achieve it

Operator/activity representation Operators contain three parts: Action depiction Precondition - conjunction of positive literals Effect - conjunction of positive or negative literals which portray how circumstance changes when administrator is connected Example: Op[Action: Go(there), Precond: At(here) ^ Path(here,there), Effect: At(there) ^ ~At(here)] All variables are all around evaluated Situation variables are understood preconditions must be valid in the state promptly before administrator is connected; impacts are genuine instantly after At(here) ,Path(here,there) Go(there) At(there) , ~At(here)

Blocks world administrators Here are the great fundamental operations for the pieces world: stack(X,Y): put square X on square Y unstack(X,Y): expel piece X from square Y pickup(X): pickup piece X putdown(X): put square X on the table Each will be spoken to by a rundown of preconditions a rundown of new truths to be included (include impacts) a rundown of realities to be evacuated (erase impacts) alternatively, an arrangement of (basic) variable imperatives For instance: preconditions(stack(X,Y), [holding(X), clear(Y)]) deletes(stack(X,Y), [holding(X),clear(Y)]). adds(stack(X,Y), [handempty, on(X,Y), clear(X)]) constraints(stack(X,Y), [X\==Y,Y\==table,X\==table])

Blocks world administrators II operator(unstack(X,Y), [on(X,Y), clear(X), handempty], [holding(X),clear(Y)], [handempty,clear(X),on(X,Y)], [X\==Y,Y\==table,X\==table]). operator(putdown(X), [holding(X)], [ontable(X),handempty,clear(X)], [holding(X)], [X\==table]). operator(stack(X,Y), Precond [holding(X),clear(Y)], Add [handempty,on(X,Y),clear(X)], Delete [holding(X),clear(Y)], Constr [X\==Y,Y\==table,X\==table]). operator(pickup(X), [ontable(X), clear(X), handempty], [holding(X)], [ontable(X),clear(X),handempty], [X\==table]).

STRIPS arranging STRIPS keeps up two extra information structures: State List - all presently genuine predicates. Objective Stack - a push down pile of objectives to be settled, with current objective on top of stack. On the off chance that present objective is not fulfilled by present state, analyze include arrangements of administrators, and push administrator and preconditions list on stack. (Subgoals) When a present objective is fulfilled, POP it from stack. At the point when an administrator is on top stack, record the use of that administrator on the arrangement grouping and utilize the administrator\'s add and erase records to redesign the present state.

A C B A B C Typical BW arranging issue Initial state: clear(a) clear(b) clear(c) ontable(a) ontable(b) ontable(c) handempty Goal: on(b,c) on(a,b) ontable(c) An arrangement: pickup(b) stack(b,c) pickup(a) stack(a,b)

A C B A B C Another BW arranging issue Initial state: clear(a) clear(b) clear(c) ontable(a) ontable(b) ontable(c) handempty Goal: on(a,b) on(b,c) ontable(c) An arrangement: pickup(a) stack(a,b) unstack(a,b) putdown(a) pickup(b) stack(b,c) pickup(a) stack(a,b)

A B C A B Goal state Goal connection Simple arranging calculations accept that the objectives to be accomplished are free Each can be understood independently and afterward the arrangements linked This arranging issue, called the "Sussman Anomaly," is the great case of the objective association issue: Solving on(A,B) first (by doing unstack(C,A), stack(A,B) will be fixed when settling the second objective on(B,C) (by doing unstack(A,B), stack(B,C)). Settling on(B,C) first will be fixed when fathoming on(A,B) Classic STRIPS couldn\'t deal with this, albeit minor alterations can inspire it to do basic cases Initial state

A B C A B Sussman Anomaly Achieve on(a,b) by means of stack(a,b)