Optimizing Earth Observation Satellite Schedules under Unknown Operational Constraints: An Active Constraint Acquisition Approach

이 논문은 지구 관측 위성 스케줄링에서 운영 제약 조건이 명시적으로 정의되지 않은 상황을 해결하기 위해, 최적화 과정과 제약 조건 학습을 교차적으로 수행하는 'CCA(Conservative Constraint Acquisition)' 기반의 상호작용적 'Learn&Optimize' 프레임워크를 제안하고, 이를 통해 기존 방법론 대비 적은 질의 횟수와 실행 시간으로 더 높은 품질의 해를 도출함을 입증합니다.

핵심

🌍 1. 상황 설정: "눈먼 사진작가"와 "검은 상자"

상상해 보세요. 지구 주변을 돌며 지구의 아름다운 풍경을 찍으려는 **인공위성 (사진작가)**이 있습니다.

• 목표: 가장 가치 있는 (Priority 가 높은) 장소를 최대한 많이 찍는 것.
• 문제: 위성은 빠르게 움직이기 때문에, 한 장소를 찍고 다음 장소를 찍으려면 카메라를 돌리는 시간이 필요합니다. 또한, 배터리나 열 문제 때문에 한 번에 너무 많은 사진을 찍으면 안 됩니다.

여기서 핵심적인 어려움은?
위성을 만든 엔지니어들은 이 모든 규칙 (카메라 회전 시간, 배터리 소모량 등) 을 정확한 수식으로 알려주지 않았습니다. 대신, 이 규칙들은 위성의 복잡한 엔지니어링 문서나 정교한 시뮬레이션 프로그램 속에 숨겨져 있습니다.

우리는 이 규칙을 직접 볼 수 없습니다. 대신, 우리가 짜낸 일정을 **검은 상자 (Oracle)**에 넣으면, 그 상자가 "OK(가능)" 혹은 **"NO(불가능)"**라고만 알려줍니다. 어떤 규칙을 위반했는지는 말해주지 않습니다.

비유: 마치 눈을 가린 채 요리를 하는 상황입니다.

• 당신은 "이 요리는 맛있다 (OK)" 혹은 "이 요리는 실패했다 (NO)"는 말만 들을 수 있습니다.
• "소금이 너무 많았어"나 "불이 너무 세서 탔어"라는 구체적인 이유는 알려주지 않습니다.
• 그럼에도 불구하고, 당신은 어떻게 하면 가장 맛있는 요리를 만들 수 있을까요?

---

🚀 2. 기존 방식 vs 새로운 방식

❌ 기존 방식 (FAO): "일단 다 배우고, 그다음에 요리하기"

기존 연구자들은 "규칙을 다 찾아낸 뒤, 그 규칙대로 요리를 하자"고 생각했습니다.

1. 학습 단계: 검은 상자에 수백 번 질문을 던져서 모든 규칙을 찾아냅니다. (예: "소금 1g 은 OK?", "소금 2g 은 OK?")
2. 요리 단계: 모든 규칙을 알아낸 후, 가장 맛있는 요리를 만듭니다.

• 단점: 규칙을 다 찾는 데 시간이 너무 오래 걸립니다. 그사이 위성은 이미 지나가버릴 수도 있습니다.

✅ 새로운 방식 (L&O): "배우면서 동시에 요리하기"

이 논문이 제안하는 **CCA (Conservative Constraint Acquisition)**와 Learn&Optimize 방식은 다릅니다.

1. 한 번에 하나씩: "이렇게 요리해 보면 어떨까?"라고 제안합니다.
2. 검은 상자 확인: "NO"가 나오면, "아, 이 정도는 안 되구나"라고 배우고 규칙을 조금 더 단단하게 만듭니다.
3. 즉시 다시 시도: 배운 규칙을 바탕으로 다시 요리를 시도합니다.
4. 성공 시 종료: 만약 "OK"가 나오는 요리를 찾으면, 더 이상 규칙을 다 찾을 필요 없이 그 요리를 바로 제출합니다.

비유:

• 기존 방식: 요리사에게 "소금, 설탕, 기름의 정확한 양을 100 번 테스트해서 레시피를 완성하라"고 시킨 뒤, 그 레시피로 요리를 합니다.
• 새로운 방식: 요리사가 "소금 좀 넣어볼까?"라고 시도하다 "NO"가 나오면 "아, 소금 적게 넣어야겠다"고 바로 수정하고 다시 맛을 봅니다. 맛있는 요리를 찾자마자 바로 끝냅니다.

---

🛠 3. 이 방법의 핵심 전략: "보수적인 학습 (Conservative)"

이 논문에서 가장 재미있는 점은 **"완벽한 규칙 찾기가 필요 없다"**는 것입니다.

• 상황: 검은 상자가 "NO"라고 했을 때, 정확히 어떤 규칙 (예: 회전 시간 3 초) 을 위반했는지 모릅니다.
• 전략: 연구자들은 "아마도 회전 시간이 3 초보다 더 길어야겠지?"라고 조금 더 보수적으로 (안전하게) 규칙을 설정합니다.
  • 실제 규칙이 "회전 3 초"라면, 우리는 "회전 4 초"라고 배울 수 있습니다.
  • 이렇게 하면 완벽하지는 않지만, 위성이 고장 나지 않는 안전한 일정을 짤 수 있습니다.
• 결과: 모든 숨겨진 규칙을 100% 완벽하게 찾아내지 않아도, 최고의 사진을 찍을 수 있는 일정은 찾을 수 있습니다.

비유:
다리를 건너는 상황입니다.

• 정확한 다리 강도는 모릅니다.
• "이 정도 무게는 견딜 수 있겠지?"라고 추측하다가 "NO"가 나오면, "아, 그보다 더 가벼운 사람만 건너야겠다"고 규칙을 강화합니다.
• 결국 다리가 무너지지 않는 안전한 길은 찾지만, 다리가 견딜 수 있는 정확한 최대 무게를 알 필요는 없습니다.

---

📊 4. 실험 결과: 얼마나 효과적일까?

연구팀은 컴퓨터 시뮬레이션으로 이 방법을 테스트했습니다.

• 작은 문제 (10~30 개 목표): 기존 방식보다 약 2 배~5 배 더 빠르면서 더 좋은 결과를 냈습니다.
• 큰 문제 (50 개 목표):
  • 기존 방식 (FAO): 100 번의 질문을 다 던진 후 해결책을 찾음 (약 695 초 소요).
  • 새로운 방식 (L&O): 평균 21 번의 질문으로 해결책을 찾음 (약 130 초 소요).
  • 결과: 질문 횟수는 5 분의 1 로 줄였는데, 해결책의 질은 더 좋아졌습니다. (오차율 20.3% → 17.9%)

---

💡 5. 결론: 왜 이것이 중요한가?

이 연구는 **"완벽한 지식을 기다리지 말고, 불완전한 정보로도 최선의 결정을 내릴 수 있다"**는 것을 증명했습니다.

우주 임무처럼 시간이 제한되고, 규칙이 복잡하며, 실시간으로 변할 수 있는 상황에서는 **"다 배우고 시작하는 것"**보다 **"배우면서 바로 실행하는 것"**이 훨씬 효율적입니다.

한 줄 요약:

"위성의 숨겨진 규칙을 완벽하게 해석할 필요는 없습니다. 틀릴 때마다 조금씩 배우면서, 동시에 최고의 사진을 찍는 일정을 찾아내는 것이 바로 이 기술의 마법입니다."

기술 요약

1. 문제 정의 (Problem Formulation)

• 배경: 지구 관측 위성은 특정 시간 창 (Visibility Window) 내에 지상 표적을 촬영해야 하며, 이때 표적 간 회전 시간 (Separation), 전력 소모 (Power Budget), 열적 한계 등 다양한 운영 제약 조건을 준수해야 합니다.
• 핵심 문제: 기존 스케줄링 알고리즘은 제약 조건 모델이 완전히 주어진다고 가정하지만, 실제로는 제약 조건이 고충실도 시뮬레이터나 엔지니어링 마진 문서에 숨겨져 있어 명시적인 수학적 모델로 추출하기 어렵습니다.
• 제안된 모델 (EOSP-UC):
  • 목표: 가시화 창 (Visibility Window) 과 우선순위가 주어진 $n$개의 촬영 작업 중, 제약 조건을 만족하는 하위 집합을 선택하여 총 우선순위를 최대화합니다.
  • 제약 조건:
    1. 쌍별 분리 (Pairwise Separation): 두 작업 $i, j$를 촬영할 경우, 위성의 회전 및 안정화 시간으로 인해 일정 시간 간격 ($\delta$) 을 두어야 함.
    2. 전체 용량 (Global Capacity): 임의의 시간 창 (Window) 내에 촬영할 수 있는 작업의 최대 개수 제한 (전력/대역폭 한계).
  • 블랙박스 오라클 (Oracle): 제안된 스케줄이 실행 가능한지 (Yes/No) 만 반환하고, 구체적으로 어떤 제약이 위반되었는지는 알려주지 않습니다. 이는 실제 위성 시뮬레이터나 운영 검증 도구의 동작 방식을 반영합니다.

2. 방법론 (Methodology)

저자들은 Learn&Optimize (L&O) 프레임워크에 보수적 제약 획득 (Conservative Constraint Acquisition, CCA) 알고리즘을 통합하여 문제를 해결합니다.

A. Learn&Optimize (L&O) 프레임워크

• 인터랙티브 프로세스: 제약 조건 획득 (Constraint Acquisition) 과 최적화 (Optimization) 를 번갈아 수행합니다.
  1. 현재 학습된 제약 모델 ($L$) 하에서 최적 스케줄을 찾습니다.
  2. 이 스케줄을 오라클에 제출하여 실행 가능 여부를 확인합니다.
  3. Yes: 알고리즘 종료 및 해당 스케줄을 최종 해로 반환.
  4. No: CCA 를 통해 새로운 제약 조건을 학습하고 모델을 정제 (Refine) 한 후 다시 최적화를 수행합니다.
• 장점: 모든 제약 조건을 학습할 때까지 기다리지 않고, 오라클이 수용하는 첫 번째 양질의 해를 찾으면 즉시 종료할 수 있는 Anytime 특성을 가집니다.

B. 보수적 제약 획득 (CCA)

• 도메인 특화 알고리즘: 일반적인 제약 획득 알고리즘 (예: QuAcq) 이 아닌, EO 스케줄링의 분리 (Separation) 및 용량 (Capacity) 구조에 최적화되었습니다.
• 작동 원리:
  • 오라클이 스케줄을 거절하면, 위반된 제약 조건을 식별하기 위해 **부분 질의 (Partial Queries)**를 수행합니다.
  • 분리 제약: 위반된 작업 쌍에 대해 이진 탐색 (Binary Search) 을 통해 가장 강력한 (가장 긴) 분리 시간 $\delta^*$를 찾습니다.
  • 용량 제약: 분리 제약이 명확하지 않을 경우, 위반된 시간 창과 작업 수를 기반으로 용량 제약을 학습합니다.
  • 보수적 접근 (Conservatism): 오라클의 거절 원인을 정확히 구분하지 못할 경우 (예: 분리 위반인지 용량 위반인지 모호할 때), 더 엄격한 (Over-tightened) 제약 조건을 학습하여 안전성을 확보합니다. 이는 최적 해를 놓칠 수 있지만, 실행 불가능한 해를 피하는 데 효과적입니다.

3. 주요 기여 (Key Contributions)

1. EOSP-UC 문제 공식화: 이진 오라클 뒤에 숨겨진 제약 조건 하에서의 EO 스케줄링 문제를 처음 정의했습니다.
2. CCA 알고리즘 개발: EO 스케줄링의 구조적 특성 (순서 의존성, 분리/용량) 을 활용한 도메인 특화 획득 절차를 제안했습니다.
3. Learn&Optimize 통합: 제약 학습과 최적화를 교차 수행하여, 완전한 모델 획득 없이도 실행 가능한 최적 해를 빠르게 찾을 수 있음을 보였습니다.
4. 실험적 검증: 합성 데이터 (작업 수 $n=10 \sim 50$) 를 통해 기존 방법론 대비 성능을 입증했습니다.

4. 실험 결과 (Results)

합성 인스턴스 (작업 수 $n$) 에 대한 실험 결과는 다음과 같습니다.

• 비교 대상:
  • PG (Priority Greedy): 제약 조건을 전혀 모르는 탐욕 알고리즘.
  • FAO (Full Acquire-then-Optimise): 100 회 오라클 호출로 모든 제약 조건을 학습한 후 최적화 (2 단계 방식).
  • L&O (제안 방법): 학습과 최적화를 교차 수행 (1 단계 방식).
• 성능 지표 (Gap): CP-SAT 기준 최적 해 (또는 120 초 내 최선 해) 대비 목표 함수 값의 차이.
• 주요 결과:
  • $n \le 30$일 때: PG 의 평균 Gap(6568%) 을 L&O 는 **17.735.8%**까지 크게 감소시켰습니다.
  • $n=50$일 때:
    • 해의 질: L&O 가 FAO 보다 평균적으로 더 좋은 성능을 보였습니다 (Gap 17.9% vs 20.3%).
    • 쿼리 효율성: L&O 는 평균 21.3 회의 주요 오라클 호출로 종료된 반면, FAO 는 고정된 100 회를 사용했습니다.
    • 실행 시간: L&O 는 FAO 대비 약 5 배 빠른 (695 초 $\to$ 130 초) 실행 시간을 기록했습니다.
  • 부분 학습의 효과: L&O 는 숨겨진 제약 조건의 약 4~10% 만 정확하게 식별해도 최적 해를 찾을 수 있었습니다. 이는 모든 제약 조건을 완벽하게 복원할 필요 없이, 경쟁적인 비실행 가능 해를 배제하는 핵심 제약만 학습하면 됨을 시사합니다.

5. 의의 및 결론 (Significance & Conclusion)

• 실용적 가치: 실제 위성 임무에서 제약 조건 모델이 불완전하거나 시뮬레이터에 의존하는 상황에서, 명시적 모델 구축 없이도 효율적으로 스케줄링을 수행할 수 있는 첫 번째 체계적인 연구입니다.
• 핵심 통찰: "완벽한 제약 조건 복원"이 필수적이지 않으며, **적극적인 학습 (Active Learning)**을 통해 실행 불가능한 해를 빠르게 걸러내고 실행 가능한 고가치 해를 찾는 과정이 더 중요합니다.
• 한계 및 향후 과제:
  • CCA 의 보수적 접근으로 인해 학습된 제약이 실제보다 과도하게 엄격해질 (Over-tightening) 수 있어, 진정한 최적 해를 놓칠 가능성이 있습니다.
  • 현재는 분리 및 용량 제약만 다루었으며, 더 복잡한 제약 조건 집합으로 확장 필요.
  • 노이즈가 있는 오라클이나 제약 조건의 시간에 따른 변화 (Drift) 를 고려하지 않음.

이 연구는 지구 관측 위성 운영의 불확실성을 해결하고, 실시간 또는 제한된 자원 하에서 더 효율적인 의사결정을 지원할 수 있는 새로운 패러다임을 제시합니다.