Transcription
Automated(AI) PlanningIntroductionAutomated (AI) PlanningAutonomous SystemsWhat lgorithmsSummaryCarmel Domshlak
PrerequisitesAutomated(AI) PlanningIntroductionCourse prerequisites:foundations of AI: search, heuristic searchpropositional logic: syntax and semanticscomputational complexity theory: decision problems,reductions, NP-completenessWhat lgorithmsSummary
OutlineAutomated(AI) PlanningIntroductionThe focus of the course is on Artificial Intelligence planning( domain-independent planning) techniquesWhat isplanning?Transitionsystems1What planning problems are and why they are interesting?Representation2The “Holy Triangle” of AI problem solvingTowardsAlgorithms3Too hard or Too easy?, or Can this all be any practical?Summary
What is AI?Automated(AI) PlanningTwo of somewhat more pragmatic attemptsThe study of mental faculties through the use ofcomputational models.(E. Charniak & D. McDermott)The science concerned with understanding intelligentbehavior by attempting to create it in the artificial.(T. Smithers)IntroductionAI approach toproblemsFrom AI to IEWhat lgorithmsSummaryIntelligent behavior can be considered (postulated?) asability to solve problems for which the machine has noknowledge of an suitable algorithm
Why do we need such an AI?Automated(AI) PlanningIntroductionAI approach toproblemsFrom AI to IEWhat lgorithmsSummary
NASA ExperienceGalileo Jupiter or Cassini Saturnmissions 1G budgetGround crew of 100-300personnelAutomated(AI) PlanningIntroductionAI approach toproblemsFrom AI to IEWhat isplanning?TransitionsystemsMars micro-rover Sojourne 100M budgetSmall (and tired!) groundteamsSojourne operated for two month, but future robots areexpected to operate much longer!RepresentationTowardsAlgorithmsSummary
NASA VisionSpace-explorating systems should beLow-cost and rapid development, low-cost controlAutonomous operation for long periods of timeAutonomous operation must guarantee success, giventight deadlines and resource constraintsAutomated(AI) PlanningIntroductionAI approach toproblemsFrom AI to IEWhat wardsAlgorithmsSummary
NASA VisionSpace-explorating systems should beLow-cost and rapid development, low-cost controlAutonomous operation for long periods of timeAutonomous operation must guarantee success, giventight deadlines and resource constraintsAutomated(AI) PlanningIntroductionAI approach toproblemsFrom AI to IEWhat isplanning?TransitionsystemsUtopy? Not really. First progress in this direction has beenaccomplished in 1998 in the scope of the Deep Space Oneproject!RepresentationTowardsAlgorithmsSummary
Planning ProblemsAutomated(AI) PlanningA sample of problems:Solving Rubik’s cube (or 15-puzzle, or .)Selecting and ordering movements of an elevator or a craneScheduling of production linesIntroductionWhat isplanning?Problem classesDynamicsObservabilityObjectivesAutonomous robotsTransitionsystemsCrisis hat is in common?
Planning ProblemsWhat is in common?All these problems deal with action selection or controlSome notion of problem state(Often) specification of initial state and/or goal stateLegal moves or actions that transform states into otherstateAutomated(AI) PlanningIntroductionWhat isplanning?Problem stemsRepresentationTowardsAlgorithmsSummary
Planning ProblemsAutomated(AI) PlanningFor now focus on:Plans (aka solutions) are sequences of moves thattransform the initial state into the goal stateIntuitively, not all solutions are equally desirableWhat is our task?1 Find out whether there is a solution2Find any solution3Find an optimal (or near-optimal) solution4Fixed amount of time, find best solution possible5Find solution that satisfy property ℵ (what is ℵ? youchoose!)IntroductionWhat isplanning?Problem stemsRepresentationTowardsAlgorithmsSummary
Planning ProblemsWhat is our task?1 Find out whether there is a solution2Find any solution3Find an optimal (or near-optimal) solution4Fixed amount of time, find best solution possible5Find solution that satisfy property ℵ (what is ℵ? youchoose!) While all these tasks sound related, they are very different.The techniques best suited for each one are almostdisjoint.In AI planning, (1) is usually assumed not to be an issue.(In contrast, in formal verification this is the central issue.)Automated(AI) PlanningIntroductionWhat isplanning?Problem stemsRepresentationTowardsAlgorithmsSummary
Planning vs. SchedulingClosely related but conceptually different problemsSchedulingDeciding when to performa given set of actionsTime constraintsResource constraintsGlobal constraints (e.g.,regulatory issues)Automated(AI) PlanningIntroductionPlanningDeciding what actions toperform (and when) to achievea given objectivesame issuesObjective functionsThe difference comes in play in solution techniques, andactually even in worst-case time/space complexityWhat isplanning?Problem stemsRepresentationTowardsAlgorithmsSummary
Planning and Action Selection in AIAutomated(AI) PlanningThree approaches in AI (in general?) to the problems ofaction selection or controlLearning : learn control from experienceProgramming : specify control by handPlanning : specify problem by hand, derive controlautomaticallyIntroductionWhat isplanning?Problem stemsRepresentationAll three have strengths and weaknesses; approaches notexclusive and often complementary.Planning is a form of general problem solvingTowardsAlgorithmsSummary
Three Key Ingredients of Planning. and of AI approach to problems in general?Automated(AI) PlanningPlanning is a form of general problem solvingIntroductionProblem Language Planner SolutionWhat isplanning?Problem classesDynamicsObservabilityObjectives1models for defining, classifying, and understandingproblems- what is a planning problem- what is a solution (plan), and- what is an optimal solution2languages for representing problems3algorithms for solving msSummary
Three Key Ingredients of Planning. and of AI approach to problems in general?Automated(AI) PlanningPlanning is a form of general problem solvingIntroductionProblem Language Planner SolutionWhat isplanning?Problem classesDynamicsObservabilityObjectives1models for defining, classifying, and understandingproblems- what is a planning problem- what is a solution (plan), and- what is an optimal solution2languages for representing problems3algorithms for solving msSummary
State model for Classical AI Planningfinite state space San initial state s0 Sa set SG S of goal statesapplicable actionsA(s) A for s Sa transition functions0 f (a, s) for a A(s)a cost function c : A [0, )Automated(AI) PlanningIntroductionWhat isplanning?Problem stemsRepresentationTowardsAlgorithmsSummaryA solution is a sequence of applicableactions that maps s0 into SGAn optimal solution minimizes c
Why planning is difficult?Automated(AI) PlanningSolutions to planningproblems are paths from aninitial state to a goal statein the transition graphDijkstra’s algorithm solvesthis problem inO( V log ( V ) E )Can we go home?IntroductionWhat isplanning?Problem stemsRepresentationTowardsAlgorithmsSummary
Why planning is difficult?Solutions to planningproblems are paths from aninitial state to a goal statein the transition graphDijkstra’s algorithm solvesthis problem inO( V log ( V ) E )Can we go home? Not exactly V of ourinterest is 1010 , 1020 , 10100 ,.But do we need suchvalues of V ?!Automated(AI) PlanningIntroductionWhat isplanning?Problem stemsRepresentationTowardsAlgorithmsSummary
Why planning is difficult?Generalize the earlierexample:Five locations, three robotcarts, 100 containers, threepiles V 10277The number of atoms in theuniverse is only about 1087The state space in ourexample is more than 10109times as large (uppss .)And solving such a problemis not hopeless!Automated(AI) PlanningIntroductionWhat isplanning?Problem stemsRepresentationTowardsAlgorithmsSummary
Beyond Classical PlanningAutomated(AI) PlanningAdding into the modelUncertainty about initial state and action outcomesInfinite state spaces (resources, time, .)Continuous state spaces (resources, time, .)Complex models of solution, and solution optimalityIntroductionWhat isplanning?Problem classesDynamicsObservabilityObjectivesInterleaving planning and gorithmsSide comment .It is not that classical planning is easyIt is not even clear that it is too far from modelingand/or solving real-world problems well!Summary
Different classes of problemsAutomated(AI) Planningdynamics: deterministic, nondeterministic or probabilisticobservability: full, partial, or nonehorizon: finite or infinite.IntroductionWhat isplanning?Problem classesDynamicsObservabilityObjectives1classical planningTransitionsystems2conditional planning with full observabilityRepresentation3conditional planning with partial observabilityTowardsAlgorithms4conformant planningSummary5Markov decision processes (MDP)6partially observable MDPs (POMDP)
Properties of the world: dynamicsAutomated(AI) PlanningDeterministic dynamicsAction current state uniquely determine successor state.IntroductionWhat isplanning?Nondeterministic dynamicsFor each action and current state there may be several possiblesuccessor states.Problem stemsRepresentationProbabilistic dynamicsFor each action and current state there is a probabilitydistribution over possible successor states.Analogy: deterministic versus nondeterministic automataTowardsAlgorithmsSummary
Determistic dynamics exampleMoving objects with a robotic hand:move the green block onto the blue block.Automated(AI) PlanningIntroductionWhat isplanning?Problem stemsRepresentationTowardsAlgorithmsSummary
Nondetermistic dynamics exampleMoving objects with an unreliable robotic hand:move the green block onto the blue block.Automated(AI) PlanningIntroductionWhat isplanning?Problem stemsRepresentationTowardsAlgorithmsSummary
Probabilistic dynamics exampleMoving objects with an unreliable robotic hand:move the green block onto the blue block.Automated(AI) PlanningIntroductionWhat isplanning?Problem classesDynamicsObservabilityObjectivesp 0.1TransitionsystemsRepresentationp 0.9TowardsAlgorithmsSummary
Properties of the world: observabilityAutomated(AI) PlanningCamera ACamera BIntroductionWhat isplanning?Problem stemsRepresentationGoalTowardsAlgorithmsSummary
Properties of the world: observabilityFull observabilityObservations/sensing determine current world state uniquely.Partial observabilityObservations determine current world state only partially:we only know that current state is one of several possible ones.No observabilityThere are no observations to narrow down possible currentstates. However, can use knowledge of action dynamics todeduce which states we might be in.Consequence: If observability is not full, must represent theknowledge an agent has.Automated(AI) PlanningIntroductionWhat isplanning?Problem stemsRepresentationTowardsAlgorithmsSummary
Different objectivesAutomated(AI) Planning1Reach a goal state.Example: Earn 500 euro.2Stay in goal states indefinitely (infinite horizon).Example: Never allow the bank account balance to benegative.3Maximize the probability of reaching a goal state.Example: To be able to finance buying a house by 2018study hard and save money.4Collect the maximal expected rewards/minimal expectedcosts (infinite horizon).Example: Maximize your future income.5.IntroductionWhat isplanning?Problem stemsRepresentationTowardsAlgorithmsSummary
Relation to games and game theoryAutomated(AI) PlanningGame theory addresses decision making in multi-agentsetting: “Assuming that the other agents are rational,what do I have to do to achieve my goals?”Game theory is related to multi-agent planning.I will concentrate on single-agent planning.Some of the techniques are also applicable to special casesof multi-agent planning.Example: Finding a winning strategy of a game like chess.In this case it is not necessary to distinguish between anintelligent opponent and a randomly behaving opponent.Game theory in general is about optimal strategies whichdo not necessarily guarantee winning. For example cardgames like poker do not have a winning strategy.IntroductionWhat isplanning?Problem stemsRepresentationTowardsAlgorithmsSummary
Where classical planning stands?Automated(AI) Planningdynamics: deterministic, nondeterministic or probabilisticobservability: full, partial or nonehorizon: finite or infinite.IntroductionWhat isplanning?Problem classesDynamicsObservabilityObjectives1classical planningTransitionsystems2conditional planning with full observabilityRepresentation3conditional planning with partial observabilityTowardsAlgorithms4conformant planningSummary5Markov decision processes (MDP)6partially observable MDPs (POMDP)
Transition systemsAutomated(AI) Planninggoal statesCIntroductionBWhat resentationTowardsAlgorithmsSummaryEFinitial state
Transition systemsFormalization of the dynamics of the world/applicationAutomated(AI) PlanningDefinition (transition system)A transition system is hS, I, {a1 , . . . , an }, Gi whereS is a finite set of states (the state space),I S is a finite set of initial states,every action ai S S is a binary relation on S,G S is a finite set of goal states.IntroductionWhat sentationTowardsAlgorithmsSummaryDefinition (applicable action)An action a is applicable in a state s if sas0 for at least onestate s0 .
Transition systemsDeterministic transition systemsA transition system is deterministic if there is only one initialstate and all actions are deterministic. Hence all future statesof the world are completely predictable.Definition (deterministic transition system)A deterministic transition system is hS, I, O, Gi whereS is a finite set of states (the state space),Automated(AI) PlanningIntroductionWhat isplanning?TransitionsystemsDefinitionExampleI S is a state,Representationactions a O (with a S S) are partial functions,TowardsAlgorithmsG S is a finite set of goal states.SummarySuccessor state wrt. an actionGiven a state s and an action a so that a is applicable in s, thesuccessor state of s with respect to a is s0 such that sas0 ,denoted by s0 appa (s).
Blocks worldThe rules of the gameAutomated(AI) PlanningLocation on the table does not matter.IntroductionWhat isplanning? TransitionsystemsDefinitionExampleLocation on a block does not matter.RepresentationTowardsAlgorithmsSummary
Blocks worldThe rules of the gameAutomated(AI) PlanningAt most one block may be below a block.IntroductionWhat sentationAt most one block may be on top of a block.TowardsAlgorithmsSummary
Blocks worldThe transition graph for three blocksAutomated(AI) PlanningIntroductionWhat sentationTowardsAlgorithmsSummary
Blocks 405137633394353459655313564373693588558173Finding a solution is polynomial time in the number ofblocks (move everything onto the table and then constructthe goal configuration).Finding a shortest solution is NP-complete (for a compactdescription of the problem).Automated(AI) PlanningIntroductionWhat sentationTowardsAlgorithmsSummary
Deterministic planning: plansAutomated(AI) PlanningDefinition (plan)A plan for hS, I, A, Gi is a sequence π a1 , . . . , an of actioninstances such that a1 , . . . , an A and s0 , . . . , sn is a sequenceof states (the execution of π) so thatIntroductionWhat isplanning?TransitionsystemsDefinitionExample1s0 I,2si appai (si 1 ) for every i {1, . . . , n}, and3sn G.RepresentationTowardsAlgorithmsSummaryThis can be equivalently expressed asappan (appan 1 (. . . appa1 (I) . . . )) G
Three Key Ingredients of Planning. and of AI approach to problems in general?Automated(AI) PlanningPlanning is a form of general problem solvingIntroductionProblem Language Planner SolutionWhat isplanning?TransitionsystemsRepresentation1models for defining, classifying, and understandingproblems- what is a planning problem- what is a solution (plan), and- what is an optimal solution2languages for representing problems3algorithms for solving themState ary
Succinct representation of transition systemsAutomated(AI) PlanningMore compact representation of actions than as relationsis oftenpossible because of symmetries and other regularities,unavoidable because the relations are too big.IntroductionWhat t different aspects of the world in terms ofdifferent state variables.A state is a valuation of statevariables.Represent actions in terms of changes to the statevariables.State ary
State variablesAutomated(AI) PlanningThe state of the world is described in terms of a finite setof finite-valued state variables.Examplehour: {0, . . . , 23} 13minute: {0, . . . , 59} 55location: {51, 52, 82, 101, 102} 101weather: {sunny, cloudy, rainy} cloudyholiday: {T, F} FIntroductionWhat isplanning?TransitionsystemsRepresentationState aryAny n-valued state variable can be replaced by dlog2 neBoolean (2-valued) state variables.Actions change the values of the state variables.
Blocks world with state variablesAutomated(AI) PlanningState variables:location-of-A: {B, C, table}location-of-B: {A, C, table}location-of-C : {A, B, table}IntroductionWhat (location-of-A) tables(location-of-B) As(location-of-C) tableBA CNot all valuations correspond to an intended blocks worldstate, e. g. s such that s(location-of-A) B ands(location-of-B) A.State ary
Blocks world with Boolean state variablesAutomated(AI) PlanningExampleIntroductions(A-on-B) 0What isplanning?s(A-on-C) 0Transitionsystemss(A-on-table) 1s(B-on-A) 1s(B-on-C) 0s(B-on-table) 0s(C-on-A) 0s(C-on-B) 0s(C-on-table) 1RepresentationBA CState ary
Deterministic planning tasksDefinition (deterministic planning task)A deterministic planning task is a 4-tuple Π hV, I, A, GiwhereV is a finite set of state variables,I is an initial state over V ,A is a finite set of actions over V , andG is a constraint ( formula) over V describing the goalstates.Notes:Unless stated otherwise, G will be a single partialassignment to VWe will omit the word “deterministic” where it is clearfrom context.Automated(AI) PlanningIntroductionWhat isplanning?TransitionsystemsRepresentationState ary
Mapping planning tasks to transition systemsAutomated(AI) PlanningIntroductionFrom every deterministic planning task Π hV, I, A, Gi we canproduce a corresponding transition systemT (Π) hS, I, A0 , G0 i:123S is the set of all valuations of V ,A0 {R(a) a A} whereR(a) {(s, s0 ) S S s0 appa (s)}, andG0 {s S s G}.What isplanning?TransitionsystemsRepresentationState ary
Planning LanguagesAutomated(AI) PlanningIntroductionKey issueModels represented implicitly in a declarative languageWhat isplanning?TransitionsystemsRepresentationPlay two rolesspecification: concise model descriptioncomputation: reveal useful info about problem’s structureState ary
The SAS LanguageA problem in SAS is a tuple hV, A, I, GiV is a finite set of state variables with finite domainsdom(vi )I is an initial state over VG is a partial assignment to VA is a finite set of actions a specified via pre(a) and eff(a),both being partial assignments to VAn action a is applicable in a state s dom(V ) iffs[v] pre(a)[v] whenever pre(a)[v] is specifiedApplying an applicable action a changes the value of eachvariable v to eff(a)[v] if eff(a)[v] is specified.Example: 8-puzzleAutomated(AI) PlanningIntroductionWhat isplanning?TransitionsystemsRepresentationState ary
The STRIPS languageUseful fragment of SASAutomated(AI) PlanningA problem in STRIPS is a tuple hP, A, I, GiP stands for a finite set of atoms (boolean vars)IntroductionI P stands for initial situationWhat isplanning?G P stands for goal situationTransitionsystemsA is a finite set of actions a specified via pre(a), add(a),and del(a), all subsets of PRepresentationStates are collections of atomsAn action a is applicable in a state s iff pre(a) sApplying an applicable action a at s results ins0 (s \ del(a)) add(a)State ary
Why STRIPS is interestingAutomated(AI) PlanningIntroductionSTRIPS operators are particularly simple, yet expressiveenough to capture general planning problems.In particular, STRIPS planning is no easier than generalplanning problems.Many algorithms in the planning literature are easier topresent in terns of STRIPS .What isplanning?TransitionsystemsRepresentationState ary
Three Key Ingredients of Planning. and of AI approach to problems in general?Automated(AI) PlanningPlanning is a form of general problem solvingIntroductionProblem Language Planner SolutionWhat s for defining, classifying, and understandingproblemslanguages for representing problemsalgorithms for solving themNEXT: algorithms for classical planningwhere a significant progress has been recently achievedTowardsAlgorithmsSummary
More on the MotivationPlanning is a form of general problem solvingAutomated(AI) PlanningIntroductionProblem Language Planner SolutionWhat isplanning?TransitionsystemsModeling Time vs. Solution Time and Qualityspecialized methods are typically more efficient(though even that is not necessarily correct),but tend to require lots of programminggoal in AI problem solving is to facilitate modeling andyet provide efficient solutionsthis involves general languages (a la SAS or STRIPS)and thus language-specific algorithmsRepresentationTowardsAlgorithmsSummary
What do you learn in this course?Automated(AI) Planningalgorithms for solving different problem classes,with an emphasis on the classical (“simplest”) setting:algorithms based on heuristic search in state spacealgorithms based on heuristic search in plan spacealgorithms based on satisfiability testing (SAT) and generalconstraint satisfaction (CSP)Many of these techniques are applicable to problemsoutside AI as well.hands-on experience with problem modeling and (mostlyclassical) plannersIntroductionWhat lgorithmsSummary
systems Representation Towards Algorithms Summary Planning vs. Scheduling Closely related but conceptually di erent problems Scheduling Decidingwhento perform agivenset of actions Time constraints Resource constraints Global constraints (e.g., regulatory issues) Objective functions Planning Decidingwhatactions to perform (andwhen) to achieve a .
