人工智能英文版课件：09 Planning

1、Chapter 8 Planning2OutlineThe Planning ProblemPlanning with State-Space SearchPartial-Order PlanningPlanning GraphsPlanning with Propositional LogicAnalysis of Planning Approaches3The Planning ProblemWhat is planning ?The task of coming up with a sequence of actions that will achieve a goalTwo examp

2、les of planning agentsThe search-based problem-solving agentThe logical planning agent4The Planning ProblemWhat is concerned primarily in this chapter ?Scaling up to complex planning problems that defeat the approaches we have seen so farClassical planning environments in this chapterFully observabl

3、e, deterministic, finite, static (change happens only when the agent acts), and discrete (in time, action, objects, and effects)5The Planning ProblemWhat can happen ?When an ordinary problem-solving agent using standard search algorithms - depth-first, A*, and so on comes up against large, real-worl

4、ds problems.This can help us design better planning agents6The Planning ProblemDifficultiesThe problem-solving agent can be overwhelmed by irrelevant actionsFind a good heuristic functionThe problem solver might be inefficientWhy ?7The Planning ProblemThe problem-solving agent can be overwhelmed by

5、irrelevant actionsThe most obvious difficultyConsider the task of buying a copy of AI: A Modern Approach from an online booksellerSuppose one buying action for each 10-digit ISBN number, for a total of 10 billion actions8The Planning ProblemHow to this ?The search algorithmExamine the outcome states

6、 of all 10 billion actions to find one that satisfiers the goalA sensible planning agentWork back from an explicit goal description such as Have(ISBN0137903952) and generate the action Buy(ISBN0137903952) directlyThe agent needs the general knowledge that Buy(x) results in Have(x)The planner can dec

7、ide in a single unification step by the given knowledge and the goal9The Planning ProblemFind a good heuristic functionSuppose the agents goal is to buy four different books onlineSearching without an accurate heuristic is out of the question because there will be 1040 plans of just four steps10The

8、Planning ProblemA good heuristic estimate is the number of books that remain to be boughtObvious to a humanNot obvious to a problem-solving agentThe problem-solving agent sees the goal test as a black boxThe problem-solving agent lacks autonomyThe problem-solving agent requires a human to supply a h

9、euristic function for each new problemIt can use a single domain-independent heuristic if the planning agent has access to an explicit representation of the goal as a conjunction of subgoals 11The Planning ProblemThe problem solver might be inefficientBecause it cannot take advantage of problem deco

10、mpositionConsider the problem of delivering a set of overnight packagesFind out the nearest airport for each destinationDivide the overall problem into several subproblems, one for each airport12The Planning ProblemThe efficiency of decompositionContribute to the efficiency of constraint satisfactio

11、n problem solvers in chapter 5For planners: in the worst case, it take O(n!) time to find the best plan to deliver n packages, but only O(n/k)!*k)13The Planning ProblemDesign of many planning systemsBased on the assumption that most real-world problems are nearly decomposableThe planner can work on

12、subgoals independently, but might need to do some additional work to combine the resulting subplansFor some problem, this assumption breaks down because working on one subgoal is likely to undo another subgoal14The Planning ProblemThe language of planning problemsThe representation of planning probl

13、ems (states, actions, and goals)Should make it possible for planning algorithms to take advantage of the logical structure of the problemThe keyFind a language that is expressive enough to allow efficient algorithms to operate over it15The Planning ProblemRepresentation of statesPlanners decompose t

14、he world into logical conditions and represent a state as a conjunction of positive literalsLiterals:The propositional literalsFirst-order literals. e.g. At(Plane1, Melbourne) At(Plane2, Sydney)In first-order state: must be ground and function-freeSuch as At(x, y) or At(Father(Fred), Sydney) are not

15、 allowed16The Planning ProblemRepresentation of goalsA goal is a partially specified state, represented as a conjunction of positive ground literals, such as Rich Famous or At(P2, Tahiti)A propositional state s satisfiers a goal g if s contains all the atoms in g (and possibly others). e.g. Rich Fam

16、ous Miserable satisfies Rich Famous17The Planning ProblemRepresentation of actionsAn action is specified in terms of the preconditions that must hold before it can be executed and the effects that ensue when it is executede.g.Action(Fly(p, from, to), PRECOND: At(p, from) Plane(p) Airport(from) Airpo

17、rt(to) EFFECT: At(p, from) At(p, to)18The Planning ProblemThree parts of Action schemaThe action name and parameter list servers to identify the actionThe precondition a conjunction of function-free positive literals stating what must be true in a state before the action can be executedThe effecta c

18、onjunction of function-free literals describing how the state changes when the action is executedTo improve readability, some planning divided it into add list and delete list19The Planning ProblemHow to define the semantics ?The most straightforward way: describe how actions affect statesAn alterna

19、tive method: specify a direct translation into successor-state axioms, whose semantics comes from first-order logic 20The Planning ProblemFirst, an action is applicable in any state that satisfies the precondition; otherwise, the action has no effectSecond, starting in state s, the result of executi

20、ng an applicable action a is a state s that is the same as s except that any positive literal P in the effect of a is added to s and any negative literal P is removed from sFinally, we can define the solution for a planning problem21The Planning ProblemExpressiveness and extensionRestrictions impose

21、d by STRIPS representation were chosen in the hope of make planning algorithms simpler and more efficient, without making it too difficult to describe real problemsOne of the most important restrictionsLiterals are function-freeWith it, we can be sure that any action schema can be propositionalized2

22、2The Planning ProblemThe STRIPS is insufficiently expressive for some real domainsSo, many language variants have been developed An important one, the Action Description Language (ADL)23The Planning ProblemWhat is planning ?The task of coming up with a sequence of actions that will achieve a goalTwo

23、 examples of planning agentsThe search-based problem-solving agentThe logical planning agent24The Planning ProblemPlanning Domain Definition language (PDDL) Allows researchers to exchange benchmark problems and compare resultsIncludes sublanguages for STRIPS, ADL, and the hierarchical task networks2

24、5The Planning ProblemThe STRIPS and ADL notations are adequate for many domainsStill some significant restrictionsThe most obvious is that they cannot represent in a natural way the ramifications of actionsWe will see more examples of state constraints in section 11.5Classical planning systems do no

25、t even attempt to address the qualification problem, we will see how to address qualifications in chapter 1226The Planning ProblemExample1: Air cargo transport27The Planning ProblemExample2: The spare tire problem28The Planning ProblemExample3: The blocks world29Planning with State-Space SearchOur a

26、ttention in this section is the planning algorithmsThe most straightforward approach: use state-space searchuse the explicit action and goal representations to derive effective heuristics automatically30Planning with State-Space Search31Planning with State-Space SearchForward state-space searchPlann

27、ing with forward state-space search Moves in the forward direction, so sometimes it is called progression planningStart in the problems initial state, considering sequence of actions until we find a sequence that reaches a goal state32Planning with State-Space SearchThe formulation of planning probl

28、ems as state-space search problems The initial state of the search is the initial state from the planning problemThe actions that are applicable to a state are all those whose preconditions are satisfied. The successor state is generated by adding the positive effect literals and deleting the negati

29、ve effect literals The goal test checks whether the state satisfies the goal of the planning problemsThe step cost of each action is typically 1. 33Planning with State-Space SearchIn the absence of function symbols, the state space of a planning problem is finiteAny graph search algorithm that is co

30、mplete will be a complete planning algorithm such as A*34Planning with State-Space SearchWhy forward state-space search was too inefficient to be practical ?First, forward search does not address the irrelevant action problemall applicable actions are considered from each stateSecond, the approach q

31、uickly bogs down without a good heuristic.35Planning with State-Space SearchBackward state-space searchDescribed as part of bidirectional search in chapter3Backward searchDifficult to implement when the goal states are described by a set of constraints rather than being listed explicitlyNot obvious

32、how to generate a description of the possible predecessors of the set of goal statesThe STRIPS representation makes it easySets of states can be described by the literals that must be true in those states36Planning with State-Space SearchThe main advantage of backward searchAllow us to consider only

33、 relevant actionsWhat is an action relevant to a conjunctive goal ?Action achieves one of the conjuncts of the goalE.g. At(C1, B) At(C2, B) At(C20, B)consider At(C1, B), working backwards, we can seek actions that have this as an effect. only one: Unload(C1, p, B)37Planning with State-Space SearchMa

34、ny irrelevant actions can also lead to a goal stateBackward search that allows irrelevant actions will still be complete, but it will be much less efficientThe restriction to relevant actionsBackward search often has a much lower branching factor than forward search38Planning with State-Space Search

35、Searching backwards is called regression planningThe principal question in regression planningWhat are the states from which applying a given action leads to a goal ?Regression the goal through the actionComputing the description of those states39Planning with State-Space SearchThe general process o

36、f constructing predecessors for backward searchGiven a goal description G, let A be an action that is relevant and consistent The corresponding predecessorAny positive effects of A that appear in G are deletedEach precondition literal of A is added, unless it already appears40Planning with State-Spa

37、ce SearchHow to carry out the search ?Any of the standard search algorithmTermination occurs when a predecessor description is generated that is satisfied by the initial state of the planning problemIn the first-order case, satisfaction might require a substitution for variables in the predecessor d

38、escription41Planning with State-Space SearchE.g. the predecessor description is satisfied by the initial stateIn(C1, P12) At(P12, B) At(C2, B) At(C20, B) with substitution p/P12. the substitution must be applied to the actions leading from the state to the goal, producing the solution Unload(C1, P12

39、,B)42Planning with State-Space SearchHeuristics for state-space searchNeither forward nor backward search is efficient without a good heuristicA heuristic function estimates the distance from a state to the goalSTRIPS planning: the distance is the number of actions Basic idea: the effects and the go

40、alsFind the exact is NP hard, but it is possible to find estimates without too much computation most of the timeDerive an admissible heuristic43Planning with State-Space SearchTwo approachesDerive a relaxed problem from the given problemThe optimal solution cost for the relaxed problem gives an admi

41、ssible heuristic for the original problem Pretend that a pure divide-and-conquer algorithm will workCalled the subgoal independence assumption44Planning with State-Space SearchSubgoal independenceOptimisticWhen there are negative interactions between the subplans for each subgoalPessimisticWhen subp

42、lans contain redundant actions45Planning with State-Space SearchHow to derive relaxed planning problemsBy modifying those explicit representations of preconditions and effectsThe simplest ideaRelax the problem by removing all preconditions from the actionsThen every action will always be applicable,

43、 and any literal can be achieves in one stepCombine our relaxed problem46Planning with State-Space SearchA more accurate heuristicConsidering at least the positive interactions arising from actions that achieve multiple goalsFirst, relax the problem further by removing negative effectsThen, count th

44、e minimum number of actions required such that the union of those actions positive effects satisfies the goal47Planning with State-Space SearchAnother way to generate relaxed problemsBy removing negative effects without removing preconditions48Planning with State-Space SearchThe heuristics described

45、 here can be used in either the progression or the regression directionProgression planners using the empty-delete-list heuristic hold the lead49Partial-Order PlanningDrawbacks of Forward and Backward state-space search ?Particular forms of totally ordered plan searchExplore only strictly linear seq

46、uences of actions connected to the start or goalCannot take advantage of problem decomposition50Partial-Order PlanningThe approach in this sectionWorks on several subgoals independently, solves them with several subplans, and then combines the subplansThe advantage: flexibility in the order in which

47、 it constructs the plan 51Partial-Order PlanningLeast commitment strategyThe general strategy of delaying a choice during searchA useful concept for analyzing when decisions should be made in any search problem52Partial-Order PlanningA formal planning problemGoal(RightShoeOn LeftShoeOn)Init()Action(

48、RightShoe, PRECOND: RightSockOn, EFFECT: RightShoeOn)Action(RightSock, EFFECT: RightSockOn)Action(LeftShoe, PRECOND: LeftSockOn, EFFECT: LeftShoeOn)Action(LeftSock, EFFECT: LeftSockOn)53Partial-Order PlanningPartial-order-plannerAny planning algorithm that can place two actions into a plan without s

49、pecifying which comes firstFigure 11.6 shows the solution to the shoes and socks problemThe partial-order solution corresponds to six possible total-order plans; each of these is called a linearization of the partial-order plan54Partial-Order Planning55Partial-Order PlanningHow to implement the part

50、ial-order planningImplemented as a search in the space of partial-order plansStart with an empty planThen consider ways of refining the until come up with a complete plan that solves the problem56Partial-Order PlanningThe pop algorithm for partial-order planningWrite out as a stand-alone problemInst

51、ead formulate partial-order planning as an instance of a search problemA wide variety of uninformed or heuristic search methods can be applied once the search problem is formulated57Partial-Order PlanningThe states are the plansTo avoid confusion with the sates of the world, we will talk about plans

52、 rather than statesEach plan have four components 58Partial-Order PlanningFour components of each planA set of actions that make up the steps of the planA set of ordering constraintsA set of causal linksA set of open preconditionsThe first two define the steps of the plan, and the last two serve a b

53、ookkeeping function to determine how plans can be extended59Partial-Order PlanningE.g. Figure 11.6 has the following components60Partial-Order PlanningConsistent planA plan in which there are no cycles in the ordering constraints and no conflicts with the causal linksSolutionA consistent plan with n

54、o open preconditions61Partial-Order PlanningFormulate the search problem that POP solvesBegin with a formulation suitable for propositional planning problems, leaving the first-order complications for laterThe definition includes the initial state, actions, and goal test62Partial-Order PlanningA par

55、tial-order planning example63Partial-Order PlanningThe sequence of events1. Pick the only open precondition, At(Spare, Axle) of Finish. Choose the only applicable action, PutOn(Spare, Axle)2. Pick the At(Spare, Ground) precondition of PutOn(Spare, Axle). Choose the only applicable action, Remove(Spa

56、re, Trunk) to achieve it. The resulting plan is shown in Figure 11.864Partial-Order Planning65Partial-Order Planning3. Pick the At(Flat, Axle) precondition of PutOn(Spare, Axle). Just to be contrary, choose the LeaveOvernight action rather than the Remove(Flat, Axle) action. Notice that LeaveOvernig

57、ht also has the effect At(Spare, Ground), which means it conflicts with the causal linkto solve the conflict we add an ordering constraint putting LeaveOvernight before Remove(Spare, Trunk).The resulting plan is shown in Figure 11.9 66Partial-Order Planning67Partial-Order Planning4. We are forced to

58、 back up, remove the LeaceOvernight action and the last two causal links, and return to the state in Figure 11.8. In essence, the planner has proved that LeaceOvernight dosent work as a way to change a tire.5. Consider again the At(Flat, Axle) precondition of the PutOn(Spare, Axle). This time we cho

59、ose Remove(Flat, Axle). 68Partial-Order Planning6. Once again, pick the At(Spare, Trunk) precondition of Remove(Spare, Trunk) and choose Start to achieve it. This time there are no conflicts.7. Pick the At(Flat, Axle) precondition of Remove(Flat, Axle), and choose Start to achieve it. This gives us

60、a complete, consistent plan as shown in Figure 11.10 69Partial-Order Planning70Partial-Order PlanningPartial-order planning with unbound variablesThe complications that can arise when POP is used with first-order action representations that include variables is consideredThe variable unbounddelay ma