Using Logic to Formulate Discrete Planning

For many discrete planning problems that we would like a computer to solve, the state space is enormous (e.g., 10100 states). Therefore, substantial effort has been invested in constructing implicit encodings of problems in hopes that the entire state space does not have to be explored by the algorithm to solve the problem. This will be a recurring theme throughout this book; therefore, it is important to pay close attention to representations. Many planning problems can appear trivial once everything has been explicitly given.

Logic-based representations have been popular for constructing such implicit representations of discrete planning. One historical reason is that such represen- tations were the basis of the majority of artificial intelligence research during the 1950s–1980s. Another reason is that they have been useful for representing cer- tain kinds of planning problems very compactly. It may be helpful to think of these representations as compression schemes. A string such as 010101010101... may compress very nicely, but it is impossible to substantially compress a random string of bits. Similar principles are true for discrete planning. Some problems contain a kind of regularity that enables them to be expressed compactly, whereas for others it may be impossible to find such representations. This is why there has been a variety of representation logics proposed through decades of planning research.

Another reason for using logic-based representations is that many discrete plan- ning algorithms are implemented in large software systems. At some point, when these systems solve a problem, they must provide the complete plan to a user, who may not care about the internals of planning. Logic-based representations have seemed convenient for producing output that logically explains the steps involved to arrive at some goal. Other possibilities may exist, but logic has been a first choice due to its historical popularity.

In spite of these advantages, one shortcoming with logic-based representations is that they are difficult to generalize. It is important in many applications to enable concepts such as continuous spaces, unpredictability, sensing uncertainty, and multiple decision makers to be incorporated into planning. This is the main reason why the state-space representation has been used so far: It will be easy to extend and adapt to the problems covered throughout this book. Nevertheless, it is important to study logic-based representations to understand the relation- ship between the vast majority of discrete planning research and other problems considered in this book, such as motion planning and planning under differential constraints. There are many recurring themes throughout these different kinds of problems, even though historically they have been investigated by separate research communities. Understanding these connections well provides powerful insights into planning issues across all of these areas.

• • 1. A STRIPS-Like Representation

STRIPS-like representations have been the most common logic-based representa- tions for discrete planning problems. This refers to the STRIPS system, which is considered one of the first planning algorithms and representations [337]; its name is derived from the STanford Research Institute Problem Solver. The original representation used first-order logic, which had great expressive power but many technical difficulties. Therefore, the representation was later restricted to only propositional logic [743], which is similar to the form introduced in this section. There are many variations of STRIPS-like representations. Here is one formula- tion:

Formulation 2.4 (STRIPS-Like Planning)

1. A finite, nonempty set I of instances.
2. A finite, nonempty set P of predicates, which are binary-valued (partial) functions of one of more instances. Each application of a predicate to a specific set of instances is called a positive literal. A logically negated positive literal is called a negative literal.
3. A finite, nonempty set O of operators, each of which has: 1) preconditions, which are positive or negative literals that must hold for the operator to apply, and 2) effects, which are positive or negative literals that are the result of applying the operator.
4. An initial set S which is expressed as a set of positive literals. Negative literals are implied. For any positive literal that does not appear in S, its corresponding negative literal is assumed to hold initially.
5. A goal set G which is expressed as a set of both positive and negative literals.

Formulation 2.4.1 provides a definition of discrete feasible planning expressed in a STRIPS-like representation. The three most important components are the sets of instances I, predicates P, and operators O. Informally, the instances characterize the complete set of distinct things that exist in the world. They could, for example, be books, cars, trees, and so on. The predicates correspond to basic properties or statements that can be formed regarding the instances. For example, a predicate called Under might be used to indicate things like Under(Book, T able) (the book is under the table) or Under(Dirt, Rug). A predicate can be interpreted as a kind of function that yields true or false values; however, it is important to note that it is only a partial function because it might not be desirable to allow any instance to be inserted as an argument to the predicate.

If a predicate is evaluated on an instance, for example, Under(Dirt, Rug), the expression is called a positive literal. The set of all possible positive literals can be formed by applying all possible instances to the domains over which the predicates are defined. Every positive literal has a corresponding negative literal, which is

formed by negating the positive literal. For example, Under(Dirt, Rug) is the negative literal that corresponds to the positive literal Under(Dirt, Rug), and denotes negation. Let a complementary pair refer to a positive literal together with its counterpart negative literal. The various components of the planning problem are expressed in terms of positive and negative literals.

¬

¬

The role of an operator is to change the world. To be applicable, a set of pre- conditions must all be satisfied. Each element of this set is a positive or negative literal that must hold true for the operator to be applicable. Any complemen- tary pairs that can be formed from the predicates, but are not mentioned in the preconditions, may assume any value without affecting the applicability of the op- erator. If the operator is applied, then the world is updated in a manner precisely specified by the set of effects, which indicates positive and negative literals that result from the application of the operator. It is assumed that the truth values of all unmentioned complementary pairs are not affected.

Multiple operators are often defined in a single statement by using variables. For example, Insert(i) may allow any instance i I to be inserted. In some cases, this dramatically reduces the space required to express the problem.

∈

The planning problem is expressed in terms of an initial set S of positive literals and a goal set G of positive and negative literals. A state can be defined by selecting either the positive or negative literal for every possible complementary pair. The initial set S specifies such a state by giving the positive literals only. For all possible positive literals that do not appear in S, it is assumed that their negative counterparts hold in the initial state. The goal set G actually refers to a set of states because, for any unmentioned complementary pair, the positive or negative literal may be chosen, and the goal is still achieved. The task is to find a sequence of operators that when applied in succession will transform the world from the initial state into one in which all literals of G are true. For each operator, the preconditions must also be satisfied before it can be applied. The following example illustrates Formulation 2.4.

Example 2.6 (Putting Batteries into a Flashlight) Imagine a planning prob- lem that involves putting two batteries into a flashlight, as shown in Figure 2.17. The set of instances are

I = {Battery1, Battery2, Cap, Flashlight}. (2.21)

Two different predicates will be defined, On and In, each of which is a partial function on I. The predicate On may only be applied to evaluate whether the Cap is On the Flashlight and is written as On(Cap, Flashlight). The pred- icate In may be applied in the following two ways: In(Battery1, Flashlight), In(Battery2, Flashlight), to indicate whether either battery is in the flashlight. Recall that predicates are only partial functions in general. For the predicate In, it is not desirable to apply any instance to any argument. For example, it is meaning- less to define In(Battery1, Battery1) and In(Flashlight, Battery2) (they could be included in the model, always retaining a negative value, but it is inefficient).

Figure 2.17: An example that involves putting batteries into a flashlight.

Name Preconditions Effects

PlaceCap {¬On(Cap, Flashlight)} {On(Cap, Flashlight)}

RemoveCap {On(Cap, Flashlight)} {¬On(Cap, Flashlight)} Insert(i) {¬On(Cap, Flashlight), ¬In(i, Flashlight)} {In(i, Flashlight)}

Figure 2.18: Three operators for the flashlight problem. Note that an operator can be expressed with variable argument(s) for which different instances could be substituted.

The initial set is

S = {On(Cap, Flashlight)}. (2.22)

Based on S, both In(Battery1, Flashlight) and In(Battery2, Flashlight) are assumed to hold. Thus, S indicates that the cap is on the flashlight, but the batteries are outside.

¬ ¬

The goal state is

G = {On(Cap, Flashlight), In(Battery1, Flashlight),

In(Battery2, Flashlight)},

(2.23)

which means that both batteries must be in the flashlight, and the cap must be on.

The set O consists of the four operators, which are shown in Figure 2.18. Here is a plan that reaches the goal state in the smallest number of steps:

(RemoveCap, Insert(Battery1), Insert(Battery2), PlaceCap). (2.24)

In words, the plan simply says to take the cap off, put the batteries in, and place the cap back on.

This example appears quite simple, and one would expect a planning algorithm to easily find such a solution. It can be made more challenging by adding many more instances to I, such as more batteries, more flashlights, and a bunch of objects that are irrelevant to achieving the goal. Also, many other predicates and

operators can be added so that the different combinations of operators become overwhelming. ．

A large number of complexity results exist for planning expressed using logic. The graph search problem is solved efficiently in polynomial time; however, a state transition graph is not given as the input. An input that is expressed using Formulation 2.4 may describe an enormous state transition graph using very few instances, predicates, and operators. In a sense, the model is highly compressed when using some logic-based formulations. This brings it closer to the Kolmogorov complexity [248, 630] of the state transition graph, which is the shortest bit size to which it can possibly be compressed and then fully recovered by a Turing machine. This has the effect of making the planning problem appear more difficult. Concise inputs may encode very challenging planning problems. Most of the known hardness results are surveyed in Chapter 3 of [382]. Under most formulations, logic-based planning is NP-hard. The particular level of hardness (NP, PSPACE, EXPTIME, etc.) depends on the precise problem conditions. For example, the complexity depends on whether the operators are fixed in advance or included in the input. The latter case is much harder. Separate complexities are also obtained based on whether negative literals are allowed in the operator effects and also whether they are allowed in preconditions. The problem is generally harder if both positive and negative literals are allowed in these cases.

• • 1. Converting to the State-Space Representation

It is useful to characterize the relationship between Formulation 2.4 and the origi- nal formulation of discrete feasible planning, Formulation 2.1. One benefit is that it immediately shows how to adapt the search methods of Section 2.2 to work for logic-based representations. It is also helpful to understand the relationships between the algorithmic complexities of the two representations.

Up to now, the notion of “state” has been only vaguely mentioned in the con- text of the STRIPS-like representation. Now consider making this more concrete. Suppose that every predicate has k arguments, and any instance could appear in each argument. This means that there are P I k complementary pairs, which corresponds to all of the ways to substitute instances into all arguments of all predicates. To express the state, a positive or negative literal must be selected from every complementary pair. For convenience, this selection can be encoded as a binary string by imposing a linear ordering on the instances and predicates.

| | | |

Using Example 2.6, the state might be specified in order as

(On(Cap, Flashlight), In(Battery1, Flashlight1), In(Battery2, Flashlight)).

¬

(2.25)

Using a binary string, each element can be “0” to denote a negative literal or “1” to denote positive literal. The encoded state is x = 101 for (2.25). If any instance can appear in the argument of any predicate, then the length of the string is

k

|P | |I| . The total number of possible states of the world that could possibly be

distinguished corresponds to the set of all possible bit strings. This set has size

2|P | |I| . (2.26)

k

The implication is that with a very small number of instances and predicates, an enormous state space can be generated. Even though the search algorithms of Section 2.2 may appear efficient with respect to the size of the search graph (or the number of states), the algorithms appear horribly inefficient with respect to the sizes of P and I. This has motivated substantial efforts on the develop- ment of techniques to help guide the search by exploiting the structure of specific representations. This is the subject of Section 2.5.

The next step in converting to a state-space representation is to encode the initial state xI as a string. The goal set, XG, is the set of all strings that are consistent with the positive and negative goal literals. This can be compressed by extending the string alphabet to include a “don’t care” symbol, δ. A single string that has a “0” for each negative literal, a “1” for each positive literal, and a “δ” for all others would suffice in representing any XG that is expressed with positive and negative literals.

Now convert the operators. For each state, x X, the set U(x) represents the set of operators with preconditions that are satisfied by x. To apply the search techniques of Section 2.2, note that it is not necessary to determine U(x) explicitly in advance for all x X. Instead, U(x) can be computed whenever each x is encountered for the first time in the search. The effects of the operator are encoded by the state transition equation. From a given x X, the next state, f(x, u), is obtained by flipping the bits as prescribed by the effects part of the operator.

∈

∈

∈

All of the components of Formulation 2.1 have been derived from the com- ponents of Formulation 2.4. Adapting the search techniques of Section 2.2 is straightforward. It is also straightforward to extend Formulation 2.4 to represent optimal planning. A cost can be associated with each operator and set of literals that capture the current state. This would express l(x, u) of the cost functional, L, from Section 2.3. Thus, it is even possible to adapt the value-iteration method to work under the logic-based representation, yielding optimal plans.