Warning: strlen() expects parameter 1 to be string, array given in /home/sharpr6/public_html/wp-content/themes/starscape/code/starscape.php on line 450
STRIPS for Classical Plan Representation and Planning | SharpRobotica.com - Sharp ideas for the software side of robotics

STRIPS for Classical Plan Representation and Planning

datePosted on 04:38, April 11th, 2011 by Billy McCafferty

Planning concerns itself with determining future actions to achieve goals.  One, albeit naïve, approach to planning is to explicitly represent plans via ifs and for loops, laying out the sequential via low-level code.  But for better flexibility and scalability, if warranted for the task at hand, it’s preferred to represent plans less rigidly; plans that can be more easily adapted to changing and unforeseen circumstances.

Flexible plans, by definition, are not fully constrained by a preset order before execution – a planning algorithm is leveraged to assemble a plan, from a set of available actions, to achieve goals.  Certainly, a challenge is in representing plans formally enough as to be understood and searchable by a planning engine.  As described in Artificial Intelligence [1], “the key is to find a language that is expressive enough to describe a wide variety of problems, but restrictive enough to allow efficient algorithms to operate over it.”  An early language towards this aim is STRIPS; a planning language providing the foundational backbone of many modern day planning representation techniques.

(For historical clarification, STRIPS (Stanford Research Institute Problem Solver) was an automated planner developed in 1971 and also used to name the language providing input to the planner [2].)

Classical Planning

When studying planning techniques, it’s appropriate to begin in the realm of classical planning environments.  These environments apply a number of restrictive assumptions to a planning problem:

  • The planning problem has a finite set of states.
  • It is fully observable:  the state of the system is known with 100% confidence.
  • It is deterministic:  for every action applicable to a state, and applied, the system is brought to a single other state.
  • It is static:  the system state remains constant between applied actions.
  • It is discrete:  actions and events are instantaneous state transitions – they have no duration.
  • A solution plan is an ordered, finite sequence of actions.

Although it’s difficult to wedge real-world problems into these assumptions, there are practical motivations for starting with such classical planning environments:

  • When faced with difficult problems, simplified models help to work out well-founded approaches.
  • Classical planning has served as the foundation for scalable, real-world approaches.
  • Extensions may be applied for relaxing specific (or all) assumptions for practical problem domains.

STRIPS Planning Language

STRIPS is a classical planning language, representing plan components as states, goals, and actions, allowing algorithms to parse the logical structure of the planning problem to provide a solution.

In STRIPS, state is represented as a conjunction of positive literals.  Positive literals may be a propositional literal (e.g., Big ^ Tall) or a first-order literal (e.g., At(Billy, Desk)).  The positive literals must be grounded – may not contain a variable (e.g., At(x, Desk)) – and must be function-free – may not invoke a function to calculate a value (e.g., At(Father(Billy), Desk)).  Any state conditions that are not mentioned are assumed false.

The goal is also represented as a conjunction of positive, ground literals.  A state satisfies a goal if the state contains all of the conjuncted literals in the goal; e.g., Stacked ^ Ordered ^ Purchased satisfies Ordered ^ Stacked.

Actions (or operators) are defined by action schemas, each consisting of three parts:

  • The action name and any parameters.
  • Preconditions which must hold before the action can be executed.  Preconditions are represented as a conjunction of function-free, positive literals.  Any variables in a precondition must appear in the action’s parameter list.
  • Effects which describe how the state of the environment changes when the action is executed.  Effects are represented as a conjunction of function-free literals.  Any variables in a precondition must appear in the action’s parameter list.  Any world state not explicitly impacted by the action schema’s effect is assumed to remain unchanged.

The following, simple action schema describes the action of moving a box from location x to location y:

Action: MoveBox(x, y)
Precond: BoxAt(x)
Effect: BoxAt(y), ¬ BoxAt(x)

If an action is applied, but the current state of the system does not meet the necessary preconditions, then the action has no effect.  But if an action is successfully applied, then any positive literals, in the effect, are added to the current state of the world; correspondingly, any negative literals, in the effect, result in the removal of the corresponding positive literals from the state of the world.

For example, in the action schema above, the effect would result in the proposition BoxAt(y) being added to the known state of the world, while BoxAt(x) would be removed from the known state of the world.  (Recall that state only includes positive literals, so a negation effect results in the removal of positive literals.)  Note also that positive effects can not get duplicated in state; likewise, a negative of a proposition that is not currently in state is simply ignored.  For example, if Open(x) was not previously part of the state, ¬ Open(x) would have no effect.

A STRIPS problem includes the complete (but relevant) initial state of the world, the goal state(s), and action schemas.  A STRIPS algorithm should then be able to accept such a problem, returning a solution.  The solution is simply an action sequence that, when applied to the initial state, results in a state which satisfies the goal.

STRIPS Planning Algorithm

As previously referenced, STRIPS began as an automated planning algorithm and has double-meaning to describe the language (described above) used to provide input to that algorithm.  While the algorithm does not scale well to real-world problems, it, like the language, serves as a foundational starting point to developing and understanding more powerful automated planning algorithms.  The STRIPS algorithm [3] is found below, followed by a brief commentary:

STRIPS(A, s, g)
p = empty plan
loop…
if s satisfies g then return p
a = [an applicable action in A, relevant for g]
if a = null, then return failure
p’ = STRIPS(A, s, precond(a))
if p’ = failure, then return failure
s = apply p’ to s
s = apply a to s
p = p + p’ + a

In the above STRIPS algorithm, A represents all of the possible, grounded actions (i.e., action schemas with variables replaced with values), while s is the current state, and g is the goal state.

Critically important to note is that this algorithm is a backward-search algorithm.  In other words, the goal state of the planning problem is fed into the algorithm as s, while the initial state of the planning problem is provided as g.  The returned solution, if any, simply needs to be reversed to provide the solution to the planning problem.  Simply put, it works backwards from the goal to figure out a logical path to get there.

There’s certainly more to the STRIPS algorithm, detailed nicely in [3], than the basic explanation outlined here, but this should give a cursory introduction to how the STRIPS language can be used to define a planning problem and be searched to find a sound solution.

While the STRIPS language provides a good starting point for representing planning problems, it is far too simplistic to handle real–world planning domains.  Accordingly, the Planning Definition Domain Language (PDDL) has emerged as the de facto means for formerly representing sophisticated planning problems.  PDDL will the subject of our next post.

Enjoy!
Billy McCafferty


References

[1] Russell, Stuart and Peter Norvig.  2002.  Artificial Intelligence, 2nd Ed.

[2] Nilsson, Nils and Richard Fikes.  1971.  http://www.ai.sri.com/pubs/files/tn043r-fikes71.pdf.

[3] Ghallab, Malik, Dana Nau, and Paolo Traverso.  2004. Automated Planning: Theory & Practice.

categoryPosted in Planning | printPrint
Related Posts:

Leave a Reply

Name: (required)
Email: (required) (will not be published)
Website:
Comment:
*

© 2011-2014 Codai, Inc. All Rights Reserved