기술 요약: 계층적 하위문제 확장 및 작업 공간 분해 정제를 통한 확장 가능한 다중 로봇 운동 계획

문제 정의

다중 로봇 운동 계획 (MRMP) 은 조정과 계산 효율성 사이의 근본적인 트레이드오프에 직면해 있습니다. 로봇 간 충돌을 피하기 위한 충분한 조정을 달성하려면 일반적으로 로봇 그룹의 결합 구성 공간 (composite space) 을 탐색해야 하며, 이는 로봇 수에 따라 기하급수적으로 증가하는 상당한 계산 비용을 초래합니다. 반면, 로봇을 개별적으로 계획하는 비결합 (decoupled) 접근법은 높은 확장성을 제공하지만, 특히 밀집 환경이나 운동역학적 제약이 있는 환경에서 복잡한 충돌을 해결하는 데 필요한 조정이 종종 부족합니다. 기존 하이브리드 방법은 작업 공간 위상 (예: 골격) 을 사용하여 계획을 안내함으로써 이 균형을 맞추려고 시도하지만, 이러한 표현은 개방형 환경에서는 어려움을 겪거나 로봇을 불필요한 근접 상태로 강제하여 충돌 해결 비용을 증가시키는 경향이 있습니다.

방법론: CIPHER

저자들은 CIPHER(Coordinated Incremental Planning with Hierarchical Expansion and Refinement, 계층적 확장과 정제를 통한 조정 점진적 계획) 를 제안합니다. 이는 해상도 안내 (resolution guidance) 를 활용하여 고수준에서 로봇을 조정함으로써 계산 비용이 많이 드는 결합 공간에서의 계획 필요성을 줄이는 하이브리드 MRMP 알고리즘입니다.

핵심 프레임워크

CIPHER 는 계획 - 확인 - 해결 (plan-check-resolve) 패러다임에 따라 작동하며, 다섯 단계로 구성됩니다:

1. 분해 및 MAPF(고수준): 작업 공간은 직사각형 셀의 균일한 그리드로 분할됩니다. 다중 에이전트 경로 찾기 (MAPF) 알고리즘 (특히 충돌 기반 탐색) 이 각 로봇에 대한 충돌 없는 영역 전환 시퀀스를 계산합니다. 이는 특정 로봇 역학에 독립적인 고수준 위상적 안내를 제공합니다.
2. 안내 계획 (저수준): 각 로봇은 샘플링 기반 계획기 (기하학적 시스템의 경우 RRT Connect, 운동역학적 시스템의 경우 Region-Guided DB-RRT) 를 사용하여 동적으로 실현 가능한 궤적을 독립적으로 계산합니다. 고수준 영역 경로는 경로를 엄격하게 제한하지 않으면서도 특정 영역으로 샘플링을 편향시키는 휴리스틱으로 작용하여 확률적 완전성을 유지합니다.
3. 충돌 감지: 생성된 궤적은 고정된 지속 시간의 세그먼트로 이산화됩니다. 시스템은 각 시간 단계에서 모든 로봇 쌍에 대해 기하학적 충돌을 확인합니다.
4. 계층적 충돌 해결: 충돌이 감지되면 CIPHER 는 즉시 결합 공간 계획으로 의존하지 않고 충돌을 해결하기 위해 점진적으로 상승하는 계층적 전략을 사용합니다:
   • 분해 정제: 충돌이 발생한 특정 그리드 셀을 더 높은 해상도로 세분화합니다. 충돌하는 로봇들을 위한 대체 하위 영역을 찾기 위해 이 정제된 셀 내에서 MAPF 문제를 다시 풉니다.
   • 공간 확장: 정제가 실패하면, 해결 영역은 인접한 셀 (대각선 포함) 을 포함하도록 확장됩니다. MAPF 문제를 이 더 넓은 영역에 대해 다시 풀어 대체 경로를 발견합니다.
5. 백업 계획: 계층적 해결 전략을 모두 소진한 후에도 충돌이 지속되면, 계획기는 결합 구성 공간에서 문제를 해결하기 위해 표준 결합 계획기 (Composite RRT) 로 백업합니다.

주요 차이점

이전 연구들이 개방 공간에서 이동을 제한할 수 있는 골격 기반 안내나 반응형 충돌 해결을 사용한 것과 달리, CIPHER 는 반복적인 영역 분해 정제를 사용합니다. 이를 통해 계획기는 작업 공간 표현의 해상도를 필요한 곳에서만 증가시킴으로써 로봇을 능동적으로 별도의 경로로 분리할 수 있습니다.

주요 기여

이 논문은 세 가지 주요 기여를 식별합니다:

1. CIPHER 알고리즘: 영역 분해 위에서 탐색하여 고수준에서 로봇을 조정함으로써 결합 공간 계획의 빈도를 현저히 줄이는 하이브리드 계획 알고리즘.
2. 해상도 안내: 계획 중에 작업 공간 표현이 반복적으로 정제되는 새로운 과정. 이는 시스템이 정적 안내에만 의존하는 대신 충돌을 해결하기 위해 더 세밀한 수준에서 로봇 이동을 지시할 수 있게 합니다.
3. 실험적 검증: 다양한 환경에서 CIPHER 를 최신 기하학적 및 운동역학적 MRMP 접근법 (Coupled RRT, Decoupled RRT, sRRT, ARC, WG-DaSH 포함) 과 비교한 광범위한 평가.

실험 결과

저자들은 로봇 수가 최대 32 개까지 확장되는 빈 공간부터 매우 혼잡한 방까지 다양한 환경에서 기하학적 및 운동역학적 시스템에 대해 CIPHER 를 평가했습니다.

• 성공률: CIPHER 는 기하학적 및 운동역학적 변형 모두에서 모든 테스트 환경과 로봇 수에 걸쳐 100% 성공률을 달성했습니다. 반면, WG-DaSH 와 같은 방법은 골격 제약으로 인해 개방형 환경에서 어려움을 겪었으며, 비결합 계획기 (PP-RG-RRT 등) 는 해결되지 않은 충돌로 인해 고밀도 시나리오에서 실패했습니다.
• 계획 시간: CIPHER 는 다른 최신 방법 대비 최대 한 자릿수 (order of magnitude) 의 계획 시간 개선을 보여주었습니다.
  • Coupled RRT와 비교할 때, CIPHER 는 결합 공간 탐색의 기하급수적 비용을 피했습니다.
  • Decoupled RRT 및 PP-RG-RRT와 비교할 때, CIPHER 는 다른 방법들이 실패하는 높은 성공률을 유지하면서도 충돌 발생 후에만 결합 공간으로 확장하는 반응형 하이브리드 방법 (sRRT 및 ARC 등) 보다 훨씬 빨랐습니다.
• 운동역학적 성능: 운동역학적 계획기의 경우, CIPHER 는 K-ARC 및 Kinodynamic WG-DaSH 를 능가했습니다. 단순한 안내 계획기 (PP-RG-RRT) 는 더 빨랐지만 밀집 시나리오에서 낮은 성공률을 보였으며, 이는 CIPHER 가 성공적으로 극복한 속도와 견고성 사이의 트레이드오프를 강조합니다.

중요성 및 주장

이 논문은 CIPHER 가 고차원 결합 구성 공간에서의 조정 부담을 계층적 작업 공간 표현으로 전환함으로써 다중 로봇 계획의 확장성 병목 현상을 해결한다고 주장합니다. 해상도 안내를 사용하여 이 방법은 충돌을 능동적으로 피하기 위해 적응적 정제를 사용하며, 충돌을 사후에 해결하는 대신 사전에 예방합니다.

저자들은 이 접근 방식이 다음과 같은 것을 가능하게 한다고 주장합니다:

• 견고성: 골격 안내가 실패하는 개방형 환경과 좁은 통로 모두에서 효과적인 성능.
• 효율성: 결합 공간 계획과 관련된 계산 비용을 줄여 최대 10 배의 속도 향상 달성.
• 완전성: 모든 계층적 전략이 실패할 경우 확률적으로 완전한 결합 계획기로 백업하므로 이론적 확률적 완전성이 보장됨.

이 연구는 작업 공간 표현 자체를 정제하는 것이 충돌 해결을 위한 강력한 메커니즘이 될 수 있음을 시사하며, 전통적인 결합 또는 순수 비결합 계획 전략에 대한 확장 가능한 대안을 제공합니다.