015-Introduction to Robot Planning

This chapter is mainly about introduction to robot planning,which generally includes some dictionary sefinitions of plan,outline of lecture,conceptual model for planning,planning versus scheduling,three main types of planners,domain-specific planners and so on.
展开查看详情

1. Introduction to Robot Planning Slides modified from Dana S. Nau University of Maryland

2. Some Dictionary Definitions of “Plan” plan n. 3. A systematic arrangement of elements or important parts; a configuration or 1. A scheme, program, or method outline: a seating plan; the plan of a worked out beforehand for the story. accomplishment of an objective: a 4. A drawing or diagram made to scale plan of attack. showing the structure or arrangement 2. A proposed or tentative project or of something. course of action: had no plans for the evening. 5. A program or policy stipulating a service or benefit: a pension plan.

3.plan n. 1. A scheme, program, or method worked out beforehand for the accomplishment of an objective: a plan of attack.

4.plan n. 2. A proposed or tentative project or course of action: had no plans for the evening. Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/

5.plan n. 3. A systematic arrangement of elements or important parts; a configuration or outline: a seating plan; the plan of a story. Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/

6. plan n. 4. A drawing or diagram made to scale showing the structure or arrangement of something. Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/

7.plan n. 5. A program or policy stipulating a service or benefit: a pension plan.

8. Some Dictionary Definitions of “Plan” plan n. 3. A systematic arrangement of elements or important parts; a configuration or 1. A scheme, program, or method outline: a seating plan; the plan of a worked out beforehand for the story. accomplishment of an objective: a 4. A drawing or diagram made to scale plan of attack. showing the structure or arrangement 2. A proposed or tentative project or of something. course of action: had no plans for the evening. 5. A program or policy stipulating a service or benefit: a pension plan. • These two are closest to the meaning used in AI

9. 02Ca l mp b o a rd 03Es a t b lis h d a tu m p o in ta tb u ls e y e (0 .2 5 ,1 .0 0 ) 0 0 4 B V M C 1 0 .1 0 0 .3 4 0 1 In s ta l0 .1 5 -d ia me te rs id e -miln g to o l [a representation] 0 2 R o u g h sof id e future -milp o c k e ta t(-0 .2 5 ,1 .2 5 ) le n g th 0 .4 0 ,w id th 0 .3 0 ,d e p th 0 .5 0 behavior 0… usually a set of 3 F in is h s id e -m ilp o c k e ta t(-0 .2 5 ,1 .2 5 ) actions, with le n g th temporal 0 .4 0 ,w id th 0 .3 and0 ,d e p th 0 .5 0 0 4 R o u g h s id e -milp o c k e ta t(-0 .2 5 ,3 .0 0 ) other constraints le n g th 0 .4 0 ,w on id th them, 0 .3 0 ,d e p th 0 .5 0 for execution0 5 F inby is h ssome id e -m ilp oagent c k e ta t(-0 .2 5 ,3 .0 0 ) le n g th 0 .4 0 ,w id th 0 .3 0 ,d e p th 0 .5 0 or agents.0 0- 4Austin C V M C 1 0Tate .1 0 1 .5 4 0 1 In s ta l0 .0 8 -d ia me te re n d -miln g to o l [MIT Encyclopedia 0 0 4 T V M C 1 2 .5 0 of [.] 4 .8 7the 0 1T o ta ltim e o n V M C 1 Cognitive 0 0 5Sciences, A E C 1 0 .0 0 3 21999] .2 9 0 1 P re -c le a n b o a rd (s c ru b a n d w a s h ) 0 2 D ry b o a rd in o v e n a t8 5 d e g .F 005BEC13 00 . 0 0 .4 8 0 1 S e tu p 0 2 S p re a d p h o o t re s is fro t m1 8 0 0 0 R P M s p in n e r 0 0 5 C E C 1 3 0 .0 0 2 .0 0 0 1 S e tu p 02Ph oo t lith o g ra p h y o fp h o to re s is t us n i g p h o to o t o in l "re a l.ig e s " 0 0 5 D E C 1 3 0 .0 0 2 0 .0 0 0 1 S e tu p 02Ec t hni g o fc o p p e r 0 0 5 T E C 1 9 0 .0 0 5 4 .7 7 0 1 T o ta ltime o n E C 1 0 0 6 A M C 1 3 0 .0 0 4 5 . 7 0 1 S e tu p 0 2 P re p a re b o a rd o f rs o ld e rin g 0 0 6 B M C 1 3 0 .0 0 0 .2 9 0 1 S e tu p A portion of a manufacturing process plan Dana Nau: Lecture slides for Automated Planning 0 2 Commons Licensed under the Creative S c re e nAttribution-NonCommercial-ShareAlike p rin ts o ld e rs to p o n b o a rd License: http://creativecommons.org/licenses/by-nc-sa/2.0/

10. Generating Plans of Action • Computer programs to aid human planners – Project management (consumer software) – Plan storage and retrieval P ro c e s s e s : • e.g., variant process planning in manufacturing O p n A B C /WWS e tu p R u n im t e L N D e s c rip tio n 0 0 1 A V M C 1 2 .0 0 0 0 . 0 0 1 O rie n b t o ad r 0 2 C la mp b o a rd 0 3 E s ta b lis h d a tu mp o in ta tb u ls e y e (0 .2 5 ,1 .0 0 ) 0 0 1 B V M C 1 0 .1 0 0 .4 3 0 1 In s ta l0 .3 0 -d ia me te rd rilb it 0 2 R o u g h d rila t(1 .2 5 ,-0 .5 0 )to d e p th 1 .0 0 03Fn i is h d ila r t(1 2 . 5 -0 , .5 0 )to d e p th 1 .0 0 0 0 1 C V M C 1 0 .1 0 0 7 . 701n I s at l0 2 . 0d- ia me te rd rilb it – Automatic schedule generation 0 2 R o u g h d rila t(0 .0 0 ,4 .8 8 )to d e p th 1 .0 0 0 3 F in is h d rila t(0 .0 0 ,4 .8 8 )to d e p th 1 .0 0 [.] 0 0 1 T V M C 1 2 .2 0 1 .2 0 0 1 T o ta ltime o n V M C 1 [.] 0 0 4 A V M C 1 2 .0 0 0 .0 0 0 1 O rie n tb o a rd 0 2 C la mp b o a rd 0 3 E s ta b lis h d a tu mp o in ta tb u ls e y e (0 .2 5 ,1 .0 0 ) 0 0 4 B V M C 1 0 .1 0 0 .3 4 0 1 In s ta l0 .1 5 -d ia me te rs id e -miln g to o l 0 2 R o u g h s id e -milp o c k e a t t(-0 2 . 5 ,1 .2 5 ) • various OR and AI techniques le n g th 0 4 . 0w , id th 0 .3 0 d , e p th 0 .5 0 0 3 F in is h s id e -m ilp o c k e ta t(-0 .2 5 ,1 .2 5 ) le n g th 0 .4 0 ,w id th 0 .3 0 ,d e p th 0 .5 0 0 4 R o u g h s id e -milp o c k e ta t(-0 .2 5 ,3 .0 0 ) le n g th 0 .4 0 ,w id th 0 .3 0 ,d e p th 0 .5 0 05Fn i is h s d i em - ilp o c k e at t(-0 2 . 5 ,3 .0 0 ) le n g th 0 .4 0 ,w d i th 0 .3 0 ,d e p h t 05. 0 0 0 4 C V M C 1 0 .1 0 1 .5 4 0 1 In s ta l0 .0 8 -d ia me te re n d -miln g to o l [.] 0 0 4 T V M C 1 2 .5 0 4 .8 7 0 1 T o ta ltime o n V M C 1 0 0 5 A E C 1 0 .0 0 3 2 .2 9 0 1 P re -c le a n b o a rd (s c ru b a n d w a s h ) 0 2 D ry b o a rd in o v e n a t8 5 d e g .F 005BEC1300 . 0 0 .4 8 0 1 S e tu p 02Sp e r adpho o t re s is fro t m1 8 0 0 0 R P M s p in n e r • For some problems, we would like generate 0 0 5 C E C 1 3 0 .0 0 2 .0 0 0 1 S e tu p 0 2 P h o to lith o g ra p h y o fp h o to re s is t u s in g p h o to to o lin "re a l.ig e s " 0 0 5 D E C 1 3 0 .0 0 2 0 .0 0 0 1 S e tu p 02Ec t hni g o fc o p p e r 0 0 5 T E C 1 9 0 .0 0 5 4 .7 7 0 1 T o ta ltime o n E C 1 0 0 6 A MC 1 3 0 .0 0 4 .5 7 0 1 S e tu p 0 2 P re p a re b o a rd fo rs o ld e rin g 0 0 6 B MC 1 3 0 .0 0 0 .2 9 0 1 S e tu p plans (or pieces of plans) automatically 0 2 S c re e n p in r ts o ld e rs o t p o n b o a rd 0 0 6 C MC 1 3 0 0 . 0 7 .5 0 0 1 S e tu p 0 2 D e p o s its o ld e rp a s te a t(3 .3 5 ,1 .2 3 )o n b o a rd u s in g n o z z le [.] 3 1 D e p o s its o ld e rp a s te a t(3 .5 2 ,4 .0 0 )o n b o a rd u s in g n o z z le 0 0 6 D MC 1 0 0 . 0 5 .7 1 0 1 D ry b o a rd ni o v e n a t8 5 d e g .F to s o lid ify s o ld e rp a s te 0 0 6 T MC 1 9 0 0 . 0180 . 701T oat ltime o n M C 1 [.] 0 1 1 A T C 1 0 .0 0 3 5 .0 0 0 1 P e rfo rmp o s t-c a p te s tin g o n b o a rd 0 1 1 B T C 1 0 .0 0 2 9 .6 7 0 1 P e rfo rmfi n a lin s p e c tio n o fb o a rd – Much more difficult 0 1 1 T T C 1 0 .0 0 6 4 .6 7 0 1 T o ta ltime o n T C 1 9 9 9 T 3 1 9 .7 0 4 0 3 .3 7 0 1 T o ta ltime to ma n u fa c tu re – Automated-planning research is starting to pay off • Here are some examples …

11. Space Exploration • Autonomous planning, scheduling, control – NASA: JPL and Ames • Remote Agent Experiment (RAX) – Deep Space 1 • Mars Exploration Rover (MER) Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/

12. Manufacturing • Sheet-metal bending machines - Amada Corporation – Software to plan the sequence of bends [Gupta and Bourne, J. Manufacturing Sci. and Engr., 1999] Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/

13. Games • Bridge Baron - Great Game Products – 1997 world champion of computer bridge [Smith, Nau, and Throop, AI Magazine, 1998] – 2004: 2nd place Us:East declarer, West dummy Finesse(P1; S) Opponents:defenders, South & North Contract:East – 3NT On lead:West at trick 3 East:KJ74 West: A2 LeadLow(P1; S) FinesseTwo(P ; S) Out: QT98653 2 PlayCard(P1; S, R1) EasyFinesse(P2; S) StandardFinesse(P2; S) BustedFinesse(P2; S) West— 2 … (North— Q) … (North— 3) StandardFinesseTwo(P2; S) StandardFinesseThree(P3; S) FinesseFour(P4; S) PlayCard(P2; S, R2) PlayCard(P3; S, R3) PlayCard(P4; S, R4) PlayCard(P4; S, R4’) Dana Nau: Lecture slides for Automated Planning North— 3 East— J South— 5 South— Q Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/

14. Outline of lecture • Conceptual model for planning • Example planning algorithms • What’s bad • What’s good

15.Conceptual model for planning

16.Conceptual Model 1. Environment State transition system System   = (S,A,E,) S = {states} A = {actions} E = {exogenous events}  = state-transition function

17. s1 s0 State Transition put System take  = (S,A,E,) location 1 location 2 location 1 location 2 • S = {states} move2 move1 move2 move1 s3 s2 • A = {actions} put • E = {exogenous events} • State-transition take function location 1 location 2 location 1 location 2 unload load : S x (A  E)  2S s4 s5 – S = {s0, …, s5} move2 – A = {move1, move2, put, take, load, unload} move1 – E = {} location 1 location 2 location 1 location 2 – : see the arrows The Dock Worker Robots (DWR) domain

18. Conceptual Model 2. Controller Controller Given observation o in O, produces Observation function action a in A h: S  O s3 location 1 location 2

19. Conceptual Model 3. Planner’s Input Planning problem Planner Omit unless planning is online

20. s1 s0 Planning put Problem take location 1 location 2 location 1 location 2 Description of  move1 move2 move1 move2 Initial state or set of states s3 s2 Initial state = s0 put Objective Goal state, set of goal take states, set of tasks, location 1 location 2 location 1 location 2 “trajectory” of states, unload load objective function, … s4 s5 Goal state = s5 move2 move1 location 1 location 2 location 1 location 2 The Dock Worker Robots (DWR) domain

21.Conceptual Model 4. Planner’s Output Planner Instructions to the controller

22. s1 s0 Plans put Classical plan: a sequence of take take actions location 1 location 2 location 1 location 2 move2 move1 move1 move2 move1 take, move1, load, move2 s3 s2 put Policy: partial function from S into A take location 1 location 2 location 1 location 2 {(s0, take), unload load load (s1, move1), s4 s5 (s3, load), move2 move2 (s4, move2)} move1 location 1 location 2 location 1 location 2 The Dock Worker Robots (DWR) domain

23. Planning Versus Scheduling • Scheduling – Decide when and how to perform a given set of actions Scheduler • Time constraints • Resource constraints • Objective functions – Typically NP-complete • Planning – Decide what actions to use to achieve some set of objectives – Can be much worse than NP-complete; – worst case is undecidable

24. Three Main Types of Planners 1. Domain-specific 2. Domain-independent 3. Configurable • I’ll talk briefly about each

25.Domain-Specific Planners

26. 1. Domain-Specific Planners • Made or tuned for a specific domain • Won’t work well (if at all) in any other domain • Most successful real-world planning systems work this way

27.Domain-Independent Planners

28. Types of Planners 2. Domain-Independent • In principle, a domain- independent planner works in any planning domain • Uses no domain-specific knowledge except the definitions of the basic actions

29. Types of Planners 2. Domain-Independent • In practice, – Not feasible to develop domain-independent planners that work in every possible domain • Make simplifying assumptions to restrict the set of domains – Classical planning – Historical focus of most automated-planning research Dana Nau: Lecture slides for Automated Planning Licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/