PowerPoint PresentationMotivationTwo ApproachesHTN PlanningSlide 5Simple Task Network (STN) PlanningMethodsMethods (Continued)Domains, Problems, SolutionsExampleExample (continued)Total-Order FormulationPartial-Order FormulationSolving Total-Order STN Planning ProblemsComparison to Forward and Backward SearchSlide 16Limitation of Ordered-Task PlanningPartially Ordered MethodsAlgorithm for Partial-Order STNsSlide 20Slide 21Slide 22Comparison to Classical PlanningComparison to Classical Planning (cont.)Increasing Expressivity FurtherSlide 26Slide 27Example, ContinuedSlide 29SHOP & SHOP2 vs. TLPlan & TALplannerDomain-Configurable Planners Compared to Classical PlannersExample from the AIPS-2002 CompetitionSlide 33Slide 34Slide 35Slide 36Slide 37Slide 38Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/1Chapter 11Hierarchical Task Network PlanningLecture slides forAutomated Planning: Theory and PracticeDana S. NauUniversity of Maryland03:27 PM January 14, 2019Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/2MotivationWe may already have an idea how to go about solving problems in a planning domainExample: travel to a destination that’s far away:Domain-independent planner:»many combinations of vehicles and routesExperienced human: small number of “recipes”e.g., flying:1. buy ticket from local airport to remote airport2. travel to local airport3. fly to remote airport4. travel to final destinationHow to enable planning systems to make use of such recipes?Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/3Two ApproachesControl rules (previous chapter):Write rules to prune every action that doesn’t fit the recipeHierarchical Task Network (HTN) planning:Describe the actions and subtasks that do fit the recipeDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/4HTN Planningtravel(UMD, LAAS)get-ticket(IAD, TLS)travel(UMD, IAD)fly(BWI, Toulouse)travel(TLS, LAAS)get-taxiride(TLS,Toulouse)pay-drivergo-to-travel-web-sitefind-flights(IAD,TLS)buy-ticket(IAD,TLS)get-taxiride(UMD, IAD)pay-driverTask:Problem reductionTasks (activities) rather than goalsMethods to decompose tasks into subtasksEnforce constraints»E.g., taxi not good for long distancesBacktrack if necessaryMethod: taxi-travel(x,y)get-taxi ride(x,y) pay-driverget-ticket(BWI, TLS)go-to-travel-web-sitefind-flights(BWI,TLS) BACKTRACKtravel(x,y)Method: air-travel(x,y)travel(a(y),y)get-ticket(a(x),a(y))travel(x,a(x))fly(a(x),a(y))Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/5HTN PlanningHTN planners may be domain-specifice.g., see Chapters 20 (robotics) and 23 (bridge)Or they may be domain-configurableDomain-independent planning engineDomain description that defines not only the operators, but also the methodsProblem description»domain description, initial state, initial task networkTask:Method: taxi-travel(x,y)get-taxi ride(x,y) pay-drivertravel(x,y)Method: air-travel(x,y)travel(a(y),y)get-ticket(a(x),a(y))travel(x,a(x))fly(a(x),a(y))Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/6Simple Task Network (STN) PlanningA special case of HTN planningStates and operatorsThe same as in classical planningTask: an expression of the form t(u1,…,un)t is a task symbol, and each ui is a termTwo kinds of task symbols (and tasks):»primitive: tasks that we know how to execute directly•task symbol is an operator name»nonprimitive: tasks that must be decomposed into subtasks•use methods (next slide)Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/7MethodsTotally ordered method: a 4-tuplem = (name(m), task(m), precond(m), subtasks(m))name(m): an expression of the form n(x1,…,xn)»x1,…,xn are parameters - variable symbolstask(m): a nonprimitive taskprecond(m): preconditions (literals)subtasks(m): a sequenceof tasks t1, …, tk air-travel(x,y)task: travel(x,y)precond: long-distance(x,y)subtasks: buy-ticket(a(x), a(y)), travel(x,a(x)), fly(a(x), a(y)), travel(a(y),y)travel(x,y)buy-ticket (a(x), a(y)) travel (x, a(x)) fly (a(x), a(y)) travel (a(y), y)long-distance(x,y)air-travel(x,y)Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/8Partially ordered method: a 4-tuplem = (name(m), task(m), precond(m), subtasks(m))name(m): an expression of the form n(x1,…,xn)»x1,…,xn are parameters - variable symbolstask(m): a nonprimitive taskprecond(m): preconditions (literals)subtasks(m): a partially orderedset of tasks {t1, …, tk} air-travel(x,y)task: travel(x,y)precond: long-distance(x,y)network: u1=buy-ticket(a(x),a(y)), u2= travel(x,a(x)), u3= fly(a(x), a(y))u4= travel(a(y),y), {(u1,u3), (u2,u3), (u3 ,u4)}travel(x,y)buy-ticket (a(x), a(y)) travel (x, a(x)) fly (a(x), a(y)) travel (a(y), y)long-distance(x,y)air-travel(x,y)Methods (Continued)Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/9Domains, Problems, SolutionsSTN planning domain: methods, operatorsSTN planning problem: methods, operators, initial state, task listTotal-order STN planning domain and planning problem:Same as above except thatall methods are totally orderedSolution: any executable planthat can be generated byrecursively applying methods tononprimitive tasksoperators toprimitive tasksnonprimitive taskprecondmethod instances0precond effects precond effectss1s2primitive taskprimitive