Factored Planning

1 Introduction

Many planning algorithms use independencies or loose in­ teractions between components in the planning domain to find plans more efficiently. For example, hierarchical plan­ ners divide a goal into subgoals (high-level operators) using a decomposition of the domain into loosely interacting parts (e.g., [Knoblock, 1990; Erol eta!., 1994]). Planning is done at each level separately, and later the subplans are pieced to­ gether to build a valid plan. Other planners that use domain decomposition (e.g., [Lansky and Getoor, 1995]) are not lim­ ited to domains with explicit hierarchical structure, but re­ quire backtracking across subdomains, and often replan for subgoals that already have valid plans. In general, domain­ decomposition planning does not scale well because back­ tracking between subdomains can dominate the complexity of the search, and the domain decomposition is often ad hoc.

In this paper we present an approach to planning that scales to very large domains by taking advantage of domain struc­ ture. This approach is composed of two procedures: factoring and planning. The factoring procedure partitions a planning domain into loosely interacting subdomains that are orga­ nized in a tree structure. Our factoring procedure uses decom­ position algorithms from graph theory, and our contribution in this matter is in translating the planning-problem decompo­ sition task into a graph decomposition task. After factoring, our planning procedure finds plans for multiple subgoals in each of the subdomains separately, using a generic black box planner. It searches over possible plans using complex action descriptors from each of the subdomains to form a plan for the overall goal. The planning procedure uses dynamic pro­ gramming principles, and backtracking occurs only within a subdomain as part of the black box planner.

We prove that our planning procedure runs in time linear in the number of subdomains and takes time that is at most ex­ ponential in the size of the largest subdomain and the number of dependencies between subdomains. The type of factoring that we select is justified by this complexity result. We also prove that the combined algorithm is sound and complete, and that it can be applied to solve any planning problem us­ ing any generic black box planner for planning within subdo­ mains. The complexity is upper bounded by the complexity of the black box planner on the unpartitioned domain.

We implemented and tested our planning algorithm on a simple domain to guide further development. We created two implementations, one with the IPP planning system [Koehler and Hoffmann, 2000] and one with the FF planner [Hoffmann and Nebel, 2001]. We compared the results of our algorithm with those ofiPP and FF, and have shown that for a single do­ main our results scale much better than these planners alone. The example validates our analytical results and shows that our planner's performance scales linearly with the size of the domain for this problem, motivating further development.

2 Factored Planning

In this section we present an algorithm for planning with a partitioned planning domain, where the subdomains are ar­ ranged in a rooted tree. Each subdomain corresponds to a subset of the fluents, or single states, in the domain and a subset of the actions which use only those fluents. Neighbor­ ing subdomains may share fluents and actions, and the ideal partition has the smallest number of shared fluents. We ana­ lyze this algorithm computationally and present a procedure for finding a tree partition with close-to-optimal properties.

2.1 Partitioned Planning Problems

We restrict ourselves to partitioned planning problems that are described using a simple propositional action language. A partitioned domain description is a labeled graph that de­ scribes a set of subdomains and the connections between the subdomains. Formally, a partitioned domain description is a labeled graph G(l!J), E, l) with

• liJ) = {D;};<m vertices: for all i, D; = (P;, A;) is a planning domain description with
• P; a set ofpropositional.fluents (features of our do­ main that may change value over time),
• A ; a set of action (operator) definitions over P; .
• Edges E over l!J), and
• A labeling l of the edges in E. For every Du, Dv E l!J), l(Du , Dv) is a subset offluents from U i$m P;.

The Iabell ( Du, Dv) includes at least the fluents shared be­ tween Du , Dv (i.e., Pu n Pv), but it may include other (e.g. global) fluents. We use the convention that action A; refers to the action definition (also called action schema) and that a; denotes the instantiation of the action in a plan. We say that action a; is in subdomain Du iff it is defined in Au.

We specify the preconditions and effects of actions in A; using the simple language of situation calculus (with proposi­ tional fluents), and allow actions to have conditional effects. We use the simple compilation technique of [Reiter, 2001] to provide monotonic semantics for this language (and avoid the frame problem). All of our results apply to the PDDL language [Fox and Long, 2002] as well. PDDL is the repre­ sentation language used in our example (Section 3) to model the domains, the subdomains, and the plans.

2.2 Planning Algorithm

Here we present our planning algorithm, PartPlan (Figure 2), which finds plans in a partitioned domain. We use the follow­ ing notation. For P a set of propositional fluents, .C( P) is the language of P, i.e., the set of propositional sentences that can be built with P.

High-Level Overview

PartPlan processes a partitioned domain tree iteratively from the leaves to the root (the subdomain that holds the goal of PartPlan ). It selects a leaf subdomain, tries to build plans for each of a set of possible preconditions and goals (Step 2b ), records the successful attempts, adds them as new (macro­ like) actions to this leaf's single parent subdomain (Step 2c), and removes that leaf subdomain from the graph.

The result of planning in each subdomain is not a complete plan, but rather a compilation of capabilities, which contain both subdomain actions and capabilities of descendant sub­ domains. Generally, every subdomain's capabilities are those plans that it can find (using its own actions and capabilities of its neighbors) that affect the fluents that it shares with its par­ ent subdomain in the tree. Capabilities of a subdomain are shared by sending a message to the parent domain containing a complex action describing the capability.

When the tree is reduced to the single subdomain (after the iterative processing and removal of leaves) that contains the problem goal, we perform planning in that node to achieve the goal condition, based on the capabilities from the ( elim­ inated) child subdomains (Step 3). Then, the plan found by this subdomain is expanded into a plan that achieves the over­ all problem goal, using the actions of this subdomain along with the reported capabilities of the children in the tree. Ev­ ery capability that appears in this plan is expanded into a sub­ plan by the subdomain that reported it. Those subplans can themselves contain capabilities that are then expanded, and the process continues until the plan contains only the original domain actions.

The Simple Algorithm is Incomplete

The view presented above leaves the exact nature of plan­ ning in each subdomain unspecified. It suggests, roughly, that planning in each subdomain takes the form of finding a plan that starts from some initial state of local fluents and reaches a specified end state of local fluents. Unfortunately, limiting ourselves to this kind of message from children subdomains to parents is incomplete, as demonstrated in the following ex­ ample (see Figure 1 for an illustration).

Consider a scenario in which we have a charger that can charge batteries and a robot that can connect power cables to­ gether and that uses two batteries. Initially, every charge ac­ tion of the charger charges exactly one battery, so two charge actions are required to charge both of the robot's batteries. However, if the charger is connected to an additional power source, then a single charge action charges two batteries at once. Our task is to upgrade the charger so that it can charge two batteries at once. For this, the robot needs to build a power line that is long enough to reach the charger, and the charger needs to switch to using both sources. Thus, build­ ing this line requires multiple charges interleaved with adding lines. A plan that solves this problem needs to charge the robot's batteries, add a line segment, charge again, add an­ other line segment, charge again, add the final line segment, and switch the charger to the new mode.

We want our factored-planning approach to apply to any given planning problem and be complete (i.e., find a plan if there is one) regardless of the plan partition. We will show that there is a partitioning of this problem so that simple mes­ sages of the form "if X holds, then I can make Y hold" are not sufficient in a directed tree to find a complete plan. Mes­ sages of the form "if X 0 holds, then I can cause Y0 ; if you subsequently make X1 hold, then I can cause Y1 to hold" are required for domains with interleaved interactions as in this example. These complex messages can be extended for larger nUlllbers of interleaved preconditions and effects, and the al­ gorithm we present allows that type of message.

One possible partitioning of the example above is pre­ sented in Figure 1. On the left-hand side we include the actions charge and switch, and the features batteryLfull, battery2_full, second_power _line, and upgraded. The ac­ tion charge has the following effects and preconditions:

• charge causes batteryLfull.
• If batteryLfull or upgraded, then charge causes battery2_full.

Action switch has the following effects and preconditions:

• If second_power Jine, then switch causes upgraded.

On the right-hand subdomain we include the ac­ tion addJ ine_segment, and the features batteryLfull , battery2_full, second_power J ine, one_segment , and two_segments. The action addJine_segment has the fol­ lowing effects and preconditions:

• If batteryLfull 1\ battery2_full, then addJ ine_segment causes one_segment 1\ ·batteryLfull 1\ ·battery2_full.
• If one_segment, then addJine_segment causes two_segments.
• If two_segments, then addJine..segment causes second_power J ine.

Now, consider all the possible simple messages, i.e., mes­ sages of the form "if X, then I can cause Y to hold". We require each of those X and Y to be a combination of flu­ ent values for fluents that are shared between the two subdo­ mains. In our case, those shared fluents are batteryLfull, battery2_full, and second_power _line.

Assume that we chose the root node in our partition to be the left-hand side subdomain. The only non-trivial message that the right-hand side can send is

• If batteryLfull 1\ battery2_full , then I can cause ·batteryLfull 1\ ·battery2_full.

We would like to find a plan in the root subdomain (the left-hand side subdomain) that uses these messages and that results in the charger being upgraded. Note that this is not possible with only simple messages.

One way to resolve this problem is to allow more complex messages. Particularly, in our example, we can allow the fol­ lowing message to be sent:

If batteryLfull 1\ battery2_full ,

then I can cause ·batteryLfull 1\ ·battery2_full and if subsequently batteryLfull 1\ battery2_full,

then I can cause

(1)

• ·batteryLfull 1\ ·battery2_full and

if subsequently batteryLfull 1\ battery2_full, then I can cause second_power Jine .

If our planner on the left-hand subdomain can handle such complex actions, then it can use such a message to find a plan that succeeds in upgrading the charger. Indeed allow­ ing this kind of messages makes our planning algorithm com­ plete. This is consistent with results achieved by [Amir and Mcllraith, 2000; Mcllraith and Amir, 2001] for inference in first-order logic, and is also consistent with [Amir, 2002] that presented results for projection in factored domains.

An alternative to using such long messages is to include in­ ternal (i.e., not shared) fluents in shorter messages. However, this has the effect of breaking the encapsulation and structure that we strive to employ, reducing our problem to that of tradi­ tional planning on the entire domain and forcing backtracking across different subdomains.

Detailing the Planning Algorithm

Procedure PartPlan is presented in Figure 2 and its subrou­ tines are presented in Figures 3 and 4. PartPlan is given a partitioned planning domain G([)), E, l), [)) = {D;};<m, a set of initial conditions I= {I;};<m, indexed by subdomain such that I; is the initial state for the fluents in P;, a goal state condition Q in £(Pt) for root node De, and search pa­ rameters k (interactions) and d (depth). It returns a plan for achieving the specified goal conditions in the given domain, if such a plan exists under the search constraints. Notice that we show goals that can be represented in a single subdomain. We illustrate how to get around this restriction in Section 2.5.

We discuss two of the subroutines of PartPlan in detail. The first, SinglePlan, is presented in Figure 3. It determines whether there is a plan with at most d actions in subdomain Dv that starts with the state described by the initial state Iv and arrives at a state that satisfies eff k· We require the plan to have k - 1 preconditions interleaved within k effects, corre­ sponding to the number of interleaved conditions in the mes­ sage (e.g., in (1), the message sent in our example above, k = 4). To find such an interleaving message the planner uses fluent-setting actions, which set the fluents in l(Du, Dv) to a truth assignment in one of {pre;};<k· They correspond to (yet undetermined) action sequences that can be performed in ancestor (or cousin) subdomains. If the parent subdomain wishes to use the result of this planning, it will need to find a sequence of actions that replaces these fluent-setting actions.

Every fluent-setting action, bi, can be used at most once, and all of b1 , . .. , bi-l must have been used before this ac­ tion. Also, prior to using this fluent-setting action, effi-l must hold. This condition corresponds to the state that is required by the other subdomain's complex action as a pre­ condition for the subsequent complex action.

Subroutine SendMessage (Figure 4) takes a plan found by subdomain Dv (stored in table T by subroutine StorePian) and adds a new complex action definition in the parent sub­ domain, Dv., whose initial state and goal are fluents found in Dv. This new action contains complex action definitions from child subdomains and actions local to Dv.. Plans execute sequentially to ensure that the preconditions for complex ac­ tions are satisfied at the appropriate times.

2.3 Properties of PartPlan

In this section we prove the completeness and soundness of PartP!an and analyze its computational behavior. We pursue the intuition that our planning algorithm can find a plan more efficiently if the number of interactions between subdomains is small. The maximum shared fluents across the partition determines the time complexity of the algorithm.

Definition 2.1 (Width of a Plan) Let G( {Ddi<m, E, l) be a partitioned planning domain tree, and 1r = (a1 , . .. , a1) a sequence of actions. The width of 1r for G is the largest k

(minus one) for which there is a subsequence of actions and an edge (Dv., Dv) in G such that ai , ai+1 are in subdomains on different sides of(Dv. , Dv) in G.for every i < k.

The plan-width k for our partitioned domain is the least k that will allow PartPlan to find a plan. In our example in Figure I k = 4 because for k < 4 there is no message that we can send that will allow us to find a plan in the left-hand subdomain. Also, notice that every plan 1r forD has width at most l1rl-l.

A tree decomposition of planning domain D is a parti­ tioned domain description tree G(ID>, E, l) satisfying the run­ ning intersection property: if a fluent f appears in Pi and also in Pj, then all the edge-labels on the path between Di , Dj in G must include f.

Theorem 2.2 Let G(ID>, E, l), be a tree decomposition of planning domain D with m subdomains. PartPlan(G, I, Q, k, d) returns a plan 1r of that achieves Q in D starting from I, if and only if one exists with width at most 2k and at most d · m actions.

The role of dis to bound the length of the complex actions to at most d interactions; bounding this variable can be used in an iterative deepening algorithm to find plans with the short­ est possible complex actions. The parameter k can be used similarly, and its role is to restrict the length of messages that are sent from children subdomains to parent subdomains.

Corollary 2.3 Iterative deepening of search parameters k, d in PartPlan is a sound and complete planning algorithm.

The time bound for procedure PartPlan is exponential in the number of fluents in the links between subdomains and the plan-width of the partitioned-planning problem, but is lin­ ear in the number of subdomains.

Theorem 2.4 PartPlan(D, I, Q, k, d) terminates in time O(m· 2 2 k+ 1 .min((a+k)d, k· 2w)),for a, w being the largest number of action symbols and largest number affluent sym­ bols in any subdomain, respectively, and l being the largest number of symbols in l(Du, Dv)for all subdomains Du, Dv.

2.4 Automatic Factoring

Theorem 2.2 assumes that a tree decomposition G(IDl, E, l) is given. For a planning domain D we can build the decomposi­ tions by hand, adding a knowledge-engineering and planning perspectives to the domain description. We can also find a de­ composition automatically using graph decomposition tech­ niques. In this section we describe such an algorithm.

The notion of tree decomposition in planning domains is a special case of tree decomposition in graphs [Robertson and Seymour, 1986]. The width of a tree-decomposition is the width of the largest subset in the tree minus one. The treewidth of a graph G(V, E) is the minimum width over all tree-decompositions of G minus one

Finding optimal tree decompositions is NP-hard. Nonethe­ less, there are several algorithms that find close-to-optimal tree decompositions (e.g., [Becker and Geiger, 1996; Amir, 200 I]), and there are also some heuristics (e.g., [K.jaerulff, 1993 ]) that have been applied successfully in inference algo­ rithms for Bayesian networks and theorem proving.

The reduction of the planning decomposition problem into a graph decomposition problem is as follows. We create a graph G(V, E) with a vertex v E V for every propositional fluent in our domain D. E is the set of edges in this graph, and it includes an edge between v, u E V if and only ifthere is an action definition that includes both v, u (either as a precondi­ tion or as an effect). In the next step we find a tree decompo­ sition (S, T), S = {X; I i :::; m}, T =(I, F) for this graph using one of the algorithms mentioned above. Finally, we cre­ ate a partitioned domain description CD( {Di};~m, ED, l) as follows: The vertices (domain descriptions) D; = (P;, A) are chosen such that P; includes all the fluents in X;, and A; includes all the action definitions that can be expressed with the fluents in P;. The edges in ED are the tree edges, F, in T. The labeling l of a edge (Du, Dv) E ED is the set of fluents that are shared between the vertices Du, Dv, i.e., l(u, v) =Pun Pv.

This algorithm complexity is taken up by the decomposi­ tion of the graph G(V, E). Most heuristics are at most O(n 2 ), and one approximation algorithm [Amir, 2001] takes time O(n3log 4 n. k 5 iog k) (k is the treewidth of G, and is typ­ ically much smaller than n). This is an upper bound on the time taken by the planning domain decomposition algorithm.

2.5 Distribution of the Goal

So far we have assumed that the goal is represented in the set of fluents of a single subdomain. In many planning problems the goal consists of a conjunction of conditions on many dif­ ferent fluents. If we create a single subdomain that includes all those fluents, then the width of the tree decomposition will be high, and so will be the planning time. Instead, we can dis­ tribute the goal between subdomains, as we show here.

Assume that we are given a tree decomposition G(IDl, E, l) of domain D, with IDl = {Di};~m· Let a goal condition be 1\i<m Q;, where Q; is a part of the goal represented with the fluents in P;. Arbitrarily, choose a single subdomain, Dt, as the root of the tree. To each subdomain D; we add a new fluent symbol, q;, and a new action, af. For every leaf sub­ domain, a?'s precondition is Q; and its effect is q;. For every internal node in the tree, with children DJt, ... , Dj. , a{'s pre­ condition is qj 1 1\ ... 1\ qj., and its effect is q;.

When planning with this revised decomposition we use a single goal, qt, in subdomain Dt. The revised planning prob­ lem in this tree decomposition is equivalent to the original one, and we have reduced a (worst case) exponentially large problem down to a linear one.

3 An Extended Example

Consider the following domain, where a robot can move around in a set of rooms connected by doors as a ring [ Cimatti and Roveri, 2000]. Each room has a window which can be open, closed, or locked. The robot has four possible actions: move clockwise, move counterclockwise, close the window of the current room, and lock the window of the current room if the window is already closed. The goal state is that the win­ dows of all the rooms are locked. The start state is the robot in one of the r rooms and some configuration of windows open, closed, and locked. In this simple example we assume that the state of windows and the location of the robot are known. In other words, the initial condition is one of r · 3r possible initial configurations.

Define the following set of fluents:

• Agent location: in1 , . . . , inr
• Windows closed: closed1, ... , closedr
• Windows locked: locked1, ... , lockedr
• Windows locked from room 1 up to room i: all1, ... , allr.

The all; fluents represent conjunctions of the locked1, ... ,locked; fluents from parent and ancestor subdomains in the tree, as in the previous section. Define the following set of actions and corresponding effect axioms:

• Actions: close, lock, movec1, moveccl
• Effect axioms:

in;(s) 1\ ·closed;(s) ==> closed;(res(close, s)) in;(s) 1\ closed;(s) ==> locked;(res(locked, s)) in;(s) ==> ini+1(res(movec1, s)) 1\ ·in;(res(movec~, s)) in;(s) ==> in;_1(res(moveccl, s)) 1\ ·in;(res(moveccl, s)) locked1 (s) ==> all1 (s) all;_1(s) 1\ locked;(s) ==> all;(s) (1 < i:::; m)

In the last set of axioms we use the convention that addition and subtraction are modulo the number of rooms in the ring. In other words, the next room after i is ( i ± 1 + m) mod m.

For the ring of rooms, an obvious partition turns out to be a good one. Specifically, we associate each subdomain with one room, letting the fluents and actions for subdomain Di be

Each subdomain contains all actions whose preconditions and effects mention only ftuents in that subdomain.

The graph of subdomains is not a tree (see Figure 5). One way to tum it into a tree decomposition is by removing one of the edges completing a cycle and adding (in the worst case) the label of that edge to the rest of the edges in this graph (this is an example of a more general algorithm that is outside the scope of this paper; see [Amir and Mcllraith, 2000]). There­ sult is presented in Figure 6. The graph G connects every two consecutive subdomains but D1, Dm, for m being the num­ ber of rooms (and subdomains). The labeling on the edges is originally l(i,i + 1) = {ini,ini+1,alli} fori s; m. After transforming to graph into a tree we get the labeling

We show how PartPlan finds a plan for this domain. We set the goal to be allm, which is expressed in the ftuents of subdomain m. We set t = m to be the root of the tree.

We take node v = 1, whose parent in the tree is u = 2, and find all the plans possible with k = 2, d = 2. One such plan is "if the robot is in room I and the window is open, then close, lock and move clockwise." We find a plan for D1:

Both pre1,eff2 are complete state descriptions in l'(1,2)). There is a plan 1r1 that SinglePlan(Dl, !1, (pre1), (eff1), eff2, d) will return. Thus, one message that is sent to subdomain Du is "if in some state the robot is in room I, then D1 has a sequence of actions that results in all1 being true and the robot moving to room 2." In more precise terms, the defi­ nition for this capability c2,1 is added to subdomain Du by subroutine SendMessage.

Now, we take node v = 2, whose parent in the tree is u = 3, and find all the plans possible with k = 2, d = 2. One such plan is, "if in some state the robot is in room 2, then move counter-clockwise, execute a subdomain-1-action, then close, lock and move clockwise." We find a plan for D 2:

These are all complete state descriptions in l'(2, 3). There is a plan 1r(c2) that SinglePlan(D2, h {pred, {effl}, eff2, d) will return. The message that is sent to subdomain Du is roughly speaking "if the robot is in room 2, then D2 has a sequence of actions that results in all2 being true". In more precise terms, the definition for action c2,1 is added to subdo­ main Du by subroutine SendMessage.

This method continues for all the subdomains up to Dm that contains the goal. Subdomain m can conclude that there exists a plan for closing and locking all the windows, satisfy­ ing allm. If the initial condition of our problem specifies that the robot is in room r, then starting in subdomain Dr we will already have a plan independent of the position of the robot. This will lead to a complete plan in subdomain m.

When the plan is found in subdomain m, the algorithm then goes on to expanding the complex actions into their capabil­ ity plans. For example, when the complex action c2,1 of sub­ domain 1 is encountered in the plan 1r , it is expanded into a segment (close, lock, movec~) that is placed instead of c2,1 in plan 1r. It results in a sequence of actions that is between the state satisfying condition eff1 (i.e., when the robot appears in room I) and the state satisfying eff2.

Using this domain and associated tree decomposition above we implemented our algorithm to see that the run time scaled linearly as the number of rooms increased. The re­ sults are compared in figure (7), which shows four different planning algorithm on this domain as the size of the domain grows. For all runs, the optimal-sized plans were found. In very small domains, there is some constant time overhead in­ volved in the PartPlan algorithm, but asymptotically the Part­ Plan algorithms begin to dominate because of the linear scal­ ing with respect to the number of rooms. Although this exam­ ple is not rigorous enough to show the empirical dominance of the PartPlan algorithm for every domain, it does motivate further development of the ideas in real-world domains.

4 Related Work

Some of the techniques that we apply have been used be­ fore in automated reasoning. Best known are methods for reasoning with probabilistic graphical models [Pearl, 1988]), logical theories [Dechter and Rish, 1994; Amir and Mcll­ raith, 2000] and constraint satisfaction problems [Dechter and Pearl, 1989]. The common principle for those applications is the advantage taken of low treewidth available in many do­ mains. With a tree decomposition of close-to-optimal width, these reasoning algorithms use two sweeps of the tree, an evi­ dence collection and evidence distribution sweep, and the en­ tire process is linear in the number of nodes.

Similar techniques to these have also been used in prob­ abilistic planning to find approximate policies for factored MOPs (e.g., [ Guestrin eta/., 2002]), and also in the context of multi-agent stochastic planning with MOPs. The main differ­ ence with this approach is that we find an exact solution, and we act in domains that do not have universal reachability (all states are reachable from all states), as is assumed in MOPs.

Section I discusses approaches for multi-agent planning [Lansky and Getoor, 1995; Ephrati and Rosenschein, 1994; Wolverton and desJardins, 1998].

5 Conclusions

Two contributions of our work are automated planning do­ main decomposition by minimizing subdomain interactions, and an algorithm to plan in this decomposed domain with no backtracking. The planning algorithm is sound and com­ plete, and exploits a low treewidth partition for a particular planning domain, enabling planning to scale linearly with the domain size. Our automatic factoring algorithm for a plan­ ning domain attempts to optimize the run-time complexity of the planner. Theoretical results and empirical examples show that the planning algorithm scales well in domains with de­ composable structure.

Directions for future work in this area include the devel­ opment of algorithms for richer domains and description lan­ guages, such as nondeterministic planning actions, stochas­ tic actions, and actions involving duration and numerical pa­ rameters. Our approach is built on the language of situation calculus (in which we developed our first version of the al­ gorithms), leading us to believe that it will extend to these directions and more. Our work connects automated reason­ ing and planning, and we expect to extend this connection to allow first-order decomposition of planning and other related problems, such as diagnosis and reactive control.

Acknowledgments

The first author is supported under an ONR MURI Funds N00014-01-1-0890, and N00014-00-1-0637, and NSF grant ECS-9873474. The second author is supported under an NSF Graduate Research Fellowship.