시간 제약 조건 하의 분산 임무 할당 및 스케줄링을 위한 근사 메시지 패싱 알고리즘 = Approximate Message Passing Algorithm for Decentralized Task Allocation and Scheduling with Time Constraints

국문 초록 (Abstract)

다중 무인 이동체 시스템의 운용 효율을 극대화하기 위해서는 복잡한 시공간적 제약 하에서 임무를 적절히 배분하고 수행 순서를 결정하는 분산 형 임무 할당 및 스케줄링(Task Assignment and Scheduling, TAS) 기술이 필수적이다. 본 연구에서는 기존의 그래프 모델 기반 근사 메시지 전달 알고리즘 (TAS-AMP)을 확장하여, 시간 창(Time Window)과 임무 기한(Time Horizon) 등 현실적인 시간 제약을 고려하는 TW-TAS-AMP(Time Window-TAS with Approximated Message Passing) 알고리즘을 제안한다. 기존 TAS-AMP는 계산 복잡도를 낮추기 위해 메시지 유도 과정을 근사화하였으나, 이로 인해 에이전트의 용량이 포화 상태일 때 한계 이득을 과대 혹은 과소평가하는 구조적 오차를 내포하고 있었다. 또한, 이를 보정하기 위해 모든 에이전트의 할당정보를 취합하는 정제(Refinement) 과정에 의존함으로써, 국소적 메시지 전달만을 전제로 하는 완전 분산형 시스템을 구현하는 데 한계가 있었다. 이러한 문제를 해결하기 위해 본 연구에서는 다음과 같은 핵심 기법들을 제안한다. 첫째, Repacking 메커니즘을 도입하여 에이전트가 내부적인 교체(Swap) 가능성을 고려한 정확한 한계 이득을 스스로 산출하도록 하였다. 이를 통해 Refinement 과정 없이도 근사 오차를 자율적으로 보정하고 해의 완결성을 확보하였다. 둘째, 강제 할당 오류를 해결하기 위해 수정된 T2A(Task-to-Agent) 메시지 전달 규칙을 적용하여, 실질적인 이득이 없는 임무는 미할당 상태로 유지될 수 있는 유연한 할당 구조를 구현하였다. 셋째, 시간 가변적 목적함수를 Reward Decay와 Score Decay로 세분화하여 설계하였다. Reward Decay는 고가치 임무의 우선 수행을 유도하며, Score Decay는 전체 임무 완료 시간(Makespan)을 단축함으로써 작전 목적에 따른 운용 효율성을 제고하였다. 시뮬레이션 분석 결과, 제안된 TW-TAS-AMP는 희소 네트워크(Sparse Network) 환경에서도 우수한 수렴성과 해 품질을 보였으며, 특히 고밀도 임무 환경에서 Repacking 기법을 통해 국지적 포화로 인한 미할당 문제를 효과적으로 해소함을 확인 하였다. 결과적으로 본 연구에서 제안하는 알고리즘은 복잡한 시간 제약 조건 하에서 분산 시스템의 자율성을 유지하면서도 최적에 근접한 성능을 보장하는 실용적인 해결책임을 입증하였다.

목차 (Table of Contents)

• I. Introduction 1
• 1.1 연구 배경 (background) 1
• 1.2 관련 연구 및 한계 3
• 1.2.1 중앙집중식 접근 3
• 1.2.2 분산형 경매 기반 접근 (Auction Based Approach) 4
• 1.2.3 분산형 Belief Propagation 기반 접근 (BP Based Approach) 5
• 1.3 연구 동기 및 목적 (Motivation and Contribution) 8
• 1.3.1 기존 연구의 한계 8
• 1.3.2 연구 동기 및 목적 9
• II. 배경 지식 및 기존 연구 (Preliminaries) 11
• 2.1 문제 정의 11
• 2.1.1 Integer Programming Formulation 11
• 2.1.2 Probabilistic Graphical Model Formulation: Pairwise MRF 13
• 2.1.3 Distributed MAP Inference via Message Passing 16
• 2.2 TAS-AMP 알고리즘 17
• 2.2.1 Concept of Approximate Message Passing for TAS 17
• 2.2.2 Message Calculation Formulas 19
• 2.2.3 Algorithm Structure 22
• 2.3 TAS-AMP의 한계 24
• 2.3.1 메시지 근사과정에서의 오차 및 Refinement의 의존성 24
• 2.3.2 T2A 메시지 계산 수식의 논리적 오류 25
• 2.3.3 시간 제약(Horizon, Time Window)의 고려 부재 25
• 2.3.4 모든 에이전트 간 직접 통신 가정의 비현실성 26
• III. Proposed Method : TW-TAS-AMP 28
• 3.1 Mathematical Formulation and MAP 28
• 3.1.1 TW-TAS-AMP의 Mathematical formulation 28
• 3.1.2 TW-TAS-AMP의 MAP Formulation in Graphical Model 33
• 3.2 메시지 갱신 규칙 개선 및 Repacking 메커니즘 35
• 3.2.1 Modified Message Passing Rules 35
• 3.2.2 Repacking Mechanism 38
• 3.3 시간 제약 조건 및 시간 의존적 점수 함수 42
• 3.3.1 시간 가변 목적함수 처리(Reward and Score Decay) 42
• 3.3.2 시간 제약 조건 구현 - Horizon and Time Window 43
• 3.4 Sparse 통신 환경에서의 정보 교환 전략 45
• 3.4.1 분산형 데이터 관리 구조 (Distributed Data Management) 46
• 3.4.2 정보 갱신 및 순위 경쟁 규칙 47
• 3.4.3 의사결정 및 충돌 해결 (Conflict Resolution) 48
• IV. Analysis of Results 52
• 4.1 실험 환경 설정 (Experimental Setup) 52
• 4.2 T2A 규칙 수정 효과 분석 54
• 4.2.1 TAS-AMP의 기존 T2A 수식의 한계 : 강제 할당과 음수 이득의 역설 54
• 4.2.2 수정된 T2A 규칙의 적용 및 결과 57
• 4.3 Repacking 효과 분석 58
• 4.3.1 실험 1. 용량 임계점에서의 방어력 및 거동 분석 59
• 4.3.2 실험 2 : 대규모 문제에서의 확장성(Scalability) 분석 64
• 4.3.3 고찰 66
• 4.4 목적 함수 및 시간 제약 분석 67
• 4.4.1 Decay 모델의 결과 분석 68
• 4.4.2 연산 효율성 및 해의 품질 간 Trade Off 분석 71
• 4.4.3 시간 제약 준수 검증 72
• 4.5 Sparse 통신 환경에서의 정보 교환 74
• 4.5.1 갱신 규칙에 따른 수렴성 및 중복 할당 분석 . 74
• 4.5.2 Horizon 제약 길이에 따른 성능 역전 현상 . 76
• V. 결론 79
• 5.1 연구 요약 79
• 5.2 연구 기여 및 시사점 80
• 5.3 한계 80
• 5.4 Future Work 81