기술 요약: FLIP – 점군 정합을 통한 대규모 분산 군집을 위한 실시간 및 복원력 있는 형성 계획

1. 문제 제기

대규모 군집 로봇의 형성 계획은 성능과 계산 확장성 간의 근본적인 트레이드오프에 직면해 있습니다. 기존 접근 방식은 일반적으로 두 가지 범주로 나뉘며, 둘 다 상당한 한계를 보입니다:

• 과도하게 단순화된 표현: 다면체 구조, 확률 분포, 또는 인공 퍼텐셜 필드를 사용하는 방법은 계산 부하를 줄이기 위해 에이전트 간 상호작용을 분리합니다. 그러나 이러한 단순화는 장애물이 풍부한 환경에서 특히 형성 성능이 저하되어 심각한 형태 변형과 느린 수렴을 초래합니다.
• 완전한 협력 관계: 모든 에이전트의 운동을 정밀하게 고려하는 방법 (완전 그래프를 근사) 은 높은 형성 충실도를 보장하지만 과도한 계산 제약을 도입합니다. 군집 규모가 커질수록 이러한 방법은 높은 계산 부하, 지역 최적점 (local optima) 에 대한 취약성, 그리고 복원력 부족으로 고통받습니다. 이러한 시스템에서 비최적 궤적이나 비정상 에이전트 상태는 네트워크를 통해 전파되어 전체 군집의 성능을 저하시킵니다.

현재의 희소 그래프 접근 방식은 이러한 요인들을 균형 있게 맞추려 시도하지만, 군집이 100 개를 초과할 때 형성 성능을 보장하지 못하는 경우가 많습니다. 또한, 기존 방법들은 정규화된 라플라시안 행렬의 한계로 인해 긴 형상 (elongated formations) 을 다루는 데 어려움을 겪는데, 이는 주축 기울기가 부축 기울기를 압도하게 만들어 문제를 야기합니다.

2. 방법론

제안된 FLIP(Real-Time and Resilient Formation Planning) 프레임워크는 최적 형성 위치 시퀀스 (OFPS) 계산 문제를 시공간 점군 정합 (PCR) 문제로 변환함으로써 이러한 과제를 해결합니다. 이 시스템은 에이전트들이 이웃에게 궤적을 브로드캐스트하는 분산 비동기 계획 프레임워크 내에서 작동합니다.

핵심 메커니즘: PCR 기반 OFPS 계산

복잡한 그래프 기반 비용 함수를 최적화하는 대신, 각 에이전트는 다른 모든 에이전트의 현재 위치를 소스 점군으로, 원하는 형성 위치를 타겟 점군으로 간주합니다.

1. 문제 변환: 에이전트의 최적 형성 위치를 찾는 목표는 소스 점군 (다른 에이전트들의 위치) 을 타겟 점군 (원하는 형성) 과 정렬시키는 최적의 변환 파라미터 (회전 $R$, 이동 $t$, 스케일 $s$) 를 찾는 문제로 재정의됩니다.
2. 효율적인 근사: 모든 에이전트에 대해 반복 최적화의 계산 부담을 피하기 위해, 이 방법은 문제를 완화합니다. 자신을 제외한 모든 다른 에이전트의 위치를 사용하여 최적의 변환 파라미터 $\{R^*, t^*, s^*\}$ 를 계산합니다. 그런 다음 에이전트의 최적 형성 위치는 변환을 통해 직접 유도됩니다: $p^*_i = s^* R^* p^{des}_i + t^*$.
3. 이상치 제거: 복원력을 보장하기 위해, 프레임워크는 PCR 과정에서 RANSAC(Random Sample Consensus) 알고리즘을 사용합니다. 이를 통해 시스템은 정합 과정에서 이상치 포인트 (비정상 또는 비최적 에이전트 궤적을 나타냄) 를 식별하고 제거할 수 있습니다. 결과적으로 비정상 상태는 네트워크를 통해 전파되어 정상 에이전트의 계획에 영향을 미치지 않습니다.

궤적 최적화

OFPS 가 계산되면, 각 에이전트는 이를 로컬 궤적 최적화의 제약 조건으로 사용합니다. 궤적은 TMINCO(최소 제어 다항식 궤적 표현) 를 사용하여 표현됩니다. 최적화는 다음을 만족하면서 제어 노력과 비행 시간을 최소화합니다:

• 동적 실현 가능성 제약.
• 장애물 회피.
• 군집 상호 회피.
• OFPS 에서 유도된 형성 제약.

제약 최적화 문제는 페널티 전략을 사용하여 비제약 문제로 변환되며, L-BFGS 알고리즘을 사용하여 효율적으로 해결됩니다.

3. 주요 기여

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

1. PCR 기반 대규모 계획: 저자들은 효율적인 PCR 을 활용하여 최적 형성 위치 시퀀스를 계산하는 새로운 알고리즘을 제안합니다. 이 접근 방식은 완전히 연결된 협력 그래프와 관련된 계산 폭발을 피함으로써 대규모 군집에 대한 실시간 계획을 가능하게 합니다.
2. 이상치 제거를 통한 복원력 있는 계획: PCR 단계에 이상치 제거 (RANSAC) 를 통합함으로써, 이 방법은 분산 최적화 과정에서 비최적 또는 비정상 에이전트 궤적의 영향을 본질적으로 제거합니다. 이는 오류의 전파를 방지하고 상당한 비율의 비정상 에이전트가 있더라도 군집이 형상을 유지하도록 보장합니다.
3. 검증 및 오픈 소스: 이 방법의 효과는 State-of-the-Art (SOTA) 방법들에 대한 광범위한 시뮬레이션 및 벤치마크를 통해 검증되었습니다. 저자들은 또한 추가 연구를 촉진하기 위해 코드를 오픈 소스로 공개할 것을 약속합니다.

4. 실험 결과

저자들은 표준 PC(Intel Core i7 8700K, 32GB RAM) 에서 다양한 군집 크기 (최대 120 개 에이전트) 와 형성 모양에 대한 성능을 평가하기 위해 시뮬레이션을 수행했습니다.

• 확장성 및 효율성:

  • SOTA 방법 (Quan 의 [1] 과 Zhou 의 [10]) 과 비교하여 FLIP 은 우수한 계산 효율성을 보여줍니다. Quan 의 방법은 40 대 드론으로 실시간 계획을 유지하지 못하며 (계산 시간 > 1 초), Zhou 의 방법은 100 대 드론에서 어려움을 겪는 반면, FLIP 은 장애물 환경에서 100 개 에이전트에 대해 평균 0.040 초, 120 개 에이전트에 대해 0.09 초의 계획 시간을 유지합니다.
  • FLIP 의 형성 거리 오차 ($\bar{e}_{dist}$) 는 낮게 유지됩니다 (예: 100 개 에이전트 기준 0.6065). 이는 유사한 규모에서 실패하거나 높은 오차를 보인 Zhou 의 방법보다 우월합니다.
  • OFPS 계산 자체는 매우 경량화되어 1000 개 에이전트에서도 0.06 초 미만으로 유지됩니다.

• 복원력:

  • 비정상 에이전트 (이상치) 를 포함한 실험에서 FLIP 은 최대 **12%**의 비정상 에이전트 (특정 테스트에서는 75 명 중 9 명, 일반적인 주장에서는 약 10%) 로도 형성 성능을 성공적으로 유지했습니다.
  • 반면, 단일 단계 최대 클릭 (maximum clique) 접근 방식을 사용하는 Zhou 의 방법은 비정상 에이전트 수가 3% 를 초과하면 형성 저하로 이어지는 어려움을 겪었습니다. Quan 의 방법은 비정상 상태의 전파로 인해 진동을 보였습니다.

• 형성 모양의 다양성:

  • FLIP 은 하트, 큐브, 무작위 3D 등 다양한 모양에서 SOTA 방법과 비교 가능한 오차로 일관된 성능을 발휘했습니다.
  • 특히 긴 형상(예: 13.5m x 1.5m 직사각형) 의 경우, FLIP 은 정규화된 라플라시안 행렬 기반 방법보다 우월했습니다. 후자는 짧은 축 오류에 대한 민감도 감소로 인해 변형을 겪은 반면, FLIP 은 일관된 민감도와 낮은 오차 (장애물이 없는 조건에서 $\bar{e}_{dist} = 0.028$) 를 유지했습니다.

5. 중요성 및 주장

이 논문은 FLIP 이 고성능 형성 유지와 계산 효율성 사이의 균형을 달성함으로써 대규모 군집 로봇 공학에서 중요한 진전을 이루었다고 주장합니다.

• 실시간 능력: 이 방법은 지연이나 지역 최적점으로 인해 이전 분산 방법들이 종종 실패하는 100 개 이상의 에이전트 군집에 대한 실시간 궤적 계획을 가능하게 합니다.
• 본질적 복원력: 점군 정합 문제에서 비정상 에이전트를 이상치로 취급함으로써, 시스템은 복잡한 적응형 제어 법칙이나 사전 계획된 이상치 제거 단계 없이도 노이즈와 고장을 자연스럽게 필터링합니다.
• 확장성: 이 접근 방식은 그래프 기반 최적화 방법과 달리 핵심 형성 조정 (PCR) 의 계산 비용이 에이전트 수에 따라 비례적으로 급증하지 않기 때문에 효과적으로 확장됩니다.

저자들은 변환 계산 중 에이전트 자신의 현재 위치 영향을 무시함으로써 정밀도를 약간 희생하지만, 이 트레이드오프가 복잡하고 대규모인 임무에 적합한 견고하고 확장 가능하며 실시간 솔루션을 산출한다고 결론지었습니다. 향후 작업은 그룹 기반 전략을 사용하여 이를 더 큰 규모로 확장하고 글로벌 경로 계획을 통합하는 것을 목표로 합니다.