Arranging otherwise known as Activity Arranging, Auto. Arranging and Booking.


50 views
Uploaded on:
Description
the robot. 6. STRIPS Language. through Examples. 7. Vacuum-Robot Example. Two rooms: R1 and R2 ... Right. 12. Activity Representation. Right. Precondition = In(Robot, R1) ...
Transcripts
Slide 1

Planning otherwise known as Action Planning, Auto. Arranging & Scheduling

Slide 2

Administrative HW2 and Final Project Proposal due at end of class HW3 accessible online

Slide 3

Agenda Representing arranging issues in STRIPS dialect Planning as inquiry Planning chart heuristic Backward fastening

Slide 4

The objective of activity arranging is to pick activities and requesting relations among these activities to accomplish indicated objectives Search-based critical thinking connected to 8-riddle was one case of arranging, yet our portrayal of this issue utilized particular information structures and capacities Here, we will build up a non-particular , rationale based dialect to speak to learning about activities, states, and objectives, and we will concentrate how seek calculations can misuse this representation

Slide 5

Knowledge Representation Tradeoff SHAKEY the robot Expressiveness versus computational productivity STRIPS: a straightforward, still sensibly expressive arranging dialect taking into account propositional rationale Examples of arranging issues in STRIPS Planning strategies Extensions of STRIPS Like programming, information representation is still a workmanship

Slide 6

STRIPS Language through Examples

Slide 7

R 1 R 2 Vacuum-Robot Example Two rooms: R 1 and R 2 A vacuum robot Dust

Slide 8

R 1 R 2 Logical "and" connective Propositions that "hold" (i.e. are valid) in the State Representation In(Robot, R 1 )  Clean(R 1 )

Slide 9

R 1 R 2 State Representation In(Robot, R 1 )  Clean(R 1 ) Conjunction of suggestions No refuted recommendation, for example, Clean(R 2 ) Closed-world presumption: Every recommendation that is not recorded in a state is false in that express No "or" connective, for example, In(Robot,R 1 )  In(Robot,R 2 ) No variable, e.g., x Clean(x)

Slide 10

Goal Representation Example: Clean(R 1 )  Clean(R 2 ) Conjunction of suggestions No nullified suggestion No "or" connective No variable An objective G is accomplished in a state S in the event that all the suggestions in G (called sub-objectives ) are additionally in S

Slide 11

R 1 R 2 R 1 R 2 Action Representation Right Precondition = In(Robot, R 1 ) Delete-list = In(Robot, R 1 ) Add-list = In(Robot, R 2 ) In(Robot, R 1 )  Clean(R 1 ) Right In(Robot, R 2 )  Clean(R 1 )

Slide 12

Action Representation Right Precondition = In(Robot, R 1 ) Delete-list = In(Robot, R 1 ) Add-list = In(Robot, R 2 ) Sets of suggestions Same structure as an objective: conjunction of suggestions

Slide 13

Action Representation Right Precondition = In(Robot, R 1 ) Delete-list = In(Robot, R 1 ) Add-list = In(Robot, R 2 ) An activity An is relevant to a state S if the recommendations in its precondition are all in S The use of A to S is another state acquired by erasing the recommendations in the erase list from S and including those in the add list

Slide 14

Other Actions Left P = In(Robot, R 2 ) D = In(Robot, R 2 ) A = In(Robot, R 1 ) Suck(R 1 ) P = In(Robot, R 1 ) D =  [empty list] A = Clean(R 1 ) Left P = In(Robot, R 2 ) D = In(Robot, R 2 ) A = In(Robot, R 1 ) Suck(R 2 ) P = In(Robot, R 2 ) D =  [empty list] A = Clean(R 2 )

Slide 15

Other Actions Left P = In(Robot, R 2 ) D = In(Robot, R 2 ) A = In(Robot, R 1 ) Suck(r) P = In(Robot, r) D =  [empty list] A = Clean(r)

Slide 16

Left P = In(Robot, R 2 ) D = In(Robot, R 2 ) A = In(Robot, R 1 ) Suck(r) P = In(Robot, r) D =  A = Clean(r) Action Schema It depicts a few activities, here: Suck(R 1 ) and Suck(R 2 ) Parameter that will get "instantiated" by coordinating the precondition against a state

Slide 17

R 1 R 2 Left P = In(Robot, R 2 ) D = In(Robot, R 2 ) A = In(Robot, R 1 ) Suck(r) P = In(Robot, r) D =  A = Clean(r) R 1 R 2 In(Robot, R 2 )  Clean(R 1 ) Action Schema Suck(R 2 ) In(Robot, R 2 )  Clean(R 1 )  Clean(R 2 ) r  R 2

Slide 18

Left P = In(Robot, R 2 ) D = In(Robot, R 2 ) A = In(Robot, R 1 ) Suck(r) P = In(Robot, r) D =  A = Clean(r) Action Schema R 1 R 2 R 1 R 2 Suck(R 1 ) In(Robot, R 1 )  Clean(R 1 ) In(Robot, R 1 )  Clean(R 1 ) r  R 1

Slide 19

C TABLE A B Blocks-World Example A robot hand can move obstructs on a table The hand can\'t hold more than one square at once No two pieces can fit straightforwardly on the same square The table is discretionarily expansive

Slide 20

C TABLE A B State Block(A)  Block(B)  Block(C)  On(A,TABLE)  On(B,TABLE)  On(C,A)  Clear(B)  Clear(C)  Handempty

Slide 21

C B A Goal On(A,TABLE)  On(B,A)  On(C,B)  Clear(C)

Slide 22

C B A Goal On(A,TABLE)  On(B,A)  On(C,B)  Clear(C)

Slide 23

C B A Goal An On(A,TABLE)  On(C,B)

Slide 24

Action Unstack(x,y) P = Handempty  Block(x)  Block(y)  Clear(x)  On(x,y) D = Handempty, Clear(x), On(x,y) A = Holding(x), Clear(y)

Slide 25

C A B Action Unstack(x,y) P = Handempty  Block(x)  Block(y)  Clear(x)  On(x,y) D = Handempty, Clear(x), On(x,y) A = Holding(x), Clear(y) Block(A)  Block(B)  Block(C)  On(A,TABLE)  On(B,TABLE)  On(C,A)  Clear(B)  Clear(C)  Handempty Unstack(C,A) P = Handempty  Block(C)  Block(A)  Clear(C)  On(C,A) D = Handempty, Clear(C), On(C,A) A = Holding(C), Clear(A )

Slide 26

A B Action Unstack(x,y) P = Handempty  Block(x)  Block(y)  Clear(x)  On(x,y) D = Handempty, Clear(x), On(x,y) A = Holding(x), Clear(y) C Block(A)  Block(B)  Block(C)  On(A,TABLE)  On(B,TABLE)  On(C,A)  Clear(B)  Clear(C)  Handempty  Holding(C)  Clear(A) C Unstack(C,A) P = Handempty  Block(C)  Block(A)  Clear(C)  On(C,A) D = Handempty, Clear(C), On(C,A) A = Holding(C), Clear(A )

Slide 27

A B Action Unstack(x,y) P = Handempty  Block(x)  Block(y)  Clear(x)  On(x,y) D = Handempty, Clear(x), On(x,y) A = Holding(x), Clear(y) C Block(A)  Block(B)  Block(C)  On(A,TABLE)  On(B,TABLE)  On(C,A)  Clear(B)  Clear(C)  Handempty  Holding(C)  Clear(A) Unstack(C,A) P = Handempty  Block(C)  Block(A)  Clear(C)  On(C,A) D = Handempty, Clear(C), On(C,A) A = Holding(C), Clear(A )

Slide 28

All Actions Unstack(x,y) P = Handempty  Block(x)  Block(y)  Clear(x)  On(x,y) D = Handempty, Clear(x), On(x,y) A = Holding(x), Clear(y) Stack(x,y) P = Holding(x)  Block(x)  Block(y)  Clear(y) D = Clear(y), Holding(x) A = On(x,y), Clear(x), Handempty Pickup(x) P = Handempty  Block(x)  Clear(x)  On(x,Table) D = Handempty, Clear(x), On(x,Table) A = Holding(x) Putdown(x) P = Holding(x),  Block(x) D = Holding(x) A = On(x,Table), Clear(x), Handempty

Slide 29

All Actions Unstack(x,y) P = Handempty  Block(x)  Block(y)  Clear(x)  On(x,y) D = Handempty, Clear(x), On(x,y) A = Holding(x), Clear(y) Stack(x,y) P = Holding(x)  Block(x)  Block(y)  Clear(y) D = Clear(y), Holding(x), A = On(x,y), Clear(x), Handempty Pickup(x) P = Handempty  Block(x)  Clear(x)  On(x,Table) D = Handempty, Clear(x), On(x,TABLE) A = Holding(x) Putdown(x) P = Holding(x),  Block(x) D = Holding(x) A = On(x,TABLE), Clear(x), Handempty A piece can simply fit on the table

Slide 30

R 1 R 2 Key-in-Box Example The robot must bolt the entryway and put the key in the case The key is expected to bolt and open the entryway Once the key is in the container, the robot can\'t get it back

Slide 31

R 1 R 2 Initial State In(Robot,R 2 )  In(Key,R 2 )  Unlocked(Door)

Slide 32

R 1 R 2 Goal Locked(Door)  In(Key,Box) [The robot\'s area isn\'t indicated in the goal]

Slide 33

R 1 R 2 Actions Grasp-Key-in-R 2 P = In(Robot,R 2 )  In(Key,R 2 ) D =  A = Holding(Key) Lock-Door P = Holding(Key) D =  A = Locked(Door) Move-Key-from-R 2 - into-R 1 P = In(Robot,R 2 )  Holding(Key)  Unlocked(Door) D = In(Robot,R 2 ), In(Key,R 2 ) A = In(Robot,R 1 ), In(Key,R 1 ) Put-Key-Into-Box P = In(Robot,R 1 )  Holding(Key) D = Holding(Key), In(Key,R 1 ) A = In(Key,Box)

Slide 34

Planning Methods

Slide 35

Suck(R 1 ) R 1 R 2 R 1 R 2 R 1 R 2 Forward Planning Right Left Initial state Suck(R 2 ) Goal: Clean(R 1 )  Clean(R 2 )

Slide 36

B C Pickup(B) C B C B An Unstack(C,A)) B C An A C B C A B A B C An A B C Forward Planning Goal: On(B,A)  On(C,B)

Slide 37

Need for an Accurate Heuristic Forward arranging just ventures the space of world states from the underlying to the objective state Imagine a specialists with an extensive library of activities, whose objective is G, e.g., G = Have(Milk) all in all, numerous activities are pertinent to any given state, so the expanding element is gigantic In any given state, most material activities are immaterial to achieving the objective Have(Milk) Fortunately, an exact reliable heuristic can be figured utilizing arranging charts

Slide 38

R 1 R 2 S 0 A 0 S 1 A 1 S 2 In(Robot,R 1 ) Clean(R 1 ) In(Robot,R 1 ) Clean(R 1 ) In(Robot,R 2 ) In(Robot,R 1 ) Clean(R 1 ) In(Robot,R 2 ) Clean(R 2 ) constancy activities Right Suck(R 1 ) Left Suck(R 2 ) Planning Graph for a State of the Vacuum Robot S 0 contains the state\'s recommendations (here, the underlying state) A 0 contains all activities whose preconditions show up in S 0 S 1 contains all recommendations that were in S 0 or are contained in the add arrangements of the activities in A 0 So, S 1 contains all genius

Recommended
View more...