A Fast Goal Recognition Technique Based on Interaction Estimates

1 Introduction

Goal recognition aims to infer an actor's goals from some or all of the actor's observed actions. It is useful in many areas such as intelligent personal assistants [Weber and Pollack, 2008], smart environments [Wu et al., 2007], monitoring user's needs [Pollack et al., 2003; Kautz et al., 2002], and for intelligent tutoring systems [Brown et al., 1977]. Several different techniques have been used to solve plan recognition problems: hand-coded action taxonomies [Kautz and Allen, 1986], probabilistic belief networks [Huber et al., 1994], consistency graphs [Lesh and Etzioni, 1995], Bayesian inference [Albrecht et al., 1997; Bui, 2003], machine learning [Bauer, 1998], parsing algorithms [Geib and Goldman, 2009], and more recently AI planning. In particular, Jigui and Minghao [2007] developed Incremental Planning Recognition (IPR) that is based on reachability in a plan graph.

Ram´ırez and Geffner [2009] developed an approach that identifies goals where the observed actions are compatible with an optimal plan for one or more of those goals. To identify those plans, they used optimal and satisficing planners, as well as a heuristic estimator [Keyder and Geffner, 2007], which approximates the solution by computing a relaxed plan. The limitation of this work is the assumption that agents act optimally - suboptimal plans compatible with the given observations are not considered. To remove this limitation, they developed an approach for estimating the probability of each possible goal, given the observations [2010; 2012]. The likelihood of a goal given a sequence of observations is computed using the cost difference between achieving the goal complying with the observations, and not complying with them. This cost is computed by means of two calls to a planner for each possible goal.

A significant drawback to the Ram´ırez approach is the computational cost of calling a planner twice for each possible goal. This makes the approach impractical for real-time goal recognition, such as for a robot observing a human and trying to assist or avoid conflicts. In this paper we present an approach that can quickly provide a probability distribution over the possible goals. This approach makes use of the theoretical framework of Ram´ırez, but instead of invoking a planner for each goal, it computes cost estimates using a plan graph. These cost estimates are more accurate than usual because we use interaction [Bryce and Smith, 2006]. Moreover, we can prune the cost-plan graph considering the observed actions sequence. Consequently, we can quickly compute cost estimates for goals with and without the observations, and thus infer a probability distribution over those goals. We show that this approach is much faster, but still yields high quality results.

In the next two sections we review the basic notions of planning and goal recognition from the perspective of planning. In Section 4 we develop our fast technique for approximate goal recognition, which includes the propagation of cost and interaction information through a plan graph, and a plan graph pruning technique from IPR. In Section 5 we present an empirical study, and in Section 6 we discuss future work.

2 Planning Background

Automated planning is the problem of choosing and organizing a sequence of actions that when applied in a given initial state results in a goal state. Formally, a STRIPS planning problem is defined as a tuple Π =< P, O, I, G > where P is a finite set of propositional state variables; O is a set of operators, each having the form < prec(O), add(O), del(O) > where prec(O) ⊆ P is the set of propositions that must be satisfied before the operator can be executed; add(O) ⊆ P is the set of positive propositions that become true when the operator is applied; del(O) ⊆ P is the set of propositions that become false when the operator is applied; I ⊆ P is the initial state; G ⊆ P is the goal state. A solution or plan for a planning problem is a sequence of actions π = (o1, ..., on), which represents the path to reach G starting from I.

Each action a ∈ O has an associate cost Costa > 0. Thus, a plan solution cost is the sum of the cost of the operators in the plan, i.e., Cost(π) = ∑a∈π Costa. The optimal plan cost, Cost∗ (π), is the minimum cost among all the possible plans.

3 Goal Recognition Background

Ram´ırez (2010; 2012), defines a goal recognition problem to be a tuple T = 〈P, G, O, Pr〉 where P is a planning domain and initial conditions, G is a set of possible goals or hypotheses, O is the observed action sequence O = o1, ..., on, and Pr is the prior probability distribution over the goals in G. The solution to a plan recognition problem is a probability distribution over the set of goals G ∈ G giving the relative likelihood of each goal. These posterior goal probabilities P (G|O) can be characterized using Bayes Rule as:

where α is a normalizing constant, Pr(G) is the prior distribution over G ∈ G, and Pr(O|G) is the likelihood of observing O when the goal is G. Ram´ırez goes on to characterize the likelihood P r(O|G) in terms of cost differences for achieving G under two conditions: complying with the observations O, and not complying with the observations O. More precisely, Ram´ırez characterizes the likelihood, Pr(O|G), in terms of a Boltzman distribution:

where β is a positive constant and ∆(G, O) is the cost difference between achieving the goal with and without the observations:

Putting equations (1) and (2) together yields:

By computing ∆(G, O) for each possible goal, equation 4 can be used to compute a probability distribution over those goals. The two costs necessary to compute ∆ can be found by optimally solving the two planning problems G|O and G|O. Ram´ırez shows how the constraints O and O can be compiled into the goals, conditions and effects of the planning problem so that a standard planner can be used to find plans for G|O and G|O.

To illustrate the Ram´ırez approach, consider the example shown in Figure 1, where an agent can move up, left, and right at cost 1. It has two possible goals, G1 and G2, and O = (o1) as the observed sequence. For goal G1, Cost(G1|O) = 3, and Cost(G1|O) = Cost(G1) = 3. (The costs are the same since o1 is on an optimal path to G1 and there is another optimal path that reaches G1 but does not include o1.) Hence, ∆(G1,O) = 0, and Pr(G1|O) = 0.5. In contrast, Cost(G2|O) = 2 and Cost(G2|O) = 4, since avoiding o1 requires a suboptimal plan for G2. This results in ∆(G2,O) = -2, and Pr(G2|O) = 0.88. This means that G2 is more likely to occur than G1.

This result is somewhat counterintuitive. The fact that the sequence of observed actions consists exclusively of optimal action landmarks for G2 causes Cost(G2|O) to differ from Cost(G2) yielding a higher probability for G2. However, In most cases, Cost(G|O) = Cost(G) because there are multiple possible paths to a goal. In order for the two costs to be different, the observation sequence would need to consist exclusively of optimal landmarks (like the case for G2 above). For example, if we were to shift G1 and G2 left one column there would now be multiple optimal paths to G2 so Cost(G2|O) would equal Cost(G2). This would result in both ∆(G1,O) = 0 and ∆(G2,O) = 0 yielding the same probability for both goals.

4 Fast Goal Recognition

The major drawback to the Ram´ırez approach is the computational expense of finding two plans for every possible goal. Moreover, the constraints O and O make the planning problems more difficult to solve. As a result, even for relatively simple Logistics and Blocks World problems it can take 1530 minutes to find all the plans necessary for this computation. This makes it impractical to use this approach for any sort of real-time goal recognition. To address this problem, we developed a heuristic approach that combines two principal ideas: 1) cost and interaction estimates using a plan graph, and 2) the pruning technique of IPR. As with Ram´ırez, we assume that we are given T = 〈P, G, O, Pr〉, which includes the problem P (planning domain and initial conditions), the set of possible goals G, a set of observations O, and a prior distribution over the possible goals G. It is also assumed that the sequence of observed actions may be incomplete, but is accurate (not noisy).

4.1 Plan Graph Cost Estimation

Simple propagation of cost estimates in a plan graph is a technique that has been used in a number of planning systems to do heuristic cost estimation (e.g: [Do and Kambhampati, 2002]). Unfortunately, the cost information computed this way is often inaccurate because it does not consider the interaction between different actions and subgoals.

Cost Interaction is a quantity that represents how more or less costly it is that two propositions or actions are established together instead of independently. Formally, the optimal Interaction, I ∗ , is an n-ary interaction relationships among propositions and among actions (p0 to pn) in the plan graph, and it is defined as:

where the term cost∗ (p0∧...∧pn) is the minimum cost among all the possible plans that achieve all the members in the set. Computing I ∗ would be computationally prohibitive. As a result, we limit the calculation of these values to pairs of propositions and pairs of actions in each level of a plan graph - in other words, binary interaction:

A value I < 0 means that two propositions or actions are synergistic - that is, the cost of establishing both is less than the sum of the costs of establishing the two independently. When I = 0 the two propositions or actions are independent. When I > 0 the two propositions or actions interfere with each other, so it is harder to achieve them both than to achieve them independently. The extreme value I = ∞, indicates that the two propositions or actions are mutually exclusive. One can therefore think of interaction as a more nuanced generalization of the notion of mutual exclusion.

The computation of cost and interaction information begins at level zero of a plan graph and proceeds sequentially to higher levels. For level zero we assume 1) the cost for propositions at this level is 0 because the initial state is given, and 2) the interaction between each pair of propositions is 0, that is, the propositions are independent. With these assumptions, we start the propagation by computing the cost of the actions at the first level of the plan graph. In general, for an action a at level l with a set of preconditions Pa, the cost is approximated as:

The next step is to compute the interaction between two actions. The interaction between two actions a and b at level l is:

where cost∗ (a ∧ b) is defined to be cost(Pa ∪ Pb), which is approximated as in (7) by:

If the actions are mutex by inconsistent effects, or interference, then the interaction is ∞. Otherwise, the interaction above simplifies to:

For a proposition x at level l, achieved by the actions Ax at the preceding level, the cost is calculated in the same way as for traditional plan graph cost estimation:

where Ax is the set of actions that support x.

Finally, in order to compute the interaction between two propositions at a level l, we need to consider all possible ways of achieving those propositions at the previous level. That is, all the actions that achieve the pair of propositions and the interaction between them. Suppose that Ax and Ay are the sets of actions that achieve the propositions x and y at level l. The interaction between x and y is then:

Using equations (7), (8), and (9), a cost-plan graph is built until quiescence. On completion, each possible goal proposition has an estimated cost of achievement, and there is an interaction estimation between each pair of goal propositions. Using this information, one can estimate the cost of achieving a conjunctive goal G = g1, ..., gn as:

Using this information, we can estimate the cost of a plan for each possible goal G. While this allows us to estimate Cost(G), what we need for goal recognition is to compute ∆(G,O), which requires Cost(G|O) and Cost(G|O). As discussed earlier, unless O is a subsequence of every optimal plan for G, Cost(G|O) = Cost(G). Even when this is not the case, these two costs tend to be similar except in a few rare cases. (This is confirmed in our experiments; for most problems there are multiple distinct optimal plans for each goal.) As a result, we approximate Cost(G|O) by Cost(G), which can be estimated as shown above. To estimate Cost(G|O) we modify the plan graph as described in the next section, and repropagate cost and interaction information.

4.2 Incremental Plan Recognition

Jigui and Minghao [2007] developed a framework for plan recognition that narrows the set of possible goals by incrementally pruning a plan graph as actions are observed. The approach consists of building a plan graph to determine which actions and which propositions are true (1), false (-1), or unknown (0) given the observations. For level zero, since it is assumed that the initial state is true, every proposition has value 1. In addition, when an action is observed at a level it gets value 1. The process incrementally builds a plan graph and updates it level by level. The values of propositions and actions are updated according to the following rules:

1. An action in the plan graph gets value -1 when any of its preconditions or any of its effects is -1.
2. An action in the plan graph gets value 1 when it is the sole producer of an effect that has value 1, noop included.
3. A proposition in the plan graph gets value -1 when all of its consumers or all of its producers are -1, noop included.
4. A proposition in the plan graph gets value 1 when any of its consumers or any of its producers is 1, noop included.

The process results in a plan graph where each proposition and each action is labeled as 1, -1, or 0. Those propositions and actions identified as -1 can be ignored for plan recognition purposes, meaning that these are pruned from the resulting plan graph. To illustrate this propagation and pruning technique, consider a simple problem with three operators:

Suppose that the sequence of observed actions is A at level 0, and C at level 2. Figure 2 shows the plan graph for this problem. The numbers above the propositions and actions are the values for each proposition and action computed using the above propagation rules. As a result of the propagation, z must be true (has value 1) at level 1 because action A was observed. As a result, since A and B are mutually exclusive, action B and its effects t and ¬y are false (have value -1) at level 0. As a consequence of t being false, C is also false at level 1 along with its effects k and ¬t. At level 2, k and ¬t must be true because action C was observed. (This results in t being true at level 1.) Since A and C, and B and C are mutually exclusive, A, B, ¬y, and t are not possible (have value -1) at level 2. Action B is unknown (has value 0) at level 1 since there is not enough information to determine whether it is true or false. The proposition y is true at level 0 since it is assumed that the initial state is true, and is unknown at level 1 because there is not enough information to determine whether it is true or false. However, it is false at level 2 due to the mutual exclusion between C and noop-y. Proposition z is true at every level since there are no operators in the domain that delete it.

4.3 Relaxing the Time Step Assumption

We have modified the IPR pruning technique in order to relax the assumption of knowing the time step of each action in the observed sequence. Like Ram´ırez and Geffner [2010], we assume that the sequence of actions is sequential. Initially, we assign an earliest time step (ets) i to each action o in the observed sequence. The ets is given by the order of each action in the observed sequence. That is, given (o0, o1, ..., oi), the ets for each action is: ets(o0)=0, ets(o1)=1, ets(o2)=2, etc. When the pruning process starts, we establish that an observed action o is possible to be observed at the assigned level i if all its preconditions are true (value 1) and/or unknown (value 0), and they are not mutually exclusive at level i - 1. Otherwise, the action cannot be executed at that level, which results in an update of the ets of each remaining action in the observed sequence. For instance, considering the initial sequence where ets(o0)=0, ets(o1)=1, ets(o2)=2, and o0 can be executed at level 0. If o1 cannot be executed at level 1, then ets(o1)=2 and ets(o2)=3. If necessary, the cost-plan graph will be expanded until an ets is assigned to each observed action in the sequence. To illustrate this method, consider the example from Figure 2. Let us suppose the sequence of observed actions is A and C, with initial ets 0 and 1 respectively. As a result of the propagation, z must be true (have value 1) at level 1 because action A was observed. As a result, since A and B are mutually exclusive, action B and its effects t and ¬y are false (have value -1) at level 0. Action C is initially assumed to be at level 1, but this cannot be the case because its precondition t is false at level 0. Therefore, the ets for C is updated to 2. The result of this updating is that each observed action is assumed to occur at the earliest possible time consistent with both the observation sequence and the constraints found in constructing the plan graph, using the interaction information.

4.4 Computing Goal Probabilities

With the plan graph cost estimation technique described in Section 4.1, and the observation pruning technique described in Section 4.2 and Section 4.3, we can now put these pieces together to allow fast estimation of cost differences ∆(G, O), giving us probability estimates for the possible goals G ∈ G. The steps are:

1. Build a plan graph for the problem P (domain plus initial conditions) and propagate cost and interaction information through this plan graph according to the technique described in Section 4.1.
2. For each (possibly conjunctive) goal G ∈ G estimate the Cost(G) from the plan graph using equation (10).
3. Prune the plan graph, based on the observed actions O, using the technique described in Section 4.2 and Section 4.3.
4. Compute new cost and interaction estimates for this pruned plan graph, considering only those propositions and actions labeled 0, or 1.
5. For each (possibly conjunctive) goal G ∈ G estimate the Cost(G|O) from the cost and interaction estimates in the pruned plan graph, again using equation (10). The pruned cost-plan graph may discard propositions or/and actions in the cost-plan graph necessary to reach the goal. This constraint provides a way to discriminate possible goals. However, it may imply that 1) the real goal is discarded, 2) the calculated costs are less accurate. Therefore, computation of Cost(G|O) has been developed under two strategies:
6. (a) Cost(G|O) is computed using the pruned cost-plan graph.
7. (b) Cost(G|O) is computed after the pruned cost-plan graph is expanded to quiescence again. This will reintroduce any pruned goals that are still possible given the observations.
8. For each goal G ∈ G, compute ∆(G,O), and using equation (4) compute the probability Pr(G|O) for the goal given the observations.

To illustrate this computation, consider again the actions A, B, and C from equation (11), and the plan graph shown in Figure 2. Suppose that A, B, and C have costs 2, 1, and 3 respectively, and that the possible goals are g1 = {z, k} and g2 = {z, t}. Propagating cost and interaction information through the plan graph, we get Cost(t) = 1, Cost(z) = 2, Cost(k) = 4, and interaction values I(k, t) = ∞ and I(k, z) = 0 at level 3. Now consider the hypothesis g1 = {z, k}; in order to compute Cost(k ∧ z), we use the cost and interaction information propagated through the plan graph. In order to compute Cost(k ∧ z|O), the cost and interaction information is propagated again only in those actions with status 1 and 0. In our example, these costs are:

Thus, the cost difference is:

As a result:

For the hypothesis g2 = {z, t}, the plan graph dismisses this hypothesis as a solution because once the plan graph is pruned, propositions t and z are labeled as -1. Therefore:

So:

If we expand the pruned cost-plan graph until quiescence again, the solution is still the same because A and B are permanently mutually exclusive.

Assuming uniform priors, Pr(G), after normalizing the probabilities, we get that Pr(g1|O) = 1 and Pr(g2|O) = 0, so the goal g1 is certain in this simple example, given the observations of actions A and C.

5 Experimental Results

We have conducted an experimental evaluation on planning domains used by Ram´ırez and Geffner: BlocksWord, Intrusion, Kitchen, and Logistics. Each domain has 15 problems. The hypotheses set and actual goal for each problem were chosen at random with the priors on the goal sets assumed to be uniform. For each problem in each of the domains, we ran the LAMA planner [Richter et al., 2008] to solve the problem for the actual goal. The set of observed actions for each recognition problem was taken to be a subset of this plan solution, ranging from 100% of the actions, down to 10% of the actions. The experiments were conducted on an Intel Xeon CPU E5-1650 processor running at 3.20GHz with 32 GB of RAM.

Ram´ırez evaluates his technique using an optimal planner HSP∗f [Haslum, 2008], and LAMA, a satisficing planner that is used in two modes: as a greedy planner that stops when it finds the first plan (LAMAG), and as a planner that returns the best plan found in a given time limit (LAMA). For purposes of this test, Ram´ırez technique is also evaluated using the heuristic estimator hsa , which was used by Ram´ırez and Geffner (2009). Like our technique, this requires no search since the cost is given by a heuristic estimator. We compare our goal recognition technique, GR, against Ram´ırez's technique for those three planners and hsa , on the aforementioned domains, using a range of time limits from 5 seconds up to 1800 seconds. We present two variations of our technique, with and without extension of the plan graph after pruning:

• GRI: the propagation of cost information through the plan graph considers interaction information.
• GRIE: same as above, but the pruned cost-plan graph is expanded until quiescence.
• GR¬I: the propagation of cost information through the plan graph does not consider interaction information.

Table 1 and 2 show the results. For each planner, each column shows average performance over the 15 problems in each domain. The first row in the table represents the optimal solution where HSP∗f (HSP∗f u) computes ∆(G,O) using equation (3). The second row in the table represents the optimal solution where HSP∗f (gHSP∗f u) computes ∆(G,O) using Cost(G) instead of Cost(G|O) (Equation (3)). Both approaches were allowed to run for an unlimited amount of time. The other rows represent different measures of quality and performance:

• T shows the average time in seconds taken for solving the problems.
• Q shows the fraction of times the actual goal was among the goals found to be the most likely.
• S shows the spread, that is, the average number of goals in G that were found to be the most likely.
• Q20 and Q50 show the fraction of times the actual goal is in the top 20% and top 50% of the ranked goals. Although Q might be less than 1 for some problem, Q20 or Q50 might be 1, indicating that the actual goal was close to the top.
• d is the mean distance between the probability scores produced for all the goal candidates, and the probability scores produced by gHSP∗f u. More precisely, if the set of possible goals is {G1, ..., Gn}, a method produces probabilities {e1, ..., en} for those goals, and gHSP∗f u produces {p1, ..., pn}, d is defined as:

In all the domains except Kitchen and Logistics, HSP∗f u finds the actual goal with highest probability (Q = 1). In Logistics, the value of Q degrades with lower percentages of observed actions. The spread increases as the percentage of observed actions decreases, because there is not enough information to distinguish among different possible goals. Results for HSP∗f u are the same except for the Kitchen domain where gHSP∗f u actually finds higher quality solutions. We note, however, that gHSP∗f u is significantly faster than HSP∗f u because it is generally easier to plan for G than for G|O.

LAMA and LAMAG planners solve all the problems for the BlocksWord domain within 1800 seconds, which is actually slower than HSP∗f . However, the quality Q is high, which means that the actual goal is among the most likely goals for most problems. In the Campus domain, LAMA solves all the problems within 1.5 seconds, and generates high quality solutions. LAMAG solves all the problems in less than a second, but the quality of the solution decreases as the percentage of observed actions drops. In the Grid domain, LAMA solves all the problems within the 13 seconds. The quality of the solution is low when the percentage of observed actions is high, and it improves as the percentage of observed actions drops. LAMAG solves all the problems in the Grid domain within 10 seconds, but the quality of the solution is lower than for LAMA. In the Intrusion domain, LAMA solves all the problems producing quality solutions within 90 seconds, when the percentage of observed actions is high. The computational time decreases to 18 seconds as the percentage of observed actions drops. LAMAG solves all the problems in the Intrusion domain within 3 seconds, but the quality of the solutions is very low when the percentage of observed actions is high. In the Kitchen domain, the quality of solutions given by LAMA and LAMAG varies depending on the percentage of observations. However, LAMAG is faster than LAMA. In the Logistics domains, LAMA solves all the problems, and produces quality solutions within 42 seconds as long as the percentage of observed actions is high. The computation time decreases to around 11 seconds as the percentage of observed actions drops. For LAMAG the problems are solved within 5 seconds. When the percentage of observed actions is high, the quality of the solution is good. (The quality degrades as the percentage of observed actions drops.)

The hsa heuristic solves all the problems within a second. In all the domain except Logistics, the quality Q of the solution is 1, which means that the actual goal is among the most likely goals for all the problems. However, the spread is very high, which means that the approach does not discriminate among the possible goals very well. In Logistics, the quality Q of the solution is very low, although in most cases, the actual goal appears in the top 20% of the ranked goals (Q20).

GRI solves all the problems, except those in the Grid domain, within 2 seconds, GRI E solves them within 10 seconds. In general, the three approaches quickly provide high quality solutions when the percentage of observed actions is high, although this degrades a bit as the percentage of observed actions drops. Considering the expansion of the pruned costplan graph, we expected GRIE to dominate GRI in terms of goal recognition accuracy. Surprisingly, this does not appear to be the case in the domains studied. In some cases, GRIE shows a small improvement, but in others the quality of the solutions drops. Our hypothesis is that the pruned goals are sufficiently unlikely that reintroducing them does not significantly impact the resulting probability distribution. Considering the use of interaction estimates, GRI gets more high quality solutions than GR¬I, except for some cases of BlocksWord and Logistics domains for 30% and 10% of observed actions. In the Grid domain, GRI solves all the problem within 100 seconds and GRI E within 130 seconds, which is slower than HSP∗f . However, for all the percentages of observed actions, except for 70%, both approaches provide almost the same quality solution as that provided by LAMA.

GR¬I solves all the problems in the Grid domain within the 35 seconds, but the quality is a bit lower than GRI .

We have conducted a second test where the set of observed actions for each recognition problem was considered to be the prefix of the plan solution, ranging from 100% of the actions, down to 10% of the actions. (Priors on the goal sets are also assumed to be uniform.) The reason for this test is to model incremental goal recognition as actions are observed. This produces essentially the same results as the previous test for all the different techniques. We have also tested the approaches in Table 1 on test problems where the observation sequences were generated using an optimal planner (rather than LAMA). This also makes no difference in the results.

6 Conclusions and FutureWork

In this paper we presented a fast technique for goal recognition. This technique computes cost estimates using a plan graph, and uses this information to infer probability estimates for the possible goals. This technique provides fast, high quality solutions when the percentage of observed actions is relatively high, and degrades as the percentage of observed actions decreases. In many domains, this approach yields results two orders of magnitude faster than the Ram´ırez approach using HSP∗f , LAMA, or greedy LAMA on the more difficult domains. The solutions are comparable or better in quality than those produced by greedy LAMA.

The ranking that we produce could be used to select the highest probability goals, and then feed this set to the Ram´ırez approach to provide further refinement to the probabilities. While this does reduce the amount of computation time require by the Ram´ırez approach, in our experiments the ranking occasionally improved, and the computation time was still large for the more difficult domains and problems. When the top goals are fed to the Ram´ırez approach with the LAMA planner, the overall ranking occasionally improves for higher time limits. For low time limits, it doesn't improve or decreases the solution quality.

It appears possible to extend our approach to deal with temporal planning problems involving durative actions and concurrency. It is not clear whether the compilation technique of Ram´ırez would extend to temporal problems, but even if this were possible, the overhead of solving two temporal planning problems for each possible goal is likely to be prohibitive.

Acknowledgments

This work was funded by the Junta de Comunidades de Castilla-La Mancha project PEII-2014-015A, Universities Space Research Association, and NASA Ames Research Center.