Contact info.
 
My Secret Life as a Spaghetti Coder
home | about | contact | privacy statement
It was apparent as far back as 1975 that "linear planning" (or totally ordered planning, as described in What is Partial-Order Planning?) was not sufficient. Russell and Norvig relay the story of Allen Brown's experiment: that it could not solve simple problems such as the Sussman anomaly, where given 3 blocks labeled A, B, and C, with block B on the table and C on top of A which is on the table, get to the goal state of A on top of B on top of C (Russell, 410, 414) (See Figure 1). Around that time, as part of his Ph.D., Austin Tate released a paper which described INTERPLAN, a system to solve the problem of interleaving shown by Brown using Sussman's HACKER program (the Sussman Anomaly) (Tate [A] / Russell 410).

Shortly thereafter, Earl D. Sacerdoti released his paper, "The Nonlinear Nature of Plans" which presented a new data structure to represent plans and gave a glimpse of the first partial order planners, Nets Of Action Hierarchies (NOAH) (and compared that to INTERPLAN, among others) (Sacerdoti, 8).


Figure 1. The Sussman Anomaly.

Sacerdoti begins by acknowledging that, "we usually think of plans as linear sequences of actions … because plans are usually executed one step at a time." However, he observed, the "plans themselves are not constrained by limitations of linearity." Because of this, a new structure is needed, which he calls a "procedural net," that would represent "a plan as a partial ordering of actions with respect to time" (Sacerdoti, 1). He backs up his assertion showing the famous Sussman anomaly (described above), and moves on to describe procedural nets and NOAH itself.

Procedural nets are networks of four different types of nodes (GOAL, PHANTOM, SPLIT, and JOIN) and each node represents an action. The nodes are then linked together to form plans. GOAL nodes, clearly, represent a goal that should be achieved. PHANTOM nodes "represent goals that should already be true at the time they are encountered." And, as one might imagine, SPLIT nodes represent splits in the plan, while JOIN nodes represent forks that are coming to an end. Finally, as it is implemented, each of the nodes has a pointer to some code (also known as a closure, lambda expression, or anonymous function) (Sacerdoti, 2).

NOAH uses that structure to represent plans, and a "generic" domain specific language called SOUP (Semantics of a Users' Problem) to give the system knowledge about the task domain (Sacerdoti, 2). To clarify, I call it generic here because it is suitable for describing problems in many domains, but it is specific in that its sole purpose is to describe problems.

To create a new plan, first give NOAH a goal to achieve and tell it about the problem with SOUP. Then it builds a procedural net with only a goal node, which contains a "list of all relevant SOUP functions as its body." Finally, run the planning algorithm. The planning algorithm is described as (quoting Sacerdoti, 3):
  1. Simulate the most detailed plan in the procedural net. This will have the effect of producing a new, more detailed plan.
  2. Criticize the new plan, performing any necessary reordering or elimination of redundant operations.
  3. Go to Step 1.
(Sacerdoti, 3).
Step one is performed in effect by calling the anonymous function pointed to by the node. Step two runs the plan against several critics, namely "Resolve Conflicts," "Use Existing Objects," and "Eliminate Redundant Preconditions," which all perform the actions one would expect from knowing their names (Sacerdoti, 4).

After the release of NOAH, Tate created a new partial order planner dubbed NONLIN. From Sacerdoti, he recognizes "that ordering constraints should only be imposed between the actions comprising a plan if these are necessary for the achievement of the overall purpose of the plan" and bases his work upon it (Tate [B], 889). On the other hand, Tate realized the need for NONLIN because NOAH
still had to make choices as to the order that actions were to be placed-in a plan to correct for interactions. NOAH made this choice in one particular way. It did not keep any backtrack choice points, so this decision, once made, was irreversible. This leads to an incompleteness of the search space which can render some simple block pushing tasks unachieveable (sic) by NOAH… NONLIN is capable of correcting for an interaction by suggesting two orderings (which are sufficient to ensure the incompleteness of NOAH mentioned above is avoided…). (Tate [B], 889)
Additionally, Tate said that "other operations performed by NOAH deterministically … should also be considered as choice points" and gives two examples where "if such decisions cannot be undone, some problems are unsolvable." Of course, NONLIN fixed these problems (Tate [B], 889).

Questions, comments, observations, and critiques on how to improve this are appreciated, as always.


References:
Figure 1: Retrieved on 4/20/2007 from this place and verified in Russell and Sacerdoti.

Russell, Stuart and Norvig, Peter. Artificial Intelligence: A Modern Approach 2nd Edition. New Jersey: Pearson Education, 2003.

Sacerdoti, Earl D. "The Nonlinear Nature of Plans." 1975. Proceedings of the Fourth International Joint Conference on Artificial Intelligence. Retrieved on 4/20/2007 from here on the World Wide Web.

Tate, Austin [A]. "INTERPLAN: a plan generation system which can deal with interactions between goals" Research Memorandum MIP-R-109, Edinburgh: Machine Intelligence Research Unit, December 1974. (Can be found online at here)

Tate, Austin [B]. "Generating Project Networks", Proceedings of the Fifth International Joint Conference on Artificial Intelligence (IJCAI-77) pp. 888-893, Boston, Mass. USA, August 1977. (Can be found online here)

Hey! Why don't you make your life easier and subscribe to the full post or short blurb RSS feed? I'm so confident you'll love my smelly pasta plate wisdom that I'm offering a no-strings-attached, lifetime money back guarantee!


Comments
Leave a comment

What about ABSTRIPS? Was the idea of abstraction spaces completely abandoned?

Posted by Artur on Jan 11, 2008 at 02:19 AM UTC - 6 hrs

I hadn't heard of it at the time I wrote this. Was the original paper "An Analysis of ABSTRIPS" by Craig Knoblock, or something else?

If you're interested in more, I have a part 2 of the selected history at http://www.codeodor.com/index.cfm/2007/4/24/Select... or a PDF of that, an intro to the subject, along with development of a planner in Ruby. The planner is incomplete, however, and has some glaring holes as of today (Never found the time to fix it since they've been discovered)

The PDF of all of it is at http://www.codeodor.com/papers/Larbi__History_of_P...

The HTML of the last bit is at http://www.codeodor.com/index.cfm/2007/5/4/Constru...

Posted by Sammy Larbi on Jan 12, 2008 at 10:45 PM UTC - 6 hrs

Leave a comment

Leave this field empty
Your Name
Email (not displayed, more info?)
Website

Comment:

Subcribe to this comment thread
Remember my details
Google
Web CodeOdor.com

Me
Picture of me

Topics
.NET (19)
AI/Machine Learning (14)
Answers To 100 Interview Questions (10)
Bioinformatics (2)
Business (1)
C and C++ (6)
cfrails (22)
ColdFusion (78)
Customer Relations (15)
Databases (3)
DRY (18)
DSLs (11)
Future Tech (5)
Games (5)
Groovy/Grails (8)
Hardware (1)
IDEs (9)
Java (38)
JavaScript (4)
Linux (2)
Lisp (1)
Mac OS (4)
Management (15)
MediaServerX (1)
Miscellany (75)
OOAD (37)
Productivity (11)
Programming (168)
Programming Quotables (9)
Rails (31)
Ruby (67)
Save Your Job (58)
scriptaGulous (4)
Software Development Process (23)
TDD (41)
TDDing xorblog (6)
Tools (5)
Web Development (7)
Windows (1)
With (1)
YAGNI (10)

Resources
Agile Manifesto & Principles
Principles Of OOD
ColdFusion
CFUnit
Ruby
Ruby on Rails
JUnit



RSS 2.0: Full Post | Short Blurb
Subscribe by email:

Delivered by FeedBurner