기술 요약: DISPATCH - 협력적 이종 에이전트를 위한 분산형 정보 기반 공간 계획 및 작업 할당

문제 정의

본 논문은 다중 로봇 배송, 수색 및 구조, 환경 모니터링과 같은 도메인 내의 이종 다중 에이전트 시스템에서 발생하는 공간적 작업 할당 문제를 다룹니다. 핵심 문제는 $N$개의 이종 에이전트가 부분 관측 가능성(partial observability) 하에서 공간적으로 분산된 $m$개의 작업을 수행하도록 조정하는 것입니다.

주요 제약 조건 및 특성은 다음과 같습니다:

• 이종성(Heterogeneity): 에이전트는 서로 다른 서비스 능력(기술 수준)을 보유하며, 작업은 다양한 작업량, 중요도 가중치 및 긴급성을 가집니다. 호환성은 선호도 벡터를 통해 모델링됩니다.
• 공간 비용(Spatial Costs): 에이전트는 장애물이 있는 복잡한 2D 환경을 항해해야 하며, 이 과정에서 이동 비용과 시간 지연이 발생합니다.
• 공정성 vs 효율성 트레이드오프(Fairness vs. Efficiency Trade-off): 탐욕적(Greedy)이거나 순수하게 효율성만을 추구하는 정책(예: 총 이동 거리 최소화)은 불평등한 서비스를 초래할 수 있습니다. 즉, 일부 작업은 신속하고 고품질의 서비스를 받는 반면, 다른 작업은 긴 지연 시간이나 부적절한 매칭에 직면하게 됩니다.
• 부분 관측 가능성(Partial Observability): 에이전트는 전역 상태 정보에 접근할 수 없으며, 오직 로컬 센싱 반경 내의 엔티티만을 인지할 수 있습니다.

기존 방식들은 대개 전역 정보를 갖춘 중앙 집중식 조정에 의존하거나, 엄격한 평형 기반의 공정성 기준 없이 보상 형성(reward shaping)에 의존합니다. 본 논문은 아이젠버그-게일(Eisenberg–Gale, EG) 평형 이론(파레토 효율성과 엔비-프리(envy-freeness)를 보장함)과 분산형, 부분 관측 가능 다중 에이전트 학습 사이의 간극을 메우고자 합니다.

방법론

저자들은 공정성과 효율성을 통합하는 두 가지 상호 보완적인 알고리즘을 제안합니다.

1. EG-MARL (중앙 집중식 훈련, 분산 실행)

이 프레임워크는 CTDE (Centralized Training with Decentralized Execution) 구조를 활용합니다.

• 훈련 단계 (Training Phase): 중앙 집중식 비평가(critic)는 전역 상태에 접근하며, 공간적으로 수정된 **아이젠버그-게일(EG) 볼록 프로그램(convex program)**을 해결합니다. 이 프로그램은 로그 효용(logarithmic utility)의 가중 합을 최대화하며, 여기서 효용은 에이전트-작업 선호도와 거리 감쇄 계수를 결합하여 $u_{ji} = (\alpha d_{ij}) \cdot \text{preference}_{ji}$로 정의됩니다. 이 프로그램의 해는 "교사(teacher)" 또는 감독 신호 역할을 합니다.
• 실행 단계 (Execution Phase): 에이전트는 오직 로컬 관측값만을 사용하여 독립적으로 작동합니다. 에이전트는 **그래프 신경망(GNN)**을 사용하여 로컬 에이전트-엔티티 그래프(이웃, 작업 및 장애물을 나타냄)를 처리하고 분산 정책을 학습합니다.
• 보상 형성 (Reward Shaping): 학습 과정은 탐사 보너스, 작업 진행도, 완료 보너스, 그리고 EG 할당 목표로부터 유도된 특정 **공정성 형성 항(fairness shaping term)**이 포함된 복합 보상에 의해 유도됩니다.

2. 확률적 온라인 할당 (Stochastic Online Assignment)

이는 중앙 집중식 통신이 제공되는 환경을 위한 협력적 탐사 및 할당 메커니즘입니다(강력한 온라인 베이스라인 역할을 함).

• 메커니즘: 에이전트들은 그리드 기반 샘플링 전략을 사용하여 환경을 협력적으로 탐사합니다. 새로운 작업이 임계값 $k$만큼 발견되면, 알고리즘은 **부분 집합 기반 할당(subset-based assignment)**을 수행합니다.
• 프로세스: 현재 자유 상태인 에이전트들의 부분 집합을 열거하고, 각 부분 집합에 대해 발견된 작업들과의 EG 최적화 문제를 해결한 뒤, 평형 목적 함수를 최대화하는 부분 집합을 선택합니다. 할당된 에이전트는 즉시 목표를 수행하며, 나머지 에이전트는 탐사를 계속합니다.
• 목적: 조합론적 열거($O\binom{N}{k}$)로 인해 계산 비용이 많이 들지만, 이는 분산 정책이 온라인의 중앙 집중식 EG 솔루션에 얼마나 근접할 수 있는지 보여주는 벤치마크를 제공합니다.

주요 기여

1. 공간 인지형 아이젠버그-게일 프레임워크: 저자들은 클래식한 EG 프레임워크에 공간적 이동 비용을 효용 공식에 통합함으로써, 이를 체화된(embodied) 다중 에이전트 작업 할당과 효과적으로 연결했습니다.
2. EG-MARL 알고리즘: 그래프 기반 정책과 공간 인지형 EG 할당을 통합한 새로운 CTDE 프레임워크입니다. 이를 통해 에이전트는 부분 관측 가능성 하에서 EG 평형의 유도를 받아 공정성과 이동 효율성을 공동으로 최적화하는 분산 정책을 학습할 수 있습니다.
3. 확률적 온라인 할당: 작업이 발견됨에 따라 실시간으로 가이드된 탐사와 부분 집합 기반의 공정한 할당을 수행하는 협력적 메커니즘을 통해, 온라인 공정성-효율성 트레이드오프에 대한 중앙 집중식 베이스라인을 구축합니다.
4. 실증적 검증: 제안된 방식은 다양한 팀 규모(3~15명 에이전트)에서의 다중 에이전트 파티클 환경(MPE) 시뮬레이션과, 이종 로봇(예: Summit-XL, TurtleBot3, Pioneer)을 사용한 Webots 기반 창고 프로토타입을 통해 검증되었습니다.

실험 결과

평가는 EG-MARL 및 Stochastic Online 방법을 중앙 집중식 EG, 헝가리안 알고리즘(공리주의적 최적해), 그리고 Min-Max Distance(형평성 중심)와 같은 중앙 집중식 베이스라인과 비교합니다.

• 후회(Regret): EG-MARL은 (특히 소규모 팀에서) 낮은 후회 값을 달-성합니다(분산형과 중앙 집중식 EG 목표 사이의 격차). 팀 규모가 커짐에 따라 후회 값이 증가하지만 여전히 경쟁력 있는 수준을 유지합니다.
• 공정성(Fairness): EG-MARL과 Online 방식 모두 변동 계수(Coefficient of Variation) 및 Jain's Fairness Index 측면에서 헝가리안 및 Min-Max 베이스라인보다 일관되게 우수한 성능을 보였습니다. EG 기반 방식은 더 균형 잡힌 작업 결과를 달성하며, 공정성-효율성 트레이드오프 곡선의 "좌상단" 영역(높은 공정성, 낮은 완료 시간)에 밀집되어 있습니다.
• 효율성(Efficiency): EG-MARL은 대부분의 구성(N=7, 10)에서 가장 빠른 완료 시간을 달성했으며, 때로는 총 이동 거리가 약간 늘어남에도 불구하고 중앙 집중식 EG 솔루션보다 빠른 속도를 보이기도 했습니다.
• 절제 연구(Ablation Studies): EG 공정성 형성 보상이나 탐사 보상을 제거하면 공정성이 저하되고 완료 시간이 증가하여, 평형 유도형 보상 구조의 필요성을 확인시켜 주었습니다.
• Webots 검증: 이종 로봇이 존재하는 실제적인 창고 시나리오에서, 중앙 집중식 EG 할당이 가장 강력한 전반적 균형을 보여주며 헝가리안 및 Min-Max 방식에 비해 높은 공정성 점수를 유지하면서도 경쟁력 있는 완료 시간을 달성했습니다.

의의 및 주장

본 논문은 공간 인지형 EG 공식이 이종 능력을 가진 에이전트들의 분산 협력을 효과적으로 가이드할 수 있음을 주장합니다.

• 이론적 연결: 본 연구는 EG 평형 볼록 프로그램과 분산형, 부분 관측 가능 다중 에이전트 학습 사이의 연결 고리를 구축하며, 평형 개념이 효과적인 감독 신호로 기능할 수 있음을 입증했습니다.
• 실무적 균형: 결과는 분산형 에이전트가 전역 상태 정보에 의존하지 않고도 파레토 효율적이고 공정성을 고려한 결과를 근사할 수 있음을 시사합니다.
• 한계점: 저자들은 Stochastic Online Assignment가 조합론적 열거로 인해 대규모 팀에서는 계산 집약적이며, 이는 주로 베이스라인 용도이지 확장 가능한 배포 솔루션이 아님을 명시했습니다. 또한 EG-MARL 프레임워크가 이론적인 근사 알고리즘이라기보다는 경험적으로 유도된 학습 방식임을 인정했습니다.

결론적으로, 순수 효율성은 종종 불평등을 야기할 수 있지만, 분산 학습에 평형 기반의 공정성을 통합함으로써 다중 에이전트 시스템은 역동적이고 공간적인 환경에서 서비스 품질과 운영 효율성 사이의 견고한 균형을 달성할 수 있습니다.