Feasibility Restoration under Conflicting STL Specifications with Pareto-Optimal Refinement

이 논문은 상충하는 신호 시간 논리 (STL) 명세 하에서 자율 주행과 같은 안전-중요 시스템의 고정을 방지하고 해석 가능한 의사결정을 가능하게 하기 위해, 최소 완화로 실현 가능성을 복원한 후 가치 인식 다목적 최적화를 통해 파레토 최적 해를 도출하는 통합 2 단계 프레임워크를 제안합니다.

핵심

이 논문은 자율주행 자동차가 "모든 규칙을 지키면서" 길을 갈 수 없을 때, 어떻게 현명하게 결정을 내리는지에 대한 이야기를 담고 있습니다.

기존의 자율주행 시스템은 "모든 규칙을 100% 지켜야 한다"는 원칙을 고수하다가, 규칙들이 서로 충돌하면 (예: "구급차를 막지 마라" vs "보행자를 치지 마라") 아무것도 못 하고 멈춰 서버리는 (Deadlock) 문제가 있었습니다. 마치 "왼쪽으로 가도 안 되고, 오른쪽으로 가도 안 되니 그냥 서 있는 것" 같은 상황입니다.

이 논문은 그 문제를 해결하기 위해 두 단계로 이루어진 똑똑한 의사결정 시스템을 제안합니다.

---

🚗 비유: "혼란스러운 교차로에서의 택시 기사"

자율주행차를 운전 실력이 좋은 택시 기사라고 상상해 보세요. 그는 손님을 목적지로 데려가야 하고 (목표), 보행자를 보호해야 하며 (안전), 구급차가 지나가면 길을 비켜줘야 합니다 (규칙).

하지만 갑자기 보행자가 건너오는데, 뒤에는 구급차가 급하게 다가오고, 길은 좁아서 멈출 공간도 없습니다. 모든 규칙을 동시에 지키는 것은 물리적으로 불가능합니다.

1 단계: "최소한의 타협으로 길을 열다" (Feasibility Restoration)

기존 시스템은 "어차피 다 지키기 힘들어"라고 생각하며 차를 멈추고 버텼을 것입니다. 하지만 이 논문의 시스템은 이렇게 말합니다.

"모든 규칙을 완벽하게 지키는 건 불가능해. 하지만 **가장 중요한 안전 규칙 (보행자나 차에 부딪히지 않기)**은 절대 어기지 않고, **상대적으로 덜 중요한 규칙 (예: 차선 유지)**만 아주 조금만 어기자. 그래야 차가 멈추지 않고 움직일 수 있어."

이 단계에서는 **가장 적은 비용 (가장 적은 규칙 위반)**으로 차가 움직일 수 있는 '최소한의 해결책'을 찾습니다. 마치 "보행자를 피하기 위해 차선을 살짝 넘어서는 것"처럼, 최소한의 타협으로 길을 엽니다.

2 단계: "가장 현명한 선택을 고르다" (Pareto-Optimal Refinement)

1 단계에서 "차선이 살짝 어겨도 움직일 수 있는 방법"을 찾았다고 해서, 그게 가장 좋은 방법일까요? 아닐 수도 있습니다.

• 방법 A: 보행자를 피하기 위해 급정거. (보행자는 안전하지만, 뒤따라오던 구급차가 들이받을 위험이 큼)
• 방법 B: 보행자를 피하기 위해 살짝 차선을 넘어서서 천천히 우회. (보행자도 안전하고, 구급차도 지나갈 수 있음)

이 논문은 1 단계에서 찾은 여러 가지 "움직일 수 있는 방법들"을 나열한 뒤, 어떤 방법이 가장 현명한지 비교합니다. 이를 **'파레토 최적 (Pareto-Optimal)'**이라고 하는데, 쉽게 말해 **"어떤 것을 더 좋게 하려면 다른 것을 더 나빠지게 해야 하는, 그중에서 가장 균형 잡힌 선택지"**를 찾는 과정입니다.

비유: "음식을 고를 때, '맛'과 '건강' 두 가지가 충돌할 때, 단순히 '맛만 좋은 것'이나 '건강만 좋은 것'을 고르는 게 아니라, **'맛과 건강의 균형이 가장 좋은 메뉴'**를 찾아내는 것"과 같습니다.

이 과정을 통해 시스템은 "왜 이 길을 선택했는지"를 설명할 수 있게 됩니다. "보행자를 보호하기 위해 차선을 살짝 넘었지만, 구급차와의 충돌 위험은 최소화했습니다"라고 설명할 수 있는 거죠.

---

🌟 이 기술의 핵심 장점

1. 멈추지 않음 (No Freezing): 규칙이 충돌해도 차가 얼어붙지 않고, 최소한의 타협으로 움직입니다.
2. 현명한 선택 (Smart Trade-off): 단순히 "움직이는 것"만 찾는 게 아니라, "가장 안전한 움직이는 방법"을 찾습니다.
3. 이해 가능한 결정 (Interpretable): 왜 이 길을 선택했는지, 다른 선택지들은 왜 버렸는지를 명확하게 보여줍니다. (예: "차선을 넘지 않고 멈추면 구급차를 막게 되니, 차선을 살짝 넘어서 우회하는 게 더 안전합니다")

📝 요약

이 논문은 **자율주행차가 "모든 규칙을 지키는 신"이 아니라, "상황에 따라 현명하게 타협하는 인간 같은 운전자"**가 되도록 돕는 기술을 개발했습니다.

• 문제: 규칙이 서로 충돌하면 차가 멈춰서 위험해짐.
• 해결:
  1. 1 단계: 가장 중요한 안전 규칙은 지키고, 나머지는 아주 조금만 어겨서 차를 움직이게 함.
  2. 2 단계: 여러 가지 움직이는 방법 중, 위험과 규칙 위반의 균형을 가장 잘 맞춘 '최고의 선택'을 골라냄.

이 기술은 자율주행차가 복잡한 도시 환경에서도 안전하면서도 유연하게 움직일 수 있게 해줍니다.

기술 요약

1. 문제 정의 (Problem Statement)

• 배경: 신호 시간 논리 (Signal Temporal Logic, STL) 는 로봇 공학 및 자율 주행 시스템에서 시공간적 요구사항을 명시하는 강력한 형식 언어입니다. STL 의 정량적 강건성 (Quantitative Robustness) semantics 는 최적화 기반 제어 (예: MPC) 와 통합하기 용이합니다.
• 핵심 문제: 실제 환경에서는 안전 규칙, 교통 규정, 작업 목표 등 서로 다른 STL 명세들이 상충 (Conflict) 하여 동시에 만족할 수 없는 상황이 발생합니다.
  • 예: 구급차 양보, 중앙선 침범 금지, 장애물과의 안전 거리 유지 등 세 가지 요구사항이 좁은 도로에서 동시에 충족 불가능.
• 기존 접근법의 한계: 전통적인 STL 제약 MPC 는 명세 충돌 시 최적화 문제가 실현 불가능 (Infeasible) 해지며, 시스템은 보수적인 '정지 (Freezing)' 또는 대기 모드로 전환됩니다. 이는 안전-중요 (Safety-critical) 시나리오에서 오히려 위험을 증가시키고 (예: 구급차 길 막기), 교통 흐름을 방해하는 '데드락'을 유발합니다.
• 목표: 명세 충돌 시 시스템이 정지하지 않고, 최소한의 위반 (Minimal Relaxation) 으로 실현 가능성을 복원한 후, 다양한 대안 간의 트레이드오프 (Tradeoff) 를 명시적으로 분석하여 해석 가능한 결정을 내리는 프레임워크 개발.

2. 제안 방법론 (Methodology)

저자들은 2 단계 통합 프레임워크를 제안합니다.

1 단계: 최소 완화 기반 실현 가능성 복원 (Minimal-Relaxation Feasibility Restoration)

• 목표: 현재 상황에서 명세 집합이 충돌하여 MPC 가 해를 찾을 수 없을 때, 협상 가능한 명세 (Negotiable Specifications, $\Phi_S$) 만을 최소한으로 완화하여 해를 구합니다. 비협상 가능 안전 명세 (Non-negotiable Safety Constraints, $\Phi_H$) 는 엄격하게 유지합니다.
• 수식적 접근:
  • 각 협상 가능 명세 $\phi \in \Phi_S$ 에 대해 완화 변수 $\delta_\phi \ge 0$ 를 도입합니다.
  • 강건성 제약을 $\rho_\phi(x) \ge -\delta_\phi$ 로 완화합니다.
  • 목적 함수: 완화 변수들의 $L_1$ 노름 ($\|\delta\|_1$) 을 최소화하여, 실현 가능성을 되찾기 위해 필요한 최소 총 위반 수준 ($\Delta_{min}$) 을 계산합니다.
  • 이를 통해 로봇이 '정지'하는 대신, 최소한의 규칙 위반으로 움직일 수 있는 기본 해 (Baseline) 를 확보합니다.

2 단계: 가치 인식 파레토 최적 정제 (Value-Aware Pareto-Optimal Refinement)

• 목표: 1 단계에서 복원된 해는 유일하지 않을 수 있으며, 다양한 완화 배분이 서로 다른 결과 (위험, 효율성 등) 를 초래할 수 있습니다. 이 단계에서는 상충되는 목표 간의 트레이드오프를 체계적으로 탐색합니다.
• 가상 시나리오 분석 (Counterfactual Analysis):
  • 동일한 맥락에서 다른 완화 배분 ($\delta$) 과 제어 시퀀스 ($u$) 가 초래하는 결과를 다목적 함수 $g(u, \delta)$ (예: 충돌 확률, 충돌 심각도, 취약성 등) 로 평가합니다.
  • 허용 가능한 완화 예산 ($\Delta_{min} \le \|\delta\|_1 \le \Delta_{min} + \alpha$) 내에서 파레토 프론트 (Pareto Front) 를 근사화합니다.
• 알고리즘:
  • $\epsilon$-제약법 (Epsilon-constraint method) 을 사용하여 다목적 최적화 문제를 일련의 단일 목적 하위 문제로 변환합니다.
  • 각 목적 함수에 대한 상한 ($\epsilon$) 을 설정하고 해를 탐색한 후, 우세 관계 (Dominance) 를 통해 비우세 (Non-dominated) 인 해 집합인 파레토 집합을 추출합니다.
  • 이를 통해 "어떤 규칙 위반을 감수하면 어떤 위험이 줄어드는가"에 대한 해석 가능한 의사결정 지원을 제공합니다.

3. 주요 기여 (Key Contributions)

1. 최소 위반 기반 실현 가능성 복원 메커니즘: $L_1$-노름 최소화를 기반으로 협상 가능 명세만 최소한으로 완화하여 MPC 의 실현 가능성을 복원합니다. 이는 로봇의 '정지'를 방지하고 최소 편차 행동을 유도합니다.
2. 가치 인식 정제 및 파레토 프론트 근사: 복원된 해를 기반으로 $\epsilon$-제약법을 통해 파레토 프론트를 근사화합니다. 이를 통해 경쟁하는 목표 간의 체계적인 트레이드오프 분석과 대안 행동에 대한 가상 시나리오 (Counterfactual) 추론이 가능해집니다.
3. 자율 주행 사례 연구를 통한 검증: 상충되는 명세 하에서 자율 주행 시나리오를 통해 제안된 방법의 유효성을 입증했습니다.

4. 실험 결과 (Results)

두 가지 자율 주행 시나리오를 통해 검증되었습니다.

• 실험 1: 교차로에서의 구급차 통과 vs 보행자 우선권

  • 상황: 구급차를 막지 않으려면 교차로로 진입해야 하지만, 갑자기 나타난 보행자와 충돌 위험이 존재함.
  • 결과: 1 단계만 수행하면 실현 가능한 해가 나오지만, 위험 분포가 비효율적일 수 있음 (예: 보행자는 피했으나 급제동으로 구급차 추돌 위험 증가).
  • 2 단계 효과: 파레토 최적 해를 선택함으로써 보행자와 구급차 모두에 대한 위험을 균형 있게 줄이는 (서서히 감속하며 좌회전하는 등) 최적의 행동을 도출했습니다.

• 실험 2: 통제 불능 후방 차량 및 비상 차선 침범

  • 상황: 후방에서 통제 불능 차량이 접근하여 추돌 위험이 발생. 비상 차선 침범 (규칙 위반) 을 통해 회피해야 함.
  • 결과: 1 단계 (최소 완화) 는 규칙 위반을 최소화하는 방향으로 해를 찾지만, 이는 후방 추돌 위험을 충분히 줄이지 못할 수 있음.
  • 2 단계 효과: 파레토 정제를 통해 비상 차선 침범 정도를 약간 늘리는 대신 후방 추돌 위험을 크게 낮추는 대안을 선택했습니다. 이는 위험 최소화를 위해 규칙 위반을 의도적으로 재분배하는 것을 보여줍니다.

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

• 안전-중요 자율 시스템의 실용성: 명세 충돌 시 시스템이 마비 (Deadlock) 되지 않고, 원칙 있는 타협 (Principled Compromise) 을 통해 계속 작동할 수 있게 합니다.
• 해석 가능한 의사결정 (Interpretable Decision-making): 단순히 "무엇을 할 것인가"뿐만 아니라, "왜 그 행동을 선택했고, 어떤 대안은 기각되었는지"에 대한 명확한 근거 (파레토 프론트 상의 위치) 를 제공합니다. 이는 안전-중요 시스템의 신뢰성 확보에 필수적입니다.
• 미래 전망: 실시간 성능 향상을 위한 파레토 프론트 근사 효율화, 비우세 집합 내 선택 정책 학습, 불확실성 모델 및 다중 에이전트 상호작용으로의 확장 등이 향후 과제로 제시되었습니다.

요약하자면, 이 논문은 STL 기반 제어 시스템이 명세 충돌로 인해 멈추는 문제를 해결하기 위해, 최소 위반으로 해를 구한 후 (Stage 1), 다양한 대안 간의 위험과 성능 트레이드오프를 파레토 최적화를 통해 분석하여 (Stage 2) 가장 합리적인 결정을 내리는 체계를 제안했습니다.