[ADD] 논문 : Case-Based Learning in Goal-Driven Autonomy Agents for Real-Time Strategy Combat Tasks

Case-Based Learning in Goal-Driven Autonomy Agents for Real-Time Strategy Combat Tasks

실시간 전략 전투 작업을 위한 목표 중심 자율 에이전트의 사례 기반 학습

Ulit Jaidee1, Héctor Muñoz-Avila1, and David W. Aha2
1Department of Computer Science and Engineering, Lehigh University, Bethlehem, PA
Keywords: Case-based learning, goal-driven autonomy, real-time strategy 

---

 

요약.
실시간 전략 게임을 위한 목표 중심 자율 에이전트(GDA)에서 사례 기반 학습 기술을 사용하는 방법에 대한 연구를 설명합니다. LGDA (Learning GDA) 에이전트에 저장하는 두 가지 사례는 다음과 같습니다.

• 행동을 수행할 때 에이전트가 도달할 수 있는 것으로 예상되는 상태
• 예상한 상태와 실제 상태간에 불일치가 발생할 때, 추구할 다음 목표

우리는 LGDA를 사용한 성능 향상을 보여주는 ablation study에 대해 보고합니다.

 

---

1 Introduction

GDA는 에이전트가 현재 계획의 실행을 지속적으로 모니터링하며, 발견된 상태와 예상한 상태와 일치하는지 여부를 평가하는 목표 추론 모델입니다 (Molineaux et al., 2010). GDA 에이전트가 예상 상태와 실제 상태의 불일치를 감지하면, 달성 시 장기 보상 극대화와 같은 목표를 이룰 수 있는 새로운 Goal을 수립할지 여부를 고려합니다. 이 모니터링 과정과 보상을 극대화하기 위한 장기 목표는 강화 학습 (RL)을 연상시킵니다 (Sutton & Barto, 1994). 우리는 예상과 불일치를 명시적으로 표현함으로써, GDA 에이전트가 RL 에이전트보다 동적 환경의 불일치에 더 빨리 적응할 수 있다고 주장합니다.

우리는 실시간 전략 (RTS) 게임에서 전투 과제에 대한 예상과 불일치를 학습할 수 있는 GDA 학습 알고리즘을 제시합니다. 이때 게임 환경은 인기 있는 Wargus 게임 엔진을 사용합니다(Aha et al., 2005; Judah et al., 2010). 전투 작업에서 플레이어는 자신의 유닛을 조종하여 상대방의 유닛을 물리칩니다. 이 작업은 두 가지 이유로 복잡합니다.

첫째, 다양한 기능을 가진 여러 유닛 유형이 존재하며 RTS 게임은 유형에 따라 유닛을 적절하게 사용하도록 하는 가위 바위 보 상성을 따릅니다. 예를 들어, 궁수는 풋맨을 빠르게 제거 할 수 있는 장거리 유닛으로 느리고 근거리에서만 공격 할 수 있습니다. 그리고 빠르게 움직이는 기사들은 근접 공격을 사용하여 궁수를 쉽게 제거 할 수 있습니다. 마지막으로, 푸트 맨은 기사를 모아서 기사를 제거 할 수 있습니다.

둘째, RTS 게임은 전술 역할에 유닛을 할당합니다. 그룹의 각 유닛은 유형과 그룹에 있는 다른 유닛의 유형에 따라 역할을 맡습니다. 예를 들어, 풋맨은 전차의 역할을 할 수 있고, 궁수는 중화기의 역할을 할 수 있으며, 기사는 문제가 발생할 경우 예비 역할을 할 수 있습니다. 그러나 그룹에 풋맨이 없으면 기사가 전차의 역할을 할 수 있습니다.

이 두 가지 특성은 전투 과제를 배우는 방법에 있어 어려운 과제입니다. 이러한 어려움은 RTS 게임의 다른 특성으로 인해 악화 됩니다 : 상대방, 실시간 및 확률적 행동 (예 : 확률적으로 공격 할 때 발생하는 피해량을 결정합니다).

우리는 (1) 계획 실행 중의 예상(2) 예상 상태와 발생 상태간에 발생하는 불일치에 대해 추론하여, 게임 전체에서 어떤 목표를 달성하는 것이 가장 좋은지를 자동으로 배우는 에이전트에 관심이 있습니다. LGDA는 예상되는 상황을 기록하는 예상 Case-Base와, 불일치가 발생할 때 추구 할 다음 목표를 기록하는 목표 구성 Case-Base, 이렇게 두 가지 사례 기반을 학습하여 이를 달성합니다.

2장에서는 Wargus 게임 요소를 사용하고 잘 알려진 RL 개념과 대조하여 GDA 개념을 정의합니다.
3장은 사례 기반 학습을 위한 기술을 제시합니다. 우리는 이것들을 강화학습 사이클과 대조합니다.
4장은 학습 에피소드의 예를 보여줍니다.
5장은 경험적 평가를 제시합니다.
6장은 관련 작업,
7장은 향후 작업에 대해 논의합니다.

2 Elements of the Learning Goal-Driven Autonomy Algorithm

LGDA는 기본 행동 모델 S : S · A 2S를 제공받습니다. 여기서 S는, 각 상태 s와 각 동작 a에 대하여 s상태에서 a가 실행될 때 도달할 수 있는 상태들의 집합 S (s, a)를 나타냅니다. 이는 강화학습으로 학습한 상태 이동 모델과 동일하며, 계획 에이전트가 요구하는 행동 모델과 동일합니다. 예를 들어, 상태 정보는 궁수가 적군 풋맨의 공격 범위 내에 있다는 것을 포함할 수 있습니다. 공격을 실행 한 후, 환경 상태는 풋맨이 죽었거나, 아처가 죽었거나, 둘 다 죽었음을 나타낼 수 있습니다.

LGDA는 (1) 어떤 행동이 어떤 상태에 대해 "최고의" 행동인지, (2) 상태 s에서 행동 a를 실행할 때, 상태 s'에 도달할 확률이 얼마인지 모릅니다. 이 예시에서는 에이전트는 궁수 또는 풋맨이 상대를 죽일 확률을 모릅니다. 이것은 강화학습 에이전트를 연상시킵니다. 강화학습 에이전트는 이 정보를 사용하여 임의의 s에 대한 V(s)값과 상태 s에서 행동 a를 실행했을 때의 Q(s, a)를 학습합니다.

However, GDA agents also know the goals G that can be pursued. For example, a goal “divide and conquer” may require splitting a force into two groups, with the first advancing towards the enemy from the north and the latter from the south. Furthermore, for each goal g, LGDA is given the policy pg: S  2[0,1] · A, which indicates how to achieve g by mapping, for every state s, the  probability distribution pg(s), which is a collection of pairs (p,a), where p is the probability that action a is taken. Acquiring such policies automatically is possible as demonstrated in Gillespie et al. (2010), which observes a player’s actions while pursuing a goal g and records the probability distribution pg(s) for each state s over multiple games. 

Initially, LGDA has no knowledge about which goal in G it should pursue at a given time or the semantics of these goals g (i.e., what they achieve). It is also not given the semantics of their policies pg. However, if it can learn this information, then LGDA could self-determine which goal it should pursue, and could constantly monitor the environment to make sure that the states it encounters are as expected.

그러나 GDA 에이전트는 추구 할 수 있는 목표 G도 알고 있습니다. 예를 들어, “분할 정복” 이라는 목표는 힘을 두 그룹으로 나누고, 첫 번째는 북쪽에서, 다른 하나는 남쪽에서 전진할 것을 요구합니다. 또한 각 목표 g에 대해 LGDA는 다음과 같은 정책 pg: S 2[0,1] · A를 부여 받습니다. 이는 모든 상태 s에 대해 확률 분포 pg (s)를 매핑하여 g를 달성하는 방법을 나타냅니다. 쌍 (p, a), 여기서 p는 동작 a가 취해질 확률입니다. Gillespie et al.에 설명 된대로 이러한 정책을 자동으로 획득 할 수 있습니다. (2010) : 목표 g를 추구하면서 플레이어의 행동을 관찰하고 여러 게임에서 각 주에 대한 확률 분포 pg (s)를 기록합니다.

처음에 LGDA는 주어진 시간에 어떤 목표를 추구해야 하는지 또는 이러한 목표의 의미론 (즉, 달성 한 목표)에 대해 알지 못합니다. 또한 정책 pg의 의미론도 제공되지 않습니다. 그러나 이 정보를 배울 수 있다면 LGDA는 어떤 목표를 추구해야 하는지 스스로 결정할 수 있고, 직면 한 상태가 예상 한 것인지 확인하기 위해 환경을 지속적으로 모니터링 할 수 있습니다.

One way that LGDA can learn the meaning of the goal g is by inspecting pg(s) for each state s to examine the possible actions and the probability of taking them, and then observe for each action a in pg(s), the states S(s,a) that could be reached. However, it is difficult to automatically elicit from these inspections anything resembling our description of the “divide and conquer” goal. Instead, LGDA learns (during environment interactions) the expectations case base (ECB), which records the expected states encountered, and the goal formulation case base (GFCB), which records the next goal to pursue when a discrepancy occurs. 

The ECB enhances the state transition model by defining the probability that a state s′ will be reached when taking action a in state s. More precisely, ECB computes the mapping S · A  2[0,1] · S, where for each state-action pair (s,a), it returns a probability distribution ECB(s,a) as a collection of pairs (p,s′), where p is the probability that state s′ is reached when executing action a in state s.

LGDA가 목표 g의 의미를 배울 수 있는 한 가지 방법은 각 상태에 대한 pg (s)를 검사하여 가능한 조치와 취할 가능성을 조사한 다음 각 조치 a에 대해 pg (s) 상태로 관찰하는 것입니다 도달 할 수 있는 S 그러나“분할 및 정복”목표에 대한 설명과 유사한 내용을 이러한 검사에서 자동으로 도출하는 것은 어렵습니다. 대신, LGDA는 (환경 상호 작용 중에) 발생하는 예상 상태를 기록하는 기대 사례 기반 (ECB)과 불일치가 발생할 때 추구 할 다음 목표를 기록하는 목표 구성 사례 기반 (GFCB)을 학습합니다.

ECB는 상태 s에서 조치를 취할 때 상태 s '에 도달 할 확률을 정의하여 상태 전이 모델을 향상시킵니다. 보다 정확하게, ECB는 매핑 S · A 2 [0,1] · S를 계산합니다. 여기서 각 상태-작업 쌍 (s, a)에 대해 확률 분포 ECB (s, a)를 쌍의 모음으로 반환합니다 (p 여기서, p는 상태 s에서 동작 a를 실행할 때 상태 s '에 도달 할 확률이다.

 We use a standard feature-value vector representation to represent a state. More precisely, we define a state as an n-tuple vector of values s = (v1,…,vn), where each value vi is of some type Ti. In our Wargus scenarios, armies include multiple unit types. Given this, our states are vectors s=(f,a,m,k,f’,a’,m’k’), which respectively denote the number of footmen, archers, mages, and knights in the army being controlled by our team and those controlled by the opponent. This simple model works surprisingly well in scenarios where no units and buildings can be created, maps have no obstacles and the available units from the opponents are observable.

We define a state discrepancy (or simply a discrepancy) as an n-vector of binary values (b1,…,bn). Given two states x and s′ (i.e., the expected and actual states), the discrepancy value for the coordinate k, bk, is defined as 1 if x and s′ have the same value on coordinate k and 0 if otherwise.

The GFCB denotes, for a goal g being pursued and a discrepancy d, the expected value of pursuing another goal g′ given (g,d). More precisely, GFCB computes the mapping G · D   2[0,1] · G, where for each goal discrepancy pair (g,d), it returns a probability distribution GFCB(g,d) as a collection of pairs (v,g′), where v is the expected value of selecting goal g′ when (g,d) occurs.

표준 피처-값 벡터 표현을 사용하여 상태를 나타냅니다. 보다 정확하게, 상태를 값 s = (v1,…, vn)의 n- 튜플 벡터로 정의합니다. 여기서 각 값 vi는 Ti 유형입니다. 우리의 Wargus 시나리오에서 군대는 여러 유닛 유형을 포함합니다. 이것을 감안할 때, 우리의 상태는 벡터 s = (f, a, m, k, f ', a', m'k ')이며, 각각에 의해 통제되는 군대의 기병, 궁수, 마법사 및 기사의 수를 나타냅니다. 우리 팀과 상대방이 통제하는 팀. 이 간단한 모델은 유닛과 건물을 만들 수 없고, 지도에 장애물이 없고 상대방의 사용 가능한 유닛을 관찰 할 수 있는 시나리오에서 놀랍게 잘 작동합니다.

상태 불일치 (또는 단순히 불일치)를 이진 값의 n- 벡터 (b1,…, bn)로 정의합니다. 두 상태 x와 s '(즉, 예상 및 실제 상태)가 주어지면 좌표 k, bk에 대한 불일치 값은 x와 s'가 좌표 k에서 동일한 값을 갖는 경우 1로 정의되고 그렇지 않으면 0으로 정의됩니다.

GFCB는 목표 g가 추구하고 불일치 d에 대해 주어진 다른 목표 g '(g, d)를 추구 할 것으로 예상되는 값을 나타낸다. 보다 정확하게, GFCB는 매핑 G · D 2 [0,1] · G를 계산합니다. 여기서 각 목표 불일치 쌍 (g, d)에 대해 확률 분포 GFCB (g, d)를 쌍 (v, g '), 여기서 v는 (g, d)가 발생할 때 목표 g'를 선택하는 기대 값이다.

3 The Feedback Loop in LGDA

Figure 1 presents the feedback loop that our learning agent LGDA follows when performing goal-driven autonomy after training. LGDA’s inputs are a collection of goals and a collection of policies, one policy pg for each goal g. The outputs from training are the expectations case base ECB and the goal formulation case base GFCB; we discuss learning these below. LGDA begins with some given goal g = ginit and an initial state s = s0 (Label 1). The following steps are repeated while LGDA interacts with the environment (i.e., in this paper, Wargus). For further details about LGDA please see Jaidee et al. (2011):

그림 1은 학습 후 목표 중심 자율성을 수행 할 때 학습 에이전트 LGDA가 따르는 피드백 루프를 보여줍니다. LGDA의 의견은 목표 및 정책 모음으로, 각 목표 g마다 하나의 정책 pg입니다. 훈련 결과는 기대 사례 기반 ECB와 목표 공식 사례 기반 GFCB이다. 우리는 아래에서 이것을 배우는 것에 대해 토론합니다. LGDA는 주어진 목표 g = ginit 및 초기 상태 s = s0 (라벨 1)로 시작합니다. LGDA가 환경과 상호 작용하는 동안 (이 문서에서는 Wargus) 다음 단계가 반복됩니다. LGDA에 대한 자세한 내용은 Jaidee et al. (2011) :

 SHAPE  \* MERGEFORMAT

Figure 1:

Information flow in LGDA

1. Given s and g, the next action a is computed by executing policy pg. Thus, a is chosen according to the probability distribution pg(s) (Label 2).

2. Action a is executed in the environment, resulting in a new state s′ (Label 3).

3. After a fixed amount of time, s′ is compared against the expected state x (Label 4). Since expected states have a probability distribution, the expected state is computed as the one with the maximum probability:

x = maxp {(x,p) ˛ ECB(s,a)}.

4. A discrepancy d occurs whenever x „ s′ and it is computed as described in Section 2. When a discrepancy occurs a new goal g′ is selected based on (g,d) (Label 5). The new goal is selected with an e-greedy selection process: with a probability 1-e a random goal in GFCB(g,d) is selected; with probability e, the goal with the highest expected value is computed:

1. s와 g가 주어지면, 다음 조치 a는 정책 pg를 실행하여 계산됩니다. 따라서, 확률 분포 pg (s) (라벨 2)에 따라 a가 선택된다.

2. 액션 a가 환경에서 실행되어 새로운 상태 s '(라벨 3)가 생성됩니다.

고정 된 시간 후, s '는 예상 상태 x와 비교된다 (라벨 4). 예상 상태에는 확률 분포가 있으므로 예상 상태는 최대 확률이 있는 상태로 계산됩니다.

x = maxp {(x, p) ˛ ECB (s, a)}.

불일치 d는 x 's'마다 발생하고 섹션 2에 설명 된대로 계산됩니다. 불일치가 발생하면 새로운 목표 g '가 (g, d)에 따라 선택됩니다 (라벨 5). 새로운 목표는 전자 탐욕 선택 과정으로 선택 된다: 확률 1-e에서 GFCB (g, d)의 랜덤 목표가 선택된다; 확률 e를 사용하면 예상 값이 가장 높은 목표가 계산됩니다.

g′ = maxv {(g′,v) ˛ GFCB(g,d)}

Learning the Expectations Case Base. In Step 3, the values of s, a, and s′ are used to update the ECB’s probabilities for ECB(s,a) by incorporating the new occurrence of (s,a,s′). If an entry (s′,p) already exists in ECB(s,a), then its probability is increased (and the probabilities of the other entries are decreased). If the entry (s′,p) does not exist in ECB(s,a), then a new one is added with a low probability (and the probabilities of the other entries are slightly decreased).

기대 사례 기반 학습. 3 단계에서 s, a 및 s '값은 새로운 (s, a, s')를 통합하여 ECB (s, a)에 대한 ECB의 확률을 업데이트하는 데 사용됩니다. ECB (s, a)에 항목 (s ', p)이 이미 존재하면 확률이 증가하고 다른 항목의 확률이 감소합니다. 항목 (s ', p)이 ECB (s, a)에 존재하지 않으면 새로운 항목이 낮은 확률로 추가되고 다른 항목의 확률이 약간 감소합니다.

Learning the Goal Formulation Case Base. In Step 4, the values of g, d, and g′ are used to update GFCB via Q-learning (Sutton & Barto, 1998). LGDA maps Q-learning states to (g,d) pairs and maps actions to the next goal g′. Hence, Q((g,d),g′) represents the expected value of taking goal g′ when g and d are the current goal and discrepancy. The reward is taken from the environment after executing an action. In a Wargus game, the reward is the difference in score between the time that an action a is selected and the time when its execution ends. Hence, our formulation seeks to choose new goals that maximize the game score.

목표 공식화 사례 기반 학습. 단계 4에서, g, d 및 g '의 값은 Q- 러닝을 통해 GFCB를 업데이트하는데 사용된다 (Sutton & Barto, 1998). LGDA는 Q- 러닝 상태를 (g, d) 쌍에 매핑하고 동작을 다음 목표 g '에 매핑 합니다. 따라서 Q ((g, d), g ')는 g와 d가 현재 목표와 불일치 인 경우 목표 g'를 취하는 예상 값을 나타냅니다. 보상은 행동을 수행 한 후 환경에서 가져옵니다. Wargus 게임에서 보상은 행동 a가 선택된 시간과 실행이 종료되는 시간 사이의 점수 차이입니다. 따라서 우리의 공식은 게임 점수를 극대화하는 새로운 목표를 선택하려고 합니다.

4 Domain Model and Example

To demonstrate case-based learning of GDA agents for real-time strategy combat tasks, we use Wargus for our environment (Figure 2). Wargus is a modified version of Warcraft II , which is a RTS game developed by Blizzard Entertainment.

실시간 전략 전투 작업을 위한 사례 기반 GDA 에이전트 학습을 시연하기 위해 환경에 Wargus를 사용합니다 (그림 2). Wargus는 Blizzard Entertainment가 개발 한 RTS 게임 인 Warcraft II의 수정 된 버전입니다.

 SHAPE  \* MERGEFORMAT

Figure 2:

Snapshot of a Wargus Game

Wargus is a multiplayer combat game. In our experiments, we use two competing teams. Each team includes multiple types of units. Units vary in their number of hit points. When a unit is attacked, its hit points are decreased. When a unit’s hit points is reduced to zero, it dies (i.e., is removed from the game). When a unit A of one team kills a unit B of another team, the score of unit A’s team is increased. For combat tasks, the game ends when all units of one team are eliminated.

Wargus는 멀티 플레이어 전투 게임입니다. 실험에서는 두 개의 경쟁 팀을 사용합니다. 각 팀에는 여러 유형의 단위가 포함됩니다. 적중 횟수는 다양합니다. 유닛이 공격을 받으면 적중률이 감소합니다. 유닛의 체력이 0으로 줄어들면 죽습니다 (즉, 게임에서 제거됩니다). 한 팀의 유닛 A가 다른 팀의 유닛 B를 죽이면 유닛 A의 팀 점수가 증가합니다. 전투 작업의 경우 한 팀의 모든 유닛이 제거되면 게임이 종료됩니다.

Teams are initially composed of n units of k different types. States are 2k-tuples (x1,x2,…xk,y1,y2,…,yk) where xi and yi are the current number of units of type i on our team and the opponent team, respectively. The first half of the vector encodes the number of units for the first team of each type ti and the second half the types of units of each type ti-k for the second team. The states include information about only the current units. Thus, each value is an integer in the range [0,n], and the number of units per team also remains in the range [0,n]. In our experiments we have 5 types: footmen, archers, knights, mages, and ballistae. Actions are n-tuples (a1, a2,… an-1, an), where ai ˛ {0,1,…,k-1,k} such that 0 indicates that the unit does nothing and ai ≥ 1 indicates that unit i will attack an opponent unit of type ai.

The utility U of state s is defined by the function U(s) = F(s)–E(s), where F(s) is our team’s score and E(s) is the enemy’s score. The discrepancy between states s and s′ is a 2k-dimensional vector (v0,v1,…vk-1,vk,vk+1,… ,v2k-2,v2k-1), where vi is true (i.e., 1) if s and s′ have the same value in coordinate i and false otherwise.

팀은 처음에 k 개의 다른 유형의 n 개 단위로 구성됩니다. 상태는 2k 튜플 (x1, x2,… xk, y1, y2,…, yk)입니다. 여기서 xi 및 yi는 각각 팀과 상대 팀에서 현재 유형 i의 단위 수입니다. 벡터의 전반부는 각 유형 ti의 첫 번째 팀에 대한 단위 수를, 후반은 두 번째 팀에 대한 각 유형 ti-k의 단위 유형을 인코딩 합니다. 상태에는 현재 단위에 대한 정보 만 포함됩니다. 따라서 각 값은 [0, n] 범위의 정수이며 팀 당 단위 수도 [0, n] 범위에 있습니다. 실험에서 우리는 기수, 궁수, 기사, 마법사, 발리스타의 5 가지 유형이 있습니다. 동작은 n- 튜플 (a1, a2,… an-1, an)이며, 여기서 ai ˛ {0,1,…, k-1, k}는 0이 장치가 아무 것도 하지 않음을 나타내고 ai ≥ 1은 해당 장치를 나타냅니다 나는 ai 형의 상대 유닛을 공격 할 것입니다.

상태 s의 유틸리티 U는 함수 U (s) = F (s) -E (s)로 정의되며, 여기서 F (s)는 우리 팀의 점수이고 E (s)는 적의 점수입니다. 상태 s와 s '간의 불일치는 2k 차원 벡터 (v0, v1,… vk-1, vk, vk + 1,…, v2k-2, v2k-1)이며, 여기서 vi는 참입니다 (즉, 1). s 및 s '가 좌표 i에서 동일한 값을 갖는 경우 그렇지 않으면 false.

Example. Suppose each team has four units of two different types, the current goal g is HiMaxHPTeam (see Table 1 for a description of the goals) and the current state state s is (2,2,1,2). Suppose that according to policy pg the next action a is (0,0,0,0) and according to ECB the expected state ݔ for (s,a) is (ʹǡʹǡͲǡʹ). Suppose the resulting state ݏᇱafter executing a in s is (1,2,1,2). LGDA will calculate the discrepancy ݀ between the current and expected states. Here, d is (false, true, false, true). The next goal g¢ is chosen by retrieving it from GFCB(g,d), thus closing the loop.

예. 각 팀에 두 가지 유형의 네 가지 단위가 있다고 가정하고 현재 목표 g는 HiMaxHPTeam (목표 설명은 표 1 참조)이고 현재 상태 s는 (2,2,1,2)입니다. 정책 pg에 따르면 다음 동작 a는 (0,0,0,0)이고 ECB에 따르면 (s, a)에 대한 예상 상태 ݔ는 (ʹǡʹǡͲǡʹ)라고 가정합니다. in s를 실행 한 후의 결과 상태가 (1,2,1,2)라고 가정합니다. LGDA는 현재 상태와 예상 상태 간의 불일치 ݀를 계산합니다. 여기서 d는 (false, true, false, true)입니다. 다음 목표 g ¢는 GFCB (g, d)에서 검색하여 루프를 닫음으로써 선택됩니다.

5 Experimental Evaluation

We used the task of winning Wargus games to investigate the hypothesis: LGDA can significantly outperform ablated agents that use only RL or only CBR, respectively.

우리는 가우스를 조사하기 위해 Wargus 게임에서 이기는 작업을 사용했습니다. LGDA는 각각 RL 만 또는 CBR 만 사용하는 제거 된 에이전트보다 훨씬 뛰어납니다.

 

Table 1: List of goals and their associated policies

Goals	Description of Policies
HIMAXHPTEAM	All units attack opponent units with the highest hit points first (ballistae for our experiment), then attack opponent units with second highest hit points (knights), etc. 모든 유닛은 가장 높은 체력을 가진 상대 유닛을 먼저 공격 한 다음 (이 실험에서는 발리스타) 두 번째로 높은 히트 포인트를 가진 상대 유닛을 공격합니다 (기사) 등
HIRANGETEAM	All units on our team attack opponent units with the highest range of attack first (ballistae in our experiment), and then attack opponent units with the second highest range of attack (archers and mages), etc. 우리 팀의 모든 부대는 가장 높은 공격 범위를 가진 상대 유닛을 먼저 공격하고 (실험에서 발리스타), 두 번째로 높은 공격 범위를 가진 상대 유닛을 공격하십시오 (아처와 마법사).
GOOFYTEAM	Different unit types on our team attack different kinds of enemy units as indicated in the following list: 우리 팀의 다른 유닛 유형은 다음 목록에 표시된 것처럼 다른 종류의 적 유닛을 공격합니다.  SHAPE  \* MERGEFORMAT Type of                 units      Attacking list
		footman	Knightfifootmanfiarcherfiballistafimage
		ballista	footmanfiknightfiarcherfimagefiballista
		knight	archerfimagefiballistafiknightfifootman
		archer	knightfimagefiarcherfifootmanfiballista
		mage	knightfifootmanfiarcherfiballistafimage
KAMIKAZETEAM	Different unit types on our team attack different kinds of enemy units as indicated in the following list: 우리 팀의 다른 유닛 유형은 다음 목록에 표시된 것처럼 다른 종류의 적 유닛을 공격합니다.
TYPEDESCENDTEAM	All units on our team attack opponent enemy units in the same order: magesfiarchersfiknightsfiballistaefifootmen.

 

5.1 Experimental Setup

Game configuration. We ran Wargus on two maps: a medium-sized map (64 x 64 cells) with 8 units per team and a large map (128×128 cells) with 32 units per team.  In the medium map, each team had 4 footmen, 1 archer, 1 knight, 1 mage, and 1 ballista. For the large map, each team had 16 footmen, 4 archers, 4 knights, 4 mages, and 4 ballistae. The set of goals used by LGDA and their associated policies are described in Table 1. A game is won by the first team to reach a predetermined score limit. Scores are computed by Wargus by adding the number of enemy units killed (weighted according to the type of unit) and subtracting the number of own units killed (with the same weights). We set the score limit of the medium map to 200 points and 1000 points for the large map.

We compared LGDA versus the following agents: Retaliate (Smith et al., 2007), which performs Q-learning, and the ablation Random GDA (RGDA), which replaces LGDA’s e-greedy goal selection procedure with a random selection procedure.

게임 구성. 팀당 8 개 단위의 중간 크기 맵 (64 x 64 셀)과 팀 당 32 개 단위의 큰 맵 (128 × 128 셀)의 두 가지 맵에서 Wargus를 실행했습니다. 중형지도에서 각 팀에는 4 명의 선수, 1 명의 궁수, 1 명의 기사, 1 명의 마법사, 1 명의 발리스타가 있었습니다. 큰지도의 경우 각 팀에는 16 명의 풋맨, 4 명의 궁수, 4 명의 기사, 4 명의 마법사, 4 명의 발리스타가 있었습니다. LGDA가 사용하는 일련의 목표와 관련 정책은 표 1에 설명되어 있습니다. 첫 번째 팀이 미리 정해진 점수 한도에 도달하면 게임이 승리합니다. 점수는 살해 된 적 유닛의 수 (유닛 유형에 따라 가중)를 더하고 살인 된 유닛의 수를 빼서 (같은 가중치로) 계산합니다. 중간지도의 점수 제한을 큰 지도의 경우 200 점 및 1000 점으로 설정했습니다.

Q- 러닝을 수행하는 Retaliate (Smith et al., 2007)와 LGDA의 e-greedy 목표 선택 절차를 무작위 선택 절차로 대체하는 절제 무작위 GDA (RGDA)를 LGDA와 비교했습니다.

All agents (LGDA, Retaliate, and RGDA) use the same model for S and A. The learning agents use the same utility function U. The definitions for S, A, and U are given in Section 4. Scores were averaged over 10 games.

This study addresses our hypothesis: it directly compares LGDA versus the other agents. We trained each learning agent versus the five policies described in Table 1. LGDA received as input these policies. We recorded results before and after each training repetition of LGDA versus each of the two other agents, continuing until their relative performance stabilized. Knowledge learned during testing was flushed between games. Our performance metric is state utility, as defined in Section 4. For the e-greedy goal selection procedure, we set e=0.1 for the large map for LGDA agents: it will choose the next best goal 90% of the time and randomly select a goal 10% of the time. For the medium map, we set e=0.3 because games on that map end quickly and we want to encourage LGDA to explore other goals. For this same reason we ran 40 iterations for the medium map to obtain a better estimate of asymptotic performance. In contrast, 20 rounds were sufficient to observe this for the large map.

모든 에이전트 (LGDA, Retaliate 및 RGDA)는 S와 A에 대해 동일한 모델을 사용합니다. 학습 에이전트는 동일한 유틸리티 기능 U를 사용합니다. S, A 및 U에 대한 정의는 섹션 4에 나와 있습니다. 점수는 평균 10 게임 이상입니다. .

이 연구는 우리의 가설을 다룹니다. LGDA와 다른 에이전트를 직접 비교합니다. 우리는 각 학습 에이전트를 표 1에 설명 된 5 가지 정책과 비교하여 교육했습니다. LGDA는 이러한 정책을 입력으로 받았습니다. 우리는 상대적인 성능이 안정화 될 때까지 LGDA의 각 훈련 반복 전과 후의 다른 두 요원 각각에 대한 결과를 기록했다. 테스트하는 동안 배운 지식은 게임간에 쏟아졌습니다. 우리의 성과 지표는 섹션 4에 정의 된 상태 유틸리티입니다. 전자 탐욕적인 목표 선택 절차의 경우 LGDA 에이전트의 큰 지도에 대해 e = 0.1을 설정합니다. 시간의 다음 최고 목표를 90 % 선택하고 무작위로 선택합니다. 시간의 목표 10 %. 중간 맵의 경우 해당 맵의 게임이 빨리 종료되고 LGDA가 다른 목표를 탐색하도록 장려하기 때문에 e = 0.3으로 설정합니다. 같은 이유로 우리는 점근선 성능의 더 나은 추정치를 얻기 위해 매체 맵에 대해 40 번의 반복을 실행했습니다. 대조적으로, 20 라운드는 큰 지도에서 이것을 관찰하기에 충분했습니다.

5.2     Experimental Results

Figures 3 and 4 show the results for the medium and large maps. The ordinate plots the utility and the abscissa plots the number of training iterations that have been completed with the 5 policies shown in Table 1.

그림 3과 4는 중대형지도에 대한 결과를 보여줍니다. 세로 좌표는 유틸리티를 표시하고 가로 좌표는 표 1에 표시된 5 개의 정책으로 완료된 교육 반복 횟수를 표시합니다.

 

Figure 3: Results for 8 versus 8 units on a medium-sized map

 

Figure 4: Results for 32 versus 32 units on a large map

The results validate our hypothesis for LGDA versus Retaliate but not for LGDA versus RGDA. For the former, the mean of the underlying distribution of their difference in utility values in the results for the medium map was 14.3 – 10.1 and in the large map this was 183.8 – 49.9, both at the 95% confidence level. Thus, this supports our hypothesis that LGDA outperforms its RL-only ablation on these maps. However, the results versus RGDA are 17.2 – 19.1 and 88.1 – 110.1, respectively; LGDA is not guaranteed to have a positive utility value vs. RGDA with high confidence. The reason for this is that the given policies are competent and hence, randomly selecting a goal will always select a competent policy. We do observe that, as the number of training iterations increases, LGDA’s performance improves compared to RGDA; LGDA won the last 9 medium map games and the last 7 large map games. This indicates that LGDA is fine-tuning its goal selection behavior asymptotically.

결과는 LGDA 대 보복에 대한 가설을 검증하지만 LGDA 대 RGDA에 대해서는 가설을 검증하지 않습니다. 전자의 경우, 중간 맵 결과에서 유틸리티 값의 차이에 대한 기본 분포의 평균은 14.3 – 10.1이었고 큰 맵에서 이것은 95 % 신뢰 수준에서 183.8 – 49.9였습니다. 따라서 이는 LGDA가이지도에서 RL 전용 절제를 능가한다는 가설을 뒷받침합니다. 그러나 결과 대 RGDA는 각각 17.2 – 19.1 및 88.1 – 110.1입니다. LGDA는 높은 신뢰도로 RGDA에 비해 효용 가치가 긍정적 인 것은 아닙니다. 그 이유는 주어진 정책이 유능하므로 목표를 임의로 선택하면 항상 유능한 정책을 선택하기 때문입니다. 우리는 훈련 반복 횟수가 증가함에 따라 LGDA의 성과가 RGDA에 비해 향상되는 것을 관찰했다. LGDA는 지난 9 개의 중간 맵 게임과 마지막 7 개의 큰 맵 게임에서 승리했습니다. 이는 LGDA가 목표 선택 행동을 점진적으로 미세 조정하고 있음을 나타냅니다.

6 Related Work

The LGDA algorithm used in this paper is identical to the one described in (Jaidee et al., 2011). However, in this paper we instead apply LGDA to combat tasks in realtime strategy games, which is a more complex task than we previously investigated. Weber et al. (2010) also use GDA for real-time strategy games, but their algorithm does not learn 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 they use 1-nearest neighbor to compare the current state with recorded cases to perform goal selection. LGDA instead learns expectations, discrepancies, and goals to achieve. Furthermore, goals can be state abstractions (e.g., win the game) and LGDA could map a discrepancy to multiple goals. 

Other approaches investigating reasoning techniques for RTS games include reinforcement learning methods (Balla & Fern, 2009) and case-based reasoning (Szczepanski & Aamodt, 2009). LGDA combines both of these methods.

본 논문에 사용 된 LGDA 알고리즘은 (Jaidee et al., 2011)에서 설명한 것과 동일하다. 그러나 이 백서에서는 실시간 전략 게임의 작업을 처리하기 위해 LGDA를 적용합니다. 이는 이전에 조사한 것보다 더 복잡한 작업입니다. Weber et al. (2010)은 실시간 전략 게임에도 GDA를 사용하지만 알고리즘은 기대치를 배우지 않습니다. 그들의 사례는 (현재 상태와 에이전트가 달성하려는 목표 사이의) 불일치를 새로운 목표 (상태로 표시됨)에 매핑하고 1- 인접 이웃을 사용하여 현재 상태를 기록 된 사례와 비교하여 목표 선택을 수행합니다. LGDA는 대신 기대, 불일치 및 달성 목표를 학습합니다. 또한 목표는 상태 추상화 (예 : 게임 승리) 일 수 있으며 LGDA는 불일치를 여러 목표에 매핑 할 수 있습니다.

RTS 게임에 대한 추론 기법을 조사하는 다른 접근법으로는 강화 학습 방법 (Balla & Fern, 2009)과 사례 기반 추론 (Szczepanski & Aamodt, 2009)이 있습니다. LGDA는이 두 가지 방법을 결합합니다.

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 & Luck, 2007), first-person shooters (Muñoz-Avila et al., 2010), and Navy training simulators (Molineaux et al., 2010). We are instead focusing on combat tasks for RTS games. 

In contrast to the original model of goal-driven autonomy (Molineaux et al., 2010), LGDA does not perform discrepancy explanation, and we have ignored the topic of goal management. We leave these topics for future research.

GDA is also related to systems that interleave planning and execution (AmbrosIngerson & Steel, 1988). Those systems detect discrepancies when the state reached after executing the next action doesn’t match the action’s state. In contrast, LGDA doesn’t have knowledge about the action’s expectations. Also, those systems replan by pursuing the same goals. In GDA, the goals themselves change as a result of resolving observed discrepancies.

인지 아키텍처의 목표 관리에 대한 연구 (Choi, 2010), 목표 생성 (Hanheide et al., 2010) 및 메타 추론 (Cox, 2007)을 포함하여 목표 추론에 최근 몇 가지 기여가 있었습니다. 시뮬레이션 로봇 (Meneguzzi & Luck, 2007), 1 인칭 슈터 (Muñoz-Avila et al., 2010) 및 해군 훈련 시뮬레이터 (Molineaux et al., 2010)가 애플리케이션에 포함되었습니다. 우리는 대신 RTS 게임의 전투 작업에 집중하고 있습니다.

목표 주도형 자율성 (Molineaux et al., 2010)의 원래 모델과 달리 LGDA는 불일치 설명을 수행하지 않으며 목표 관리 주제를 무시했습니다. 우리는 미래의 연구를 위해 이러한 주제를 남깁니다.

GDA는 계획 및 실행을 인터리브 하는 시스템과도 관련이 있습니다 (AmbrosIngerson & Steel, 1988). 이러한 시스템은 다음 작업을 실행 한 후 상태에 도달하면 작업 상태와 일치하지 않을 때 불일치를 감지합니다. 반면, LGDA는 조치의 기대치에 대한 지식이 없습니다. 또한 이러한 시스템은 동일한 목표를 추구하여 재 계획합니다. GDA에서 목표 자체는 관찰 된 불일치를 해결 한 결과 변경됩니다.

7 Conclusions and Future Work

Our study demonstrates the use of case-based techniques to learn knowledge that permits LGDA agents to perform effectively on combat tasks for real-time strategy games. Our algorithm, LGDA, integrates a case-based reasoning method with a reinforcement learning algorithm. Our empirical study demonstrates significant performance gains for LGDA compared to its RL-only ablation, and encouraging but not significant gains versus its CBR-only ablation, on two Wargus scenarios.

In our future work we want to explore more robust representations for the discrepancies. Currently they are simple binary vectors indicating whether the current and expected states match on each feature. Potential extensions could include a degree of dissimilarity. Also, in our current framework the set of goals is fixed. We plan to explore learning new goals when the opportunity arises.

우리의 연구는 LGDA 요원이 실시간 전략 게임을 위한 전투 작업에서 효과적으로 수행 할 수 있는 지식을 배우기 위해 사례 기반 기술을 사용하는 것을 보여줍니다. LGDA 알고리즘은 사례 기반 추론 방법과 강화 학습 알고리즘을 통합합니다. 우리의 경험적 연구는 두 개의 Wargus 시나리오에서 LGDA의 RL 전용 절제와 비교했을 때 LGDA의 성능이 크게 향상되었으며 CBR 단독 절제에 비해 크게 향상되지는 않았음을 보여줍니다.

향후 작업에서 불일치에 대한보다 강력한 표현을 탐색하고자 합니다. 현재 이들은 현재 및 예상 상태가 각 기능에서 일치하는지 여부를 나타내는 간단한 이진 벡터입니다. 잠재적 인 확장에는 어느 정도의 비 유사성이 포함될 수 있습니다. 또한 현재 프레임 워크에서 목표는 고정되어 있습니다. 우리는 기회가 생길 때 새로운 목표를 배우는 것을 탐구 할 계획입니다.