Feasibility Analysis and Constraint Selection in Optimization-Based Controllers

1. 문제 정의 (Problem Definition)

자율 시스템의 안전하고 신뢰할 수 있는 제어를 위해서는 **제약 조건 하의 최적화 문제 (Constrained Optimization Problem)**를 해결하는 것이 필수적입니다. 특히 모델 예측 제어 (MPC) 나 제어 장벽 함수 (CBF) 와 같은 최적화 기반 제어기는 매 시간 단계마다 제어 입력을 계산하기 위해 제약 조건을 만족하는 해를 찾아야 합니다.

• 핵심 문제: 여러 개의 제약 조건 (하드 제약과 소프트 제약) 이 동시에 존재할 때, 최적화 문제가 **실현 불가능 (Infeasible)**해지는 경우가 빈번하게 발생합니다.
• 기존 방법의 한계:
  • 기존 연구들은 제약 조건을 완화 (Relaxation) 하거나 슬랙 변수 (Slack variables) 를 도입하여 문제를 해결하려 했습니다. 그러나 이는 문제의 크기를 증가시키고, 최대 실현 가능 부분 집합 (Maximal Feasible Subset, maxFS) 을 보장하지 못하며, 제약 위반의 정도와 어떤 제약이 유지되는지 사이의 관계를 명확히 분리하지 못합니다.
  • Lagrange 승수 (Lagrange Multipliers) 에 기반한 기존 방법들은 실현 가능성과 비실현 가능성 사이의 명확한 '경계'를 제공하지 못해, 시스템이 비실현 가능성에 얼마나 가까운지 정량화하기 어렵습니다.

2. 방법론 (Methodology)

이 논문은 선형 제약 조건 집합에 대한 **필요충분 조건 (Necessary and Sufficient Conditions)**을 기반으로 한 새로운 이론적 분석 프레임워크를 제시합니다.

A. 실현 가능성 분석 (Feasibility Analysis)

• Farkas' Lemma 와 쌍대 문제 (Dual Problem) 활용:
  • 선형 제약 조건 집합 $A^T u \le B$의 실현 가능성 (해의 존재 여부) 을 판별하기 위해 Farkas' Lemma 를 기반으로 한 선형 계획법 (LP) 문제를 도출했습니다.
  • 기존 연구 [21] 에서 QP(2 차 계획법) 에 국한되었던 결과를 일반화하여, 비용 함수의 구조와 무관하게 선형 제약 조건 자체의 실현 가능성을 판단할 수 있음을 증명했습니다.
• 극성 원뿔 (Polar Cone) 기반 기준:
  • null space basis ($N_A$) 를 사용하여 문제를 변환하고, **극성 원뿔 (Polar Cone, $N_C$)**의 개념을 도입했습니다.
  • 벡터 $B_A = N_A^T B$가 극성 원뿔 $N_C$ 내부에 있으면 제약 조건 집합은 실현 가능합니다.
  • $\nu^*$ (뉴-스타) 변수: 새로운 LP 문제 (식 11*) 를 통해 $\nu^*$를 계산합니다. $\nu^*$의 각 성분은 해당 제약 조건이 실현 가능성에 기여하는 정도를 정량화합니다.
    • enforced(강제) 제약 조건에서 $\nu^*$ 값이 작을수록 해당 제약이 실현 불가능성을 유발할 가능성이 높음 (극성 원뿔의 경계에 가까움).
    • disregarded(무시) 제약 조건에서 $\nu^*$ 값이 0 에 가까울수록 해당 제약이 실현 가능할 가능성이 높음.

B. 온라인 제약 조건 선택 알고리즘 (Online Constraint Selection)

실시간으로 실현 가능한 제약 조건 집합을 선택하기 위해 두 가지 알고리즘을 제안했습니다.

1. 반복적 제약 조건 추가 (Iterative Constraint Addition, Alg. 2):

   • 현재 실현 가능한 구성 (Configuration) 에서 시작하여, LP 해 ($\nu^*$) 에서 양수인 성분에 해당하는 무시된 제약 조건들을 순차적으로 추가합니다.
   • 장점: 계산 효율성이 높음.
   • 단점: 지역 최적해 (Local Optima) 에 빠질 수 있으며, 초기 실현 가능 구성에 의존적입니다.

2. 지역 탐색 (Local Search, Alg. 3):

   • 현재 구성이 실현 불가능할 때, $\nu^*$ 값이 가장 작은 (실현 가능성에 가장 큰 위협이 되는) 강제 제약 조건들을 하나씩 제거하거나, 무시된 제약 조건들을 하나씩 추가하여 탐색합니다.
   • 검색 깊이 (Search Depth, $D$): 사용자가 정의한 깊이만큼 탐색하여 더 큰 실현 가능 집합을 찾을 수 있습니다.
   • 장점: 지역 최적해를 탈출하여 더 많은 제약 조건을 만족하는 해를 찾을 수 있음.
   • 단점: Alg. 2 에 비해 계산 비용이 증가함 (하지만 여전히 기존 방법보다 효율적).

3. 주요 기여 (Key Contributions)

1. 새로운 이론적 분석: 선형 제약 조건 집합의 실현 가능성에 대한 필요충분 조건을 도출했습니다. 이는 Lagrange 승수의 발산 여부가 아닌, **변수의 부호 (Sign)**와 극성 원뿔 내 위치에 기반하여 실현 가능성과 비실현 가능성 사이의 명확한 경계를 제공합니다.
2. 슬랙 변수 없는 LP 기반 접근: 기존 방법들이 필요로 했던 슬랙 변수 (Relaxation variables) 를 사용하지 않고, 순수한 LP 문제를 통해 실현 가능성을 판단하고 제약 조건을 선택합니다. 이는 문제의 크기를 줄이고 계산 효율성을 높입니다.
3. 정량적 지표 제공: $\nu^*$ 변수를 통해 각 제약 조건이 실현 불가능성에 미치는 영향을 정량화하여, 어떤 제약 조건을 우선적으로 유지하거나 제거해야 할지 체계적으로 결정할 수 있는 기준을 마련했습니다.
4. 온라인 제어 적용: 제안된 분석을 기반으로 동적 시스템의 제어 시 실시간으로 실현 가능한 제약 조건 집합을 선택하는 알고리즘을 개발했습니다.

4. 시뮬레이션 결과 (Results)

로봇의 경로 계획 및 장애물 회피 시나리오 (정적/동적 장애물 포함) 를 통해 제안된 알고리즘 (Alg. 2, Alg. 3) 을 기존 방법 (Chinneck 알고리즘, Lagrange 승수 기반 휴리스틱) 과 비교 평가했습니다.

• 성능 (제약 조건 무시 비율): 제안된 알고리즘들은 기존 방법들 (Baseline 1, 2) 과 유사하거나 더 나은 성능을 보였습니다. 특히 Baseline 2 에 비해 무시되는 소프트 제약 조건의 비율이 현저히 낮았습니다.
• 계산 시간:
  • 제안된 알고리즘들은 평균 계산 시간이 Baseline 1 과 비슷하거나 약간 느리지만, **최대 계산 시간 (Worst-case)**은 Baseline 1 보다 훨씬 짧고 안정적입니다.
  • Baseline 1 은 문제 크기가 커질수록 계산 시간 스파이크가 빈번하게 발생했으나, 제안된 방법은 모든 문제 크기에서 0.07 초 이하로 일관된 성능을 유지했습니다.
• 확장성: 제안된 방법은 $m$개의 결정 변수만 사용하는 LP 를 푸는 반면, 기존 슬랙 변수 기반 방법은 $n_s + m$개의 변수를 필요로 합니다. 이로 인해 제약 조건 수가 증가할 때 제안된 방법이 더 우아하게 확장됩니다.

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

이 논문은 최적화 기반 제어기에서 발생하는 실현 불가능성 (Infeasibility) 문제를 해결하기 위한 이론적 토대와 실용적인 알고리즘을 제공합니다.

• 안전성 및 신뢰성 향상: 시스템이 비실현 가능성에 직면했을 때, 임의의 제약 조건을 완화하는 것이 아니라, 이론적으로 검증된 기준에 따라 최소한의 제약 조건만 제거하거나 유지함으로써 시스템의 안전성과 성능을 극대화합니다.
• 실시간 적용 가능성: 계산 복잡도가 낮고 최대 계산 시간이 일정하게 유지되므로, 실시간 자율 시스템 (드론, 자율 주행 차량 등) 에 적용하기에 매우 적합합니다.
• 미래 연구 방향: 제안된 이론적 프레임워크는 최대 실현 가능 집합 (maxFS) 문제, 실현 가능 공간 모니터링, 그리고 적응형 제어기 설계 등 다양한 분야로 확장될 수 있는 잠재력을 가지고 있습니다.

요약하자면, 이 연구는 제약 조건 완화 없이도 실현 가능성을 정밀하게 분석하고 최적의 제약 조건 집합을 선택할 수 있는 새로운 수학적 도구를 제시함으로써, 자율 시스템의 안전하고 효율적인 제어에 중요한 기여를 했습니다.