Integrated Learning for Goal-Driven Autonomy

1 Introduction

Agents that perform goal reasoning explicitly model and reason about the goals they try to achieve (Aha et al. 2010). For example, goal-driven autonomy (GDA) is a goal reasoning model in which agents continuously monitor the current plan's execution and assess whether the encountered states match expectations (Molineaux et al. 2010). When a GDA agent detects a state discrepancy (i.e., when the expected and actual states mismatch), it will consider whether to formulate new goals that, if achieved, would fulfill its overarching objectives such as maximizing a longterm reward.

There have been several recent contributions on goal reasoning, including research on goal management in cognitive architectures (Choi 2010), goal generation (Hanheide et al. 2010), and meta-reasoning (Cox, 2007). Applications have included simulated robots (Meneguzzi and Luck 2007), real-time strategy games (Weber et al. 2010), first-person shooters (Mu-oz-Avila et al. 2010), and Navy training simulators (Molineaux et al. 2010).

To perform well, comprehensive GDA agents require substantial domain knowledge (e.g., to determine expected states, identify and explain discrepancies, formulate new goals, and manage pending goals). This requires, for example, experts to anticipate what discrepancies can occur, identify what goals can be formulated, and define their relative priority. However, few techniques have been investigated for learning this knowledge, and those that do learn only goal formulation knowledge (Weber et al. 2010; Powell et al. 2011). This can be problematic; while these agents may perform well in simple environments, in others a domain expert might not know the (state) expectations for executing every action in every state, nor which goal should be pursued to resolve every possible discrepancy, or even the space of all possible discrepancies.

We introduce Learning GDA (LGDA), a GDA algorithm that learns two types of cases from observed discrepancy resolution episodes: (1) expectation cases, which map stateaction pairs to a distribution over expected states, and (2) goal formulation cases, which map goal-discrepancy pairs to a distribution of expected values over discrepancyresolution goals. LGDA learns these through an integration of case-based reasoning (CBR) and reinforcement learning (RL) methods. It models goal formulation as an RL problem in which a goal's value is estimated based on the expected future reward for achieving it.

We claim that this integration can learn to perform as well as a non-learning GDA agent that employs expert knowledge, and can outperform GDA agents that use only CBR or RL. We report LGDA's comparative evaluation on a task involving the control of a team in a domination video game (DOM). The results show that LGDA outperforms most built-in hand-coded opponents (i.e., adversaries) and significantly outperforms its ablated versions. Finally, LGDA learns to perform almost as well as a non-learning GDA variant, whose case knowledge was hand-crafted by a domain expert such that it also significantly outperforms these adversaries (Mu-oz-Avila et al. 2010).

2 Background

We briefly introduce the two processes that we will integrate to acquire knowledge for a GDA agent.

3.1 Case-Based Reasoning

CBR is a four-step learning process for solving new problems by adapting solutions to similar problems:

1. Retrieval: Given problem p, retrieve cases C from a library L (i.e., those relevant to solving p), where each case c∨C is a problem-solution pair (pc,sc).
2. Reuse: Adapt C's solutions to derive a proposed solution s.
3. Revision: Apply s to p in real world (or simulated) scenarios. If needed, revise accordingly. This yields s′.
4. Retention: If revision s′ successfully solves p, store the resulting experience as a new case (p,s′) in L.

LGDA (¤5) uses CBR to predict expected states and to formulate goals in response to detected discrepancies.

3.2 Reinforcement Learning

RL concerns the topic of how agents should select actions in an environment so as to maximize cumulative reward. RL agents learn through trial-and-error by interacting with the environment. Many RL algorithms exist, including Qlearning (Sutton and Barto 1998), which learns a Q-table that associates each (s,a) pair with an estimate of Q(s,a), where here s is a state and a is an action. It employs an ⌡- greedy action selection strategy: in s, with probability 12⌡ it selects the action a with highest Q(s,a) and with probability ⌡ it selects randomly. This prevents RL agents from getting stuck in a local optimum. Q-learning searches for a policy Μ that maximizes the sum of the returned rewards, where Μ maps states to actions. Each state s has a utility value U(s). We define the reward between s and its successor s′ as U(s′)2U(s). LGDA (¤5) uses RL to learn expected values of goals to formulate, given the current goal and discrepancy.

3 Related Work

Several groups have studied integrations of CBR and RL. Bridge (2005) noted that these typically attempt to use the advantages of one to improve the other. For example, RL has been used to help CBR solve problems in continuous environments (Ram and Santamaria 1997; Molineaux et al. 2008) and to improve case retrieval (Juell and Paulson 2003). Analogously, CBR has been used to speed up the RL process (Gabel and Riedmiller 2007; Auslander et al. 2008; Bianchi et al. 2009) and to reduce RL's memory footprint (Dilts and Mu-oz-Avila 2010). We instead integrate them to automatically acquire and reuse GDA knowledge.

Our work relates to planning in dynamic environments, which spawned contingency planning methods (Dearden et al. 2003), in which agents plan for plausible contingencies that may occur during plan execution. Conformant planning methods (Goldman and Boddy 1996) instead generate plans that are guaranteed to succeed. These methods require the a priori identification of possible contingencies. Plan repair methods instead adapt a plan's remaining actions whenever the state conditions required to execute the plan's next action are not satisfied (Fox et al. 2006). These agents cannot change their goals, while GDA agents instead dynamically reason about which goals they should achieve.

Our work focuses on the meta-process of goal reasoning. Some goal reasoning planners relax the requirement that the plan must achieve all of its goals. For example, oversubscription planners attempt to satisfy only a maximal subset of the goals (Van den Briel et al. 2004).

Cox's (2007) research on self-aware agents inspired the GDA model of goal reasoning. Most research on GDA assumes that experts provide domain knowledge on what to expect when an action is executed and which goal should be achieved next if a state discrepancy arises. The two exceptions are recent work on learning goal selection knowledge. First, Weber et al. (2010) uses CBR for this task, but doesn't learn about expectations. Their cases map discrepancies (between the current state and the goal the agent is trying to achieve) to new goals, which are represented as states, and their nearest neighbor algorithm compares the current state with recorded cases to perform goal selection. LGDA instead learns expectations, discrepancies, and goals. Furthermore, goals can be state abstractions (e.g., win the game) and LGDA could map a discrepancy to multiple goals. Second, Powell et al.'s (2011) active learner requires a user to indicate which goal to achieve next when discrepancies occur. In contrast our approach is fully automated.

4 Goal-Driven Autonomy

GDA (Figure 1) is a goal reasoning model that permits autonomous agents to dynamically self-select their goals during plan execution (Molineaux et al. 2010). This model extends the conceptual model of online classical planning (Nau 2007), whose components include a Planner, a Controller, and a State Transition System ∆ = (S,A,V,γ) with states S, actions A, exogenous events V, and state transition function γ: S⋅(A⇒V)τ2 S . In the GDA model, the Controller is centric: it receives as input a planning problem (MΣ, st, gt), where MΣ is a model of Σ, st is the current state (e.g., initially s0), and gt∨G is a goal that can be satisfied by some set of states Sg ∧ S. It gives this problem to the Planner Π, which generates a sequence of actions and a corresponding sequence of expectations , where each is a set of constraints that are predicted to hold in states when executing in st using . The Controller sends to Σ for execution and retrieves resulting state st+1, at which time it performs four knowledge-intensive tasks:

1. Discrepancy detection: This compares observations with expectation . If a discrepancy (i.e., unexpected observation) is found, then explanation generation is performed to explain it.
2. Explanation generation: This explains a detected discrepancy dt. Given also state , it hypothesizes one or more explanations of the cause.
3. Goal formulation: Resolving a discrepancy may warrant a change in the current goal(s). This task generates goal given a discrepancy , its explanation , and current state .
4. Goal management: New goals are added to the set of pending goals , which may also warrant other edits to GP. The Goal Manager will select the next goal to be given to the Planner. (It is possible that .)

We focus on discrepancy detection and goal formulation here and will address the others steps in future work.

5 Learning Algorithm

5.1 Definitions

Let S be the set of states that an agent can visit, G the goals that an agent can pursue, and A the actions that can be executed. We define an expectation case base (ECB) as a mapping S ⋅ A τ 2 S⋅[0,1] from the current state and selected action to a probability distribution over expected next states (i.e., actions can be non-deterministic). LGDA clusters ECB cases that involve the same action and have similar states, and learns a state probability distribution for each cluster.

In LGDA (see ¤5.2), Get(ECB,s,a) returns, as the expected state, the one with maximal probability among the ECB cluster ∪s,a whose state is most similar to s and has the same action a. If no such cluster exists, then Update(ECB,s,a,s′) will create one. Otherwise, it will update the probability distribution for ∪s,a.

A goal formulation case base (GFCB) instead maps the current goal gt and discrepancy dt into a distribution over the expected values, G ⋅ D τ 2 G⋅[0,1] , for formulated goals. That is, multiple goals g′ may be formulated to resolve d when pursuing g. Cases with the same goal and similar discrepancies are clustered together in GFCB. LGDA uses Q-learning to track the expected value for each g′. In LGDA (¤5.2), Get(GFCB,g,d,g′) returns the expected value q from cluster ∪g,d when g′ is formulated. If no such cluster exists, it returns 0 and initializes ∪g,d. Function call Update(GFCB,g,d,g′,q′) updates the value of q for g′ in ∪g,d.

LGDA receives as input the policies √: G ⋅ S τ A that are implemented by hard-coded adversaries. The call √(g) returns the policy Μ for G, while Μ(s) returns the action that is pursued in state s (if multiple such actions exist, one is randomly selected). These input policies are static, not learned. LGDA instead learns the case bases (1) ECB and (2) GFCB. This learned knowledge is dynamic; their application varies based on the environment's state in which the actions are executed.

5.2 LGDA Algorithm

Expectations can be learned by recording the occurrence frequency of (s,a,x) triples. The interpretation of the most frequent triple (s,a,x) among those in ( ) in the ECB is that, when is the current state, it is most likely that will be the next state when a is executed. We use and for the previous, current, and expected states, respectively

Let g, g′, and g′′ be the previous, current, and next goals, respectively. LGDA uses Q-learning to learn the values of goals in each GFCB cluster. The following pseudocode provides details and is documented below.

LGDA(s0,g0,d0,∞,ECB,GFCB,∈,Β, G,√) = 1: s s0; x s0; a ⇓; g g0; g′ g0; d d0 2: While the game-playing episode continues 3: wait(∞); GETSTATE() 4: ECB UPDATE( ) 5: CALCULATEDISCREPANCY( , ) 6: GET( , , ) 7: r U( ) 2U( ) 8: q′ σq + ∈ (r + Β ARGMAXgl(GET(GFCB,g,d,gl)) - q) 9: GFCB UPDATE , d, , ) 10: if r < 0 11: if RANDOM(1) 12: g′′ σ ARGMAXgl(GET(GFCB,g,d,gl)) 13: else RAN O 14: ; 15: Μσ√(g′); Μ( ) 16: GET 17: EXECUTEACTION( ) 18: ; 19: return ECB, GFCB

LGDA initializes previous state to the initial state , action a to the null action, previous goal and current goal to the dummy goal , and discrepancy to dummy value (Line 1). Entries with these dummy values are not added to the case base, and will be assigned to non-dummy values after the algorithm's first iteration. During a gameplaying episode (Line 2), LGDA periodically waits and observes the current state (Line 3), which it uses to update the distribution of expected states when taking action in (Line 4). It then calculates the discrepancy between the current and expected states (Line 5) and uses it to retrieve GFCB's estimated value for formulating (Line 6). 1 It then computes the reward (Line 7), updates the value using the Q-learning formula (Line 8), and records it in the GFCB (Line 9). If the agent is performing poorly (Line 10), LGDA retrieves a new goal from GFCB using ⌡-greedy exploration (Lines 11-13), and updates its previous and current goal (Line 14). LGDA then retrieves the next action using policy Μ, where Μ is the policy in √ for goal g′. (Line 15), retrieves an expected state from the ECB (Line 16), executes (Line 17), and updates previous state and action (Line 18). Finally, when the game-playing episode ends, it returns the revised case bases.

1 Although not shown, if no discrepancy exists, the goal does not change.

6 Implementation and Example

An LGDA agent must determine how to cluster cases using a similarity metric and re-cluster when necessary. Our implementation was inspired by the design of Retaliate (Smith et al. 2007), an RL agent that we will use for benchmarking. For LGDA, we ensure that the states S and actions A represented in ECB and GFCB, as well as the state utility U, are the same as those in Retaliate. Theoretically, this permits a fair comparison between LGDA and Retaliate.

Retaliate was applied to control one team's actions in a domination game called DOM (see Figure 2), in which two competing teams attempt to capture specified domination locations on a two-dimensional map. Teams are composed of k bots. The teams' actions are k-tuples (l1,..lk) indicating the domination location li to which each bot bi is assigned. Domination locations are captured by a team when one of its bots moves into its location and no bots from the other team arrive within five ticks. A team receives a point for every five seconds that it owns a domination location. The first team to earn a predefined number of points wins. Each bot starts with a max number of health points, which can be lost in combat, which occurs when two or more opposing bots are within a certain range of each other. Combat is solved using a biased random function that determines the health points lost by each competing bot (it favors bots on the team that has more bots within range). When a bot's health is zero, it is removed, respawns after a few ticks in a (randomly-selected) respawning location, and continues with its initial max health points.

Retaliate selects the actions for the friendly team's bots. Its state representation includes only information on domination location ownership. The state is a vector (l1,l2…,ld), where d is the number of domination locations and lk indicates the team which owns location k. For a 2team game and b bots per team, this reduces the number of states to d 3 and the space of actions to (2b) d . The utility U of state s is defined by the function U(s) = F(s)-E(s), where F(s) is the friendly team's score and E(s) is the enemy's score. The discrepancy between states s and s′ is a ddimensional vector (v1,v2…,vd), where vi is true if s and s′ have the same value in coordinate i and false otherwise.

Given this representation, LGDA's cases implement a simple similarity metric: two states are deemed similar if they have the same feature values for domination location ownership. Analogously, two discrepancies are similar if they mismatch on the same features. Thus, after a case is assigned to a cluster, it will never be reassigned.

Example. Suppose the domination locations in the current game are ( , , and and there are three bots per team ( . Each location li can be in one of the three states: un-owned (U), owned by the friendly team (F), or owned by the enemy (E). Therefore, state (E,F,F) denotes that the first domination location is owned by the enemy and the others are owned by the friendly team. Suppose the previous state is ( ), the current state is ( ), the expected state is ( ), and the friendly team's previous actions were ( ). After updating the relevant ECB distribution (Line 4), LGDA will calculate the discrepancy between the current and expected states (Line 5). Here, is (true, false, true), where true means they match. After calculating the value and updating the (Lines 6-9), suppose the reward is negative, and that LGDA will retrieve/formulate a new goal. Suppose the current goal is to control the first half plus one of the domination locations, and the next goal that was retrieved from the GFCB is to control all domination locations. Then the action that will be retrieved from policy Μ will be ( ). The expectation that it retrieves from GFCB for executing action is ( ) (Line 16). LGDA will then execute a′ and record the new values for the previous state and action (Line 18).

7 Empirical Study

7.1 Experimental Setup

We used the task of winning DOM games to investigate two hypotheses: (H1) LGDA can learn to perform as well as a non-learning GDA agent that employs expert knowledge, and (H2) LGDA can significantly outperform ablated agents that use only RL or only CBR, respectively.

We also used six hand-coded adversaries as baselines. Munoz-Avila et al. (2010) describe each except Priority, which prefers to send bots to those locations that are owned by its opponent. Briefly, these adversaries pursue a unique goal gi to play DOM. Their behavior is approximately modeled using a policy Μi. That is, while the first three adversaries are easy to defeat, the latter three cannot be perfectly represented as policies based on our models for S

and A because they reason about the proximity of bots to locations. Proximal information is not represented by any of the four agents we tested. Thus, the latter three adversaries pose difficult challenges for the agents.

We compared LGDA versus the following agents: Retaliate, which performs Q-learning, the ablation Random GDA (RGDA), which replaces LGDA's ⌡-greedy goal selection procedure with a random selection procedure, and CB-gda, a non-learning CBR agent whose case bases were manually crafted by a domain expert (Mu-oz-Avila et al. 2010). It includes two case bases, whose mappings are:

PCB records the expected state for each (goal, state, action) tuple, and MCB records the preferred goal to formulate for each (goal, discrepancy) pair. All agents (CB-gda, LGDA, Retaliate, and RGDA) use the same model for S and A. The learning agents (the latter three) use the same utility function U. The definitions for S, A, and U are given in ¤6.

Games are won by the first team to reach 2000 points on Figure 2's map. There were 8 bots per team, which is typical (i.e., there are usually more team members than domination locations). Scores were averaged over 10 games. In our first study, we indirectly compared the agents by testing them against the six hard-coded adversaries using a LOOCV method: we trained each learning agent versus five adversaries, using four repetitions per starting state, and tested it against the remaining adversary. The second study addresses our hypotheses: it directly compares LGDA versus the other agents. We trained each learning agent versus the six adversaries. LGDA received as input the policies for the six adversaries but not the policies for the other agents. We recorded results before and after each training repetition of LGDA versus each of the three agents, continuing until their relative performance stabilized. Knowledge learned during testing was flushed between games. Our metric is state utility, as defined in ¤6.

7.2 Results

Experiment 1 (Table 1): CB-gda recorded the best performance among the agents; it outperformed all of the adversaries, although barely so versus EachBotToOneDom, which is the strongest of the hard-coded adversaries. This adversary maintains at least one bot in each location. LGDA outperformed five of the opponents, losing only to EachBotToOneDom. In contrast, Retaliate and RGDA performed poorly versus all three of the difficult adversaries. This provides initial evidence that LGDA performs comparatively well compared to its ablations but it is outperformed by CB-gda. Our next experiment provides strong support for these observations.

Experiment 2 (Figure 3): LGDA is outperformed by CBgda. The mean of the underlying distribution for their relative utility values after training was -14.6 χ 2.6 at the 95% confidence level. Thus, H1 is not supported, though LGDA's final performance is fairly close. This is not too surprising, given that CB-gda's case bases were manually encoded by a domain expert.

LGDA is initially outperformed by Retaliate because Retaliate quickly converges to an action that on average works well versus the adversaries. In contrast, LGDA needs to learn expectations and best goals to pursue when discrepancies occur. This results in a slower learning process in part because the interdependency between expectations and discrepancies. Over time we see that it pays off; LGDA eventually outperforms Retaliate. LGDA outperforms RGDA from the outset. Versus Retaliate, the same analysis reveals a mean of 34.3 χ 4.1 at the 95% confidence level, and the mean (at this level) versus RGDA was 62.6 χ 2.4. Thus, these results strongly support H2.

8 Conclusions

We introduced LGDA, a goal-driven autonomy agent that automatically acquires state expectation and goal selection knowledge. LGDA uses a case-based reasoning method to map (state,action) pairs to a distribution over expected states, and (goal,discrepancy) pairs to a value distribution over discrepancy-resolution goals. It also uses a reinforcement learning method to learn the goals' expected values. LGDA is the first GDA agent to automatically learn this knowledge, and the first to model these two distributions. Our ablation study demonstrated that, for a complex first-person shooter gaming task, LGDA significantly outperforms ablations that use only one of its two learning methods. LGDA also learns to play nearly as well as an expertly-engineered GDA agent.

We conjecture that the expertly-engineered GDA agent is outperforming LGDA because LGDA lacks capabilities to learn explanations of discrepancies and could benefit from a more mature goal management strategy. We will study this issue, related GDA extensions, and conduct more extensive evaluations in our future research.

Acknowledgements

This work was supported in part by NSF grant 0642882.