[BiCNet] Multi-agent Bidirectionally-Coordinated Nets Emergence of Human-level Coordination in Learning to Play StarCraft Combat Games

University College London, Alibaba Group. 14 Sep 2017

Abstract

: Scalable 하면서도 effective communication protocol를 유지하기 위해 actor critic의 vectorised extension과 함께 multi-agent BiCNet(Bidirectionally Coordinated Network)을 도입한다. QMIX 때와 비슷하게 StarCraft combat game에서 실험을 진행하며 임의의 수의 agent를 사용하여 다양한 유형의 combat을 처리할 수 있음을 보인다. 

 

 

---

Introduction

: 해당 논문에서는 multiple agents 간 collaborative behavior를 학습하기 위해 expore하는 실시간 전략 게임인 StarCraft usecase를 사용하였다. large-scale multi-agent system에서의 학습은 agent 수가 증가하면 parameter space 또한 exponentially 증가하는 scalability 문제와 따라 agents' action이 너무 정교해져서 joint learner는 비효율적이며 게임에서 변화하는 agent의 수를 처리할 수 없다는 문제가 존재한다. 

 

- 우리는 StarCraft combat task를 zero-sum Stochastic Game으로 formulate 한다. agent는 actor-critic framework 학습 중에 BiCNet으로 communicate한다. 추가로, scalability issue를 해결하기 위해 parameter sharing을 도입한다. 

 

 

---

Multi-agent BiCNet StartCraft combat as stochastic game

: Zero-sum stochastic game은 아래의 tuple로 표현된다. 차례로, state space of current game, action space, enemy's action space, deterministic transition function of env, reward function of each agent i이다.  

 

 

- Flexible framework를 유지하기 위해서는, agent와 enemy 모두 동일한 state space S를 공유한다고 간주한다. 그리고 각각의 진영에서 action space는 각각 A, B을 갖는다. discrete action space는 처리가 불가능할 정도로 크기 때문에, attack angle 혹은 distance와 같은 continuous control output을 고려한다. 

 

- Reward function을 정의할 때, 두 개의 consecutive time-step 간의 health level 차이를 기반으로 하는 time-variant global reward를 도입한다. time-step t에서 state s가 주어졌을 때, agent i's reduced health level인 reward는 R^t-1_i(s, a, b) - R^t_i(s, a, b)이다. 적의 global agent는 정반대이므로 두 진영의 reward sum = 0이 된다. 만약 적의 health decrement이 아군의 health decrement를 초과하면 time-step t에서 positive reward를 제공하게 된다.

 

reward function

 

 

- Global reward를 정의했기 때문에 agent's objective는 expected sum of discounted reward를 최대화하는 policy의 학습이고, 반대로 적의 joint policy는 expected sum을 최소화하는 것이다. 따라 아래의 Minimax game을 따르게 된다. 그러나 단순화를 위해 적의 policy는 고정되어 있다고 가정하고 SG는 MDP problem으로 전환시킨다. 

 

SG problem

MDP problem

 

→ 그러나 global reward만을 사용하는 것과 그에 따른 zero-sum game은 team collaboration이 일반적으로 local collaboration와 reward function으로 구성되고 특정 internal structure를 포함한다는 사실을 무시한다는 잠재적 단점이 존재한다.

 

Local, individual reward

: 새로운 modeling을 위해, global reward를 각 agent's local reward로 바꾸고, interacting한 다른 agent에 대한 기여도 평가를 포함하여 reward function을 아래와 같이 확장한다. 각 agent는 top-K-u(i)와 top-K-e(i)를 유지하고 top-K는 해당 agent와 interact 하는 다른 agents 혹은 적들의 list이다. 

 

 

 

Communication w/ bidirectional backpropagation

: BiCNet에서는 agent 간 collaboration을 위해 communication을 허용한다. 아래 그림과 같은 bi-directional RNN based actor-critic network를 각각 포함하고 있으며, policy network에서는 local view를 통한 shared observation으로 각 agent에서의 action을 결정한다. 

 

→ BiCNet에서의 communication이란, agent 간의 local observation의 교환이 아니라 bi-directional RNN에서의 hidden layer 간의 정보 교환을 의미한다. 

 

- Bi-directional RNN structure은 communication channel 뿐만 아니라 local memory saver 역할도 수행할 수 있으므로, 각 agent는 own internal state를 유지하고 collaborator와 정보를 공유할 수 있다. 

 

 

- 학습은 기본적으로 길이가 N인(제어되는 agent 개수) network를 펼친다음 backpropagation을 적용하여, gradient가 individual Q_i function과 policy function 모두에게 전달된다. 

 

- 수학적으로 표현하자면, single agent i와 N agents의 objective는 아래와 같이 정의된다. 

 

single agent objective

N agents objective

 

- BiCNet은 agent dependency가 action에 직접적으로 허용되지 않고, 잠재적으로 layer에 포함되기 때문에 greedy MDP approach와 현저하게 다르다. 따라서 gradient가 전체 network 상에서 효율적으로 전파되어 agent 간 완전한 dependency를 허용한다.

 

→ CommNet과 달리 communication은 완전히 대칭적이지 않으며 RNN에 합류하는 agent의 순서를 고정하여 특정 social convention와 role를 유지한다. 이는 여러 optimal joint actions 사이의 가능한 모든 연결을 해결하는데 도움이 된다. 

 

- 여러 agent 간에 parameter는 공유되어, parameter 수는 agent 수와 무관하다. parameter sharing은 학습 과정의 속도를 높일 수 있는 model의 간결함을 가져오고, 이는 소규모 agent team에서 훈련된 network에서 더 큰 agent team으로 효과적으로 확장되는 domain 적용까지 가능할 것으로 보인다. 

 

 

---

BiCNet results

: StarCraft combat env에서 다음의 setting으로 실험을 진행하였으며, baseline으로 IND(Independent controller), FC(Fully-connected), CommNet, GMEZO(GreedyMDP)와 비교했다. 

 

1. Easy combats

: {3 Marines vs. 1 Super Zergling, and 3 Wraiths vs. 3 Mutalisks}

 

2. Hard combats

: {5 Marines vs. 5 Marines, 15 Marines vs. 16 Marines, 20 Marines vs. 30 Zerglings, 10 Marines vs. 13 Zerglings, and 15 Wraiths vs. 17 Wraiths}

 

3. Heterogeneous combats

: {2 Dropships and 2 Tanks vs. 1 Ultralisk}

 

- 비교 결과 BiCNet에서 가장 뛰어난 성능을 보였으며, 특히 collaboration이 필요한 agent 수가 10명이 넘어갈수록 BiCNet과 second algorithm의 성능 격차가 벌어지기 시작했다. 

 

 

Difference of Q-value

: 10k steps에 걸친 critic network의 last hidden layer의 Q-value를 수집한 다음 2D로 표현해보면 아래와 같다. 좌상단 그림에서 적이 agent를 공격할 수 없을 때, agent가 원거리에서 적을 공격하는 것을 보여주고 이 때 model은 high Q-value를, 좌하단 그림에서는 적으로 인해 agent가 공격받게 되고 공격을 할 경우에는 low Q-value를 출력한다. 

 

 

→ 학습된 high Q-value는 agent들이 더 좋은 optimal join action를 갖게 한다. 

 

 

Bi-RNN communication layer

: Agent 1는 high observation number를 관찰할 때, agent 2에 high value를 전달한다. agent 2가 agent 3과 communicate할 때, 자신과 이전에 communicate한 agent 1 value에 'additive' value를 출력하는 경향이 보인다. 

 

 

→ 즉, agent 1과 agent 2의 observation의 sum이 높을수록 hidden state value가 증가하고 이 sum은 communication을 통해 agent 3로 전달된다. 

 

 

---

Emerged human-level coordination

: 적절한 교육을 통해 BiCNet은 몇 가지 효과적인 collaboration strategies를 발견했다. 

 

Coordinated moves without collision

: Agents들은 각각 위치를 이동하면서 생긴 collision 수가 감소했으며, 이는 large-scale combats에서 중요하게 작용한다. 

 

 

Hit and Run tactics

: 공격을 받고 있는 경우 agent를 이동시키고, agent가 안전할 때 다시 공격하는 tactic를 학습했다. 

 

 

Coordinated cover attack

: Real-battlefield에서 사용되는 high-level collaborative strategy를 학습했다. 한 agent가 적의 공격을 받거나 주의를 끌도록 하고, 다른 agent가 이 시간 또는 거리 차이를 이용하여 더 많은 피해를 입히는 방식이다. 

 

 

Focus fire without overkill

: 특정 적에게 사격을 집중하기 위해 각 agent를 제어하는 방법을 배우고 다른 agent가 사격을 분산시키고 공격 사격을 낭비하는 overkill를 피하기 위해 옆으로 이동하는 경향을 학습했다. 

 

 

Collaborations between heterogeneous agents

: 다양한 functionalities, action space, strength, weakness를 지닌 여러 agent unit들 간에도 collaboration을 통해 win-win 상황에 도달한다. 같은 종류의 unit에게만 parameter sharing을 제한함으로써 heterogeneous collaboration를 구현 가능하다. 

 

 

 

---

Conclusion

: BiCNet에서는 각 dimension이 agent에 해당하는 vectorised actor-critic framework를 구성하여 task를 학습한다. coordination은 internal layers에서 bi-directional recurrent communication에 의해 수행된다. BiCNet algorithm은 end-to-end 학습을 통해 효과적인 coordination strategies를 성공적으로 학습할 수 있었다. 

 

 

https://hyen4110.tistory.com/29

[딥러닝][NLP] Bidirectional RNN