Inapproximability of STRIPS Planning

In which we see how an agent can take advantage of the structure of a problem to construct complex plans of action. The task of coming up with a sequence of actions that will achieve a goal is called planning. We have seen two examples of planning agents so far: the search-based problem-solving agent of Chapter 3 and the logical planning agent of Chapter 10. This chapter is concerned primarily with scaling up to complex planning problems that defeat the approaches we have seen so far. Section 11.1 develops an expressive yet carefully constrained language for representing planning problems, including actions and states. The language is closely related to the propositional and first-order representations of actions in Chapters 7 and 10. Section 11.2 shows how forward and backward search algorithms can take advantage of this representation, primarily through accurate heuristics that can be derived automatically from the structure of the representation. (This is analogous to the way in which effective heuristics were constructed for constraint satisfaction problems in Chapter 5.) Sections 11.3 through 11.5 describe planning algorithms that go beyond forward and backward search, taking advantage of the representation of the problem. In particular, we explore approaches that are not constrained to consider only totally ordered sequences of actions. For this chapter, we consider only environments that are fully observable, deterministic, finite, static (change happens only when the agent acts), and discrete (in time, action, objects, and effects). These are called classical planning environments. In contrast, nonclassical planning is for partially observable or stochastic environments and involves a different set of algorithms and agent designs, outlined in Chapters 12 and 17. THE PLANNING PROBLEM Let us consider what can happen when an ordinary problem-solving agent using standard search algorithms-depth-first, A * , and so on-comes up against large, real-world problems. That will help us design better planning agents. Chapter 11. Planning the state resulting from the action, whereas a negative literal ¬P is asserted to be false. Variables in the effect must also appear in the action's parameter list. To improve readability, some planning systems divide the effect into the add list for positive ADD LIST literals and the delete list for negative literals. DELETE LIST Having defined the syntax for representations of planning problems, we can now define the semantics. The most straightforward way to do this is to describe how actions affect states. (An alternative method is to specify a direct translation into successor-state axioms, whose semantics comes from first-order logic; see Exercise 11.3.) First, we say that an action is applicable in any state that satisfies the precondition; otherwise, the action has no effect. APPLICABLE For a first-order action schema, establishing applicability will involve a substitution θ for the variables in the precondition. For example, suppose the current state is described by This state satisfies the precondition At(p, from) ∧ Plane(p) ∧ Airport(from) ∧ Airport(to) with substitution p/P 1 , from/JFK , to/SFO (among others-see Exercise 11.2). Thus, the concrete action Fly(P 1 , JFK , SFO) is applicable. Starting in state s, the result of executing an applicable action a is a state s that is the RESULT 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 s . Thus, after Fly(P 1 , JFK , SFO), the current state becomes At(P 1 , SFO) ∧ At(P 2 , SFO) ∧ Plane(P 1 ) ∧ Plane(P 2 ) ∧ Airport(JFK ) ∧ Airport(SFO) . Note that if a positive effect is already in s it is not added twice, and if a negative effect is not in s, then that part of the effect is ignored. This definition embodies the so-called STRIPS assumption: that every literal not mentioned in the effect remains unchanged. In this way, STRIPS ASSUMPTION STRIPS avoids the representational frame problem described in Chapter 10. Finally, we can define the solution for a planning problem. In its simplest form, this is SOLUTION just an action sequence that, when executed in the initial state, results in a state that satisfies the goal. Later in the chapter, we will allow solutions to be partially ordered sets of actions, provided that every action sequence that respects the partial order is a solution. STRIPS Language ADL Language Only positive literals in states: Positive and negative literals in states: Poor ∧ Unknown ¬Rich ∧ ¬Famous Closed World Assumption: Open World Assumption: Unmentioned literals are false. Unmentioned literals are unknown. Effect P ∧ ¬Q means add P and delete Q. Effect P ∧ ¬Q means add P and ¬Q and delete ¬P and Q. Only ground literals in goals: Quantified variables in goals: Rich ∧ Famous ∃xAt (P 1 , x) ∧ At(P 2 , x) is the goal of having P 1 and P 2 in the same place. Goals are conjunctions: Goals allow conjunction and disjunction: Rich ∧