기술 요약: 비선형 다중 에이전트 충돌 회피를 위한 안전 집합 기반의 분산형 비상 MPC

문제 정의

본 논문은 비선형 동역학을 가진 다중 에이전트 시스템의 분산형 충돌 회피 과제를 다룹니다. 핵심 제약 조건은 상태 정보만 활용하는 패턴으로, 에이전트들은 동료들의 현재 상태는 관측할 수 있지만 계획된 궤적, 의도, 또는 제어 입력을 교환할 수 없습니다. 기존 접근법들은 종종 보수적인 조정 메커니즘에 의존하거나, 통신 라운드를 요구하여 (지연 발생), 또는 안전이 중요한 환경에서 재귀적 실현 가능성과 수렴성에 대한 강력한 보장을 제공하지 못합니다. 목표는 에이전트 간 통신 없이 항상 실현 가능한 백업 기동이 존재하도록 보장하면서, 에이전트들을 참조 상태나 안전 평형점으로 유도하는 충돌 없는 운동을 달성하는 것입니다.

방법론

제안된 솔루션은 새로운 Freeze-or-Shift(FoS) 안전 집합 업데이트 메커니즘을 보완한 분산형 비상 모델 예측 제어 (MPC) 프레임워크입니다.

1. 로컬 안전 집합

각 에이전트 $i$는 시간 가변 로컬 안전 집합 $S^*_i(t)$와 연관되며, 이는 유클리드 볼 $B(c_i(t), R_i(t))$로 정의됩니다. 이러한 집합들은 다음을 만족하도록 구성됩니다:

• 회복 가능성: 집합 내의 모든 상태로부터, 해당 집합 내부에 머무르고 모든 제약을 만족하며 유한 시간 내에 허용 가능한 안전 평형점에 도달하는 실현 가능한 비상 기동이 존재합니다.
• 비중합성: 충돌 회보를 보장하기 위해 모든 에이전트의 활성 안전 집합은 쌍별로 서로 겹치지 않아야 합니다.
• 재구성 가능성: 에이전트들은 통신 없이 현재 상태 관측과 이전 안전 집합 매개변수에 대한 1 단계 기억만으로 이웃의 안전 집합을 재구성할 수 있습니다.

2. 분산형 비상 MPC 공식화

각 시간 단계에서 모든 에이전트는 다음을 동시에 계산하는 로컬 유한 시간 최적 제어 문제 (FHOCP) 를 풉니다:

• 성능 및 참조 추적을 위한 명목 궤적.
• 로컬 안전 집합 내에서 실현 가능한 백업 기동이 존재함을 보장하는 안전 증명서 역할을 하는 비상 궤적.
• 결합: 두 궤적은 공유된 첫 번째 제어 입력 ($u_i(t) = u^{n,*}_{i,(0|t)} = u^{c,*}_{i,(0|t)}$) 을 강제함으로써 결합됩니다. 이는 성능을 위한 행위가 안전 계획의 첫 번째 단계가 되도록 보장합니다.

주요 제약 조건:

• 꼬리 포함 (Tail-Containment): 전체 비상 궤적은 현재 활성 안전 집합 내에 머무아야 합니다. 또한, 비상 계획의 "꼬리" (임의의 미래 단계 $k$부터) 는 $k$ 단계의 예측 상태가 생성한 안전 집합 내에 머무아야 합니다. 이는 에이전트가 다음 상태로 이동하더라도 나머지 계획이 여전히 유효함을 보장합니다.
• 라이아푸노프형 수렴: 이전 최적 해의 이동된 꼬리에서 유도된 비상 관련 비용 상수에 대한 단조 감소 조건을 강제하는 제약이 적용됩니다. 이는 시스템을 안전 평형점으로 유도합니다.
• 충돌 회피: 명목 궤적에는 명시적인 에이전트 간 충돌 제약이 부과되지 않습니다. 안전성은 분리된 안전 집합 내에서의 비상 궤적 실현 가능성에 의해 완전히 보장됩니다.

3. Freeze-or-Shift (FoS) 업데이트 규칙

분산 방식으로 안전 집합의 쌍별 비중합성을 유지하기 위해, 논문은 결정론적 업데이트 규칙을 도입합니다. 각 단계에서 에이전트는 새로운 상태에 기반한 후보 안전 집합을 계산합니다.

• Freeze ($\chi=1$): 후보 집합으로 업데이트하는 것이 이웃의 후보 집합이나 현재 활성 집합과 겹치게 될 경우, 에이전트는 안전 집합을 동결합니다 (이전 매개변수를 유지).
• Shift ($\chi=0$): 겹침이 감지되지 않으면, 에이전트는 새로운 후보 집합으로 이동합니다.
  이 규칙은 완전히 분산되어 있으며, 에이전트들은 관측된 상태로부터 이웃의 잠재적 집합을 재구성하여 $\chi$를 로컬로 결정합니다.

4. 플러그 앤 플레이 (PnP) 운영

이 프레임워크는 에이전트가 온라인으로 작업 공간에 합류하거나 떠나는 것을 지원합니다.

• 합류: 새로운 에이전트는 기존 에이전트가 동결되어 있는 경우, 보수적인 히스토리 없는 과대 근사 (위치와 알려진 반지름 경계에 기반한 재구성 볼) 를 사용하여 기존 에이전트의 "동결된" 안전 집합을 재구성합니다. 그런 다음 이러한 표현과 겹치지 않는 초기 안전 집합을 선택합니다.
• 이탈: 이탈하는 에이전트는 단순히 나머지 에이전트의 로컬 제약 집합에서 제거되어 실현 가능성을 유지합니다.

주요 기여

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

1. C1: 활성 안전 집합의 비중합성을 보존하는 시간 가변 볼록 로컬 안전 영역을 위한 완전 분산형 FoS 업데이트 규칙.
2. C2: 공유된 첫 번째 입력을 통해 명목 성능 계획과 백업 안전 증명서를 결합하는 비선형 다중 에이전트 시스템을 위한 분산형 비상 MPC 공식화.
3. C3: 이동된 비상 후보와 불변 비중합 안전 집합에 기반한 재귀적 실현 가능성 및 충돌 회피의 구성적 증명.
4. C4: 비상 관련 비용 상수에 대한 단조 감소 조건을 강제함으로써 얻어진 라이아푸노프형 수렴 결과.
5. C5: 희소, 밀집, 복잡한 병목, 그리고 플러그 앤 플레이 시나리오에서의 효과성을 입증하는 시뮬레이션 결과.

결과

이산 시간 더블 적분자 에이전트를 2D 작업 공간에서 사용하여 시뮬레이션 연구가 수행되었습니다.

• 확장성: 이 방식은 충돌 없는 궤적을 유지하면서 증가하는 에이전트 밀도 (최대 20 개) 를 성공적으로 관리했습니다.
• 병목 시나리오: 정적 장애물이 있는 좁은 통로에서 에이전트들은 성공적으로 통과했습니다. 결과는 근접 접촉이 일시적인 "동결" 이벤트를 유발하여 안전하지 않은 안전 집합 업데이트를 방지하면서도 폐루프 진행을 유지했음을 보여주었습니다.
• 플러그 앤 플레이: 시스템은 기존 에이전트의 로컬 MPC 문제에 궤적 통신이나 구조적 변경 없이 에이전트의 온라인 삽입 및 제거를 처리했습니다.
• 수렴: 라이아푸노프 제약에 의해 강제된 대로 정규화된 비상 비용이 단조 감소하여 이론적 수렴 특성을 확인했습니다.

중요성과 주장

본 논문은 통신에 의존하지 않고 비선형 다중 에이전트 시스템에서 분산 제어와 엄격한 안전 보장 사이의 간극을 해소한다고 주장합니다.

• 통신 없는 안전: 협상이나 궤적 교환을 요구하는 많은 분산 MPC 접근법과 달리, 이 방법은 상태 관측과 결정론적 기하학적 업데이트 규칙만을 사용하여 안전을 보장합니다.
• 재귀적 실현 가능성: 비상 MPC 구조와 FoS 업데이트 규칙의 결합은 최적화 문제가 매 시간 단계에서 실현 가능함을 유지하는 실용적인 보장을 제공하여, 안전 기동이 존재하지 않는 데드락에 시스템이 진입하는 것을 방지합니다.
• 토폴로지 변화에 대한 강인성: 이 프레임워크는 에이전트 집합의 변화 (PnP) 와 동적 환경을 명시적으로 처리하도록 설계되어, 에이전트 수가 변하더라도 안전 보장을 유지합니다.
• 이론적 엄밀성: 논문은 재귀적 실현 가능성, 충돌 회피, 그리고 허용 가능한 안전 평형점으로의 라이아푸노프형 수렴에 대한 공식적 증명을 제공하여, 분산 환경에서의 수렴 보장과 관련된 기존 문헌의 한계를 해결합니다.

저자들은 이 접근법이 밀집 환경에서도 moderate 한 보수성을 보이며 (비상 기동을 위한 마진 유지와 같은 직관적인 안전 행동과 일치한다고) 언급합니다. 향후 연구는 외란, 모델 불일치, 그리고 센서 노이즈를 다루는 방향으로 제안됩니다.