📌 Multiagent Systems: A Survey from a Machine Learning Perspective
📝 저자 : Peter Stone, Manuela Veloso
📅 발행 연도 : To Appear in Autonomous Robotics volume 8, number 3. July, 2000
🔗 논문 링크 : https://www.cs.cmu.edu/~mmv/papers/MASsurvey.pdf
🍀 멀티에이전트 개념에 대해서 처음 공부하는 입장이기에 멀티에이전트 문제를 머신러닝 관점에서 정리한 고전적 개론인 해당 논문을 선택하였고, 이 논문을 통해 멀티에이전트 문제의 유형과 대표적인 접근법 등을 학습해보려고 한다.
Abstract
이 논문은 다중 에이전트 시스템(Multiagent Systems, MAS) 을 머신러닝(Machine Learning, ML) 관점에서 종합적으로 정리한 Survey이다.
MAS는 분산 인공지능(Distributed Artificial Intelligence, DAI)의 한 갈래로, 여러 독립적인 에이전트들이 협력·경쟁하며 복잡한 문제를 해결하는 방식을 연구한다.
저자들은 기존 연구를 두 가지 축(에이전트 간 이질성 vs 통신 가능성) 으로 분류하여 체계화하고, 각 경우에서 발생하는 이슈·기법·학습 기회를 구체적으로 설명한다.
또한, MAS 연구의 실험장으로 Predator/Prey 도메인(술래잡기)과 로봇 축구(Robotic Soccer) 를 강조하며, 후자는 현실적이고 복합적인 테스트베드로 제시된다.
1. Introduction
Distributed Artificial Intelligence(DAI) 는 1970년대부터 연구된 분야로, 여러 지능적 개체들이 협력하여 문제를 해결하는 방법을 탐구한다.
DAI는 크게 두 갈래로 나뉜다.
1. Distributed Problem Solving(DPS): 정보를 나누고 부분문제를 해결하는 정보 중심 관점
2. Multiagent Systems(MAS): 독립적 에이전트들의 행동과 상호작용에 초점
MAS는 단일 에이전트 시스템과 달리 다른 에이전트가 단순한 환경 요소가 아니라, 스스로 목표와 행동을 가진 주체라는 점에서 차별화된다.
이 논문은 다음을 목표로 한다.
- MAS를 이해하기 위한 분류 체계 제시
- 각 시나리오에서 다루어야 할 이슈와 기법 정리
- 머신러닝이 기여할 수 있는 기회 분석
- MAS 연구용 도메인과 테스트베드 소개
2. Multiagent Systems
2.1 Taxonomy
MAS 연구를 정리하기 위해 저자들은 여러 기존 분류체계를 검토한다.
- Decker(1987): 에이전트의 세분성, 지식의 이질성, 분산 제어 방식, 통신 방식 등을 기준으로 분류
- Parunak(1996): 시스템 기능, 아키텍처, 인간 개입 여부 등을 기준으로 분류
논문에서는 이보다 단순하고 직관적인 두 가지 기준을 제안한다.
- Heterogeneity(이질성): 에이전트들이 동일한 구조·능력·목표를 가지는가?
- Homogeneous(동질) vs Heterogeneous(이질)
- Communication(통신): 에이전트들 사이에 메시지 교환이 가능한가?
- Communicating vs Non-Communicating
이 두 축을 조합하면 MAS는 네 가지 범주로 나눌 수 있다.
- Homogeneous, Non-Communicating
- Heterogeneous, Non-Communicating
- Homogeneous, Communicating
- Heterogeneous, Communicating
➡️ 각 범주는 서로 다른 학습 과제와 연구 이슈를 만들어내며, 논문은 이후 장에서 이를 체계적으로 다룬다.
2.2 Single-Agent vs Multiagent Systems
2.2.1 Single-Agent Systems
단일 에이전트 시스템은 환경에 대한 전역적 관점(omniscient view)을 가지고 문제를 해결한다.
- 장점
- 단순성
- 중앙집중적 제어가 가능
- 단점
- 확장성 부족
- 실패에 취약 (single point of failure)
- 현실 문제 반영의 어려움
2.2.2 Multiagent Systems
MAS에서는 여러 독립적인 에이전트가 존재하며, 각자 자신의 목표(goal), 행동(action), 지식(knowledge)을 가지고 있다. 즉, 다른 에이전트를 단순히 환경 요소로 보지 않고, 능동적 주체로 모델링해야 한다.
- 장점
- 병렬성: 여러 에이전트가 동시에 작업
- 강건성: 하나가 실패해도 전체 시스템은 유지 가능
- 확장성: 에이전트 추가 가능
- 지리적 분산: 멀리 떨어진 장소에서 동시에 작동 가능
- 비용 효율성: 고성능 단일 시스템보다 다수의 단순 시스템 조합이 더 나을 수 있음
3. Organization of Existing Work
3.1 The Predator/Prey (“Pursuit”) Domain
해당 도메인은 MAS 연구의 대표적인 토이 도메인이다. 여러 포식자(predators)가 한 피식자(prey)를 잡으려 한다.
- 변수 요소들
- 보드 형태 (격자, 토로이드 등)
- 이동 규칙 (직선/대각선, 동시/순차 이동)
- 관측 범위 (전역 시야 vs 부분 시야)
- 포식자 간 통신 여부
- 피식자의 행동 (무작위, 단순 전략, 지능적 전략)
- 의의
- 단순하지만 MAS 연구에서 발생하는 다양한 이슈(협력, 경쟁, 부분 관측, 학습)를 실험할 수 있음
- 동일한 문제를 여러 연구자가 반복적으로 실험할 수 있어 비교에 유용
3.2 Domain Issues
MAS 연구 도메인을 설계할 때 고려해야 할 일반적 문제들은 다음과 같다.
- 에이전트 수: 많아질수록 복잡성 증가
- 실시간성: 시간 제약이 존재하면 즉각적 반응 필요
- 동적 목표: 목표가 환경 변화에 따라 새로 생기거나 사라질 수 있음
- 통신 비용: 메시지 전송에 자원이 소모될 수 있음
- 실패 비용: 에이전트 실패가 전체 성능에 미치는 영향
- 인간 개입: 사람이 설계·개입하는 정도
- 불확실성
- 환경 자체의 랜덤성
- 다른 에이전트의 예측 불가능한 행동
- 내 행동 결과의 불확실성
➡️ 이러한 요소들은 MAS 설계와 학습 알고리즘의 성능을 크게 좌우한다.
4. Homogeneous Non-Communicating Multiagent Systems
4.1 Homogeneous Non-Communicating Multiagent Pursuit
이는 모든 포식자(predator)가 동일한 구조와 목표를 가지고, 통신 없이 개별적으로 피식자(prey)를 추적하는 것을 의미한다.
-
특징
- 각 포식자는 자신의 센서 정보만 이용
- 협력은 암묵적으로 환경을 통해 이루어짐 (ex. 서로 위치를 보며 자동으로 포위)
-
연구 예시
- Q-learning을 이용해 각 포식자가 독립적으로 학습 (Mataric, 1997)
- 단순 규칙 기반 행동 (ex. “가장 가까운 방향으로 이동”)
4.2 General Homogeneous MAS
- Pursuit 도메인 외에도, 동질적인 에이전트들이 같은 규칙으로 움직이는 상황 연구
- ex) 다수 로봇이 같은 장애물 회피 알고리즘을 사용해 군집 이동
4.3 Issues and Techniques
4.3.1 Reactive vs Deliberative agents
- Reactive agents
- 환경 자극에 즉각 반응
- 장점은 빠름, 단점은 유연성 부족
- Deliberative agents
- 계획과 모델을 이용해 숙고한 후 행동
- 장점은 정교함, 단점은 계산 비용 큼
→ 실제 시스템은 보통 두 방식을 혼합
4.3.2 Local or global perspective
- 에이전트가 자신의 지역적(local) 정보만 보는가, 아니면 팀 전체 전역적(global) 전략을 반영하는가?
- 전역적 관점이 가능하다면 효율적인 협력이 가능하지만, 통신이 없을 때는 로컬 정보에 의존
4.3.3 Modeling of other agents’ states
- 다른 에이전트가 어디에 있는지, 무엇을 보고 있는지를 추정
- ex) Recursive Modeling Method (RMM) → 다른 에이전트가 나를 어떻게 모델링하는지까지 재귀적으로 생각
→ 실용적 한계 때문에 “제한된 깊이”로만 고려
4.3.4 How to affect others
- 내 행동이 다른 에이전트의 행동 기회를 만들어 줄 수 있음
- ex) 한 포식자가 일부러 피식자를 몰아가 다른 포식자가 잡게 함
→ 이는 enable-others’ actions 문제라고 불림
4.4 Further Learning Opportunities
- 다른 에이전트의 상태 추정 학습: 센서 정보만으로 상대의 위치·상태를 예측
- 협력적 행동 학습: 내 보상이 아니라 팀 전체 보상을 높이는 행동 학습
- Delayed reward 문제: 내 행동이 당장은 보상이 없지만, 나중에 팀에 이득이 될 수 있음 → 학습 알고리즘이 이를 처리해야 함
5. Heterogeneous Non-Communicating Multiagent Systems
5.1 Heterogeneous Non-Communicating Multiagent Pursuit
이는 포식자와 피식자가 서로 다른 목표를 가지며, 통신은 불가능한 것을 의미한다.
-
특징
- 피식자가 무작위로 움직일 수도 있고, 지능적으로 도망칠 수도 있음
- 학습은 본질적으로 경쟁(co-evolution) 문제
-
연구 예시
- Haynes & Sen (1996): 포식자와 피식자가 동시에 학습 → 진화적 군비 경쟁(arms race) 현상
- 팀 단위 진화: 4마리 포식자를 하나의 팀으로 보고 유전 알고리즘으로 전략을 진화
5.2 General Heterogeneous MAS
- 현실에서 가장 흔한 유형: 각 에이전트가 서로 다른 능력·목표를 가짐
- 통신이 불가능하므로, 협력은 환경을 통한 간접적 조정(indirect coordination)에 의존
- ex) 자율 주행 차량들이 같은 도로를 공유하나, 서로 대화를 하지 않고도 신호등·규칙을 통해 조정
5.3 Issues and Techniques
5.3.1 Benevolence vs competitiveness
- 다른 에이전트가 나와 협력적(benevolent)인가, 경쟁적(competitive)인가?
- 협력적이면 이득 공유 가능, 경쟁적이면 상대 전략을 학습해야 함
5.3.2 Stable vs evolving agents
- 상대가 항상 같은 전략(stable)을 쓰는가, 아니면 계속 학습·진화(evolving)하는가?
- 진화적 상황에서는 학습이 끊임없이 변동 → 성능 평가가 어려움
5.3.3 Modeling of others’ goals, actions, and knowledge
- 단순히 상태만이 아니라 상대의 목표를 추론해야 할 때도 있음
- ex) 체스에서 상대가 어떤 전략을 쓰는지 추측
5.3.4 Resource management
- MAS에서 자원은 제한적
- 네트워크 대역폭, 계산 자원, 이동 경로 등 자원 분배가 중요한 연구 주제
- Braess’ paradox: 자원을 늘리면 오히려 전체 효율이 나빠지는 현상
5.3.5 Social conventions
- 통신이 없어도, 반복 상호작용 속에서 규약·관습이 자발적으로 형성됨
- ex) “에펠탑 정오에 만나자” 같은 사회적 합의
5.3.6 Roles
- 에이전트가 자발적으로 역할 분담(role assignment)을 할 수 있음
- ex) 어떤 로봇은 수비, 다른 로봇은 공격
5.4 Further Learning Opportunities
- 상대방 전략을 모델링하는 학습: 협력/경쟁 상황에서 모두 중요
- 사회적 규칙 학습: 반복 상호작용을 통해 emergent convention을 학습
- 역할 분담 학습: 상황에 맞게 리더·팔로워, 공격·수비 같은 역할을 학습적으로 선택
6. Homogeneous Communicating Multiagent Systems
6.1 Homogeneous Communicating Multiagent Pursuit
-
모든 포식자가 같은 구조와 목표를 가지고 있으며, 통신 가능
-
예시 전략
- 포식자들끼리 캡처 위치를 나누어 맡는 협상
- 가장 먼 포식자가 먼저 위치를 선택 → 메시지로 알림 → 나머지가 남은 위치 선택
-
통신을 통해 “누가 어디를 맡을지” 같은 협력이 가능해져, 효율적으로 피식자를 포위할 수 있음
6.2 General Communicating MAS
- 통신이 가능한 동질 에이전트 시스템은 분산 센싱(distributed sensing)과 정보 공유에 강점
- ex) 다수 드론이 넓은 지역을 감시할 때, 각자의 관측 정보를 서로 주고받아 전체 상황 파악
6.3 Issues and Techniques
6.3.1 Distributed Sensing
-
여러 에이전트가 각자 다른 부분을 관측하고, 이를 합쳐 전체 환경을 이해
-
활용 사례
- 여러 카메라가 협력해 도시의 차량을 추적
- 로봇 팀이 센서 데이터를 공유하여 은폐된 목표를 찾아냄
-
문제: 어떤 데이터를 언제 공유해야 효율적인지
6.3.2 Communication Content
-
“무엇을 전달할 것인가?”는 MAS에서 핵심 이슈
-
두 가지 접근
- State communication: 감지된 상태, 위치 등 단순 정보 공유
- Goal/plan communication: 더 높은 수준의 목표나 계획 공유
-
상태 공유는 간단하고 빠르지만, 계획 공유는 더 깊은 협력 가능
6.4 Further Learning Opportunities
- 통신 정책 학습: 언제, 무엇을 통신할지 스스로 학습
- 정보 가치 평가: 공유할 때 이득이 있는 정보만 선택적으로 전달
- 강화학습 기반 통신: 메시지를 행동의 일부로 간주하고 최적 정책 학습
7. Heterogeneous Communicating Multiagent Systems
7.1 Heterogeneous Communicating Multiagent Pursuit
- 포식자들이 서로 다른 능력을 가지고 있고, 통신을 통해 협력 가능
- ex) 한 포식자는 빠르지만 시야가 좁고, 다른 포식자는 느리지만 넓은 시야
→ 통신으로 역할 분담 및 상호보완적 협력이 가능
7.2 General MAS
- 현실에서 가장 흔한 형태: 다양한 목표·능력을 가진 에이전트들이 통신하며 상호작용
- ex) 물류 시스템(트럭, 드론, 창고 로봇이 함께 협력), 다중 조직 협상
7.3 Issues and Techniques
7.3.1 Understanding each other
- 문제: 서로 다른 내부 표현을 가진 에이전트가 메시지를 같은 의미로 이해할 수 있는가?
- 해결책: 공유 경험을 통해 심볼을 grounding(현실 세계와 연결)
7.3.2 Planning communicative acts
- 단순 정보 전달이 아니라, “상대가 원하는 행동을 하도록 설득”하는 발화 행위 필요
- 언어학의 speech-act theory와 연결
7.3.3 Benevolence vs competitiveness
- 이질적 에이전트가 협력적일 수도, 경쟁적일 수도 있음
- 협력 상황에서는 정보 공유, 경쟁 상황에서는 기만적 발화 가능
7.3.4 Negotiation
- 협상은 MAS에서 매우 중요한 문제
- Contract Net Protocol: 작업 할당 시, 매니저 에이전트가 작업을 광고하고, 워커들이 응찰하여 분배
- 경매/시장 기반 방법: 자원 배분을 경제적 메커니즘으로 해결
7.3.5 Resource management
- 서로 다른 목표를 가진 에이전트들이 제한된 자원을 나누어 사용
- 통신을 통해 갈등 조정 및 최적화 가능
7.3.6 Commitment/decommitment
- 에이전트는 협업을 위해 약속(commitment)을 할 수 있음
- 상황 변화에 따라 약속을 취소(decommitment)할 때는 비용/보상 구조가 중요
7.3.7 Collaborative localization
- 서로 다른 위치에 있는 에이전트가 통신하여 자신의 위치를 더 정확히 추정
- ex) 로봇 팀이 GPS가 제한적인 환경에서 서로의 관측을 공유
7.3.8 Changing shape and size
- 집단 에이전트가 상황에 따라 모양·구성을 바꿈
- ex) 드론 편대가 일정한 간격으로 흩어졌다가, 목표를 포위하기 위해 집결
7.4 Further Learning Opportunities
- 대화 전략 학습: 어떤 메시지를 보내면 협상에서 더 유리할지 학습
- 신뢰/진실성 모델링 학습: 다른 에이전트의 메시지가 믿을 만한지 확률적으로 추
- 협상 정책 학습: 경매·협상 상황에서 최적의 입찰·응답 전략 학습
- 역동적 역할 학습: 팀 내에서 능력에 맞는 역할을 자동으로 조정
8. Robotic Soccer
8.1 Overview
로봇 축구(Robotic Soccer)는 MAS 연구를 위한 이상적인 테스트베드로 제시되었다.
- 이유
- 협력과 경쟁이 동시에 존재: 팀워크 vs 상대팀과의 대결
- 실시간성 요구: 즉각적인 의사결정 필요
- 부분 관측: 개별 로봇은 제한된 시야만 가짐
- 불확실성: 상대방 행동, 센서 노이즈, 예측 불가능한 상황
따라서, 로봇 축구는 MAS 연구에서 제기된 거의 모든 문제를 실제적으로 다 다룰 수 있는 환경이다.
8.2 MAS in Robotic Soccer
- 각 로봇은 독립적인 에이전트로, 부분 정보만 가지고 있음
- 통신과 전략을 통해 팀워크를 형성해야 함
- MAS 연구의 여러 측면이 동시에 나타남
- 협력(Cooperation): 같은 팀 로봇들이 패스, 수비, 공격을 협력
- 경쟁(Competition): 상대팀과 승부
- 역할(Role assignment): 공격수, 수비수, 골키퍼 등 동적 역할 분담 필요
- 학습(Learning): 슛 타이밍, 패스 선택, 포지셔닝 전략을 학습할 수 있음
8.3 Foundations
- Soccer Server: 시뮬레이터 환경. 연구자들이 동일한 플랫폼에서 팀을 구현해 비교 실험 가능
- 로봇 하드웨어: 실제 물리적 로봇도 활용, 센서·비전·통신 문제 포함
이 두 환경(시뮬레이션, 실제 로봇)은 상호 보완적으로 MAS 연구에 기여하였다.
초기에는 단순한 규칙 기반 팀이 많았으나, 점차 기계학습(Machine Learning) 방법이 도입되었다.
8.4 The Competition Years
RoboCup 대회가 시작되면서, MAS 연구는 실제 경쟁 환경에서 빠르게 발전하였다.
8.4.1 Robot Hardware
- 다양한 연구팀이 로봇의 센서, 카메라, 통신 모듈을 개선
- 하드웨어는 팀 전략의 제약이자 가능성을 동시에 결정
8.4.2 Soccer Server Accessories
- 시뮬레이터에 다양한 부가 기능이 추가됨
- 시각화 도구
- 데이터 로깅 및 분석 툴
- 학습 알고리즘 테스트를 위한 API
8.4.3 Multiagent Control and Robotic Soccer Strategy
- 로봇 축구 전략에서 MAS와 학습 기법이 본격적으로 도입
- 강화학습(RL): 슛/패스 타이밍, 이동 경로 학습
- 기억 기반 학습(Memory-based learning): 과거 상황을 참고해 의사결정
- 신경망 학습(Neural Networks): 복잡한 센서 입력을 행동으로 매핑
- 계층적 제어(Hierarchical control): 기본 동작(달리기, 슛)부터 팀 전략(공격/수비)까지 여러 레벨을 조합
- RoboCup은 MAS 연구자들에게 공통의 “대회장”이자 실험장이 되었고, 팀 간 경쟁이 MAS 연구 발전 촉진
💭 My Thoughts
이 논문을 처음부터 끝까지 읽고 나니, 멀티에이전트 시스템(MAS)은 단순히 “여러 로봇이 함께 움직인다”라는 차원이 아니라는 걸 알게 되었다.
특히 인상 깊었던 부분은 로봇 축구(RoboCup) 사례였다. 술래잡기 같은 단순한 실험에서 출발해, 실제 축구라는 복잡한 환경으로 확장하면서 MAS의 거의 모든 문제가 자연스럽게 드러나고, MAS 연구가 단순한 학문적 개념을 넘어 실제 적용 가능한 분야임을 느꼈다.
또한, 에이전트들은 사람처럼 협력하기도 하고, 경쟁하기도 하며, 규칙을 만들고, 자원을 나누고, 때로는 속이기도 하기 때문에 MAS는 “작은 사회”처럼 보였다. 이 논문을 통해 MAS가 단순한 인공지능 알고리즘의 모음이 아니라, 인간 사회를 닮은 지능적 집단 행동을 설계하고 학습하는 방법이라는 걸 깨달을 수 있었다.
