Theory Versus Practice in AI Planning - Unibs.it

1、Ordered Task Decomposition:Theory and PracticeDana S. NauDept. of Computer Science, andInstitute for Systems ResearchUniversity of Maryland, College Park, MDGenerating Plans of ActionPrograms to aid human plannersProject management (consumer software)Plan storage and retrieval(e.g., variant process

2、planning)Automatic schedule generation (various OR and AI techniques)For some problems, really want togenerate plans automaticallyMuch more difficultVery few successful programs for realistic problemsAI planning research is starting to pay offOf the few really good plan generation systems for practi

3、cal problems, most involve AI planning techniquesHowever, AI Planning Is Different in PracticeThan it Was in TheoryUnstack(x,y) Pre:on(x,y), clear(x), handempty Del:on(x,y), clear(x), handempty Add:holding(x), clear(y)Theory:Symbolic computations (STRIPS operators)Single agent (the planner)Perfect i

4、nformationPractice:Complex numeric computations(geometry, images, probabilities)Multiple agentsImperfect information, external information sourcesGoalDevelop synergybetween theoryand applicationsBy understanding what worksin practical planning situations,we can develop better theories of planningBet

5、ter theories of planningcan lead to better real-world plannersTheoryApplicationsApproach (and Outline)TheoryApplications6. Evacuationplanning3. Electronic Designand Manufacturing5. SHOP1. Principles ofHTN planning2. Computerbridge4. Ordered TaskDecompositionMainly Ill use PowerPoint slidesAt two poi

6、nts, I can run demos in LispPlease ask questions!Day 1Day 21. Principles of HTN PlanningJoint work with Kutluhan Erol and Jim HendlerTheoryApplications6. Evacuationplanning3. Electronic Designand Manufacturing5. SHOP1. Principles ofHTN planning2. Computerbridge4. Ordered TaskDecompositionWhat HTN Pl

7、anning Ismethodtravel(x,y)travel by airget taxiride taxi (x,y)pay drivertravel by taxitravel(UMD, MIT)airport(UMD,BWI)airport(MIT,Logan)ticket(BWI, Logan)travel(UMD, BWI)get taxiride taxi(UMD, BWI)pay driverfly(BWI, Logan)travel(Logan, MIT)get taxiride taxi(Logan, MIT)pay driverA type of problem red

8、uctionDecompose tasks into subtasksHandle constraints (e.g., taxi not good for long distances)Resolve interactions (e.g., take taxi early enough to catch plane)If necessary, backtrack and try other decompositionstaskticket (a,b)travel (x,a)fly(a,b)travel(b,y)airport(x,a)airport(y,b)Comparison with “

9、Classical” AI Planning“Classical” AI planning is action-basedDeclarative descriptions of actionsSpecify declaratively what theoperators are capable of doingDont prescribe how toperform complex tasksThe planner must infer that,using trial-and-error searchHTN decompositionCan represent STRIPS-styledec

10、larative operators, but its clumsyEasy to specify “recipes”for how to perform tasksbuy-ticket(x,y)pre:airport(x), have-money()del:have-money()add:have-ticket(x,y)fly(x,y)pre:at(x), have-ticket(x,y)del:at(x), have-ticket(x,y)add:at(y)travel by airticket (a,b)travel (x,a)fly(a,b)travel(b,y)airport(x,a

11、)airport(y,b)History of HTN PlanningOriginally developed about 25 years agoSacerdoti 1977; Tate 1977Long thought to have better potential for applicability to real-world planning problems than classical STRIPS-style planningProgress delayed due to lack of theoretical understandingMore recent work: t

12、heoretical basis for HTN planningFormal semanticsHTNs are strictly more expressive than STRIPS operatorsErol et al., 1994aSound and complete algorithm Erol et al., 1994bImplementation available at :/ /projects/plus/umcp/manual/ Complexity analysis Erol et al., 1996This has helped to spread interest

13、in HTN planningWhat is Expressivity?Expressivity of languagesA language L is as expressive as expressive as another language M iff any expression in L can be translated into an expression with the same meaning in M Possible ways to define “meaning”1. based on computational complexity2. based on mode

14、l theory3. based on operational semanticsHTN planning is more expressive than state-based planning according to all three of these definitionsWill summarize all three1. Complexity-Based ExpressivityTransformation must preserve answer (“yes” or “no”)Transformation must be computable/polynomialAffecte

15、d by the conciseness of the languageLanguage LLanguage Mtransformation“yes”instances“yes”instances“no”instances“no”instancesHTN Language Versus STRIPS LanguageSTRIPS-style planning is a special case of HTN planningErol 1995 presents two polynomial transformations from the STRIPS planning language to

16、 the HTN planning languageThere is no computable transformation from the HTN language to the STRIPS language, because HTNs can represent harder problems than the STRIPS languageExample problem:Given two context-free languages L1 and L2, do they have a non-empty intersection?This problem is undecidab

17、leIt cant be represented as a STRIPS-style planning problem(not unless you augment the STRIPS formalism to include function symbols!)Representing the Problem using HTNsGiven two context-free languages L1 and L2, do they have a non-empty intersection?This problem can be represented as an HTN planning

18、 problemYou dont need to use function symbolsYou dont even need to use any variable symbols!However, you need to make use ofcycles in methodsinterleaving among subtasksm1m2m1t1t11t12t13t2t21t22t232. Model-Theoretic ExpressivityErol 1995 extended the work of Baader on knowledge representation languag

19、es to planning languagesThe transformation must preserve meaningThe set of models satisfying a sentence and the set of models satisfying its tranformation must be equivalentNo restrictions on the computational aspects of the translationNot affected by the conciseness of the languagesResultErols tran

20、sformations from STRIPS to HTN (mentioned earlier) preserve the set of modelsNo transformations in the other direction, because HTN models have richer structure Thus the HTN language is more expressive than the STRIPS language3. Operational-Semantic ExpressivityTransformation must preserve the set o

21、f solutions (plans)Result:Solutions to STRIPS problems are regular setsSolutions to HTN problems can be arbitrary context-free sets Thus HTNs are more expressive than STRIPSRelated PublicationsSacerdoti, 1977E. Sacerdoti. A Structure for Plans and Behavior. American Elsevier Publishing Company, 1977

22、. Tate, 1977A. Tate. Generating Project Networks. IJCAI-77, 1977, 888-893. Erol et al., 1994K. Erol, J. Hendler and D. S. Nau. Semantics for Hierarchical Task-Network Planning. Tech. Report CS TR-3239, Univ. of Md., March, 1994. Erol et al., 1994aK. Erol, J. Hendler and D. S. Nau. HTN Planning: Comp

23、lexity and Expressivity. In AAAI-94, 1994. Erol et al., 1994bErol, Hendler and Nau. UMCP: A Sound and Complete Procedure for Hierarchical Task-Network Planning. In AIPS-94, pp. 249-254. Erol, 1995Erol. Hierarchical Task-Network Planning Systems: Formalization, Analysis, and Implementation. Ph.D. Dis

24、sertation, U. of Maryland, 1995.Erol et al., 1996K. Erol, J. Hendler and D. Nau. Complexity Results for Hierarchical Task-Network Planning. Annals of Mathematics and AI, 18:69-93, 1996. 2. Computer BridgeJoint work with Stephen J. Smith and Tom ThroopTheoryApplications6. Evacuationplanning3. Electro

25、nic Designand Manufacturing5. SHOP1. Principles ofHTN planning2. Computerbridge4. Ordered TaskDecompositionComputer Programs forGames of StrategyFundamental technique: minimax game-tree searchLargely “brute force”Can prune off portions of the treecutoff depth,alpha-beta pruning,hash tables, Even the

26、n, it still examinesthousands of game positionsThis is very different from how humans thinkEven the best human chess playersexamine at most a few dozengame positions to make their moves10-359-2-723109-239-2Connect Four:solvedGo-Moku:solvedQubic:solvedNine Mens Morris:solvedOthello:better than humans

27、Checkers:better than any living humanBackgammon:better than all but about 10 humansChess:certainly better than all but about 250 humans;possibly even better than thatBridge:probably worse than the best playerat your local bridge clubPerformance of Game-Playing Computer ProgramsFour players; 52 playi

28、ng cards dealt equally among themBidding to determine the trump suitDeclarer: whoever makes highest bidDummy: declarers partnerThe basic unit of play is the trickOne player leads; the othersmust follow suit if possibleTrick won by highest cardof the suit led, unlesssomeone plays a trump Keep playing

29、 tricks until allcards have been playedScoring based on how many trickswere bid and how many were takenWestNorthEastSouth628QQJ6597AK53A9How Bridge WorksBridge is an imperfect information gameDont know what cards the others have (except the dummy)Many possible card distributions, so many possible mo

30、vesIf we encode the additional moves as additional branches in the game tree, this increasesthe number of nodes exponentiallyworst case: about 6x1044 leaf nodesaverage case: about 1024 leaf nodesWhy Bridge is Difficultfor ComputersNot enough time to search the game treeHow to Reduce the Sizeof the G

31、ame Tree?Bridge is a game of planningThe declarer plans how to play the handThe plan combines various strategies (ruffing, finessing, etc.)If a move doesnt fit into a sensible strategy, it probably doesnt need to be consideredOur approach for declarer playAdaptation of an Hierarchical Task-Network (

32、HTN) planningGenerate a game tree in which each move corresponds to a different strategy, not a different cardOur approachWorst caseAverage caseBrute-force search 1024 leaf nodes 26,000 leaf nodes 305,000 leaf nodes 6x1044 leaf nodes(North Q)Task Network for FinessingPlayCard(P3; S, R3)PlayCard(P2;

33、S, R2)PlayCard(P4; S, R4)FinesseFour(P4; S)PlayCard(P; S, R1)StandardFinesseTwo(P2; S)LeadLow(P; S)PlayCard(P4; S, R4)StandardFinesseThree(P3; S)EasyFinesse(P2; S)BustedFinesse(P2; S)FinesseTwo(P2; S)StandardFinesse(P2; S)Finesse(P; S)Us:East declarer, West dummyOpponents:defenders, South & NorthCon

34、tract:East 3NTOn lead:West at trick 3East:KJ74West:A2Out:QT98653(North 3)East JWest 2North 3South 5South Qprimitive action by ustaskmethodprimitive action by opponentGame Tree Generated fromthe Task NetworkNQEKFINESSEN3EJN3W2EKS3SQS5S3WA3E45+600CASH OUTNS+630+630+600+600+265+265+600+600+600+600 +630

35、 100 +630 +600+600.later strategies. We incorporated our code for declarer playinto Bridge Baron (an existing commercial program)Using our code, Bridge Baron won the 1997 World Bridge Computer ChallengeOur code has been used in all versions of Bridge Baron since October 1997Has sold many thousands o

36、f copiesImplementationRelated PublicationsSmith et al., 1996S.J.J. Smith, D.S. Nau, and T. Throop. A Planning Approach to Declarer Play in Contract Bridge. Computational Intelligence, 1996. 12(1): p. 106-130. Smith et al., 1998S.J.J. Smith, D.S. Nau, and T. Throop. Computer Bridge: A Big Win for AI

37、Planning. AI Magazine, 1998. 19(2): p. 93-105. 3. Electronic Design and ManufacturingJoint work with Stephen J. Smith, Kiran Hebbar, and Ioannis MinisTheoryApplications6. Evacuationplanning3. Electronic Designand Manufacturing5. SHOP1. Principles ofHTN planning2. Computerbridge4. Ordered TaskDecompo

38、sitionIntegrated Product and Process Design (IPPD)Augment the traditional “engineering design” loop Plan and evaluate what manufacturing processes will be neededPredict cost, time, quality, manufacturing problemsModify the design to improve its manufacturabilityProductmodelingEngineering andfunction

39、alityanalysisManufacturabilityanalysisverifyparametersPreliminary designModify designAcceptable designMicrowave Transmit/Receive Modules1-20 GHz frequency range (radars, satellite communications, etc.)Difficult and expensive to design and manufactureEDAPS: Electro-mechanical Design And Planning Syst

40、emCircuit Schematic,Component SelectionRoutines in C+Product and Process Data FilesEEsof- Developed by us Microstation HTN Planner(C+)Substrate Design & 3-D Layout Process Planning& Plan EvaluationUser Interface (Tcl/Tk)Information about manufacturabilityDesignerAEL Routines- CommercialMDL RoutinesD

41、esign,ConstraintsEDAPSs Process PlannerCan express planning using “recipes” that fit well into HTN methodsGenerate and evaluate multiple process plansEstimate times and costsDisplay results graphically(alternative methods)A portion of the task network:SpindlingSprayingSpreadingPaintingPhotolithograp

42、hyApply photoresistPreclean for artworkEtching(one possible method)Make the artworkProcesses: Opn A BC/WW Setup Runtime LNDescription 001 A VMC1 2.00 0.00 01Orient board vertically 02Clamp board at (1,1,1) 03Establish datum point 001 B VMC1 0.10 0.43 01Tool: 0.30-diameter drill bit 02Drill at (1.25,

43、-0.50 d:1.00,f:50,s:30 03Drill at(1.25,-0.50) d:1.00,f:20,s:60001 C VMC1 0.10 0.77 01Tool: 0.20-diameter slot miller 02MiII start (0.044, 4.88) l: 0.5, w: 0.5, d: 1.00, f: 50, s: 40 001 T VMC1 2.20 1.20 01Total time on VMC1006 A PLAT1 1.00 0.60007 A ETR1 0.50 0.60008 A ETC1 0.20 0.30 02Dip in bath f

44、or 2 minutes Temperature:100C, Conc:1000ppm 01Etch plate for 1 minuteSubstrate Dimensions: 7,4,1 Ground Material: AluminumMaterial: Teflon Substrate thickness: 30 mils Metallized thickness: 7 mils 01Etch board for 2 minutes Temperature:100C, Conc:1000ppmExamplesfromEDAPSAlternativecomponentsPareto-o

45、ptimalcombinationsMulti-objectiveInteger ProgrammingDatabase lookupStatusEDAPS completed under NSF fundingFollow-up project with Northrop GrummanCombine AI planning with Integer Programming optimizationHTN planningAlternativeplansInteractive displayUser exploration and selectionC1CiCpAijPijkApqA11P1

46、11PpqrA1xx ApxxA1xx ApxxElectronic CADInitial componentselectionRelated PublicationsHebbar et al., 1996K. Hebbar, S. J. Smith, I. Minis and D. Nau. Plan-Based Evaluation of Designs for Microwave Modules. In Proc. ASME Design Technical Conference, August, 1996. Smith et al., 1997S.J. Smith, K. Hebbar

47、, D. Nau, and I. Minis. Integrating Electrical and Mechanical Design and Process Planning. In Knowledge Intensive CAD, Volume 2, M. Mantyla, S. Finger, and T. Tomiyama, Editors. 1997, Chapman and Hall, pp. 269-288. Nau et al., 2000D. Nau, J. Meyer, M. Ball, J. Baras, A. Chowdhury, E. Lin, R. Rajaman

48、i and V. Trichur. Integrated Product and Process Design of Microwave Modules Using AI Planning and Integer Programming. In Fourth Workshop on Knowledge Intensive CAD (KIC-4), 2000, pages 186-196. Parma, Italy: IFIP Working Group 5.2. 4. Ordered Task DecompositionJoint work with Kutluhan Erol, Naresh

49、 Gupta, and Stephen J. SmithTheoryApplications6. Evacuationplanning3. Electronic Designand Manufacturing5. SHOP1. Principles ofHTN planning2. Computerbridge4. Ordered TaskDecompositionDiscussionFor both Bridge Baron and EDAPSWe used the same approachEven some of the same code!Ordered Task Decomposit

50、ionAdaptation of HTN planningLinear ordering on the subtasks of each methodExpand the subtasks in the same order in which they will be executed later onCompare and contrast with “classical” AI planning1. Search strategy2. Data representationmethodsubtask 3subtask 2subtask 1subtask 4taskSearch Strate

51、gyOrdered task decompositionAdaptation of HTN planningRequire the subtasks of each method to be totally orderedDecompose these tasks left-to-rightThe same order that theyll later be executedAnalogous to PROLOGs search strategySpindlingSprayingSpreadingPaintingPhotolithographyApply photoresistPreclea

52、n for artworkEtchingMake the artwork for a PC boardSearch Strategy (Continued)With action-based planning, you have an either/or choice:goal-directed search (backward from the goal)forward search (forward from the initial state)In contrast, ordered task decomposition is both forward and goal-directed

53、 at the same timeCABABCPick up CPut C on the tablePick up APut A on BPick up BPut B on CExampleSTRIPS operator to stack a blockTranslate it into an HTN methodIf we expand the subtasks in left-to-rightorder, then we are searchingforward from the initial stateAlways know the current stateHowever, its

54、also agoal-directed searchThe task is the goalInvoke only those methods that match the taskstack(x,y)Pre:holding(x), clear(y)Del:holding(x), clear(y)Add:on(x,y), clear(x), handemptystack(x,y)Achieve on(x,y)Achieve clear(y)Achieve holding(x)Put x on ycabcabThe operators arent totally orderedHow do we

55、 we know what the states are?Represent states as sets of logical atomsPartially instantiate them to represent what we know about themprotected conditions in POP, mutex conditions in GraphplanThis works (it leads to sound and complete planners)Since the states arent totally instantiated, its hard to

56、reason about them in all of the ways we might likeE.g., cant call a CAD package to reason about the geometry of a machined part if some of the geometry is uninstantiatedState Representationfor Partial-Order PlanningCABABCPick up CPut C on the tablePick up APut A on BPick up BPut B on CState Represen

57、tation forOrdered Task DecompositionGoal-directed, but generates actions in the same order in which they will later be executedWhenever we want to plan the next taskweve already planned everything that comes before itThus, we know the current state of the worlds0s1s2task tmtask tnop1op2opiSi1Increas

58、ed ExpressivityIf we know what the current state is, then we can do complex reasoning about itLogical inferencesNumeric and probabilistic computationsInteractions with external programsExampleIn computer bridge, by knowing the current state, can decide which of nineteen finesse situations are applic

59、ableWith partial-order planning, it would be hard to decide which of them can be made applicableCan do lots of pruningOften only one or two consistent “next steps” Bridge declarer play: complete plans in about 11/2 minutesProcess plans for microwave modules: a few secondsExample: Blocks-World Planni

60、ngThe blocks worldOn the next page is the best blocks-world planning algorithm I know ofGupta & Nau, 1992It finds near-optimal plans in low-order polynomial timeIn this section, Ill describe the algorithmIn the next section, Ill explain how to implement it using Ordered Task Decompositionmove bfrom