It is useful to characterize the relationship between Formulation 2.4 and the original 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 context of the STRIPS-like representation. Now consider making this more concrete. Suppose that every predicate has arguments, and any instance could appear in each argument. This means that there are 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
The next step in converting to a state-space representation is to encode the initial state as a string. The goal set, , 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 that is expressed with positive and negative literals.
Now convert the operators. For each state, , the set represents the set of operators with preconditions that are satisfied by . To apply the search techniques of Section 2.2, note that it is not necessary to determine explicitly in advance for all . Instead, can be computed whenever each is encountered for the first time in the search. The effects of the operator are encoded by the state transition equation. From a given , the next state, , 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 components 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 of the cost functional, , 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.
Steven M LaValle 2012-04-20