동적 분산 위성 군집 관측 할당을 위한 대규모 연속 스케줄링 및 실행

Large-Scale Continual Scheduling and Execution for Dynamic Distributed Satellite Constellation Observation Allocation

지구 관측 위성 군집의 규모와 성능이 급격히 증가하고 있습니다. 분산형 온보드 제어를 활용하면 시간에 민감한 새로운 관측 및 대응이 가능해집니다. 그러나 대규모 다중 에이전트 위성 시스템에 자율성을 적용하려면 효율적인 연산과 통신을 갖춘 알고리즘이 필수적입니다. 본 연구는 이러한 과제를 해결하기 위해 대규모 동적 분산 제약 조건 최적화 문제(DDCOP)를 위한 새로운 온라인 알고리즘을 제안합니다. 우리는 스케줄링과 실행의 통합을 모델링하는 DDCOP의 새로운 공식화인 동적 다중 위성 군집 관측 스케줄링 문제(DCOSP)를 제시합니다. 또한 DCOSP의 새로운 최적 조건을 계산하기 위한 전지적(omniscient) 오프라인 알고리즘을 구축하고, 불완전 온라인 분해 기반 DDCOP 접근 방식인 동적 증분 이웃 확률적 탐색(D-NSS) 알고리즘을 제안합니다. 시뮬레이션을 통해 D-NSS가 근사 최적해에 수렴하며, 솔루션 품질, 연산 시간, 메시지 전송량 측면에서 기존 DDCOP 기준 모델보다 성능이 우수함을 입증합니다. 본 연구는 현재까지 가장 큰 규모의 우주 내 분산형 다중 에이전트 AI 실증인 NASA FAME 임무의 기반을 형성합니다.

The size and capabilities of Earth-observing satellite constellations are rapidly increasing. Leveraging distributed onboard control, we can enable novel time-sensitive measurements and responses. However, deploying autonomy to large multiagent satellite systems necessitates algorithms with efficient computation and communication. We tackle this challenge and propose new, online algorithms for large-scale dynamic distributed constraint optimization problems (DDCOP). We present the Dynamic Multi-Satellite Constellation Observation Scheduling Problem (DCOSP), a new formulation of DDCOPs that models integrated scheduling and execution. We construct an omniscient offline algorithm to compute the novel optimality condition of DCOSP and present the Dynamic Incremental Neighborhood Stochastic Search (D-NSS) algorithm, an incomplete online decomposition-based DDCOP approach. We show through simulation that D-NSS converges to near-optimal solutions and outperforms DDCOP baselines in terms of solution quality, computation time, and message volume. Our work forms the foundation of the largest in-space demonstration of distributed multiagent AI to date: the NASA FAME mission.