Characterizing Subgoal Interactions for Planning

1 Introduction

Despite considerable research over past decades, many topics in planning remain a black art . In particular, it is often difficult to predict the performance of a given plan­ ner on a new domain without lengthy empirical tests. Recently, Korf has suggested that subgoal interactions are a good predictor for planning performance [5] . How­ ever, while Korf's seminal analysis of independent, se­ rializable, and nonserializable collections of subgoals [5] forms the foundation for a theory of planning perfor­ mance, Korf's interaction taxonomy fails to differentiate between classes that have vastly different computational properties. In particular, we have found [1] that some sets of serializable subgoals can be quickly solved while others are intractable. In this paper we introduce a pre­ dictive theory of planning performance by refining Korf's taxonomy with the following classes:

• A set of subgoals is TRIVIALLY SERIALIZABLE if each subgoal can be solved sequentially in any order with­ out ever violating past progress. We show that triv­ ial serializability is more general than independence, yet results in comparable performance.

·This research is funded in part by National Science Foun­ dation Grant IRI-8957302, Office of Naval Research Grant 90-J-1904, and a grant from the Xerox corporation.

• A set of sub~oals is LABORIOUSLY SERIALIZABLE if there exists ;; orders in which the subgoals can not be solved without possibly violating past progress. When it is difficult to determine the correct order, on average laboriously serializable subgoals are as intractable as nonserializable ones.

In extensive empirical studies reported elsewhere [1], we found complete correlation between planning perfor­ mance in a domain and the type of subgoal interactions in that domain. Each planner performed well only when dealing with problems whose subgoals were independent or trivially serializable; problems with laboriously seri­ alizable or nonserializable subgoals were intractable.

In this paper, we argue that our extended hierarchy of subgoal interactions (figure 2) allows a crisp analysis of the performance of multiple planning algorithms on a variety of domains. To buttress our claims, we ana­ lyze three different commitment strategies for ordering decisions in planning. We consider three different plan­ ning algorithms: POCL a partial order algorithm de­ vised by McAllester and Rosenblitt [6], TOCL a similar algorithm which commits to a total order, and TOP!, a plan-state algorithm which is isomorphic to a regression search through the space of world-states.

We construct an artificial domain ( D 1 S 1 *) to differen­ tiate between the planning algorithms. D 1 S 1 * sub goals are trivially serializable for POCL, laboriously serializ­ able for TOCL, and nonserializable for TOP!. Our the­ ory predicts that POCL should perform well on problems in this domain but that the total order planners should branch intractably. We ran empirical tests on randomly generated problems which confirmed these predictions. Thus we conclude that there is supporting evidence for our claims of a predictive theory.

In the next section we formally define the class of plan­ ning problems that we consider and describe the three planning algorithms. In section 3, we extend Korf's tax­ onomy of subgoal interactions and cast it in the context of search through the space of incomplete plans. Then, in section 4 we demonstrate that the representations used by the different planners engender different classes of subgoal interactions for a given problem domain. Sec­ tion 5 confirms our predictions of the planners' empirical behavior. Finally, section 6 discusses related work and 7 summarizes our results.

2 Planning Algorithms

Like [5], we view planning as a search problem. In or­ der to discuss our planners, we need to define a planning problem and how it can be considered as a search pro­ cess. From [6] we adopt:

Definition 1 A STRIPS OPERATOR consists of an op­ erator name plus a PRECONDITION LIST, an ADD LIST and a DELETE LIST. The elements of the precondition, add, and delete lists are all function-free, atomic ex­ pressions. A STRIPS PLANNING PROBLEM is a triple -<.0, E, 0>- in which 0 denotes a set of STRIPS opera­ tors, E denotes a set of initial propositions, and 0 de­ notes a set of goal propositions.

2.1 Plan-State Searches

Previous analyses of planning problems [3; 5] viewed planning as a search through a graph of world-states - i.e. a graph in which nodes are labeled with a set of propositions that specify what is true in that state of the world. If an operator's preconditions are satisfied in a world-state, then an edge leads from that node to the node denoting the effect of applying that operator. One of the major contributions of Sacerdoti's NOAH [11] was a conceptual shift: instead of viewing planning as search through a space of world-states, NOAH searched through a space of (possibly incomplete) plan-states. Our plan­ ners perform similar searches.

Definition 2 A PLAN-STATE is a triple: -<.S, 0, B>- in which S denotes a set of plan steps (also known as ac­ tions), 0 denotes a set of ordering constraints that spec­ ify a (possibly partial) order on S, and B denotes a set of binding constraints over the variables mentioned by the steps in S.

Reformulation in terms of plan-states makes the struc­ ture of a search space dependent on the planner as well as the domain. The arcs between world-states represent feasible domain actions, but the arcs between plan-states represent feasible extensions to an incomplete plan (i.e., the addition of a step, ordering constraint or binding constraint).

In plan-state search, a planning problem is encoded in an initial plan-state -<.S, 0, B>-consisting of two steps so and Soo 0 The step so adds E, and Soo has n for pre­ conditions. This plan-state has no variable-binding con­ straints, but 0 has one constraint to force s0 before s00 · The set of operators, 0, defines the possible steps which can be added to the set of steps, S, in a plan-state. The goal of the search is to find a solution plan-state.

Definition 3 A SOLUTION PLAN-STATE -<.S, 0, B>-is a plan-state in which the preconditions of each step s; E S are all necessarily true in the input situation of s;.

To make this definition precise, we recall the following terminology from Chapman's formalization of planning [2] . The input situation of a step is a set of propositions that are true immediately prior to the execution of that step. A proposition is necessarily true in the input situa­ tion of a step in a partially ordered plan-state -<.S, 0, B>­ when it is true in all completions that extend the partial constraints of 0 and B into total constraints.

2.2 Algorithms

In order to test our intuitions regarding how represen­ tations of the space of plan-states affects planning difficulty, we implemented three different planning algo­ rithms. Each of these algorithms is sound, complete, and exhibits what McAllester terms the "systematic" property [6)1. Loosely speaking, systematicity means that each algorithm is guaranteed to search among plan­ states in an irredundant fashion - visiting every possible plan-state exactly once. This property is reflected in the structure of each planner's search space in that the di­ rected edges form a tree rooted in the initial plan-state.

The first algorithm, called POCL, is a lifted version of McAllester's algorithm. 2 It uses a partially ordered step representation for defining plans, and is shown in figure 1. POCL uses causal links to record the purpose for in­ troducing a step into a plan and to protect that purpose. If a step S; adds a proposition p to satisfy a precondition of step Si, then sJ!. ... si denotes the causal link. In a plan-state, a link sJ!. ... sj is threatened if some existing step S~c can be ordered between S; and Sj, and S~c either deletes or adds 3 a proposition that can be unified with p by adding variable-binding constraints without making the plan-state's variable constraint set inconsistent.

In an invocation of POCL, each precondition p of a plan-state step Sj is an open condition if it has no corresponding causal link s,.!...S; E L. POCL searches for a solution plan-state by eliminating open conditions in G while ensuring the safety of causal links in L.

The second algorithm, TOCL, is similar to POCL, but it restricts its use of plan-states by only generating plans with totally ordered sets of steps. It can insert steps anywhere between s0 and s00 in a plan, but it can never reorder two existing steps. The algorithm is created from POCL by adding a step to linearize the plan immediately prior to the recursive call, and optimizing the other steps to take advantage of the total-order plan.

The third algorithm, TOP/, is a simple regression planner like the one in [9] . It only adds steps to the beginning of the plan (i .e., immediately after s0 ). Al­ though TOP/ does not require data structures for links or step ordering, it shares with the other algorithms the data structures and routines for variable bindings and constraints.

3 Characterizing Subgoal Interactions

Like [3] and [5] we measure the difficulty of a problem in terms of how hard it is to break it up into subproblems and use these subproblems to guide the search for a final solution.

1 We note that the utility of systematicity has not been clearly documented. We suspect that for some domains sys­ tematic planners will be more efficient than nonsystematic algorithms while the converse will hold in other domains. Since a detailed evaluation of the utility of systematicity is beyond the scope of this paper (but see [4]), we feel that holding systematicity constant in our experiments increases their validity.

2 A COMMON LISP implementation of this algorithm, known as SNLP, has become quite popular as a frame­ work for AI research and education. Send mail to bug-snlptcs .washington. edu to acquire the source code for the three planners and for test domains.

3 Steps that add p threaten the causal link s,.!:..si because they negate the purpose for adding step S;. POCL would not be systematic if it ignored these threats.

Algorithm: POCL(-<.S, 0, B>-,G,L)

1. Termination: If G = 0, report success and stop.
2. Goal selection: Let c be a proposition in G, and let Sneed be the step for which c is a precondition.
3. Operator selection: Let Sadd be an existing step, or some new step, that adds c before Sneed· If no such step exists or can be added then backtrack. Let L' = L U {Sadd~Sneed), S' = S U {Sadd}, 0' = OU { Sadd -< Sneed}, and B = BU the set of variable bindings to make Sadd add c. Backtrack point: Each existing and possibly addable step must be considered for completeness.
4. Update goal set: Let G' = (G- {c})U precondi­ tions of Sadd, if new.
5. Causal link protection: A step SJ: threatens a causal link sJ!·+si when it can occur between s; and Sj and add or delete p. For every step SJ: that might threaten a causal link sJ!·+Sj E L':
6. Ensure that SJ: does not threaten s;Lsi by adding constraints to 0' and/or B'. Backtrack point: Each way to protect s;Lsi from SJ: must be considered for completeness.
7. Recursive call: POCL{-<S',O',B'>-,G' ,L').

Figure 1: The Partial-Order, Causal-Link Algorithm

3.1 Subgoals

In the simplest case a subgoal is an intermediate state on the path from initial state to goal. Intuitively, it is clear that searching from the initial state to the subgoal and then again from the subgoal to the goal might be faster than searching all the way in one step. Korf presents a broader definition which we adopt for this paper.

... we formally define a SUBGOAL to be a set of states, with the interpretation that a state is an element of a subgoal set if and only if it has properties that satisfy the subgoal [5, page 68].

It is frequently awkward to refer to subgoals explicitly as sets of states. A common technique used in [3] and [5] is to use goal propositions (i.e.' elements of 0) to specify subgoals. A world-state is in a subgoal if the subgoal's associated goal proposition is true in the world-state.

The conceptual shift to planning with plan-states af­ fects the way subgoals are specified. When searching the space of plan-states we define subgoals in terms of the achievability of various elements of 0 .

Definition 4 Let -<0, E, 0>- be a STRIPS planning problem and let P E 0 denote one of the goal propo­ sitions. The SUBGOAL SPECIFIED BY P WITH RESPECT TO -<0, E, 0>- is a set, U, of plan-states such that every -<S, 0, B>-E U satisfies:

1. S contains a step s0 which only adds E.
2. S contains a step S00 which only requires 0.
3. Every total order of S consistent with 0 has s0 and Soc as the first and last steps, respectively.
4. P is necessarily true in the input situation of Soc .

Proving that a proposition P is necessarily true can be done using Chapman's modal truth criterion [2] . Cer­ tain properties of our algorithms make this proof process easier. For example, in TOP/the operator selection step has the restriction that added steps cannot delete open goals. This and the fact that TOP/ can only add steps to the beginning of an incomplete plan ensures that a proposition is necessarily true when it is either in the initial conditions or it is added by a step and all of that step's preconditions are necessarily true. Thus a goal proposition P is necessarily true once all of the open preconditions of steps added to solve P are in the initial conditions.

The causal-link protection-step of TOCL and POCL makes it easy to prove the necessary truth of a propo­ sition. A goal proposition P is necessarily true if it has an associated causal link s;.!:soc, and all of the pre­ conditions step s; are necessarily true. The causal-link­ protection step ensures that no steps ever interfere with the truth of P . Thus P is necessarily true once all of preconditions of all of the steps involved in solving P

have associated causal links.

3.2 Korf's Subgoal Hierarchy

Frequently, a problem is difficult enough to make it nec­ essary to specify several subgoals in the effort to guide search. Korf classifies a set of subgoals in terms of how the members interact with each other.

Independent subgoals are the rare ideal case - progress toward one has no effect on another. We follow Korf's definition:

A collection of subgoals are INDEPENDENT if each operator only changes the distance to a single subgoal. ... One of the important prop­ erties of independent subgoals, which is clear from the definition, is that an optimal global solution can be achieved by simply concatenat­ ing together optimal solutions to the individual subproblems in any order [5, page 71] .

Solving a single independent subgoal might be non­ trivial, but the complexity of problems with independent subgoals increases only linearly with the number of sub­ goals. Korf defines serializable subgoals, those that do interact in a limited manner, with the following state­ ments.

We define a set of subgoals to be SERIALIZABLE if there exists an ordering among the subgoals such that the subgoals can always be solved sequentially without ever violating a previously solved subgoal in the order [5, page 71].

Thus, serializability means that for every state in the intersection of the first n subgoals there exists a path to a state in the n + 1st sub goal that lies wholly within the intersection. Since these paths are ways to reach later subgoals without interfering with those previously achieved, each subgoal only has to be established once. Of course, using the wrong order can lead to having to violate and reestablish a subgoal an exponential number of times.

Korf labels all sets of subgoals that aren't serializable as nonserializable:

It is often the case that given a collection of subgoals, previously satisfied subgoals must be violated in order to make further progress to­ wards the main goal, regardless of the solution order. Such a collection of subgoals will be called NON-SERIALIZABLE (5, pages 72-73).

Since nonserializable subgoals may need to be violated and reestablished many times, they offer little guidance to a planner: solution time will likely rise superlinearly with the number of subgoals.

3.3 Extending the Interaction Hierarchy

Extensive empirical experiments [1) showed that Korf's hierarchy was not detailed enough to predict the perfor­ mance of planning algorithms in a domain. In particu­ lar, some sets of serializable sub goals are easy to solve while others are intractable. Furthermore, the notion of complete subgoal independence is so restrictive that it seldom occurs in practice. We address this weakness by refining the interaction taxonomy:

Definition 5 A set of subgoals is TRIVIALLY SERIAL­ IZABLE if they can be solved in any order without ever violating a previously solved subgoal.

We note the following important properties:

Proposition 1 Let U and V be sets of subgoals such that v ~u.

1. If U is serializable then V may be serializable or nonserializable.
2. If U is trivially serializable then V is trivially seri­ alizable.

Proof: An observation of Korf's [5] regarding the Suss­ man Anomaly proves part 1. He showed that the goal set {(on A B), (on B C)} is nonserializable (in the space of world-states), but the superset {(on A B) , (on B C), (on C Table)} is serializable. The proof of part 2 is straightforward. 0

Proposition 1 illustrates why arbitrary serializable ~oals can be difficult - when subsets are considered (e.g., in localized decision making) then mistakes can be made which require backtracking over previously satis­ fied subgoals. This isn't true when subgoals are trivially serializable. Furthermore, trivial serializability is more general than independence because it is strictly a topo­ logical property while independence is metric (i.e., de­ fined in terms of a distance function). In particular, two trivially serializable sub goals are not independent if some operator helps to achieve both of them. Of course there is a price for the extra generality - trivial serializabil­ ity does not carry the compositional properties that are entailed by independence. In particular, solutions to the separate subgoals cannot necessarily be concatenated to achieve a solution to the conjunct . Nevertheless, trivial serializability is much more common than independence and it appears to make the complexity of planning linear in the number of subgoals.

Just as trivially serialized subgoals represent an ideal collection, it is natural to consider collections of sub goals that are pathological while still being serializable. For such a collection of subgoals, it is difficult to determine the correct order. Solving problems with laboriously se­ rializable sub goals, without prior knowledge of the order, may take time exponential in the number of sub goals.

Definition 6 A set of n subgoals is LABORIOUSLY SERI­ ALIZABLE if there exists at least one serializable ordering yet at least ~ of the subgoal orders can not be solved se­ quentially without possibly violating a previously solved subgoal.

Even if the majority of subgoal orderings are fine, the exponential cost of backtracking on the few pathological cases will dominate average planning time. Since bad orderings can require exponentially more time than good orderings, tractability requires that the number of bad orderings be exponentially decreasing in the number of orderings. But if ~ (or any only polynomially decreasing percentage) of the orderings are bad, then intractability will dominate. We summarize our extended taxonomy in figure 2.

4 Analyzing Planning Performance

In this section we present a problem domain which in­ duces a different class of subgoal interactions for each of the three planners. Subgoals in this domain are nonseri­ alizable for TOP!, laboriously serializable for TOCL, yet trivially serializable for POCL. As with other domains that we have tested [1], this classification was predic­ tive of empirical results: only the partial order planner was able to quickly solve randomly generated problems in this domain. These problems consist of n + 1 possi­ ble goal conditions, G. and G1 through Gn, which are achieved with n + 2 possible STRIPS actions:

(de:t-step :action Ai :precond {I;} :add {Gi} :delete Ui+l· I.}) (de:t-step :action A; :precond {P.} :add {G.} :delete {It}) (de:t-step :action A! :precond {I.} :add {P.} :delete {})

We call this domain D 1 S 1 * because it was created from D 1 S 1 (reported in [1]) by adding the actions and conditions that are subscripted with an asterisk. The steps interact with each other through their :delete lists in a manner which ensures that only a single ordering of steps will achieve a given problem. As illustrated in figure 3 steps Ai, or A;, would threaten the precondition link of the step immediately above it, and all steps Ai threaten the precondition of step A! .

Proposition 2 The subgoals specified by the problem conjuncts {i.e., specified by Gi and by G.} in the D 1 S 1 * domain are nonserializable for TOP!.

Proof: Consider the subgoals for conditions G1 and G ·. Achieving G 1 requires adding step A1 , and achiev­ ing G * requires adding steps A! and A; . Since A;

deletes h, it must be added before A1. Since A 2 is irrelevant to other subgoals, G. must be ordered before G1 . Similarly, step A1 's deleting I. leads to the requirement that G1 must be ordered before G · . Since these two constraints are contradictory, there are no valid subgoal orderings. 0

The causal link algorithms differ from TOP! in that they focus on a single subgoal and, upon reaching that subgoal, move on to the next subgoal in the ordering.

Proposition 3 The subgoals specified by the problem conjuncts in the D 1 5 1 * domain are trivially serializable for POCL.

Proof: Consider the plan-state reached by focusing on the first m subgoals. Suppose that its m steps are ordered such that A; precedes Ai+l· This is trivially true of the initial plan-state. Achieving the m + 1st sub~oal involves adding a step, and protecting . causal hnks ensures that all m + 1 steps in the new plan-state are ordered such that A; precedes Ai+l · Since this partial ordering is consistent, POCL can always achieve the next subgoal without violating a previous subgoal.

Similarly, achieving the subgoal specified by G. can be doni ~t ~ny ~oint in this arbitrary ordering. The step A. 1s JUSt hke any step A;, and protecting the link for I. always forces A! before any step A; . 0

Proposition 4 The subgoals specified by the problem conjuncts in the D 1 5 1 * domain are laboriously serial­ izable for TOCL.

Proof: Consider orderings of the subgoals specified by G1 through Gn, and let the first subgoal be speci­ fied by G;. The next sub goal in the ordering must be specified by G;_ 1 or by G;+l· When TOCL at­ tempts to satisfy the subgoal specified by Gj for Jj - iJ # 1, the steps A; and Aj will appear uncon­ strained with respect to each other because they do not affect each others preconditions. This lack of an ordering constraint gives the linearization step license to choose an arbitrary order. However since the steps in the final solution are totally ordered only one of these arbitrary orders is the correct one: This means that subgoal Gj may have to be vio­ lated, via backtracking, to find the correct order .

In general the valid serialization orders are those where a subgoal G; only appears at the beginning or after the appearance of G;_1 or G;+l · Any other ordering would have a case like the one described above. There are ( ~ = ~ ) such orders that start with �~c, and the total number of such orders is 2n-1 .

Consider including the sub goal specified by G ·. The subgoals are still serializable. Any serialization or­ dering of the subgoals specified by G1 through Gn becomes a serialization ordering for the entire set of subgoals when the subgoal for G. is inserted after G1 's subgoal, or at the beginning of the ordering that starts with G1 . This makes the total number of serialization orderings 2n. Since 2n is a small fraction of (n + 1)! for large n , the subgoals are la­ boriously serializable.D

5 Empirical Results

Our theory predicts that both total order planners should find problems in D 1 S 1 * intractable while the partial order planner should have no difficulty. We tested our predictions by generating 390 problems at 13 dif­ ferent difficulty levels (30 problems per problem type). Each problem type contained 13 initial conditions and had a difficulty of between 1 and 13 goal conditions. The initial and goal conditions were randomly permuted for each problem, and performance was measured in seconds of Sun. SPARCSTATION CPU tif!le. The results (mean CPU time and 90% confidence mtervals) appear in fig­ ure 4. As predicted , only POCL excelled.

Interestingly, [1] describes a domain which is similar to D 1 S 1 *, but in which sub goals are trivially serializ­ able for both TOCL and POCL. In this domain TOCL performed slightly better than the partial order 'planner which increases the confidence in our theory.

This paper discusses an artificial (some would say "toy") domain, but our results are quite general. Al­ though the subgoal structure of more realistic domains are messier than D 1 5 1 *, preliminary studies (1] show t~at th~. notions of t~ivial. and laborious serializability w1.ll f~Cihtate t~e e':lg1~eenng of practical planning ap­ phca~wns by pmpomtmg the subgoal interactions that are hkely to be costly for whatever planning algorithm is applied.

6 Related Work

As mentioned previously, our work builds on Korf's (5] taxonomy of subgoals and domain complexity. Joslin and Roach [3] extend Korf's analysis of nonserializable subgoals 4 with a topological analysis of sub goals in terms of their connected components. Our extensions to Korf's taxonomy are independent of Joslin and Roach's contri­ bution since they do not consider the number of viable subgoal orderings while this is the key concept underly­ ing our notions bf trivial and laborious serializability.

Our investigation of partial order planners is matched by Minton et al. [7] who analyze the TO and UA al­ gorithms which resemble propositional versions of our TOCL and POCL algorithms with one difference: un­ like our planners, TO and UA are not systematic. In a recent extension to their earlier work, Minton et al. [8] consider the effects of different search strategies and the distribution of solutions on performance. We have also done extensive empirical studies; our results are detailed in [1] .

7 Conclusions

We have presented a predictive theory of planning per­ formance and supported the theory with experiments on three algorithms which employed different strategies for delaying step ordering decisions. Our paper makes four contributions:

• We demonstrate that Korf's [5] subgoal taxonomy fails to differentiate between classes that have vastly different computational properties. Both TOCL and POCL have serializable subgoals in D 1 5 1 * yet one branches intractably while the other displays apparently linear performance.
• We present a new, predictive theory of planning performance that emphasizes the number of feasi­ ble serialization orderings. The centerpiece of our theory are the classes of TRIVIALLY SERIALIZABLE and LABORIOUSLY SERIALIZABLE sets of subgoals. Since all orderings of trivially serializable subgoals lead to a global solution, this class is computation­ ally tractable. We note that pure trivial and pure laborious serializability are but two points on a con­ tinuum of arduousness and many real problems may be intermediate in difficulty.
• We demonstrate our theory by analyzing commit­ ment strategies for ordering decisions. We consid­ ered three rlanning algorithms and presented a new domain, D S 1 * which distinguished between them. Since the natural sub goal decomposition of a D 1 5 1 * problem is trivially serializable for POCL, labori­ ously serializable for TOCL and nonserializable for TOP!, we predicted that only the partial ordered planner would have acceptable performance in this domain. An empirical study confirmed this predic­ tion providing a measure of confidence in the theory. We note that our theory is consistent with the nu­ merous additional studies presented in [1] .
• Our theory provides a new way to view the advan­ tage of the partial order plan representation. All planners perform well only when confronted with trivially serializable subgoals, but more domains are trivially serializable for partial order planners than for the total order planners.

Much remains to be done. Our results presume a com­ plete search strategy; extending the analysis to aggressive algorithms would be interesting. Our artificial do­ main was easy to analyze because all problems in that domain had the same sub goal interaction class for a given planner. In real world domains, however, a planner is likely to find some problems trivially serializable and others laboriously serializable. Extending our theory to heterogeneous subgoal interactions would be interesting. Also, we have only tested our theory on algorithms han­ dling the restrictive STRIPS representation. We plan to use UCPOP [10] to explore whether partial-order rep­ resentations are useful given more expressive domains which include conditional effects and universally quan­ tified effects. We suspect that our theory will predict UCPOP to be more efficient than totally ordered vari­ ants, but this intuition awaits validation.

4Unfortunately, Joslin and Roach do not phrase their work in these terms, appearing unaware of Korf's work.

ACKNOWLEDGEMENTS

This research was greatly improved by discussions with and comments by Paul Cohen, Ernest Davis, Oren Etzioni, Steve Hanks, James Hendler, Rao Kambham­ pati, Craig Knoblock, Neal Lesh, David McAllester, Steve Minton, Edwin Pednault, Ying Sun, Josh Tenen­ berg, Brian Williams, and Mike Williamson. We thank Steven Soderland, with whom we started this project.