Zero-Shot Signal Temporal Logic Planning with Disjunctive Branch Selection in Dynamic Semantic Maps

기술적 요약: 동적 의미 지도에서의 이산적 분기 선택을 통한 제로샷 신호 시계열 논리 계획

1. 문제 정의

본 논문은 시스템 동역학이 알려지지 않은 가변 지도 환경에서 신호 시계열 논리 (STL) 계획의 과제를 다룹니다. 목표는 동적 이진 미로 지도 $M$으로 정의된 충돌 회피 제약을 준수하면서 복잡한 STL 명세 $\phi$를 만족하는 유한 시간 구간 궤적 $x_{0:T}$를 합성하는 것입니다.

주요 제약사항과 과제는 다음과 같습니다:

• 제로샷 일반화: 솔버는 인스턴스별 재학습이나 미세 조정 없이 이전에 보지 못한 지도 레이아웃, 장애물 구성, 그리고 STL 명세를 처리해야 합니다.
• 알려지지 않은 동역학: 계획기는 명시적인 전이 함수 $f(x_t, u_t)$ 없이 작동하며, 대신 과거 궤적의 오프라인 데이터셋에 의존합니다.
• 이산적 복잡성: STL 명세에는 종종 이산 (OR 연산자, $\lor$) 이 포함됩니다. 이를 해결하려면 논리의 특정 분기를 선택하여 만족시켜야 합니다. 동적 환경에서 방향 없는 선택은 기하학적으로 불가능하거나 동역학적으로 어려운 분기를 선택하게 되어 계획 실패를 초래할 수 있습니다.
• 시간적 근거: 고수준 STL 공식을 하위 작업으로 분해하려면 정확한 시간 할당 (특정 영역을 방문하는 시기 결정) 이 필요하며, 이는 다양한 지도 기하학에 걸쳐 일관되게 학습하기 어렵습니다.

2. 방법론

제안된 프레임워크는 세 가지 핵심 구성 요소를 통합하는 "분해 후 합성" 패러다임을 따릅니다:

A. 휴리스틱 이산 분기 선택
이산의 조합적 폭발과 실현 가능성 문제를 해결하기 위해, STL 공식을 먼저 이산 정규식 (DNF) 으로 변환합니다. 그런 다음 경량 휴리스틱이 세 가지 기준에 기반하여 가장 실현 가능한 분기 ($\phi^*$) 를 선택하기 위해 후보 분기 ($\phi_k$) 를 순위 매깁니다:

1. 시간 연산자 복잡성: 경험적으로 만족하기 어려운 시간 연산자 (예: $U$, $G$) 의 복잡한 중첩을 포함하는 분기에 패널티를 부여합니다.
2. 지도 도달 가능성: 현재 지도 $M$에서 그래프 기반 거리 (예: BFS/DFS) 를 계산하여 도달하기 어렵거나 장애물로 분리된 영역을 요구하는 분기에 패널티를 부여합니다.
3. 시간 여유: 하위 작업 간의 시간 간격이 더 큰 분기에 보상을 주어 궤적 생성에 더 많은 유연성을 제공합니다.
   최소 휴리스틱 점수를 가진 분기가 하류 계획에 선택됩니다.

B. 시간 예측을 위한 전이 강화 학습 (TRL)
학습된 시간 예측기는 하위 목표 웨이포인트 간 이동에 필요한 이산 시간 단계 수를 추정합니다. 다양한 지도 규모와 레이아웃에 걸쳐 시간적 일관성을 보장하기 위해, 예측기는 표준 점별 회귀 대신 전이 강화 학습 (TRL) 을 사용하여 훈련됩니다.

• 메커니즘: TRL은 예측된 단계 길이가 훈련 데이터가 시사하는 상대적 순서를 유지하도록 강제합니다. 만약 궤적 $i$가 기준 진실에서 궤적 $j$보다 더 오래 걸린다면, 모델은 $\hat{\Delta t}_i > \hat{\Delta t}_j$를 예측해야 합니다.
• 손실 함수: 훈련 목적 함수는 $L_1$ 회귀 손실과 전이 순서 제약 위반에 패널티를 부여하는 마진 기반 순위 손실 ($L_{TRL}$) 을 결합합니다. 이는 시간 추정치의 전역 보정을 개선합니다.

C. 지도 조건부 트랜스포머 궤적 생성기
최종 궤적은 다음에 조건부인 자기회귀 트랜스포머를 사용하여 합성됩니다:

• 지도 토큰: 인코딩된 이진 미로 지도 $M$ 및 영역 설명자.
• 시간 토큰: 선택된 STL 분기에서 파생된 시간 간격.
• 궤적 접두사: 현재 상태 역사.
  모델은 토큰 단위 (상태 단위) 로 궤적을 생성합니다. 훈련 중 노출 편향을 완화하기 위해, 기준 진실 상태를 사용하는 교사 강제에서 모델 예측을 사용하는 자기회귀 생성으로 점진적으로 전환하는 스케줄링 샘플링이 사용됩니다. 생성기는 동역학 무관하며,这意味着 추론 시 명시적인 동역학 모델 매개변수를 받지 않습니다.

3. 주요 기여

1. 휴리스틱 이산 처리: 실현 불가능한 논리적 경로를 피함으로써 실제적으로 해결 가능한 STL 명세의 범위를 크게 확장하는 경량 3 기준 휴리스틱을 통한 이산 분기 선택 도입.
2. 가변 지도에서의 제로샷 계획: 재학습 없이 보지 못한 장애물 레이아웃과 지도 크기에 일반화되는 지도 조건부 트랜스포머 궤적 생성기 개발로 STL 해결의 보편성 향상.
3. 시간적 근거를 위한 전이 강화 학습: 분해된 하위 작업 전반에 걸쳐 일관된 시간 할당을 보장하고 전체 STL 만족 강건성을 개선하기 위해 시간 예측기 훈련에 TRL 적용.
4. 실증적 검증: 다양한 환경 (변화하는 지도 복잡성) 과 동역학 (이중 적분기 및 단륜 모델) 에서 일관된 성능 향상을 입증하여 분포 변화에 대한 프레임워크의 강건성 검증.

4. 실험 결과

실험은 $5\times5$, $7\times7$, $9\times9$ 크기의 지도를 가진 그리드 기반 내비게이션 벤치마크 (U-Maze 계열) 에서 이중 적분기 (DI) 및 단륜 (UNI) 동역학 하에 수행되었습니다.

• 성공률: 제안된 방법은 휴리스틱 분기 선택이 없는 기준선 (동일한 방법) 에 비해 성공률에서 일관된 개선을 달성했습니다. 성취는 더 크고 복잡한 지도 (예: $9\times9$) 에서 가장 두드러졌으며, 여기서 휴리스틱이 실현 불가능한 분기를 효과적으로 가지치기했습니다.
• 강건성: 강건성 값 (STL 만족의 정량적 측정) 은 기준선과 비슷하거나 초과하여, 더 높은 성공률이 명세 마진을 희생함으로써 달성되지 않았음을 나타냅니다.
• 효율성: 명목상 계획 시간은 기준선과 비슷했지만, 휴리스틱 선택의 포함은 검색 공간을 초기에 가지치기함으로써 실제 계획 시간을 크게 단축했습니다.
• 일반화: 궤적 생성기는 명시적인 동역학 모델 입력 없이 DI 및 UNI 동역학 모두에 대해 실현 가능한 궤적을 성공적으로 합성하여 운동 모델 간 강력한 전이 능력을 입증했습니다.

5. 중요성과 주장

본 논문은 동적이고 알려지지 않은 환경에서 형식적 논리 추론과 데이터 기반 궤적 합성 간의 격차를 해소하는 데 주요 중요성이 있다고 주장합니다. 휴리스틱을 통한 고수준 논리적 분기와 트랜스포머를 통한 저수준 기하학적 실현을 분리함으로써, 이 프레임워크는 가변 지도 기하학과 복잡한 이산 논리에 직면했을 때 기존 제로샷 계획기의 취약성을 해결합니다.

저자들은 그들의 접근 방식이 환경별 재학습이 필요하지 않은 확장 가능한 제로샷 솔루션을 제공한다고 강조하며, 지도와 장애물이 예측 불가능하게 변화하는 실제 시나리오에서 STL 기반 계획기를 배포하는 데 유망한 방향이라고 말합니다. TRL 의 통합은 학습된 계획기의 시간적 일관성을 개선하는 혁신적인 방법으로 강조되며, 이는 장기 시간 제약 조건을 만족시키는 데 있어 결정적인 요소입니다.