PlanningPlanning AgentOutlinePlanning problemPlanning vs. problem solvingGoal of PlanningSlide 7Slide 8Representations in PlanningMajor approachesPlanning languageGeneral language featuresSlide 22Language semantics?Slide 24Expressiveness and extensionsBlocks worldState RepresentationGoal RepresentationAction RepresentationExampleSlide 31Slide 32Example: air cargo transportExample: Spare tire problemPlanning with state-space searchProgression and regressionProgression algorithmRegression algorithmRegression algorithmHeuristics for state-space searchPartial-order planningShoe examplePartial-order planning(POP)POP as a search problemExample of final planSlide 47Solving POPEnforcing consistencyProcess summarySlide 51Solving the problemSlide 53Slide 54Slide 55Slide 56Slide 57Some details …Planning graphsSlide 60Cake exampleSlide 62Slide 63PG and heuristic estimationThe GRAPHPLAN AlgorithmSlide 66GRAPHPLAN exampleSlide 68Slide 69Slide 70Planning with propositional logicSlide 72SATPLAN algorithmcnf, mapping  TRANSLATE-TO_SAT(problem, T)Slide 75Slide 76assignment  SAT-SOLVER(cnf)Slide 78Analysis of planning approachPlanning SummarySlide 81Nonlinear PlanningSlide 83Slide 84Slide 85Slide 86Slide 87Slide 88Slide 89Slide 90Slide 91Slide 92Slide 93Slide 94Slide 95Slide 96PlanningPlanningRussell and Norvig: Chapter 11CMSC421 – Fall 2006Planning AgentPlanning Agentenvironmentagent?sensorsactuatorsA1 A2 A3OutlineThe Planning problemPlanning with State-space searchPartial-order planningPlanning graphsPlanning with propositional logicAnalysis of planning approachesPlanning problemClassical planning environment: fully observable, deterministic, finite, static and discrete.Find a sequence of actions that achieves a given goal when executed from a given initial world state. That is, given a set of action descriptions (defining the possible primitive actions by the agent), an initial state description, and a goal state description or predicate, compute a plan, which is a sequence of action instances, such that executing them in the initial state will change the world to a state satisfying the goal-state description. Goals are usually specified as a conjunction of subgoals to be achievedPlanning vs. problem solvingPlanning and problem solving methods can often solve the same sorts of problemsPlanning is more powerful because of the representations and methods usedStates, goals, and actions are decomposed into sets of sentences (usually in first-order logic)Search often proceeds through plan space rather than state space (though first we will talk about state-space planners)Subgoals can be planned independently, reducing the complexity of the planning problemChoose actions to achieve a certain goalBut isn’t it exactly the same goal as for problem solving?Some difficulties with problem solving:The successor function is a black box: it must be “applied” to a state to know which actions are possible in that state and what are the effects of each oneGoal of PlanningOtherwise, in the real world an agent would be overwhelmed by irrelevant actions• Suppose that the goal is HAVE(MILK). • From some initial state where HAVE(MILK) is not satisfied, the successor function must be repeatedly applied to eventually generate a state where HAVE(MILK) is satisfied. • An explicit representation of the possible actions and their effects would help the problem solver select the relevant actionsGoal of PlanningChoose actions to achieve a certain goalBut isn’t it exactly the same goal as for problem solving?Some difficulties with problem solving:The goal test is another black-box function, states are domain-specific data structures, and heuristics must be supplied for each new problemSuppose that the goal is HAVE(MILK)HAVE(BOOK)Without an explicit representation of the goal, theproblem solver cannot know that a state whereHAVE(MILK) is already achieved is more promisingthan a state where neither HAVE(MILK) norHAVE(BOOK) is achievedGoal of PlanningChoose actions to achieve a certain goalBut isn’t it exactly the same goal as for problem solving?Some difficulties with problem solving:The goal may consist of several nearly independent subgoals, but there is no way for the problem solver to know itHAVE(MILK) and HAVE(BOOK) may be achieved bytwo nearly independent sequences of actionsRepresentations in Representations in PlanningPlanning Planning opens up the black-boxes by using logic to represent:ActionsStatesGoalsProblem solvingLogic representationPlanningMajor approachesSituation calculusState space planningPartial order planningPlanning graphsPlanning with Propositional LogicHierarchical decomposition (HTN planning)Reactive planningPlanning rapidly changing subfield of AI In biannual competition at AI Planning Systems Conference:•six years ago, best planner did plan space search using SAT solver•four years ago, the best planner did regression search•two years ago, best planner did forward state space search with an inadmissable heuristic functioncmsc722: Planning, taught by Prof. NauPlanning languageWhat is a good language?Expressive enough to describe a wide variety of problems.Restrictive enough to allow efficient algorithms to operate on it.Planning algorithm should be able to take advantage of the logical structure of the problem.STRIPS and ADLGeneral language featuresRepresentation of statesDecompose the world in logical conditions and represent a state as a conjunction of positive literals. Propositional literals: Poor  UnknownFO-literals (grounded and function-free): At(Plane1, Melbourne)  At(Plane2, Sydney)Closed world assumptionRepresentation of goalsPartially specified state and represented as a conjunction of positive ground literalsA goal is satisfied if the state contains all literals in goal.General language featuresRepresentations of actionsAction = PRECOND + EFFECTAction(Fly(p,from, to),PRECOND: At(p,from)  Plane(p)  Airport(from)  Airport(to)EFFECT: ¬AT(p,from)  At(p,to))= action schema (p, from, to need to be instantiated)Action name and parameter listPrecondition (conj. of function-free literals)Effect (conj of function-free literals and P is True and not P is false)Add-list vs delete-list in EffectLanguage semantics?How do actions affect states?An action is applicable in any state that satisfies the precondition.For FO action schema applicability involves a substitution 