[AAMAS 2024] Multi-Agent Reinforcement Learning for Real-World Application (1편)

멀티 에이전트 시스템 (Multi-Agent System) 분야의 가장 크고 영향력 있는 국제 학회 중 하나인, AAMAS (International Conference on Autonomous Agents and Multi-Agent Systems)에서는 로보틱스, 게임 이론, 멀티 에이전트 시스템, 강화학습, 소셜 시뮬레이션 및 모델링 등의 주제를 다루고 있습니다.

LG AI연구원 Data Intelligence (DI) 랩은 AAMAS 2024에서 “Naphtha Cracking Center Scheduling Optimization using Multi-Agent Reinforcement Learning”^[1], “Agent-Oriented Centralized Critic for Asynchronous Multi-Agent Reinforcement Learning”^[2], 총 2 편의 논문을 발표하고, 연구자들과 함께 AI 기술의 산업 현장 적용을 위한 다양한 에이전트 모델링 및 강화학습 알고리즘에 대해 논의했습니다. 본 포스팅에서는 이번 AAMAS 2024에서 발표된 MARL을 현실 문제들에 적용한 사례로, (1) 멀티 에이전트 강화학습 (Multi-Agent Reinforcement Learning, MARL)의 다양한 적용 사례 및 관련 연구와 (2) 현실 문제 적용을 위한 효율적인 MARL 방법 연구 2 편을 소개해 드리고자 합니다.

 

Multi-Agent Reinforcement Learning for Real-World Application 시리즈 1편 Data Intelligence Lab 윤든솔 님 (본 글) 2편 Data Intelligence Lab 홍성훈 님 (Link)

 
첫 번째로 소개하는 “Surge Routing: Event-informed Multiagent Reinforcement Learning for Autonomous Rideshare^[1]”은 자율 택시 서비스를 위한 MARL 기반 On-demand Mobility 라우팅 알고리즘에 대한 논문입니다. 두 번째 논문인 “Naphtha Cracking Center Scheduling Optimization using Multi-Agent Reinforcement Learning^[2]”은 LG AI연구원에서 발표한 논문으로 MARL을 활용한 원재료 분해 시설 최적화에 관한 연구입니다.

강화학습(Reinforcement Learning, RL)은 순차적 의사결정 문제(Sequential Decision Problem)에서 에이전트(Agent)가 환경과 상호작용하며 장기적으로 얻는 보상의 합을 최대화하는 최적의 행동 방침(Policy)을 학습하는 과정을 의미합니다. 이 과정은 보통 마르코프 결정 과정(Markov Decision Process, MDP)으로 모델링되며 MDP는 다음과 같은 요소들로 구성됩니다:

1. 상태(State): 에이전트가 현재 처해 있는 환경의 상태를 나타냅니다. 예를 들어, 체스 게임에서 말의 배치가 상태가 될 수 있습니다.

2. 행동(Action): 에이전트가 취할 수 있는 행동을 의미합니다. 상태에 따라 에이전트는 다양한 행동을 선택할 수 있으며, 예를 들어 체스에서는 말 한 개를 이동시키는 것이 행동입니다.

3. 보상(Reward): 에이전트가 특정 행동을 취했을 때 환경으로부터 받는 피드백입니다. 보상은 행동이 얼마나 좋은지 또는 나쁜지를 나타내며, 에이전트는 높은 보상을 얻기 위해 학습합니다. 예를 들어, 체스에서 상대방의 말을 잡으면 보상을 받을 수 있습니다.

4. 전이 확률(Transition Probability): 현재 상태와 행동이 주어졌을 때, 다음 상태로 전이될 확률을 나타냅니다. 이는 미래 상태가 현재 상태와 행동에만 의존한다는 마르코프 특성을 반영합니다.

즉 에이전트는 현재의 상태를 보고 가능한 행동 중 하나를 선택합니다. 그러면 환경으로부터 보상을 받게 되며, 이를 통해 어떤 행동이 더 나은 결과를 가져오는지를 학습하게 됩니다. 에이전트는 이러한 시도를 반복하면서 최적의 행동 방침을 찾아가게 됩니다.

멀티 에이전트 강화학습은 여러 에이전트가 동시에 존재하는 환경에서 각각의 에이전트가 자신의 정책을 학습하는 과정입니다. 여기서 각 에이전트는 독립적으로 상태, 행동, 보상을 정의하며, 다른 에이전트와 상호작용하면서 최적의 전략을 학습합니다. 예를 들어, 축구 게임에서는 각 선수(에이전트)가 공을 차거나 패스하는 행동을 통해 최종 목표인 골을 넣기 위해 협력하거나 경쟁합니다.

1. Surge Routing: Event-informed Multiagent Reinforcement Learning for Autonomous Rideshare

최근 자율 주행 기술의 발전으로 인해 자율 택시 서비스가 주목받고 있습니다. 이러한 서비스의 효율성을 극대화하기 위해, 많은 연구자들이 온디맨드 모빌리티 라우팅(On-demand Mobility Routing) 알고리즘을 개선하고자 노력하고 있습니다. 이번에 소개할 논문은 하버드 대학교의 Daniel Garces와 Stephanie Gil이 작성한 “Surge Routing: Event-informed Multiagent Reinforcement Learning for Autonomous Rideshare”입니다.

그림 1. 온디맨드 모빌리티 라우팅 문제^[1]

온디맨드 모빌리티 라우팅 문제는 택시와 같은 공유 차량을 최적의 위치에 배치하여, 승객의 대기 시간을 최소화하는 것을 목표로 합니다. 기존의 온디맨드 모빌리티 라우팅 알고리즘들은 일반적인 수요 패턴을 기반으로 설계되었기 때문에, 대규모 이벤트(예: 콘서트, 스포츠 경기)로 인한 갑작스러운 수요 변화를 효과적으로 처리하지 못하는 경우가 많습니다. 그림 1과 같이 주황색 점에서 이벤트가 열리고 있을 때, 해당 정보를 고려하지 않으면 왼쪽과 같이 잠재적 고객의 위치를 엉뚱한 곳으로 예측하여 공유 차량들이 콘서트에서 먼 곳에서 돌아다니게 될 수 있습니다. 이와 반대로 오른쪽과 같이 해당 이벤트에 대한 정보가 고려된다면, 효율적으로 차량을 배차하여 승객의 대기 시간을 최소화할 수 있을 것입니다.

구체적으로 저자는 해당 문제에서 에이전트(Agent), 상태(State), 행동(Action), 비용(Cost)를 아래와 같이 정의하였습니다.

1. 에이전트: 차량

2. 상태: 현재 자신의 위치, 픽업들의 요청 위치, 다른 에이전트들의 진행사항

3. 행동: 현재 대기 중일때는 주변 교차로로 이동, 현재 위치 유지, 요청 수락. 요청을 수행 중일때는 현재 위치에서 요청 목적지까지의 최단 경로를 따라 다음 경로로 이동.

4. 비용: 현재 대기중인 요청의 수

따라서 해당 문제의 목표는 각 에이전트(차량)는 현재 위치, 픽업 요청 위치, 다른 에이전트들의 진행 상황을 관찰하여 주변 교차로로 이동, 현재 위치 유지, 요청 수락, 요청 수행 등의 행동을 수행하여, 대기 중인 요청의 수를 최소화하는 것을 목표로 합니다.

저자는 서비스 수요 급증 문제를 해결하기 위하여 이벤트 데이터를 활용한 수요 예측과 멀티 에이전트 강화학습을 결합하는 새로운 프레임워크를 제안하였습니다.

수요 예측 프레임워크:

1. 인터넷에서 수집한 이벤트 데이터를 활용하여 수요 급증을 예측합니다.

2. 이벤트 설명과 리뷰를 통해 이벤트 발생 시점과 장소에서의 수요를 예측하는 모델을 개발하였습니다.

멀티 에이전트 강화학습 프레임워크:

1. 수요 예측 결과를 바탕으로 ‘한 번에 한 에이전트 롤아웃’ (One-agent-at-a-time Rollout) 방식을 활용하여 도시 규모의 환경에서 효과적인 라우팅을 수행합니다.

수요 예측 프레임워크

수요 예측 프레임워크에서는 이벤트 처리 모듈(Event Processing Module), 수요 예측 모듈(Demand Prediction Module), 수요 할당 모듈(Demand Assignment Module)을 활용하여 도시의 각 교차로의 픽업 요청에 대한 수요를 예측합니다.

이벤트 처리 모듈은 인터넷에서 이벤트 정보를 수집하고 처리합니다. 주요 단계는 다음과 같습니다:

1. 이벤트 데이터 수집: 인터넷에서 이벤트의 제목, 설명, 리뷰, 일정 등의 데이터를 수집합니다. PredictHQ API와 Google Maps를 사용하여 이벤트와 관련된 리뷰를 수집합니다.

2. 문장 임베딩(Sentence Embeddings): 수집된 텍스트 데이터를 RoBERTa Large 모델을 사용해 문장 임베딩으로 변환합니다.

3. 스펙트럴 클러스터링(Spectral Clustering): Gaussian RBF 커널을 사용한 스펙트럴 클러스터링으로 유사한 리뷰를 그룹화합니다.

4. 클러스터 평균화(Cluster Averaging): 각 클러스터의 임베딩을 평균화하여 이벤트를 대표하는 벡터를 생성합니다.

수요 예측 모듈은 이벤트 처리 모듈에서 생성된 이벤트 특징 벡터를 사용하여 특정 시간과 장소에서의 택시 수요를 예측합니다.

1. 특징 벡터 결합: 이벤트 특징 벡터와 시간, 날씨 등의 공간적 및 시간적 데이터를 결합하여 입력 벡터를 생성합니다.

2. 신경망 기반 예측: 결합된 입력 벡터를 사용하여 신경망을 통해 각 구역(섹터)에서의 시간별 수요를 예측합니다. 이벤트가 없는 시간, 날씨 등의 공간적 및 시간적 데이터만을 사용하고, 이벤트가 있는 경우 이벤트 정보가 포함된 데이터를 사용합니다.

3. 수요 분포 생성: 예측된 수요를 기반으로 각 구역의 분 단위 수요 분포를 생성합니다.

수요 할당 모듈 은 수요 예측 모듈에서 생성된 수요 분포를 교차로 수준으로 할당합니다. 주요 단계는 다음과 같습니다:

1. 로컬 최대 수용량 데이터(Local Maximum Occupancy Data): 각 교차로 근처 장소(예: 레스토랑, 호텔 등)의 최대 수용량과 점유율 스케줄을 사용하여 교차로별 수요를 추정합니다.

2. 확률적 할당(Probabilistic Assignment): 예측된 수요를 교차로 수준으로 매핑합니다. 이를 통해 각 교차로에서 발생할 수 있는 수요의 확률 분포를 생성합니다.

3. 수요 분포 매핑: 특정 구역의 수요 예측을 각 교차로에 할당하고, 이를 통해 수요 분포를 교차로 수준으로 세밀하게 조정합니다.

 

멀티 에이전트 강화학습 프레임워크

모델 기반 강화학습 라우팅 모듈은 수요 할당 모듈에서 제공된, 도시의 각 교차로의 픽업 요청에 대한 수요 예측을 활용하여 자율 택시의 라우팅을 진행합니다. 일반적인 MARL 알고리즘에서는 모든 에이전트가 동시에 학습이 진행됩니다. 따라서 에이전트의 개수가 늘어나면 최적화에 필요한 탐색공간(Search space)인 상태-행동 공간(State-action Space)이 기하급수적으로 늘어나기에 수백 개의 Agent가 존재할 수 있는 온디맨드 모빌리티 라우팅 같은 문제에서 안정적으로 학습시키기가 어렵습니다.

해당 논문에서는 각 에이전트의 액션을 도출할 때, 신경망 기반의 정책(Policy)을 학습시켜 활용하는 대신 ‘한 번에 한 에이전트 롤아웃’이라 불리는 학습이 필요하지 않는 계획(Planning) 알고리즘을 활용하여 라우팅을 진행합니다. 해당 알고리즘은 모든 에이전트를 동시에 고려하기보다는 각 에이전트를 순차적으로 최적화합니다. 이에 따라 에이전트가 늘어나도 탐색공간은 선형적으로 늘어나게 되기에 계산 비용이 크게 줄어들 수 있습니다. ‘한 번에 한 에이전트 롤아웃’의 작동 방식은 아래와 같습니다.

1. 초기화:

1. 휴리스틱 기반의 기본 정책(Base Policy)으로 각 에이전트의 초기 행동을 초기화합니다.

2. 휴리스틱 기반의 기본 정책은 예를 들어 에이전트가 현재 위치에서 가장 가까운 승객을 선택하여 해당 위치로 이동하게 하는 그리디 정책(Greedy Policy)과 같이 계산이 빠르고 단순한 정책입니다.

2. 순차적 최적화:

1. 한 번에 하나의 에이전트만 최적화를 수행합니다. 예를 들어, 에이전트 A가 최적화를 수행하는 동안, 다른 에이전트 B와 C는 기본 정책을 따릅니다.

2. 에이전트 A는 가능한 행동들을 시뮬레이션해 각 행동의 미래 비용을 평가합니다.

3. 행동 선택:

1. 에이전트 A는 시뮬레이션 결과를 기반으로 미래 비용을 최소화하는 최적의 행동을 선택합니다.

2. 선택된 행동은 에이전트 A의 다음 상태로 반영됩니다.

4. 반복:

1. 다음 에이전트 B가 최적화를 수행합니다. 이때 에이전트 A의 선택된 행동은 고정되고, 에이전트 B는 자신의 행동을 최적화합니다.

2. 이 과정은 모든 에이전트가 순차적으로 최적화를 수행할 때까지 반복됩니다.

5. 행동 업데이트:

1. 모든 에이전트가 한 번씩 최적화를 수행한 후, 모든 에이전트의 행동을 업데이트합니다.

2. 업데이트된 에이전트는 위와 같은 작동 방식을 따라 각자 새로운 행동을 만들고, 환경을 반영해 다음 상태(Next State)를 도출합니다. 전체 프레임워크는 아래의 그림과 같습니다.

 

그림 2. 제안된 전체 프레임워크^[1]

그림 3. 실험 결과 비교^[1]

 

뉴욕시 맨해튼 지역에서 실제 라이드쉐어 데이터를 활용한 실험 결과, 제안된 방법이 대기 시간과 서비스 요청 처리율 측면에서 기존 방법들보다 우수한 성능을 보였습니다. 제안된 방법을 사용하면 서비스 요청당 대기 시간이 25%에서 75%까지 감소하였습니다. 또한 제안된 방법을 통해 1% ~ 4% 더 많은 서비스 요청을 처리할 수 있었습니다.

해당 논문은 멀티 에이전트 강화학습을 활용하여 자율 택시 서비스의 효율성을 극대화할 수 있는 가능성을 보여주었습니다. 특히, 대규모 이벤트로 인한 수요 급증과 같은 현실 세계의 어려운 문제를 강화학습과 수요 예측 기술의 결합을 통해 극복할 수 있음을 보여주었다는 점에서, 향후 강화학습 분야의 현실 적용 가능성을 크게 확장할 수 있는 연구였습니다. LG AI연구원에서도 이러한 수요 예측 및 최적화 기술을 실제 산업에 어떻게 적용할지에 대해 다양한 연구를 진행하고 있습니다. 향후 수요예측과 최적화 알고리즘을 통해 LG 계열사의 내의 물류 시스템 및 제품 생산 공정과 같은 다양한 현실 문제들에 적용될 수 있을 것으로 기대됩니다.

 

2. Naphtha Cracking Center Scheduling Optimization using Multi-Agent Reinforcement Learning

납사 분해 시설 (NCC; Naphtha Cracking Center)은 석유화학 산업에 있어 중요한 원재료 시설로, 원유로부터 얻어지는 납사(Naphtha) 라는 물질을 고온의 분해로에서 분해 및 가공하여 다양한 제품들을 생산하는 시설입니다. 납사는 전세계로부터 선박 등을 통해 NCC가 위치한 부두로 입고되고, 안정적인 재고관리를 위해 여러 개의 저장 탱크들에 나뉘어 저장됩니다. 여러 탱크에 나뉘어 저장된 납사는 적절한 품질을 유지할 수 있도록 한 탱크에 적절히 섞이고, 원하는 품질의 납사를 고온의 분해로를 통해 분해하면 설정에 따라 다양하게 판매가능한 제품들이 생산됩니다.

 

그림 4. 납사 분해 시설 (NCC; Naphtha Cracking Center)

 

납사 분해 시설 최적화

NCC 스케줄링 문제는 일정 기간동안 NCC 내의 다양한 공정들을 어떻게 운영할지를 결정하는 것입니다. 이때, 스케줄링의 목표는 최종 수익과 제약조건 만족이 됩니다. 기존의 관련 연구들은 각 공정을 별도로 최적화하는 내용이 많았고^[4,5,6], 실제 현장에서도 공정별로 전문인력들이 분산되어 운영 방법을 각각 정해왔기 때문에, 통합적으로 수익을 최적화하거나 다양한 제약조건들을 만족시키기에 어려움이 있었습니다. 따라서 본 연구에서는 멀티 에이전트 강화학습에 기반한 하나의 AI 모델로 전체 공정을 포괄적으로 운영하고 더 나아가 최적화하는 방법을 제안했습니다.

 

그림 5. NCC 스케줄링 최적화 개념도^[2]

 

그리고, NCC 운영을 크게 3종류의 에이전트로 구성된 시스템(Multi-agent system); 입고(Receipt), 혼합(Blending), 분해(Furnace)로 모델링했습니다.

 

1. 관측: 납사 및 제품들의 가격, 예정된 납사 입고 정보, 각 저장 탱크들의 납사 재고의 양과 품질(구성 성분), 각 제품별 생산량 등을 각자의 에이전트가 일부만 관측할 수도 있고, 모두를 관측할 수도 있음

2. 입고 에이전트 행동: 부두로 들어온 선박의 납사를 어떤 저장 탱크에 저장할 지를 결정

3. 혼합 에이전트 행동: 여러 저장 탱크들에 저장된 납사들을 어떻게 하나의 혼합 탱크에 섞을지 결정

4. 분해 에이전트 행동: 분해로의 온도, 압력 등의 제어 변수들을 어떻게 설정할지를 각각 결정

5. 보상: 수익(=[총 판매수익] – [에너지 비용] – [납사 원재료 비용])과 제약조건 만족도
   
   

$\mathit{\text{Reward}}\mathit{=}\mathit{\text{Profit}}\mathit{-}\mathit{\sum }_{\mathit{c}\mathit{\in }\mathit{\text{Constraints}}}{w}_{\mathit{c}}\mathit{\cdot }{\mathit{\text{Cost}}}_{\mathit{c}}$

$Profit=Revenue-Energy usage -Naphtha \cos t$

이 에이전트들은 각자의 제약조건을 만족시키며 수익을 최대화하는 공동의 목표를 위해 협력하여 최적의 스케줄링을 수행해야 합니다. 제약조건은 대표적으로 각 저장탱크의 납사 재고량 상하한 만족 및 납사 구성 성분 안정성 유지, 행동 변화 시점 제약, 분해로 제어 변수의 상하한 만족 등으로 구성됩니다.

 

Asynchronous 멀티 에이전트 강화학습

위에서 정의된 NCC 시스템을 MARL로 학습하기 위해서 NCC 스케줄링 환경 시뮬레이터를 개발했습니다. 이 시뮬레이터는 주어진 환경에서 각 에이전트들이 행동을 결정하면, 그에 따라 변화한 환경에서의 각 에이전트들의 관측 (Observation)과 보상을 알려주는 형태입니다.

 

그림 6. NCC 스케줄링 강화학습 환경 시뮬레이터^[2]

 

위에서 설명 드린 시뮬레이터로 에이전트를 학습시킬 수 있는 요건이 대부분 갖춰졌지만, 아직 MARL 알고리즘의 개선이 더 필요합니다. 바로 NCC 스케줄링의 대표적인 제약조건 중 하나인 “행동 변화 시점 제약” 때문입니다. 이는 실제 현장에서는 각 공정에서의 하나의 행동을 수행하기에 걸리는 시간이 다를 뿐만 아니라, 너무 자주 행동을 바꾸는 것은 실제 작업자가 수행하기에 불가능할 수 있기 때문에 특정 조건을 만족할 때만 행동을 변경할 수 있다는 내용입니다. 즉, 일반적인 MARL 환경에서는 모든 에이전트가 동일한 시점에 동일한 지속시간의 행동을 수행하는 것을 가정하는 반면에, 본 연구에서는 각 에이전트가 서로 다른 시점에 서로 다른 지속시간의 행동을 수행하는 Asynchronous MARL 문제를 다루고 있습니다.

 

그림 7. Synchronous vs Asynchronous MARL 비교^[2]

 

이를 위해 대표적인 강화학습 알고리즘인 Actor-Critic 구조에 추가로 비동기성 (Asynchronicity)을 고려하고 새롭게 고안된 학습 데이터 구성 방법(Training Buffer)을 활용하여 에이전트를 학습했니다^[3,7]. 학습은 과거에 실제로 있었던 다양한 시나리오 (초기 재고 및 입고 예정, 가격 정보 등) 위에서 이루어졌습니다. AI 스케줄러는 시나리오가 입력으로 주어지면, 학습된 에이전트들로 Beam search 방식을 통해 향후 약 2주간의 스케줄들을 생성하고, 그 중 Top-K 스케줄들을 최종 결과로 제공합니다.

 

Deployment

앞서 소개해 드린 방법을 통해 LG AI연구원은 MARL 기반 NCC 스케줄링 최적화를 위한 AI 모델을 학습시키고, LG화학과 협업하여 현장 적용을 시도하고 있습니다. 먼저 현업 전문가들의 사용성을 높이기 위해, AI 전문가가 아니더라도 쉽게 사용할 수 있도록 간편한 UI를 적용하고 웹 서비스로 개발하였습니다. 이를 바탕으로, 현장에서는 간편하게 웹 서비스를 통해 AI 스케줄러로 스케줄을 생성할 수 있고, 생성된 스케줄을 수익성 및 안정성 등 다양한 측면에서의 전문가 검토를 거쳐 현장 운영에 반영되도록 노력하고 있습니다. 진행 중인 내부 테스트를 통해 AI 스케줄러는 높은 수익과 제약조건 만족도를 확인했으며, 앞으로도 산업 현장 활용 측면에서 긍정적으로 전망됩니다.

 

그림 8. NCC 스케줄링 서비스 예시

 

Conclusion

지금까지 AAMAS 2024에서 발표한 현실 세계의 문제를 풀기 위해 MARL을 활용한 연구들에 대해 자세히 살펴보았습니다. 최근 강화학습에 대한 관심이 더욱 많아지는 가운데, MARL에 대한 연구도 주목을 받고 있습니다. 특히 납사 스케줄링 최적화 연구는 여러 강화학습 에이전트들의 협력을 통해 실제 산업 현장의 문제를 풀어낸 새로운 사례를 제시한다는 점에서 의의가 있습니다. 더 나아가, 향후 제품 생산 공정 최적화 등 다양한 현실 문제들을 강화학습 기반으로 풀어낼 수 있을 것으로 기대됩니다. 앞으로도 LG AI연구원은 실제 산업에서 새로운 문제를 발굴하고 적용 가능한 AI 기술을 만들어 나가는 것을 통해, 응용 연구 분야의 기술 발전에 앞장서겠습니다.

 

▶Agent-Oriented Centralized Critic for Asynchronous Multi-Agent Reinforcement Learning

▶Naphtha Cracking Center Scheduling Optimization using Multi-Agent Reinforcement Learning

▶24시간 일하는 AI가 석유화학 공장에 도입되면 생기는 일