If you need more context (rather than jumping straight into this), check out
What is Partial-Order Planning?
and
Selected History of Partial Order Planning, Part 1
if you haven't already.
* * * *
As David Chapman noted in 1985, "planners of the most promising ('nonlinear') sort have been complicated, heuristic, ill-defined AI programs, without clear conditions under which they work." And since the time of NOAH, INTERPLAN, and NONLIN (and others I've left out for space reasons), there have been various improvements in the realm of partial-order planning. Chapman's program, TWEAK, is one of them, and was followed by the UCPOP and RePOP planners.
Chapman said that he "decided to copy exactly" Sacerdoti's work on NOAH to implement his own planner, but struggled to make it work (and TWEAK was a result of it when he did finally get it to work). In explaining the reason for publishing his work on TWEAK, Chapman quotes Sacerdoti who said NOAH's "basic operations" (Chapman, 1) "were developed in an ad hoc fashion. No attempt has been made to justify the transformations that they perform, or to enable them to generate all transformations." (Sacerdoti, quoted in Chapman, 1) He then goes on to compare what he has done with Sacerdoti's work to the longstanding AI varieties of "scruffy" versus "neat." In general, the "scruffies" just want to try solutions and figure out what seems to work, and tolerate less mathematical rigor and proof than the "neats" (Russell, 25).
In essence, TWEAK was Chapman's successful attempt at formalizing the "theory about the ways in which interacting subgoals can be dealt with" (Sacerdoti, quoted in Chapman, 1), or formalizing partial-order planning.
Chapman called TWEAK "a rigorous mathematical reconstruction of previous nonlinear planners," and "an implemented, running program," which he described and proved correct in his paper. He was right: eighteen years later Russell and Norvig said his work "led to what arguably the first simple and readable description of a complete partial-order planner," which was incarnated as SNLP (Russell, 410) (on which Russell and Norvig base the POP in their book, which I in turn implement in Ruby in the following section).
After SNLP came UCPOP in 1992 from Daniel Weld (who also was an author of SNLP) and J. Scott Penberthy. As the title says, it is "a sound, complete, partial order planner for ADL." (ADL is a more advanced way to represent problems, Action Description Language). Their desire to create UCPOP stemmed from two problems they found with existing research into POP algorithms. The first hearkens back to the scruffies vs. neats debate: Many researchers "looked at formal characteristics of languages for describing change," as others built "actual planners, often losing a precise understanding of their programs in a forest of pragmatic choices" (Penberthy, 1). Further, the very few that had "
complete algorithms" (emphasis added) either only implemented "the restrictive STRIPS representation" of problems (citing TWEAK and SNLP), or represented "plans as totally ordered sequences of actions" (Penberthy, 1).
Penberthy and Weld described UCPOP as "a theorem prover" at its heart. The algorithm itself requires three parameters: a plan, the set of goals that remain, and a set of actions. The goals are expressed as a tuple with two elements: a precondition and a step in the plan (Penberthy 6-7). An overview of the algorithm can be described as follows:
- If the set of goal states is empty, return the plan (reporting "success").
- Select a goal from the set of goals. If there is an invalid link that makes the plan impossible, exit, reporting failure.
- Choose an operator.
- Generate subgoals.
- Protect against threats that may "cause the undoing of a needed goal if that step is done at the wrong time" (Dyer).
- Recursively call the algorithm if the plan is not inconsistent.
(Penberthy, 6)
Although UCPOP was novel for its time, a visit today to its website (maintained by the authors at the University of Washington) shows it is quite outdated. The authors note, "UCPOP is an aging system - we recommend Sensory Graphplan (SGP) instead. SGP handles a superset of UCPOP functionality and is much, much faster" (Weld). On the other hand, research by XuanLong Nguyen and Subbarao Kambhampati in 2000 has shown that quite a few improvements can be made to UCPOP in particular, and partial-order planning in general.
Nguyen and Kambhampati argue that "the prevailing pessimism about the scalability of partial order planning (POP) algorithms" is perhaps unwarranted (Nguyen, 1). The pair seem to regret that research on POP algorithms seemed to stop (around 5 years prior) and make that point that advances in "heuristic state space planners … and CSP-based planners" like Graphplan are perhaps "(mis)interpreted as establishing the supremacy of state space and CSP-based approaches over" those of the POP variety (Nguyen, 1).
As evidence of their claim, they created RePOP, which is a partial-order planner based on UCPOP. But the novelty of RePOP lies in the authors' "key insight … that the techniques responsible for the efficiency of the currently successful planners … can also be adapted to dramatically improve the efficiency of the POP algorithm" (Nguyen, 1).
The techniques they applied to RePOP that other strategies had applied, "distance based heuristics, disjunctive representations for planning constraints and reachability analysis," led to outstanding results in "several 'parallel planning' domains" (Nguyen, 6). In fact, since in general, partial ordered planners are more flexible than their CSP counterparts, they obtained greater flexibility than Graphplan, while also outperforming it in most of their experiments (Nguyen, 5-6). The performance increase wasn't slight however- in one problem that RePOP took less than 3 seconds to solve, Graphplan took 47 minutes. On average, when GraphPlan could solve a problem within 3 hours or without using all 250 MB of memory, it still took around 10 times longer than RePOP to find a solution (Nguyen, 5).
The systems described above have a common link in that they are all focused on generic problems. However, it should be noted that in some domains, such as medicine, planners of these sorts do not tend to work well. As a consequence, great improvements – in performance and in accuracy – can be made by building a planner that can be supplied with domain-specific information (Miksch). Despite the interesting nature of such systems, covering planners of that sort is outside the scope of this paper, and I now turn to the second task of this report – building a partial order planner in Ruby.
* * * *
I've been doing almost nothing besides reading academic papers the last couple of weeks, and I'm
mostly done on that front. I enjoy reading them, but at times they can be dense, and take several
readings just to understand what's going on. In any case, I'm looking forward to doing some actual
programming now.
As before, questions, comments, observations, and critiques on how to improve this are appreciated.
References:
Chapman, David. "Planning for Conjunctive Goals." Massachusetts Institute of Technology. 1985. Available online from
MIT
Dyer, C.R. "Partial-Order Planning: Chapter 11." CS 540 Lecture Notes. Retrieved on the World Wide Web on 4/24/2007 from
this place.
Figure 1: Retrieved on 4/20/2007 from
this place and verified in Russell and Sacerdoti.
Miksch, Silvia. "Plan management in the medical domain." AI Communications 12, pp 209-235. 1999.
Nguyen, XuanLong and Kambhampati, Subbarao. "Reviving Partial Order Planning." 2000. Retrieved on 4/20/2007 from
around here on the World Wide Web.
Penberthy, J. Scott and Weld, Daniel S. "UCPOP: A Sound, Complete, Partial Order Planner for ADL." Third International Conference on Principles of Knowledge Representation and Reasoning, pp. 189-197. Cambridge, MA.
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)
Weld, Dan and Penberthy, Scott. "The UCPOP Planner." Retrieved on the World Wide Web on 4/19/2007 from
Washington Univ.
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!
