OSDAG: Online Scheduling for Efficient Multi-Robot Collaboration

OSDAG 기술 요약: 효율적인 다중 로봇 협업을 위한 온라인 스케줄링

1. 문제 정의

본 논문은 복잡하고 장기적인 과업을 수행하기 위한 이종 다중 로봇 시스템(Heterogeneous Multi-Robot Systems, MRS)의 조정 문제를 다룹ون다. 대규모 언어 모델(LLM)은 로봇이 자연어를 해석하고 재프로그래밍 없이 새로운 과업에 적응할 수 있게 해주었으나, 기존의 LLM 기반 MRS 프레임워크는 두 가지 결정적인 병목 현상을 겪고 있다:

1. 반복적 추론으로 인한 지연 시간: RoCo와 같은 분산형 대화 기반 방식은 에이전트 수가 증가함에 따라 지속적인 LLM 쿼리를 요구하며, 이로 인해 대화 기록이 선형적으로 증가하여 실행 지연 시간을 팽창시킨다.
2. 오프라인 스케줄링의 비효율성: LLM을 최적화 또는 계획(planning)과 결합한 현재의 대부분의 프레임워크는 실행이 시작되기 전에 전체 계획을 계산하는 오프라인 스케줄링에 의존한다. 이는 독립적인 하위 과업들이 병렬로 실행될 준비가 되었음에도 불구하고, 로봇들이 순차적으로 정렬된 선행 작업들을 기다리며 유휴 상태로 머물게 만든다.

핵심 문제는 LLM의 고수준 추론 능력을 유지하면서도, 유휴 시간을 최소화하고 반복적인 추 inference 오버헤드를 피할 수 있는 실시간 병렬 실행을 가능하게 하는 시스템을 개발하는 것이다.

2. 방법론

제안된 프레임워크인 OSDAG(Online Scheduling for Efficient Multi-Robot Collaboration)는 LLM 기반의 과업 추론을 유향 비순환 그래프(Directed Acyclic Graph, DAG) 표현 및 제약 조건 인지형 온라인 스케줄링과 통합한다. 이 파이프라인은 세 단계로 구성된다:

A. LLM 기반 과업 분해 (단일 추론)
대화 기반 방식과 달리, OSDAG는 LLM을 정확히 한 번만 호출한다. 여기서 LLM은 저수준 컨트롤러가 아닌 고수준 추론기 역할을 한다. 자연어 지시문과 현재 워크스페이스 컨텍스트(객체 상태, 에이전트 역량, 도달 가능성)가 주어지면, LLM은 구조화된 하위 과업 목록을 생성한다.

• 입력: 프롬프트에는 지시문, 사용 가능한 에이전트, 도달 가능한 객체, 실행 가능한 동작 및 엄격한 출력 스키마가 포함된다.
• 출력: 각 과업에 할당된 에이전트, 동작, 대상 객체, 목적지 및 일련의 선행 과업(의존성)이 주석으로 달린 후보 과업 리스트이다.
• 검증: 생성된 과업은 실행 가능성 제약 조건(예: 할당된 에이전트가 객체에 도달하여 동작을 수행할 수 있는지 여부)에 따라 검증된다. 유효하지 않은 계획은 거부되고 재생성된다.

B. 과업 그래프 정형화 (DAG 구축)
검증된 과업 리스트는 유향 비순환 그래프(DAG), $G = (V, E)$로 변환된다.

• 정점(Vertices): 개별 하위 과업을 나타낸다.
• 간선(Edges): 선행 관계 제약(예: "놓기" 과업은 대응하는 "집기" 과업이 완료된 후에 시작될 수 있음)을 나타낸다.
• 의의: 이 구조는 순차적 의존성(예: 집기 $\to$ 놓기)과 에이전트 간 의존성(예: 객체 핸드오프)을 명시적으로 인코딩한다. 결정적으로, 이는 평면적인 동작 시퀀스와 달리 병렬로 실행될 수 있는 독립적인 과업 브랜치를 노출한다.

C. 제약 조건 인지형 온라인 스케줄링
경량화된 온라인 스케줄러가 실시간으로 DAG를 실행한다.

• 메커니즘: 스케줄러는 에이전트 상태(Free 또는 Busy)와 과업 완료 상태를 지속적으로 모니터링한다.
• 동적 할당: 에이전트가 자유 상태가 되면, 스케줄러는 즉시 "준비된" 과업 세트(선행 과업이 완료되었고 해당 에이전트가 수행 가능한 과업)를 식별한다. 그 후 가장 낮은 인덱스를 가진 준비된 과업을 해당 에이전트에 할당한다.
• 병렬성: 이러한 이벤트 기반 접근 방식은 DAG의 독립적인 브랜치들이 동시에 진행되도록 하여, 오프라인의 사전 확정된 스케줄에서 발생하는 유휴 시간을 제거한다.

3. 주요 기여

본 논문은 세 가지 주요 기여를 설명한다:

1. LLM-DAG 통합: LLM 추론을 통해 에이전트 역량 및 환경 제약에 기반한 의존성 주석이 달린 그래프를 단 한 번의 추론 과정으로 생성하는 메커즘을 결합하였다.
2. 온라인 스케줄링 알고리즘: 동시성을 보장하고, 유휴 시간을 최소화하며, 의존성 및 자원 제약을 엄격히 준-수하는 실시간 과업 할당 알고리즘을 제시하였다.
3. 실증적 검증: 시뮬레이션 및 실제 시나리오 모두에서 실험을 통해 기존 베이스라인 모델 대비 성공률, 지연 시간 및 확장성 측면에서 우수한 성능을 입증하였다.

4. 실험 결과

시스템은 2~3개의 에이전트를 사용하는 물체 분류, 청소, 핸드오프 등의 과업을 포함하는 테이블탑 조작 5가지 벤치마크 시나리오에서 평가되었다.

• 추론 시간: OSDAG는 대화 기반 방식(예: RoCo)에 비해 추론 시간에서 5~15배의 속도 향상을 달了. 3개 에이전트 과업의 경우, RoCo는 206.3초가 소요된 반면 OSDAG는 단 14.0초가 소요되었다. OSDAG는 의존성 인식 능력을 유지하면서도 평면 시퀀스 생성기(ChatGPT-Prompts)와 유사한 낮은 지연 시간을 달성했다.
• 메이크스팬(Makespan) 감소: 독립적인 과업을 병렬로 실행하는 온라인 스케줄링을 활용함으로써, OSDAG는 오프라인 스케줄링 베이스라인 대비 총 완료 시간(메이크스팬)을 33%에서 38%까지 단축했다. 예를 들어, 5개 에이전트 핸드오프 과업에서 메이크스팬은 41.6초(베이스라인)에서 26.0초로 감소했다.
• 성공률: OSDAG는 경쟁력 있는 성공률(80–100%)을 유지했다. 특히, 암시적 의존성 추론이 필요한 복잡한 과업(예: 물건을 놓기 전 서랍 열기)에서 RoCo 및 TwoStep과 같은 베이스라인이 객체 상태 컨텍스트 부족으로 실패(0%)한 반면, OSDAG는 80%의 성공률을 기록했다.
• 절제 연구(Ablation Studies):
  • 의존성 그래프를 제거하면 자원 충돌로 인해 완전한 실패(성공률 0%)가 발생했다.
  • 온라인 스케줄링을 제거하면 올바른 계획임에도 불구하고 메이크스팬이 49–60% 증가하여, 동적 할당의 필요성을 확인시켜 주었다.
  • 객체/동작 임베딩을 제거하면 추론 시간이 증가하고 성공률이 감소했는데, 이는 환각(hallucination) 현상 때문이다.

실제 환경 검증: 본 프레임워크는 인간과 협업하는 UF850 매니퓰레이터에 배치되었다. 시스템은 서로 다른 인터페이스를 가진 이종 에이전트(로봇과 인간)를 성공적으로 조정하였으며, 이를 통해 실무적 적용 가능성을 검증하였다.

5. 의의 및 한계

본 논문은 OSDAG가 고수준 LLM 추론과 저수준 실행 효율성 사이의 간극을 메움으로써 효율적인 다중 로봇 협업을 향한 중요한 진전임을 주장한다. 주요 의의는 단일 패스 LLM 추론과 온라인 DAG 스케줄링의 결격이 대화 중심의 분산 시스템과 경직된 오프라인 플래너 모두보다 뛰어날 수 있음을 보여준 데 있다.

그러나 저자들은 다음과 같은 한계를 인정한다:

• 프레임워크는 의존성 간선을 생성하는 데 LLM에 의존하므로, 환경 복잡도와 에이전트 수가 증가함에 따라 추론 오류가 증가할 수 있다.
• 현재의 과업 선택 정책(가장 낮은 인덱스의 준비된 과업 선택)은 전역적으로 최적화된 스케줄을 생성하지 못할 수 있다.
• 시스템은 현재 재계획(replanning) 메커니즘이 부족하여, 실행 실패 시 동적 복구가 어려울 수 있다.