659.11 변환 트리의 순환 (Cycle) 방지

1. 순환의 정의

변환 트리에서 순환(cycle)은 하나의 프레임에서 출발하여 부모-자식 관계를 따라 경로를 추적하였을 때, 다시 원래의 프레임으로 돌아오는 경로가 존재하는 상태를 말한다. 그래프 이론의 관점에서, 순환이 존재하는 그래프는 더 이상 트리(tree)가 아니며 일반적인 그래프(graph)가 된다.

형식적으로, 프레임 $f_0$ 에서 시작하여 변환 경로 $f_0 \to f_1 \to f_2 \to \cdots \to f_k$ 가 존재하고 $f_k = f_0$ 인 경우, 이 경로는 순환을 구성한다.

2. TF2에서 순환이 금지되는 이유

2.1 경로 유일성의 붕괴

트리 구조에서는 임의의 두 노드 간의 경로가 유일하게 결정된다. 순환이 존재하면 두 프레임 간에 서로 다른 경로가 존재할 수 있으며, 각 경로를 통해 계산된 변환이 서로 다른 결과를 산출할 수 있다. 이는 좌표 변환의 일관성(consistency)을 근본적으로 파괴한다.

2.2 무한 루프의 위험

순환이 존재하면, 경로 탐색 알고리즘이 순환 경로를 무한히 반복하여 무한 루프(infinite loop)에 빠질 위험이 있다. TF2의 BufferCore가 사용하는 최저 공통 조상(LCA) 기반 경로 탐색 알고리즘은 트리 구조를 전제로 설계되었으므로, 순환이 존재하면 알고리즘의 종료가 보장되지 않는다.

2.3 변환의 불확정성

순환 경로를 따라 변환을 합성하면, 항등 변환(identity transform)이 되어야 물리적으로 의미가 있다. 그러나 실제 시스템에서 각 변환에는 센서 노이즈, 캘리브레이션 오차 등에 의한 오차가 포함되므로, 순환 경로의 합성 변환은 항등 변환과 일치하지 않는다.

${}^{f_0}T_{f_1} \cdot {}^{f_1}T_{f_2} \cdot \cdots \cdot {}^{f_{k-1}}T_{f_0} \neq I_4$

이러한 불일치는 좌표 변환 결과가 경로에 따라 달라지는 모호성을 야기한다.

3. TF2의 순환 감지 메커니즘

3.1 부모 재할당 감지

TF2의 BufferCore는 새로운 변환이 입력될 때, 해당 자식 프레임에 이미 다른 부모 프레임이 할당되어 있는지 확인한다. 동일한 자식 프레임에 대해 서로 다른 부모 프레임이 발행되면, 이는 단일 부모 규칙의 위반이자 잠재적 순환의 원인이 될 수 있다.

이 경우 TF2는 기존 부모를 새로운 부모로 교체하며, 다음과 같은 경고 메시지를 출력한다.

[WARN] [tf2]: TF_OLD_DATA ignoring data from the past for frame "child_frame"

3.2 경로 탐색 중 순환 검출

BufferCore의 내부 경로 탐색 알고리즘은 프레임에서 루트까지의 조상 경로를 추적하는 과정에서, 이미 방문한 프레임을 다시 방문하는지 확인하여 순환을 검출한다. 순환이 검출되면 ConnectivityException 또는 관련 오류 메시지가 발생한다.

4. 순환이 발생하는 일반적 시나리오

4.1 시나리오 1: 양방향 변환 발행

두 개의 독립적인 노드가 동일한 프레임 쌍에 대해 서로 반대 방향의 변환을 발행하는 경우이다.

# 노드 A가 발행:
header.frame_id = "frame_a"
child_frame_id = "frame_b"

# 노드 B가 발행:
header.frame_id = "frame_b"
child_frame_id = "frame_a"

이 경우 frame_a → frame_b → frame_a의 순환이 형성된다. TF2에서는 단일 부모 규칙에 의해 frame_a의 부모가 frame_b로 재할당되면서, 기존의 frame_a → frame_b 변환이 무효화된다.

4.2 시나리오 2: 간접적 순환

세 개 이상의 프레임이 관여하는 간접적 순환이다.

# 노드 A: frame_a → frame_b
# 노드 B: frame_b → frame_c
# 노드 C: frame_c → frame_a  (순환 형성)

이 경우 frame_a → frame_b → frame_c → frame_a의 순환이 형성되며, 어떤 프레임에서 시작하든 원점으로 돌아오는 경로가 존재한다.

4.3 시나리오 3: 검출 루프와 위치 추정

특정 위치 추정 시스템에서, 센서 데이터를 기반으로 계산된 변환이 기존 변환 트리의 프레임을 횡단하여 연결되는 경우에 간접적 순환이 발생할 수 있다. 예를 들어, 카메라 기반 위치 추정 노드가 camera_frame → map 변환을 직접 발행하면서, 동시에 map → odom → base_link → camera_frame 경로가 존재하면 순환이 형성된다.

올바른 해결 방법은 카메라 기반 위치 추정 결과를 map → odom 변환의 갱신으로 반영하는 것이다.

5. 순환 방지 설계 원칙

5.1 원칙 1: 단일 발행자 원칙

각 프레임 쌍의 부모-자식 변환은 단일 노드에 의해서만 발행되어야 한다. 동일한 자식 프레임에 대해 여러 노드가 변환을 발행하면 부모 충돌과 잠재적 순환이 발생한다.

5.2 원칙 2: 변환 방향의 일관성

변환 트리에서 엣지의 방향은 항상 루트에서 말단으로의 하향(downward) 방향이어야 한다. 위치 추정이나 센서 융합의 결과로 상향(upward) 방향의 변환이 필요한 경우에는, 기존 트리 구조 내에서 적절한 위치의 변환을 갱신하는 방식으로 처리해야 한다.

5.3 원칙 3: 표준 프레임 체인 준수

ROS2의 표준 프레임 체인(earth → map → odom → base_link)을 따르고, 각 변환의 발행 책임을 명확하게 분리하면 순환 발생을 구조적으로 방지할 수 있다.

5.4 원칙 4: `view_frames` 정기 검증

시스템의 변환 트리를 view_frames 도구로 정기적으로 시각화하여, 의도하지 않은 연결이나 순환이 형성되지 않았는지 검증해야 한다.

ros2 run tf2_tools view_frames

생성된 PDF 파일에서 트리의 구조가 예상과 일치하는지, 특히 각 프레임의 부모가 올바르게 설정되어 있는지 확인한다.

6. 닫힌 운동학적 체인과의 관계

로봇 공학에서 닫힌 운동학적 체인(closed kinematic chain)은 물리적으로 존재하는 구조이다. 예를 들어, 평행 링크 메커니즘(parallel linkage mechanism)이나 스튜어트 플랫폼(Stewart platform)은 닫힌 체인 구조를 가진다.

TF2는 트리 구조만 지원하므로, 닫힌 운동학적 체인을 직접 표현할 수 없다. 이러한 경우에는 닫힌 체인의 한 부분을 개방(open)하여 트리 구조로 변환하거나, 가상의 중간 프레임을 도입하여 트리 구조를 유지하면서 닫힌 체인의 기구학적 제약을 별도의 계산 모듈에서 처리하는 방법을 사용한다.

참고 문헌 및 출처:

Foote, T., “tf: The transform library,” 2013 IEEE Conference on Technologies for Practical Robot Applications (TePRA), pp. 1-6, 2013.
Open Robotics, “tf2 — ROS 2 Documentation,” ROS 2 Jazzy Jalisco, 2024.
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., Introduction to Algorithms, 4th ed., MIT Press, 2022.
Siciliano, B., Khatib, O., Springer Handbook of Robotics, 2nd ed., Springer, 2016.