기술 요약: SE(2) 내비게이션 메쉬 (SE(2) Navigation Mesh)

문제 정의

복잡한 다층 환경(예: 계단, 오버행, 좁은 통로가 있는 산업 시설)에서 지상 로봇의 글로벌 내비게이션은 통과 가능한 영역을 정확하게 포착하면서도 효율적인 경로 계획을 가능하게 하는 표현 방식이 필요합니다. 기존 방식들은 다음과 같은 중대한 한계에 직면해 있습니다:

• 포인트 클라우드 및 볼륨형 맵(예: 점유 격자(occupancy grids), TSDF)은 명시적인 표면 구조가 부족하여, 세밀한 통과 가능성 추정이 계산적으로 비용이 많이 들며 추가적인 기하학적 추론을 요구합니다.
• 조밀한 삼각형 메쉬(triangle meshes) 상에서의 직접적인 경로 탐색은 실시간 계획을 수행하기에는 계산 비용이 너무 높습니다.
• **고전적 내비게이션 메쉬(NavMeshes)**는 통과 가능한 영역을 볼록 다각형으로 추상화하지만, **요(yaw) 불변 통과성(yaw-invariant traversability)**을 가정합니다. 로봇을 원통형으로 근사하고 모든 헤딩(heading)에 대해 타당성을 요구함으로써, 비원형 로봇(예: 직사각형 형태의 보행 로봇)의 특정 제약 조건을 포착하지 못하며, 이로 인해 유효한 경로를 버리거나 다층 구조를 효과적으로 표현하지 못하는 경우가 발생합니다.

방법론

저자들은 **요 의존적 통과성(yaw-dependent traversability)**을 명시적으로 인코딩하는 폴리곤 표현법인 **SE(2) 내비게이션 메쉬(SE(2) NavMesh)**를 제안합니다. 이 시스템은 사전 구축된 맵으로부터의 오프라인 생성 모드와 스트리밍되는 포인트 클라우드로부터의 온라인 증분 생성 모드로 작동합니다.

1. 표현 방식: SE(2) NavMesh

본 방법은 고전적 NavMesh를 확장하여 메쉬 구성에 로봇의 요($\psi$)를 포함함으로써, 상태 공간 $X = M \times S^1$ (표면 $\times$ 방향)을 생성합니다.

• 로봇 모델: 고전적 NavMesh의 원통형 근사와 달리, 본 방법은 보행 로봇의 기하학적 형상을 더 잘 나타내기 위해 직육면체 근사(cuboid approximation)(길이, 너비, 높이)를 사용합니다.
• 요 채널(Yaw Channels): 연속적인 요 구간 $[0, 2\pi)$를 $N_\Psi$개의 채널로 이산화합니다.
• 풋프린트 마스크(Footprint Masks): 통과 가능성은 연속 요 풋프린트 마스크를 사용하여 평가됩니다. 이 마스크는 로봇 풋프린트가 특정 요 구간 동안 휩쓸고 지나가는 점유 영역의 합집합을 나타내며, 이를 통해 인접한 헤딩 사이의 안전한 회전을 보장합니다.
• 계층 구조: 통과 가능한 공간은 요별 통과성 레이어(layer, $L_i$)로 분할됩니다. 각 레이어는 특정 헤딩으로 로봇이 통과할 수 있는 영역을 포함합니다.
  • 안전 영역(Safe Regions): 모든 이산화된 요 각도에서 통과 가능합니다.
  • 제한 영역(Restricted Regions): 특정 부분 집합의 요 각도에서만 통과 가능합니다.
• 연결성: 내비게이션 그래프는 두 가지 유형의 에지를 포함합니다:
  • 병진 연결성(Translational Connectivity): 동일한 요 레이어 내의 영역 간 이동 (헤딩 변화 없이 이동).
  • 회전 연결성(Rotational Connectivity): 동일한 공간 위치에 있지만 서로 다른 요 레이어에 속한 레이어별 영역 간의 이동 (제자리 회전).

2. 생성 파이프라인

• 오프라인: 환경(삼각형 메쉬)을 복셀화(voxelize)합니다. 거리 맵(distance map)을 계산하여 로봇의 풋프린트와 통과 제약 조건(스텝 높이, 경사도)을 기준으로 복셀을 안전, 제한 또는 접근 불가로 분류합니다. 이후 워터셰드(watershed) 알고리즘을 통해 이 복셀들을 볼록 다각형으로 분할하며, 이들은 타일 간에 병합되어 글로벌 메쉬를 형성합니다.
• 온라인: 시스템은 포인트 클라우드로부터의 증분 기하 구조 재구성을 위해 Voxblox를 사용합니다. 실시간 성능을 유지하기 위해 업데이트는 **국소적(local)**으로 이루어집니다. 맵은 수직 **슬랩(slabs)**으로 나뉘며, 새로운 기하 구조의 영향을 받는 슬랩과 그 즉각적인 이웃 슬랩만 재처리됩니다. 이는 글로벌 재생성과 관련된 선형적인 지연 시간 증가를 방지합니다.

3. 경로 탐색 전략: ASA

저자들은 위치와 헤딩을 모두 최적화하기 위해 3단계 A-String Pulling-A(ASA)** 전략을 도입합니다.

1. 초기 탐색: 내비게이션 그래프 상의 A* 탐색을 통해 레이어별 영역 및 상태의 실행 가능한 시퀀스를 찾습니다.
2. 경로 직선화(Path Straightening): 스트링 풀링(string-pulling) 알고리즘을 사용하여 경로를 기하학적으로 정교화하여 지그재그 움직임을 제거하고, 영역 시퀀스에 의해 정의된 통로 내에서 직선화된 경로를 생성합니다.
3. 요 최적화(Yaw Refinement): 두 번째 A* 탐색을 통해 직선화된 경로를 따라 로봇의 헤딩을 최적화하여, 최종 궤적이 요 의존적 통과성 제약을 준수하도록 합니다.

주요 기여

1. SE(2) NavMesh 표현: 풋프린트 마스크와 레이어드 그래프 구조를 사용하여 요 의존적 타당성을 인코딩하는 새로운 폴리곤 표현법입니다. 이는 고전적 NavMesh보다 훨씬 더 많은 통과 가능 영역(특히 좁은 통로에서)을 포착합니다.
2. ASA 경로 탐색 전략: 기하학적 경로 직선화와 헤딩 최적화를 분리하는 계층적 계획 방식으로, 기하학적 경로 길이를 6.2% 줄이고 최종 경로 비용을 초기 탐색 비용의 87% 수준으로 낮춥니다.
3. 온라인 생성 프레임워크: 스트리밍되는 포인트 클라우드로부터 로컬 슬랩 기반 업데이트를 통해 SE(2) NavMesh를 증분적으로 구축하고 업데이트하는 효율적인 방법으로, 온보드 하드웨어에서의 실시간 배포를 가능하게 합니다.

실험 결과

• 시뮬레이션 (통과 가능성): 6가지 다양한 실내 환경(다층 장면 포함)에서 SE(2) NavMesh는 고전적 NavMesh보다 50% 이상의 더 많은 통과 가능 영역을 포착했습니다. 또한 제한 영역을 활용함으로써 이전에 단절되었던 안전 영역들을 성공적으로 연결했습니다.
• 시뮬레이션 (계획): ASA 파이프라인은 제약이 있는 환경에서 샘플링 기반 베이스라인(RRT, RRT*, PRM)보다 일관되게 우수한 성능을 보였으며, 더 높은 성공 가중 경로 비용(SPC)과 더 낮은 계획 시간을 달ach했습니다. 개방된 공간에서는 샘플링 기반 방식이 더 빨랐으나 더 높은 비용의 경로를 생성했습니다.
• 실제 배치: ANYmal 보행 로봇을 이용한 실험을 통해 다음과 같은 복잡한 시나리오에서 온라인 생성 및 내비게이션의 성공을 입증했습니다:
  • 계단 이동이 포함된 다층 환경.
  • 좁은 복도 (너비 0.8m, 로봇 너비보다 0.27m 넓음).
  • 오버행 장애물 아래에서의 내비게이션.
  • 시스템은 로컬 업데이트를 사용하여 4 Hz 업데이트 속도를 유지했으며, 글로벌 업데이트 방식은 맵이 커짐에 따라 실시간 성능을 유지하는 데 실패했습니다.

의의 및 주장

본 논문은 SE(2) NavMesh가 로봇의 헤딩과 통과 가능성 사이의 관계를 명시적으로 모델링함으로써 지상 로봇 내비게이션의 결정적인 공백을 해결한다고 주장합니다. "원형 풋프린트" 가정을 넘어섬으로써, 이 방법은 전통적인 방식이 실패하는 제약이 많은 다층 환경에서 비원형 로봇의 신뢰할 수 있는 내비게이션을 가능하게 합니다. 온라인 생성 파이프라인의 통합은 사전 맵 없이 미지의 동적 환경에서 자율 탐사를 수행하기 위한 이 표현법의 실용성을 확립합니다. 이 연구는 산업 및 인프라 점검 작업에서 보행 로봇을 위한 더욱 견고한 글로벌 내비게이션을 향한 단계로 제시됩니다.