27.4.2.2. 타임스탬프 기반 이진 탐색 알고리즘을 이용한 보간 데이터 추출 로직

27.4.2.2. 타임스탬프 기반 이진 탐색 알고리즘을 이용한 보간 데이터 추출 로직

1. 개요 (Introduction)

비행 제어기의 확장 칼만 필터(EKF2)가 센서 지연(Delay)을 보상하기 위해서는 과거 수십에서 수백 밀리초(ms) 전의 기체 상태를 정확히 복원해 내야만 한다. 앞서 살펴본 링 버퍼(Ring Buffer) 데이터 구조 안에는 고주파수(High-frequency)의 IMU 데이터와 파생된 이전 EKF 상태(State)들이 층수대로 빼곡히 적재되어 있다.

하지만, 거친 외부 통신을 거쳐 지연되어 도착한 관측치(예: M9N GPS 데이터) 내부에 찍혀있는 측정 타임스탬프(T_{target})와 링 버퍼에 이산적으로 저장된 데이터 노드들의 스냅샷 타임스탬프(T_n)가 1마이크로초(1 \mu s) 단위까지 정확히 일치할 확률은 사실상 거의 존재하지 않는다. 이 이산화된 디지털 샘플 간의 공백(Gap)을 현명하게 극복하기 위해, PX4 ECL(Estimation and Control Library) 링 버퍼 코어 클래스는 고속 이진 탐색(Binary Search) 과 선형 보간(Linear Interpolation) 이라는 수학적 기술을 융합하여 미지의 과거 찰나 상황을 가장 물리적으로 근접하게 유추해 내는 극강의 데이터 추출 로직을 보유하고 있다.

2. 시계열 데이터 파이프라인과 이진 탐색(Binary Search)의 결합

드론 비행 제어 루프를 담당하는 MCU(Micro Controller Unit)는 다수의 센서와 액추에이터 제어 명령을 초당 수백/수천 회의 숨 가쁜 틱(Tick)으로 소화해야 하므로, 배열 전체 처음부터 끝까지를 모조리 뒤지는 무식한 선형 탐색(O(N))은 스레드 스케줄링 사이클 관점에서 심각한 연산 지연 및 부하(Overhead)를 유발한다.

링 버퍼로 새로운 데이터가 push 될 때마다 고정밀 시스템 구동 시간(time_us)을 기준으로 무조건적인 오름차순 삽입이 보장된다는 대전제가 시스템에 성립한다. PX4 EKF 워커는 이 절대적인 시계열 정렬 특징을 십분 활용하여, 버퍼에서 과거 데이터를 빼내는 메서드(pop_first_older_than(target_timestamp))가 호출되면 버퍼 내부 배열 커서 안에서 \mathcal{O}(\log N)의 놀라운 숏컷 복잡도를 가지는 직관적인 이진 탐색 트리를 가동한다.

  1. 목표물 중심 근사(Center Probing): 할당된 전체 버퍼 배열의 인덱스 중간 지점을 찔러(Probe) 해당 노드 구조체의 타임스탬프와 목푯값 T_{target}을 1차 비교한다.
  2. 구간 축소(Halving Phase): 타겟 시간이 기준점보다 더 과거라면 절반의 왼쪽 배열 부분을, 최신이라면 오른쪽 배열 부분으로 이분화하여 재귀적 또는 반복적으로 탐색 범위를 즉각 절반으로 쳐내어 나간다.
  3. 타겟 경계 노드(Boundary Nodes)의 규합: 탐색 결과 정확히 타임스탬프 값이 일치하는 행운의 노드가 없다면, 알고리즘은 T_{target}을 앞뒤 포위망으로 감싸고 있는 가장 가까운 두 개의 이웃 배열 원소, 즉 직전 과거 노드(older\_sample)와 직후 미래 노드(newer\_sample)의 인덱스를 무사히 반환하며 탐색을 탈출한다.

3. 선형 보간(Linear Interpolation)의 수학적 추출 원리 규명

이진 탐색을 통해 찾아낸 앞뒤 두 샘플 시점 사이에 정확히 위치한 “진짜 타겟 미싱(Missing) 시간“의 상태 벡터 비례값을 도출하기 위해 공학적으로 매끄러운 선형 보간(Linear Interpolation) 공식이 개입한다.

두 구간 샘플을 각각 S_{old} (타임스탬프 t_0, 제어 벡터 값 v_0)와 S_{new} (타임스탬프 t_1, 제어 벡터 값 v_1)라고 하고, 우리가 EKF 융합을 위해 복원하고자 하는 진짜 타겟 과거 시간이 t_{target} (t_0 \le t_{target} \le t_1) 라면, 최종 도출되는 보간 가상 데이터 V_{target} 은 다음의 수리적 가중치(Weight) 공식으로 연산 시뮬레이션 된다.

\alpha = \frac{t_{target} - t_0}{t_1 - t_0}
V_{target} = v_0 + \alpha \times (v_1 - v_0)

여기서 분수 값 \alpha는 두 스냅샷 찰나 사이에서 타겟 시간이 위치한 물리적 시간 비율(Fraction Ratio, 0 \le \alpha \le 1)을 뜻한다. 이 선형 수식은 ARM Cortex-M 코어와 같은 임베디드 칩에서도 FPU(부동소수점 유닛)를 태워 매우 가볍고 직관적 처리된다. 또한 v가 단순한 스칼라 값이 아닌 IMU의 3축 방향 벡터(\Delta V, \Delta \theta)이거나 EKF의 거대한 24x24 상태 공분산 행렬(Covariance Matrix)이라 할지라도 독립된 각각의 행렬 성분(Element) 단위로 빠르게 병렬 분배 연산을 수행할 수 있는 장점을 갖는다.

4. 커널 로직의 실제 비행 적용 사이클 예시

단순히 추상적인 수식을 떠나, 구체적인 수치 예시를 통해 PX4 EKF2 모듈이 보간 데이터를 추출하는 찰나의 동작 방식을 분해 해부해 본다.

  • 비행 상황 가정: 비행 중 EKF가 200ms 통신 지연이 설정된 GPS 패킷 데이터를 방금 수신했다. 이 GPS 데이터에 찍힌 타임스탬프 절대 물리 측정 시표는 10050.0ms 이다.
  • 버퍼 내부 상황 파악: 현재 EKF 링 버퍼에는 IMU 적분 상태 리스트들이 10ms 이산 단위(100Hz 스토리지)로 빼곡히 들어있다. 탐색 결과 아쉽게도 제일 일치하는 10050ms 시점의 데이터는 존재하지 않고, 오직 10040ms (속도 값: 10.0 m/s) 노드와 10060ms (속도 값: 20.0 m/s) 샌드위치 노드군만이 존재한다.

추출 알고리즘 동작 4원칙 프로세스:

  1. Binary Search 진입: 이진 탐색으로 단 몇 번의 임베디드 메모리 참조(Reference Search) 만에 두 경계 노드 그룹(10040ms, 10060ms)을 배열 묶음에서 찾아낸다.
  2. 시간 분수 팩터(Alpha Matrix) 계산:
    \alpha = \frac{10050 - 10040}{10060 - 10040} = \frac{10}{20} = 0.5
  3. 선형 보간 수학식 적용:
    V_{target} = 10.0 + 0.5 \times (20.0 - 10.0) = 15.0
  4. 가상 결과 반환 및 융합: EKF는 이 보간 공식을 통해 생성된 매끄러운 복제 조각인 벡터 값 15.0을 “10050ms 경 과거 시점의 가장 신뢰할 만한 기체 상태“로 즉석 공식 확정 짓고, 이 배출된 가상 추정값과 수신된 GPS 진짜 측정치를 베이즈 혼합(Kalman Update Stage)하여 드디어 거대 혁신(Innovation) 오차를 도출하게 된다.

4.1 탐색 및 보간 알고리즘 구조도표 (Mermaid)

graph TD
    A[타임스탬프 Target Time 10050ms 쿼리 요청 발생] --> B{Binary Search Tree 고속 가동}
    B -->|Log N 탐색 복잡도 속도| C[결과 반환: Target을 감싸는 두 노드 검출 완료]
    C --> D(Older Node 구조체: 10040ms, Value: 10.0)
    C --> E(Newer Node 구조체: 10060ms, Value: 20.0)
    D --> F[시간 가중치 비율 Alpha: 0.5 연산 도출]
    E --> F
    F --> G[Linear Interpolate 수학적 수행 <br> Interpolated Value: 15.0 도출]
    G --> H[과거 시점 롤백용 EKF 가상 상태 객체로 배출 및 융합 돌입]

5. 설계 한계점 및 이벤트성 데이터(Event Data)의 예외 우회 로직 처리 방안

선형 보간 기법은 기체의 관성 매크로 움직임이나 누적 상태 벡터처럼 무한히 연속 함수적(Continuous Function)인 특성을 가지는 데이터에는 막강한 부드러움과 오버 샘플링 이상의 정밀도를 자아낸다. 그러나 상태 머신의 제어 플래그(Flag)나 접지 센서(Touchdown Event) 같은 이산적이거나 양자화된 디지털 이벤트(Discrete Event) 객체에는 결코 수학을 적용할 수 없다. (예를 들어: 착륙을 감지한 부울 플래그 true와 공중의 false 상태 사이 0.5 보간은 소프트웨어적으로는 컴파일조차 되지 않는 무의미함이며 거대한 버그를 낳는다).

때문에 PX4의 RingBuffer 템플릿 내부 보간 오버로딩(Overloading) 메서드 구조체 설계에서는 프로그래머의 지시에 따라 극명히 나뉜다. 템플릿 인스턴스화 규격에 따라 “연속 측정 데이터(Continuous Sensor Data)“는 선형 보간 모듈을 엄격히 태워 시스템에 넘겨주는 반면, 단순히 불리언(Boolean), 센서 고장 페일 플래그, 비행 모드 변경자 등의 “이벤트(Event)성 이산 데이터“를 요구할 경우에는 보간 공식을 완전히 패스(Bypass)하고, 타겟 타임스탬프와 제일 물리적으로 근접한 단일 스냅샷 노드(Nearest single node)의 프로퍼티를 그대로 돌려주고 끝맺는 방어 로직 스위치가 장착되어 있다.

이렇듯 무결점을 지향하며 마이크로초 단위의 집착을 보여주는 정밀 타임스탬프 기반 이진 탐색 공간 확보. 그리고 그를 둘러싼 적응형 분수 보간 로직이야말로, 이산 세계의 한계에 봉착한 임베디드 컴퓨터(Flight Controller) 하드웨어 위에서 부드러운 연속 공간 시간대계(Continuous Time Dynamic)의 진실성을 성공적으로 모사해 내는 PX4 EKF 추정기의 빛나는 다크매터 예술성이라 칭송할 수 있다.