015-Introduction to Robot Planning

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/