Archive for ‘Planning’ Category
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 :
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.)
Other papers that may be of interest:
As for planning tools, you’ll certainly want to check out the following as well:
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.
Posted 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 , “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 .)
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:
Although it’s difficult to wedge real-world problems into these assumptions, there are practical motivations for starting with such classical planning environments:
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 following, simple action schema describes the action of moving a box from location x to location y:
Action: MoveBox(x, y)
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  is found below, followed by a brief commentary:
STRIPS(A, s, g)
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 , 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.
 Russell, Stuart and Peter Norvig. 2002. Artificial Intelligence, 2nd Ed.
 Nilsson, Nils and Richard Fikes. 1971. http://www.ai.sri.com/pubs/files/tn043r-fikes71.pdf.
 Ghallab, Malik, Dana Nau, and Paolo Traverso. 2004. Automated Planning: Theory & Practice.
© 2011-2014 Codai, Inc. All Rights Reserved