Interleaving Scheduling and Motion Planning with Incremental Learning of Symbolic Space-Time Motion Abstractions

이 논문은 물류 및 작업장 스케줄링과 같은 공유 작업 공간에서 다중 객체 탐색을 위해 기성 스케줄러와 모션 플래너를 교차시키며 공간적 충돌 및 시간 조정에 대한 기호 피드백을 점진적으로 학습하는 새로운 프레임워크를 제안하고 그 유효성을 검증합니다.

핵심

🚇 비유: 출근길 지하철과 로봇들

상상해 보세요. 로봇들은 출근하는 지하철 승객들입니다.
이들은 모두 **역 (창고)**에서 **회사 (배송지)**로 가야 합니다.

1. 기존의 문제점 (각자 따로 노는 방식):

   • 스케줄러 (시간표 짜는 사람): "A 는 8 시에, B 는 8 시 10 분에 출발해!"라고 시간표만 짭니다. 하지만 A 와 B 가 좁은 터널에서 마주치면 어떻게 될까요? 시간표에는 "부딪히지 마세요"라는 말이 없으니, 실제 운행에서는 두 기차가 서로 막히거나 충돌할 수 있습니다.
   • 모션 플래너 (운전기사): "아, 시간이 안 맞네, 충돌할 것 같아."라고 생각하지만, 이미 시간표가 확정되어 있어서 "시간을 좀 늦춰주세요"라고 말하기가 어렵습니다.

2. 이 논문이 제안한 해결책 (상호작용하는 새로운 방식):
   이 연구는 스케줄러와 **운전기사 (모션 플래너)**가 서로 대화하며 점점 더 좋은 시간표를 만들어가는 방식을 제안합니다.

   • 1 단계: 대략적인 시간표 제안
     스케줄러가 먼저 "A 는 8 시, B 는 8 시 10 분에 출발하자!"라고 대략적인 계획을 세웁니다. (이때는 실제 길이나 장애물은 고려하지 않음)
   • 2 단계: 운전기사의 점검 (검토)
     운전기사가 그 계획을 보고 실제 주행 시뮬레이션을 돌려봅니다.
     • "어? A 가 8 시에 출발하면 좁은 터널에서 B 와 부딪히겠네." (기하학적 충돌)
     • "또, A 가 8 시 10 분에 도착하려면 8 시 5 분에 출발해야 하는데, 시간표에는 8 시로 되어 있네." (시간적 불일치)
   • 3 단계: 피드백과 수정 (학습)
     운전기사는 스케줄러에게 "기하학적 피드백" (저기 문이 닫혀서 못 지나가요) 이나 "시간적 피드백" (A 는 5 분 더 기다려야 해요) 을 줍니다.
   • 4 단계: 새로운 시간표
     스케줄러는 이 피드백을 받아 "아, 문이 닫혀있구나, A 는 문을 열 때까지 기다리자" 혹은 "B 는 5 분 늦게 출발하자"라고 수정된 시간표를 다시 만듭니다.

이 과정을 수십 번 반복하면, 결국 **"충돌도 없고, 시간도 딱 맞는 완벽한 운행 계획"**이 완성됩니다.

---

💡 핵심 아이디어 3 가지

이 논문이 특별하게 만든 것은 다음과 같습니다.

1. 서로 배우는 과정 (점진적 학습)
   처음부터 모든 상황을 다 예측할 수는 없습니다. 대신, "아, 여기서 막히네"라는 실패 경험을 **記号 (심볼)**로 바꿔서 기억해 둡니다. 다음에는 그 실패를 미리 방지하는 규칙을 추가하는 거죠. 마치 요리사가 "소금 좀 더 넣어야 맛있네"라고 기억했다가 다음엔 바로 적용하는 것과 같습니다.

2. 함께 움직이는 로봇들 (동기화)
   로봇 한 대가 아니라 여러 대가 좁은 공간에서 일할 때, 서로 서로 기다려주거나 (Stop-and-Go) 함께 지나가는 (Synchronization) 것이 중요합니다. 이 논문은 로봇들이 서로의 움직임을 고려하며 "너가 먼저 지나가, 내가 그다음에 갈게"라고 자연스럽게 조율할 수 있게 해줍니다.

3. 유연한 도구 사용 (오프더셸)
   이 시스템은 특정 로봇이나 특정 상황에만 맞는 전용 도구를 쓰지 않습니다. 이미 잘 만들어진 스케줄링 프로그램과 모션 플래닝 프로그램을 가져와서 서로 연결만 하면 됩니다. 마치 레고 블록처럼, 어떤 상황 (창고, 공장, 물류센터) 이든 쉽게 적용할 수 있습니다.

---

🏆 왜 이것이 중요한가요?

• 실제 현실 문제 해결: 이론적으로만 완벽한 계획은 세우기 쉽지만, 실제로 로봇을 움직이면 벽에 부딪히거나 시간이 늦어집니다. 이 방식은 이론과 현실의 간극을 메워줍니다.
• 효율성 극대화: 로봇들이 서로 기다리느라 시간을 낭비하지 않고, 최대한 빠르게 일을 끝낼 수 있게 해줍니다. 실험 결과, 기존 방식보다 약 41% 더 빠른 작업을 가능하게 했습니다.
• 복잡한 상황 대처: 문이 닫혀있거나, 로봇이 많아서 좁은 통로에 막히는 등 예상치 못한 상황에서도 유연하게 대처하여 해결책을 찾아냅니다.

📝 한 줄 요약

"스케줄러와 모션 플래너가 서로 대화하며, "여기 막히네", "시간 좀 늦춰줘"라고 피드백을 주고받다 보면, 결국 로봇들이 서로 부딪히지 않고 가장 빠르게 일할 수 있는 완벽한 계획을 찾아낸다는 연구입니다."

이 기술이 발전하면, 우리 집 배달 로봇이나 대형 물류 창고의 로봇들이 훨씬 더 똑똑하고 안전하게 일할 수 있게 될 것입니다!

기술 요약

1. 문제 정의 (Problem Statement)

이 논문은 스케줄링 및 모션 플래닝 (Scheduling and Motion Planning, SAMP) 문제를 공식적으로 정의하고 해결책을 제시합니다.

• 배경: 기존의 작업 및 모션 플래닝 (TAMP) 은 '무엇을 할지 (작업 순서)'와 '어떻게 할지 (기하학적 경로)'를 동시에 결정하는 데 초점을 맞춥니다. 그러나 자동화 창고와 같은 실제 환경에서는 작업 (이동, 집기, 놓기 등) 이 미리 정의되어 있는 경우가 많습니다. 이때의 핵심 과제는 자원, 시간, 모션 제약 하에 작업을 언제, 어떻게 실행할지 결정하는 것입니다.
• SAMP 문제: 여러 로봇 (또는 객체) 이 공유 작업 공간에서 이동할 때, 작업의 순서와 타이밍을 결정하는 스케줄링과, 물리적으로 가능하고 충돌 없는 연속적인 궤적을 계산하는 모션 플래닝을 통합해야 합니다.
• 도전 과제:
  • 연속 공간과 동역학: 이산적인 경로 찾기 (MAPF) 와 달리, 실제 로봇의 기하학적 모델과 운동학적/동역학적 제약 (Kinodynamic constraints) 을 고려해야 합니다.
  • 시간적 동기화: 로봇들이 좁은 통로 등을 공유할 때 충돌을 피하거나 데드락을 방지하기 위해 정밀한 시간적 조정이 필요합니다.
  • 확장성: 모든 모션 제약을 사전에 구체화 (Grounding) 하면 계산 비용이 기하급수적으로 증가하므로, 점진적인 학습을 통한 추상화가 필요합니다.

2. 방법론 (Methodology)

저자들은 오프더셸 (off-the-shelf) 스케줄러와 모션 플래너를 **증분적 학습 루프 (Incremental Learning Loop)**로 엮어내는 새로운 프레임워크를 제안합니다.

핵심 프레임워크 구조

1. 초기 스케줄링: 스케줄러는 모션 가능성을 고려하지 않고 작업의 순서와 타이밍을 포함한 후보 스케줄 ($\rho$) 을 생성합니다.
2. 모션 검증 (Black-box Motion Planner): 생성된 스케줄을 모션 플래너가 검증합니다.
   • 성공: 모든 작업에 대해 충돌 없는 연속 궤적 ($\tau$) 을 찾으면 SAMP 솔루션을 반환합니다.
   • 실패: 기하학적 또는 시간적 제약 위반 시, **상징적 피드백 (Symbolic Feedback)**을 생성하여 스케줄러에 전달합니다.
3. 상징적 공간 - 시간 추상화 학습: 모션 플래너가 반환한 피드백은 다음 두 가지 형태로 스케줄러의 제약 조건을 강화합니다.
   • 기하학적 정제 (Geometric Refinements): 도달 불가능한 위치 ($\Sigma$) 나 방해가 되는 장애물 ($\Omega$) 을 식별하여, 해당 장애물의 상태 변경이나 작업 순서 조정을 요구하는 새로운 제약 조건을 추가합니다.
   • 시간적 정제 (Temporal Refinements): 기하학적으로 가능하지만 시간 제약 (지연, 지속 시간) 을 위반하는 경우, 실제 실행에 필요한 지연 시간 ($\delta$) 과 지속 시간 ($d$) 을 계산하여 스케줄러에 반영합니다.
4. 계층적 검증 (Layered Architecture):
   • Layer 1 (단일 작업): 개별 작업의 기하학적 경로 존재 여부만 빠르게 확인합니다.
   • Layer 2 (병렬 작업 그룹): 상호 간섭이 있는 병렬 작업 그룹에 대해 공간 - 시간 (Space-Time) 동기화 및 충돌 회피를 검증합니다.
   • 이 계층 구조는 불필요한 고비용 계산을 줄여 효율성을 극대화합니다.

알고리즘 특징

• 선택적 스케줄링 (Optional Scheduling): 필수 작업과 선택적 작업을 구분하여, 모션 충돌이 해결 불가능한 경우 일부 작업을 생략하거나 대안을 선택할 수 있게 합니다.
• 타임아웃 관리: 샘플 기반 플래너의 실패 (False Negative) 를 방지하기 위해, 초기 실패 시 타임아웃을 점진적으로 늘리고 재시도하는 메커니즘을 도입했습니다.

3. 주요 기여 (Key Contributions)

1. SAMP 문제의 공식적 정의: 다중 객체 내비게이션을 위한 스케줄링과 모션 플래닝의 통합 문제를 수학적 형식 (Fluent 조건 및 자원 제약 포함) 으로 정의했습니다.
2. 증분적 학습 기반 인터리빙 프레임워크: 스케줄러와 모션 플래너를 단방향으로 연결하는 것이 아니라, 모션 플래너의 피드백을 통해 스케줄러가 점진적으로 학습하고 개선하는 폐루프 (Closed-loop) 구조를 설계했습니다.
3. 도메인 독립성: Aries, OR-Tools 같은 다양한 스케줄러와 RRT*, ST-RRT* 같은 다양한 모션 플래너를 유연하게 결합할 수 있는 범용 프레임워크를 구현했습니다.
4. 효율적인 계층적 검증: 단일 작업 수준의 빠른 검사와 병렬 그룹 수준의 정밀 검사를 분리하여 계산 비용을 최적화했습니다.

4. 실험 결과 (Experimental Results)

저자들은 물류 (Logistics) 및 조립 공장 (Job-Shop Scheduling) 벤치마크를 확장하여 내비게이션 작업을 추가한 환경에서 실험을 수행했습니다.

• 실험 설정: 1~3 대의 로봇이 좁은 통로, 문 (개방/폐쇄), 장애물 환경에서 물건을 운반하는 시나리오.
• 성능:
  • 제안된 프레임워크는 복잡한 시공간 제약 하에서 유효한 계획을 생성했습니다.
  • 병렬화 효과: 순차적 실행 (병렬화 없음) 대비 평균 41% 의 Makespan (총 작업 완료 시간) 단축을 달성했습니다.
  • 정제 (Refinement) 의 중요성: 단순 순차 파이프라인 (스케줄링 후 모션 플래닝 1 회) 은 모든 문제를 해결하지 못했으나, 반복적 정제를 통해 해결 가능했습니다.
  • 플루언트 (Fluents) 활용: 상태 표현에 플루언트 (상태 변수) 를 사용한 스케줄러 (Aries with fluents) 가 가장 높은 성능 (평균 87.7 개 인스턴스 해결) 을 보였습니다.
  • 시간 소요: 전체 계획 시간의 약 76~92% 가 모션 플래닝에 소요되었으나, 계층적 구조 덕분에 단일 작업 수준의 기하학적/시간적 정제가 대부분 처리되어 전체 효율이 유지되었습니다.

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

• 실용적 가치: 자동화 창고 및 물류 시스템에서 로봇들의 충돌 없는 동시 작업 (Synchronization) 을 보장하는 실용적인 솔루션을 제공합니다.
• 이론적 기여: 이산적 스케줄링과 연속적 모션 플래닝 간의 간극을 메우기 위해 '상징적 공간 - 시간 추상화'를 학습하는 새로운 패러다임을 제시했습니다.
• 확장성: 향후 MAPF(다중 에이전트 경로 찾기) 와의 통합을 통해 더 넓은 범위의 문제를 해결할 수 있는 기반을 마련했습니다.

요약하자면, 이 논문은 스케줄링과 모션 플래닝을 분리하지 않고 상호 보완적으로 반복 개선하는 프레임워크를 통해, 복잡한 다중 로봇 환경에서 안전하고 효율적인 실행 계획을 생성하는 데 성공했습니다.