In business software development, the more experienced a developer becomes, the less – he realizes – he knows.  The only developers I know, for the most part, who believe they’re truly gurus in their profession have around three years experience…after that comes a few years of realizing that they’ve only seen the tip of the iceberg to becoming of craftsman in the art of software development.  But developing software for robotics takes this humbling lesson to staggering new heights.

After writing a line-follower way back when, I (thought I) had my “Ah ha, I’ve got it!” moment.  I’ve had a long series of those moments, only to be dramatically humbled again and again when trying to take on increasing complexity.  The most recent, of those humbling moments, came when I began working on the planning layer of a project of mine.  This post is to provide research guidance to others who may be sinking their teeth into this realm.

There are three primary approaches to planning [1]:

• Programming-based approach which involves anticipating every planning decision and hard-coding the planning mechanism.  This approach, while terrific on smaller problems, does not scale well, is tedious to develop and maintain, and becomes brittle as complexity increases.
• Learning-based approach which leverages learning algorithms to “teach” the control layer how to approach particular problems.  (See Ethem Alpaydin’s Introduction to Machine Learning, 2nd Ed. for a foray down this path.)
• Model-based approach which deduces the planning solution from a model of the planning problem.  This approach then has a number of general techniques, including:
  • Classical planning using a basic model using a planning language such as STRIPS, PDDL (the subject of a future post), ADL, or NDDL,
  • Markov Decision Process (MDP) where the model is represented as state transition probabilities and assumes the state is fully observable (discoverable with 100% confidence), and
  • Partially Observable MDP (POMDP) where the state is assumed to be not fully observable.

My current research focus is on emulating probabilistic planning (MDP) using classical planning techniques.  Accordingly, I’d like to share a few key papers and resources, which I have found, which have been of great assistance in my efforts to better understand the planning domain and to prepare for applying it to real-world project work.  (Listed in suggested order to be read.)

• [1] The Model-based Approach to Autonomous Behavior: A Personal View by Geffner
• Automated Planning: Theory & Practice by Ghallab, Nau, and Traverso
• PDDL papers at http://ipc.informatik.uni-freiburg.de/PddlResources
• The Fast Downward Planning System by Helmert, with planner available at http://www.fast-downward.org
• Probabilistic Planning vs. Replanning by Little and Thiebaux
• FF-Replan: A Baseline for Probabilistic Planning by Yoon, Fern and Givan (don’t skip this one!)
• RFF: A Robust, FF-Based MDP Planning Algorithm for Generating Policis with Low Probability of Failure by Teichteil-Konigsbuch, Infantes, and Kuter
• Probabilistic Plan Recognition using off-the-shelf Classical Planners by Ramirez and Geffner
• Automatic Derivation of Memoryless Policies and Finite-State Controllers Using Classical Planners by Bonet, Palacios and Geffner

Other papers that may be of interest:

• PPDDL1.0: The Language for the Probabilistic Part of IPC-4 by Younes and Littman
• Relational Dynamic Influence Diagram Language (RDDL): Language Description by Scott Sanner; RDDL is the new probabilistic language being used for the ICAPS 2011 International Probabilistic Planning Competition (IPPC)
• Planning and acting in partially observable stochastic domains by Kaelbling, Littman, and Cassandra (this will make you truly appreciate the previous paper concerning FF-Replan)
• Hierarchical Methods for Planning under Uncertainty by Pineau
• A Translation-based Approach to Contingent Planning by Albore, Palacios, and Geffner

As for planning tools, you’ll certainly want to check out the following as well:

• Teleo-Reactive Executive (T-REX) hybrid executive for autonomous robotics (uses NDDL as the planning language).  It should be duly noted that TREX has been successfully used on a number of real-world projects.
• Fast Downward planning system (uses PDDL as the planning language)

This should get you going in the right direction for reading up on background materials and emerging research areas in the realm of planning.  Certainly let me know if you have other tips or references, I’m particularly interested in other planning tools being used in real-world scenarios.

Enjoy!
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.