Graph-of-Constraints Model Predictive Control for Reactive Multi-agent Task and Motion Planning

1. 문제 정의 (Problem)

이 논문은 다중 에이전트 작업 및 운동 계획 (Multi-agent TAMP, Task and Motion Planning) 의 핵심적인 한계를 해결하는 것을 목표로 합니다. 기존 TAMP 방법론들은 다음과 같은 두 가지 주요 제한 사항을 가지고 있습니다:

• 완전 순서 (Total Order) 의 제약: 기존 방법들은 작업을 "시퀀스 (Sequence)"로 정의하여, 에이전트들이 수행해야 할 단계들을 선형적으로 나열합니다. 이는 병렬로 수행 가능한 작업들 (예: 두 로봇이 동시에 다른 물체를 잡는 경우) 을 강제로 순차적으로 실행하게 만들어 비효율적인 대기 시간을 발생시킵니다.
• 정적 에이전트 할당 (Static Agent Assignment): 에이전트와 작업 단계 간의 매핑이 고정되어 있습니다. 외부 방해 (Disturbance) 가 발생하거나 특정 에이전트가 작업을 완료하지 못할 경우, 시스템이 동적으로 에이전트 역할을 재할당하거나 작업을 재구성하지 못해 전체 팀의 진행이 지연되거나 작업이 불가능해집니다.

이러한 문제들은 실제 환경에서 예측 불가능한 방해 요소가 존재할 때, 다중 로봇 시스템의 견고성과 효율성을 크게 떨어뜨립니다.

2. 방법론 (Methodology)

저자들은 이러한 한계를 극복하기 위해 그래프 오브 컨스트레인트 (Graph-of-Constraints, GoC) 와 이를 기반으로 한 모델 예측 제어 (MPC) 프레임워크인 GoC-MPC 를 제안합니다.

가. Graph-of-Constraints (GoC)

• 부분 순서 (Partial Order) 표현: GoC 는 작업 단계를 방향성 비순환 그래프 (DAG) 로 표현합니다. 이를 통해 작업 간의 의존성만 정의하고, 독립적인 작업들은 병렬로 수행될 수 있도록 유연하게 구성합니다.
• 동적 에이전트 할당: 에이전트와 하위 작업 (Subtasks) 간의 할당을 이진 결정 변수 행렬로 정의합니다. 최적화 과정에서 이 할당이 동적으로 결정되므로, 시스템 상태나 방해 상황에 따라 에이전트 역할을 실시간으로 재배정할 수 있습니다.
• 기하학적 제약: 작업은 로봇이 추적하는 3D 키포인트 (Keypoints) 간의 기하학적 관계로 정의됩니다. 이는 정밀한 환경 모델이나 대규모 학습 데이터 없이도 시각적 관찰만으로 작업을 수행할 수 있게 합니다.

나. GoC-MPC 알고리즘 (실시간 최적화)

GoC-MPC 는 재귀적 시간 구간 (Receding Horizon) 을 사용하여 실시간으로 반응을 수행하며, 문제를 세 단계로 분해하여 효율적으로 해결합니다:

1. 웨이포인트 및 할당 하위 문제 (Waypoints & Assignments):

   • GoC 의 노드 (웨이포인트) 와 에이전트 할당 행렬을 최적화합니다.
   • 에이전트 할당에 의존하는 제약 조건을 해결하고, 전체 작업 시간을 최소화하는 경로를 찾습니다.
   • 혼합 정수 비선형 계획법 (MINLP) 으로 풀며, Ipopt 솔버를 사용합니다.

2. 에이전트 스플라인 하위 문제 (Agent Splines):

   • 결정된 웨이포인트를 통과하는 각 에이전트의 최적 경로를 3 차 스플라인 (Cubic Splines) 으로 생성합니다.
   • 에이전트 간의 타이밍 제약 (예: 특정 노드에서의 동기화 또는 순서 준수) 을 포함하여 최적화합니다.
   • 이 문제는 2 차 계획법 (QP) 으로 변환되어 MOSEK 솔버로 빠르게 해결됩니다.

3. 단시간 재귀적 호라이즌 문제 (Short Receding-Horizon):

   • 생성된 참조 궤적을 기반으로, 환경 충돌 회피 및 동역학적 제약 (가속도, 저크 등) 을 고려하여 매우 짧은 시간 구간 (H 단계) 의 상세 궤적을 계산합니다.
   • 이 과정은 실시간으로 반복되어 외부 방해에 즉각 대응합니다.

다. 위상 진행 및 백트래킹 (Phase Progression & Backtracking)

• 진행 (Progression): 에이전트가 다음 노드에 도달하면 해당 노드의 제약이 만족되는지 확인하고, 만족되면 작업 단계를 진행합니다.
• 백트래킹 (Backtracking): 외부 방해로 인해 엣지 제약 (Edge Constraints) 이 위반되면, 해당 노드를 다시 작업 목록에 추가하여 이전 단계로 되돌아가 재계획합니다. 이는 다른 에이전트의 진행을 방해하지 않고 독립적으로 재시도할 수 있게 합니다.

3. 주요 기여 (Key Contributions)

1. GoC 프레임워크 도입: 순차적 제약에서 그래프 기반 제약으로의 확장을 통해, 다중 에이전트 작업의 부분 순서 (Parallelism) 와 동적 에이전트 할당을 자연스럽게 지원합니다.
2. GoC-MPC 알고리즘: GoC 기반의 복잡한 최적화 문제를 실시간 (Real-time) 속도로 분해하여 해결하는 효율적인 MPC 알고리즘을 제안했습니다.
3. 학습 데이터 및 모델 불필요: 사전 학습 데이터나 정밀한 환경 모델 없이, 시각적 관찰 (Visual Observations) 과 키포인트 추적만으로 다양한 다중 로봇 조작 작업을 수행할 수 있는 범용성을 제공합니다.
4. 강건한 방해 대응: 외부 방해 발생 시, 전체 시스템을 재시작하지 않고 필요한 에이전트만 백트래킹하고 역할을 재할당하여 작업을 계속 수행하는 반응형 (Reactive) 능력을 입증했습니다.

4. 실험 결과 (Results)

저자들은 IsaacSim, Drake 시뮬레이션 및 실제 UR5e 로봇 (이중 암) 을 사용한 실험을 통해 GoC-MPC 를 검증했습니다.

• 성능 비교 (Baseline: ReKep):
  • 성공률: 블록 적재 (Block-Stacking), 컵 따기 (Pick-and-Pour) 등 모든 작업에서 100% 성공률을 기록했습니다 (ReKep 는 일부 실패).
  • 계산 시간: GoC-MPC 는 ReKep 대비 40 배에서 70 배 더 빠른 계산 속도를 보였습니다 (평균 0.1 초 미만).
  • 경로 길이: 병렬 처리와 최적 할당 덕분에 전체 이동 거리가 기존 방법보다 약 30~50% 단축되었습니다.
• 방해 (Disturbance) 상황:
  • 물체가 밀리거나 잡기가 실패하는 상황에서도 GoC-MPC 는 해당 에이전트만 백트래킹하고 다른 에이전트는 계속 작업을 수행하여 전체 성공률을 유지했습니다.
  • ReKep 는 전체 단계를 재시작하거나 비효율적인 경로를 생성하는 반면, GoC-MPC 는 불필요한 이동 거리를 크게 줄였습니다.
• 확장성 (Scalability):
  • 물체 수 (최대 11 개) 와 에이전트 수 (최대 4 개) 가 증가해도 실시간 반응 속도를 유지하며 높은 성공률을 보였습니다.
• 실제 환경 (Real-world):
  • 실제 UR5e 로봇을 사용하여 컵 간 액체 이동, 블록 적재, 식탁보 접기 작업을 성공적으로 수행했습니다. (블록 적재의 경우 심각한 가림 현상 (Occlusion) 이 있는 2 건을 제외하고 모두 성공).

5. 의의 및 결론 (Significance)

이 논문은 다중 로봇 시스템의 TAMP 분야에서 중요한 진전을 이룩했습니다.

• 실용성: 복잡한 모델링이나 학습 없이도 시각 피드백만으로 실시간으로 복잡한 다중 로봇 작업을 수행할 수 있음을 증명했습니다.
• 효율성: 병렬 작업 처리와 동적 할당을 통해 계산 효율성과 작업 효율성을 동시에 극대화했습니다.
• 견고성: 예측 불가능한 실제 환경의 방해 요소에 대해 유연하게 대응할 수 있는 메커니즘을 제공하여, 실제 산업 현장이나 서비스 로봇 적용 가능성을 높였습니다.

결론적으로, GoC-MPC 는 다중 에이전트 조작 작업에서 속도, 성공률, 그리고 외부 환경 변화에 대한 적응성을 모두 만족하는 강력한 솔루션으로 평가받습니다.