Representations for Classical Planning

A restricted state-transition system is one that meets all of the restrictive assumptions A0 through A7 given in before. It is a deterministic, static, finite, and fully observable state-transition system with restricted goals and implicit time.

Such a system is denoted (S,A, F) instead of (S,A, E, Y) because there are no contingent events.

Classical planning (i.e. STRIPS planning) refers generically to planning for restricted state-transition systems.

Motivations for studying classical planning:

  1. As usual in science when one is facing a very complex problem, it is very useful to make restrictive assumptions in order to work out well-founded models and approaches. In planning, assumptions A0 through A7 led to this baseline class.

Main issues (i.e. problems) in classical planning are:

  1. How to represent the states and the actions in a way that does not explicitly enumerate S,A, and y. Without such a representation, it is not possible to develop domain-independent approaches to planning.
  2. How to perform the search for a solution efficiently: which search space, which algorithm, and what heuristics and control techniques to use for finding a solution.

Why we need problem representation?

A necessary input to any planning algorithm is a description of the problem to be solved. In practice, it usually would be impossible for this problem description to include an explicit enumeration of all the possible states and state transitions: Such a problem description would be exceedingly large, and generating it would usually require more work than solving the planning problem. Instead, a problem representation is needed that does not explicitly enumerate the states and state transitions but makes it easy to compute them on-the-fly.

There are three different ways of to represent classical planning problems:

  1. In a set-theoretic representation.
    Each state of the world is a set of propositions, and each action is a syntactic expression specifying which propositions belong to the state in order for the action to be applicable and which propositions the action will add or remove in order to make a new state of the world.
  2. In a classical representation.
    The states and actions are like the ones described for set-theoretic representations except that first-order literals and logical connectives are used instead of propositions, This is the most popular choice for restricted state-transition systems.
  3. In a state-variable representation.
    Each state is represented by a tuple of values of n state variables {Xl,…, Xn}, and each action is represented by a partial function that maps this tuple into some other tuple of values of the n state variables. This approach is especially useful for representing domains in which a state is a set of attributes that range over finite domains and whose values change over time.

 

Set-Theoretic Representation

We will usually call such problems set-theoretic planning problems, and we will refer to the representation scheme as set-theoretic planning.

Note that minimal solution can’t be redundant.

Properties of the set-theoretic representations:

  1. Readability.
    One advantage of the set-theoretic representation is that it provides a more concise and readable representation of the state-transition system than we would get by enumerating all of the states and transitions explicitly.
  2. Ease of Computation.
    Most of computations depend on basic set theory operations.
  3. Expressively.
    Some problems can’t be expressed in this form (i.e. finding prime number problem)

 

Classical Representation

The classical representation scheme generalizes the set-theoretic representation scheme using notation derived from first-order logic. States are represented as sets of logical atoms that are true or false within some interpretation. Actions are represented by planning operators that change the truth values of these atoms.

A state is a set of ground atoms of L. Since L has no function symbols, the set S of all possible states is guaranteed to be finite. As in the set-theoretic representation scheme, an atom p holds in s iff p belongs to s. If g is a set of literals (i.e., atoms and negated atoms), we will say that s satisfies g (denoted s |= g) when there is a substitution SEGMA such that every positive literal of SEGMA (g) is in s and no negated literal of SEGMA (g) is in s.

 

The predicate which can be considered as a function of the set of states; will be called a fluent or flexible relation.

 

Predicates that are constant from state to state are called rigid relation.

 

Closed-world assumption means that an atom that is not explicitly specified in a state does not hold in that state.

 

Rigid relations cannot appear in the effects of any operator o because they are invariant over all the states; they can be used only in precond(o). In other words, any predicate in effects(o) is a flexible relation.

An action a is relevant for g, i.e., a can produce a state that satisfies g, if:    

DWR = Dock-Worker Robots.

Extensions to classical representation:

  1. Simple Syntactical Extensions.
  2. Conditional Planning Operators.
  3. Quantified Expressions.
  4. Disjunctive Preconditions.
  5. Axiomatic Inference.
    1. This technique distinct two new classes of flexible relations: Primary Relations and Secondary Relations.
  6. Function Symbols.
  7. Attached procedures.
  8. Extended Goals.

 

State-Variable Representation

A state-variable representation relies on the following ingredients:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s