온라인 학습 및 반복적 가격 책정을 통한 분산 제약 최적화: 대규모 위성 스케줄링 응용

Distributed Constraint Optimization via Online Learning and Iterative Pricing with Application to Large-Scale Satellite Scheduling

분산 제약 최적화 문제(DCOP)는 제한적인 통신 환경에서의 분산 의사 결정에 널리 사용되는 프레임워크를 제공하지만, 많은 실제 사례는 단일 시스템으로 해결하기에는 규모가 너무 큽니다. 우리는 이 문제를 두 가지 상호 보완적인 접근 방식으로 해결합니다. 먼저 DCOP와 잠재적 게임 간의 관계를 재검토하고, 최신 온라인 학습 알고리즘을 이용하여 균형점을 찾는 방식을 DCOP에 적용합니다. 이러한 알고리즘이 기존의 불완전한 DCOP 알고리즘과 경쟁력이 있음을 보여줍니다. 다음으로 대규모 DCOP 문제를 해결하기 위한 분해 프레임워크를 제안하며, 이는 대규모 분산 위성 스케줄링 문제에서 영감을 받았습니다. 우리는 DCOP를 두 가지 상호 작용하는 하위 문제로 분리하는 새로운 프레임워크를 제안합니다: 작업 할당을 위한 고수준 메타-DCOP와 스케줄링을 위한 독립적인 로컬 최적화 문제입니다. 이 두 수준을 연결하기 위해, 우리는 로컬 최적화기의 피드백을 사용하여 메타 수준의 유틸리티를 업데이트하는 새로운 반복적 가격 책정 방법을 개발했습니다. 우리의 온라인 학습 방법과 반복적 가격 책정 프레임워크를 결합하여 실제 분산 위성 스케줄링 문제에서 거의 최적인 성능을 달성했으며, 최고 성능 모델보다 99% 이상의 관측 요청을 처리할 수 있었습니다 (기존 모델은 87%).

Distributed constraint optimization problems (DCOPs) provide a popular framework for distributed decision making under limited communication, but many real-world instances are too large to solve monolithically. We address this challenge from two complementary directions. We revisit the connection between DCOPs and potential games, and adapt modern online learning algorithms for equilibrium finding to DCOPs. We show that these algorithms are competitive with representative incomplete DCOP algorithms. We then turn to decomposition frameworks for large-scale DCOPs, motivated by large-scale decentralized satellite scheduling. We propose a new framework that separates a DCOP into two interacting subproblems: a high-level meta-DCOP for task allocation, and independent local optimization problems for scheduling. To couple the two levels, we develop a novel iterative pricing method that updates the meta-level utilities using feedback from the local optimizers. Combining our online learning methods with our iterative pricing framework, we obtain near-optimal performance on real-world decentralized satellite scheduling problem instances, fulfilling over 99% of observation requests compared with 87% for state-of-the-art baselines.