Conflict-Based Search as a Protocol: A Multi-Agent Motion Planning Protocol for Heterogeneous Agents, Solvers, and Independent Tasks

이 논문은 이기종 에이전트들이 독립적인 작업을 수행할 때 충돌 없는 경로를 효율적으로 생성하기 위해 Conflict-Based Search(CBS) 를 표준 프로토콜로 활용하여 다양한 단일 에이전트 계획 알고리즘을 통합하는 방법을 제시합니다.

핵심

이 논문은 **"서로 다른 회사의 로봇들이 한 공간에서 서로 부딪히지 않고 일하게 하는 방법"**에 대한 획기적인 아이디어를 제시합니다.

기존의 로봇 연구들은 보통 "모든 로봇이 똑같은 두뇌 (알고리즘) 를 가지고 있어야 한다"는 전제하에 진행되었습니다. 하지만 현실은 다릅니다. A 회사의 청소 로봇, B 회사의 물류 로봇, C 회사의 감시 로봇이 한 사무실이나 공장에 섞여 있을 수 있죠. 문제는 이 로봇들이 각자 고유의 두뇌를 가지고 있어 서로 대화도 안 되고, 어떻게 움직여야 할지 모른다는 점입니다.

이 논문은 이를 해결하기 위해 **'CBS (Conflict-Based Search, 충돌 기반 탐색)'**라는 기존 기술을 단순한 '알고리즘'이 아닌 **'프로토콜 (규칙集)'**로 바꾸어 제안합니다.

🤖 핵심 비유: "다양한 요리사들이 있는 거대한 주방"

이 논문의 아이디어를 쉽게 이해하기 위해 **'거대한 주방'**을 상상해 보세요.

1. 상황:

   • 주방에는 A, B, C 등 다양한 레스토랑에서 온 요리사들 (로봇) 이 있습니다.
   • A 요리사는 프랑스 요리를, B 요리사는 일식을, C 요리사는 한식을 합니다. 각자 사용하는 도구와 비법 (알고리즘) 이 완전히 다릅니다.
   • 목표는 이 모든 요리사가 한 주방에서 서로 부딪히지 않고 각자 맡은 요리를 완성하는 것입니다.

2. 기존의 문제점:

   • 과거에는 모든 요리사가 "프랑스식 조리법 (A* 알고리즘)"만 알아야만 함께 일할 수 있었습니다. 일식 요리사나 한식 요리사는 끼어들 수 없었죠.
   • 아니면, 요리사들이 서로 눈을 마주치며 "내가 먼저 지나가겠다"고 싸우는 (재계획) 방식만 썼는데, 이건 비효율적이고 혼란스러웠습니다.

3. 이 논문의 해결책: "주방장 (중앙 관리자) 의 규칙集"

   • 이 논문은 **모든 요리사에게 "너희가 쓰는 비법은 상관없어, 다만 내 규칙만 지키면 돼"**라고 말합니다.
   • 규칙 (프로토콜): "너희는 내게 **'요리 계획서 (경로)'**와 **'그 계획이 차지하는 공간과 시간'**만 알려주면 돼. 그리고 내가 "너, 3 시에 이 위치에서 다른 사람과 부딪히네? 다시 계획해 봐"라고 하면, 너희는 너희만의 비법으로 다시 계획서를 만들어 내게 줘."
   • 중앙 관리자 (CBS): 이 규칙을 따르는 모든 요리사들의 계획을 모아서, 누가 어디서 부딪히는지 확인하고, 충돌이 생기면 "너는 3 시 10 분에 이 자리를 비켜줘"라고 지시합니다.

🌟 이 방식이 얼마나 혁신적인가요?

이 논문은 다양한 종류의 '두뇌'를 가진 로봇들을 한곳에 모아도 된다는 것을 증명했습니다. 실험에서 그들은 다음과 같은 완전히 다른 방식의 로봇들을 함께 움직였습니다:

• 수학자 로봇 (A):* 논리적으로 가장 짧은 길을 계산합니다.
• 실험가 로봇 (RRT): 무작위로 길을 찾아보며 길을 냅니다.
• 최적화 로봇: 복잡한 수식을 풀어 가장 효율적인 움직임을 찾습니다.
• 생각하는 로봇 (확산 모델/딥러닝): 데이터를 보고 패턴을 학습하여 움직입니다.
• 훈련된 로봇 (강화학습): 시행착오를 통해 스스로 배운 행동을 합니다.

이 모든 로봇들이 **서로 다른 언어 (알고리즘)**를 쓰지만, **중앙 관리자가 정한 '규칙集 (프로토콜)'**만 따르면, 서로 부딪히지 않고 완벽하게 협업할 수 있었습니다.

💡 왜 이것이 중요한가요?

• 현실적인 미래: 앞으로 우리 집이나 공장에는 삼성, LG, 현대, 그리고 외국 브랜드의 로봇들이 섞여 있을 것입니다. 이 논문은 "어떤 로봇이든 상관없어, 이 규칙만 지키면 다 같이 일할 수 있어"라고 말해줍니다.
• 유연성: 로봇이 어떤 일을 하든 (물건 나르기, 감시하기, 청소하기 등) 상관없이 이 시스템이 작동합니다.
• 비밀 유지: 로봇 제조사들은 "우리의 핵심 알고리즘 (비법) 은 공개할 수 없어"라고 해도 됩니다. 중앙 관리자는 그 비법을 알 필요 없이, 오직 **'결과물 (경로)'**만 받으면 되니까요.

🚀 결론

이 논문은 **"로봇들이 서로 다른 두뇌를 가지고 있어도, 하나의 공통된 규칙 (프로토콜) 만 공유하면 서로 부딪히지 않고 협력할 수 있다"**는 것을 보여줍니다. 마치 서로 다른 언어를 쓰는 사람들이 모두 '영어'라는 공통 규칙만 공유하면 대화할 수 있는 것과 같습니다.

이 기술이 실용화되면, 앞으로 우리가 사는 공간에는 다양한 로봇들이 조화롭게 움직이며 우리의 삶을 훨씬 더 편리하게 만들어 줄 것입니다.

기술 요약

1. 문제 정의 (Problem)

미래의 건설 현장, 병원, 사무실 등에는 다양한 제조사에서 생산된 수십 대의 로봇이 공존하게 될 것입니다. 이러한 환경에서 발생하는 핵심적인 문제는 다음과 같습니다.

• 이질적 에이전트 (Heterogeneous Agents): 로봇들은 서로 다른 물리적 형태 (Embodiment) 와 운동 동역학 (Kinodynamic) 제약을 가질 수 있습니다.
• 독립적 작업 (Independent Tasks): 각 로봇은 서로 다른 목적 (예: 이동, 감시, 커버리지 등) 을 수행하며, 반드시 같은 시작점과 목표점을 공유하지는 않습니다.
• 이질적 솔버 (Algorithmically Heterogeneous Solvers): 각 로봇은 제조사마다 고유의 독점적 (Proprietary) 운동 계획 솔버 (A*, RRT, 최적화, 강화학습 등) 를 사용할 수 있으며, 내부 알고리즘에 접근할 수 없습니다.
• 기존 방법의 한계: 기존의 다중 에이전트 경로 찾기 (MAPF) 또는 다중 에이전트 운동 계획 (MAMP) 방법론은 대부분 모든 에이전트가 동일한 계획 알고리즘을 사용하거나, 내부 상태를 공유해야 한다는 전제를 깔고 있습니다. 또한, 다른 로봇을 동적 장애물로 간주하고 개별적으로 재계획하는 방식은 효율성이 낮고 교착 상태 (Deadlock) 를 초래할 수 있습니다.

핵심 질문: "서로 다른 제조사의 로봇들이 각자의 독립적인 운동 계획 시스템을 가지고 있을 때, 어떻게 공유 환경에서 효율적이고 충돌 없는 이동을 조정할 수 있는가?"

---

2. 방법론 (Methodology)

이 논문은 **Conflict-Based Search (CBS)**를 단일 에이전트 운동 계획 솔버와 상호작용하는 **프로토콜 (Protocol)**로 재정의하여 문제를 해결합니다.

가. CBS 프로토콜의 핵심 개념

• 추상화된 API (plan()): CBS 는 모든 에이전트에게 공통된 인터페이스인 plan() API 만을 요구합니다. 이 API 는 다음과 같은 입출력을 가집니다.
  • 입력: 시간 - 공간 제약 조건 (Space-time constraints) 리스트.
  • 출력: 1) 제약 조건을 만족하는 경로, 2) 경로가 차지하는 시간 - 공간 부피 (Space-time volume, 충돌 감지를 위해), 3) 비용 (Cost).
  • 특징: CBS 는 에이전트의 내부 솔버 구현 방식 (A*, RRT, RL 등) 을 알 필요가 없으며, 오직 API 호출 결과만 사용합니다.
• 중앙 집중식 조정자 (Central Planner):
  • 고수준 탐색 (High-level Search): 제약 조건 트리 (Constraint Tree, CT) 를 탐색합니다. 초기에는 제약이 없는 루트 노드에서 각 에이전트의 경로를 개별적으로 요청합니다.
  • 충돌 감지 및 해결: 에이전트들의 시간 - 공간 부피를 비교하여 충돌을 감지합니다. 충돌이 발생하면, 해당 시점과 위치에서 특정 에이전트가 이동하지 못하도록 하는 제약 조건을 생성합니다.
  • 재계획 (Replanning): 생성된 제약 조건을 해당 에이전트의 plan() API 에 전달하여 새로운 경로를 요청합니다. 이 과정은 충돌이 사라질 때까지 반복됩니다.

나. 주요 기술적 세부 사항

• 시간 - 공간 제약 (Space-time Constraints): 연속 시간/공간 환경에서 단순한 점 (Point) 제약은 미묘한 시간 차이로 인해 충돌이 재발생할 수 있으므로, 논문은 **시간 - 공간 부피 (Space-time volumes)**를 제약 대상으로 사용하여 의미 있는 경로 변경을 유도합니다.
• 독립적 작업 지원: CBS 프로토콜은 시작점 - 목표점 (Start-Goal) 문제뿐만 아니라, 커버리지 (Coverage), 감시 (Surveillance), 탐색 (Exploration) 등 임의의 단일 에이전트 작업에도 적용 가능합니다.
• 경험 재사용 (Experience Reuse): CBS 는 에이전트에게 이전 쿼리 결과를 재사용하도록 권장합니다. 이는 제약 조건이 추가될 때 이전 경로를 기반으로 재계획 (Warm-start) 하여 계산 효율성을 높입니다.

---

3. 주요 기여 (Key Contributions)

1. 알고리즘적 이질적 MAMP (AH-MAMP) 문제 정의: 서로 다른 솔버를 사용하는 이질적 에이전트 팀을 위한 다중 에이전트 운동 계획 문제를 공식적으로 정의하고, 이를 해결하기 위한 첫 번째 체계적인 접근법을 제시했습니다.
2. CBS 를 프로토콜로 재정의: CBS 를 특정 솔버에 종속된 알고리즘이 아닌, 다양한 솔버를 연결하는 표준 프로토콜로 확장했습니다. 이를 통해 A*, RRT, 직접 콜로케이션 (Optimization), 확산 모델 (Diffusion), 강화학습 (RL) 등 완전히 다른 패러다임의 솔버를 하나의 시스템에서 통합할 수 있음을 증명했습니다.
3. 실용적 증명 (Proof-of-Concept): 다양한 솔버와 작업 유형 (이동, 감시, 커버리지) 을 혼합한 실험을 통해 프로토콜의 유효성을 입증했습니다.

---

4. 실험 결과 (Experimental Results)

• 실험 설정: 2D occupancy map 에서 Ackermann, Dubins, Unicycle 등 다양한 운동 역학을 가진 로봇들을 시뮬레이션했습니다. A*, RRT, 직접 콜로케이션, Diffusion, RL 등 5 가지 솔버를 혼합하여 사용했습니다.
• 성공률:
  • CBS 프로토콜은 초기 충돌이 없는 경우 (Root conflicts = 0) 에 높은 성공률을 보였습니다.
  • 초기 충돌이 있는 경우 (혼잡한 환경), 솔버의 성능에 따라 성공률이 달라졌습니다. (예: A* 기반 솔버는 87~94% 성공률, RL 및 최적화 솔버는 상대적으로 낮은 성공률).
  • 전체적으로 675 개의 인스턴스 중 약 54% 의 충돌이 있는 경우를 해결했습니다.
• 기반선 (Baseline) 비교:
  • 기존 방식 (개별 계획 + 로컬 우선순위 충돌 회피) 은 충돌이 있는 경우 9% 만 성공했으나, CBS 프로토콜은 훨씬 높은 성공률을 기록했습니다.
• 경험 재사용의 효과: 각 솔버의 '경험 재사용 (Experience)' 기능을 제거했을 때, API 쿼리 시간이 10%~300% 증가하여 전체 시스템 성능이 저하됨을 확인했습니다. 이는 CBS 프로토콜이 솔버의 재계획 속도에 민감하게 의존함을 보여줍니다.

---

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

• 표준화 및 상호운용성: 이 연구는 서로 다른 제조사와 기술 스택을 가진 로봇들이 표준화된 API 프로토콜을 통해 협력할 수 있는 길을 열었습니다. 이는 로봇 산업의 표준화 (Interoperability) 에 중요한 기여를 합니다.
• 연구 간극 해소: 단일 에이전트 운동 계획, 다중 에이전트 운동 계획, 그리고 MAPF 분야 간의 간극을 연결합니다.
• 미래 전망:
  • 산업 적용: 실제 이질적 로봇 시스템에 효율적으로 배포될 수 있는 기반을 마련했습니다.
  • 솔버 최적화: CBS 프로토콜의 제약 조건 (시간 - 공간 부피) 을 고려하여 더 빠르고 정확한 단일 에이전트 솔버를 개발할 필요성이 제기됩니다.
  • 지능형 조정: 서로 다른 솔버의 성능 (성공률, 계산 시간) 을 고려하여 CBS 가 더 지능적으로 에이전트를 선택하거나 조정하는 방향으로 발전할 수 있습니다.

요약하자면, 이 논문은 CBS 를 '알고리즘'이 아닌 '프로토콜'로 격상시킴으로써, 서로 다른 기술적 배경을 가진 로봇들이 하나의 공유 공간에서 충돌 없이 협력할 수 있는 강력한 프레임워크를 제시했습니다.