Planning IIReal-world planning domainsPlanning vs. schedulingHierarchical decompositionHTN operator: ExampleHTN planning: exampleIncreasing expressivityReasoning about resourcesApplications of PlanningSummary: Practical PlanningPlanning IIPlanning IIGraphPlan and Russell and Norvig: ch.12CMSC421 – Fall 2006based on material from Jim Blythe, JC Latombe,Marie desJardins and Daphne KollerReal-world planning domainsReal-world domains are complex and don’t satisfy the assumptions of STRIPS or partial-order planning methodsSome of the characteristics we may need to deal with:Modeling and reasoning about resourcesRepresenting and reasoning about timePlanning at different levels of abstractionsConditional outcomes of actionsUncertain outcomes of actionsExogenous eventsIncremental plan developmentDynamic real-time replanningPlanning vs. schedulingPlanning: given one or more goal, generate a sequence of actions to achieve the goal(s)Scheduling: given a set of actions and constraints, allocate resources and assign times to the actions so that no constraints are violatedTraditionally, planning is done with specialized logical reasoning methodsTraditionally, scheduling is done with constraint satisfaction, linear programming, or OR methodsHowever, planning and scheduling are closely interrelated and can’t always be separatedHierarchical decompositionHierarchical decomposition, or hierarchical task network (HTN) planning, uses abstract operators to incrementally decompose a planning problem from a high-level goal statement to a primitive plan networkPrimitive operators represent actions that are executable, and can appear in the final planNon-primitive operators represent goals (equivalently, abstract actions) that require further decomposition (or operationalization) to be executedThere is no “right” set of primitive actions: One agent’s goals are another agent’s actions!HTN operator: ExampleOPERATOR decomposePURPOSE: ConstructionCONSTRAINTS: Length (Frame) <= Length (Foundation), Strength (Foundation) > Wt(Frame) + Wt(Roof) + Wt(Walls) + Wt(Interior) + Wt(Contents)PLOT: Build (Foundation)Build (Frame) PARALLEL Build (Roof) Build (Walls) END PARALLEL Build (Interior)HTN planning: exampleIncreasing expressivityConditional effectsInstead of having different operators for different conditions, use a single operator with conditional effectsMove (block1, from, to) and MoveToTable (block1, from) collapse into one Move (block1, from, to):Op(ACTION: Move(block1, from, to),PRECOND: On (block1, from) ^ Clear (block1) ^ Clear (to)EFFECT: On (block1, to) ^ Clear (from) ^ ~On(block1, from) ^ ~Clear(to) when to<>TableNegated and disjunctive goalsUniversally quantified preconditions and effectsReasoning about resourcesIntroduce numeric variables that can be used as measuresThese variables represent resource quantities, and change over the course of the planCertain actions may produce (increase the quantity of) resourcesOther actions may consume (decrease the quantity of) resourcesMore generally, may want different types of resourcesContinuous vs. discreteSharable vs. nonsharableReusable vs. consumable vs. self-replenishingApplications of PlanningApplications of PlanningMilitary operationsConstruction tasksMachining tasksMechanical assemblyDesign of experiments in geneticsCommand sequences for satelliteMost applied systems use extended representation languages, nonlinearplanning techniques, and domain-specificheuristicsSummary: Practical Summary: Practical PlanningPlanningMore expressive representationsHierarchical PlanningExploit AbstractionsMix of scheduling and
View Full Document
Unlocking...