점유 격자 매핑 — LiDAR 및 카메라 데이터를 통행 가능성으로 변환

Contents — find the section you need

LiDAR 포인트 클라우드는 벽과 도로를 매우 정밀하게 표현할 수 있습니다. 하지만 계획 담당자는 다른 답을 필요로 합니다. 차량 본체가 어디에 위치해야 하는지, 아직 관측되지 않은 공간은 어디인지, 장애물의 불확실성은 어느 정도인지, 그리고 움직이는 보행자의 궤적이 언제 사라져야 하는지 등을 파악해야 합니다. 점유 격자는 연속적인 공간을 셀로 나누고 각 셀이 점유될 확률을 누적합니다.

점유 격자는 단순히 흑백 이미지가 아닙니다. 거리 측정 광선이 통과한 셀은 빈 공간임을 나타내고, 유효한 종점은 점유됨을 나타내며, 광선이 관측하지 않은 셀은 미지의 공간으로 남습니다. 미지의 공간을 빈 공간으로 표시하면 차량이 보이지 않는 골목길이나 벽 뒤로 경로를 설정할 수 있습니다. 이 글에서는 거리 측정값 업데이트를 베이지안 매핑, SLAM, 동역학, 3D 표현, 계획 및 안전 평가와 연결합니다.

점유 격자 관측 소스로서의 LiDAR

이미지: Concept of LiDAR (Cartographer3d, CC BY-SA 4.0), Wikimedia Commons. 이는 시간차 측정 개념을 나타낸 것이며, 여기에 설명된 격자의 특정 차량 또는 제품 구현을 나타내는 것은 아닙니다.

간단한 결론

각 셀에 대한 확률을 저장합니다. 0.5에 가까운 값은 알 수 없음, 1에 가까운 값은 점유됨, 0에 가까운 값은 비어 있음으로 나타냅니다.
로그 오즈는 재귀적인 베이지안 증거를 덧셈으로 변환합니다. 범위를 제한하여 오래되고 강력하게 의심되는 장애물도 결국 제거할 수 있도록 합니다.
유효한 복귀 지점을 표시하고 그 앞에 있는 자유 공간을 레이 트레이싱합니다. 최대 범위, 복귀 불가, 유리, 먼지, 눈, 하드웨어 오류에 동일한 역모델을 적용하지 않습니다.
SLAM 맵은 위치 파악 및 영구적인 구조를 지원하며, 롤링 로컬 코스트맵은 즉각적인 충돌 회피를 지원합니다. 정적 시간 척도와 동적 시간 척도를 분리합니다.
차량은 점이 아닙니다. 계획 수립 전에 장애물의 크기, 자세 및 추적 불확실성, 컨트롤러 오류, 정지 여유를 고려하여 장애물의 크기를 조정합니다.
의미론적 점유, 미래 점유 흐름, 신경망 기반 암묵적 맵은 활발한 연구 방향이지만, 충돌 질의 지연 시간, 보정, 미지의 공간에서의 동작은 여전히 중요한 과제입니다.

범위 광선에서 셀로

그림 1 — 역 센서 모델은 끝점을 표시하고 그 앞의 셀을 지웁니다. 회색의 알 수 없는 공간은 자유 공간이 아닙니다.

원점 $(x_0,y_0)$ 및 해상도 $r$ 의 경우, 월드 포인트 $(x,y)$ 는 다음과 같이 매핑됩니다.

i=\left\lfloor\frac{x-x_0}{r}\right\rfloor,\qquad j=\left\lfloor\frac{y-y_0}{r}\right\rfloor

$r$ 을 절반으로 줄이면 2D 메모리가 대략 4배로 증가하고, 조밀한 3D 복셀 메모리는 8배로 증가합니다. 센서 해상도보다 낮은 해상도와 포즈 불확실성은 실제 정밀도보다는 깜빡임을 유발합니다.

지속적인 맵 프레임, 연속적인 오도메트리 프레임 간의 변환, 차량 본체와 센서는 측정 시점의 타임스탬프에서 평가되어야 합니다. 이전 차량 포즈로 변환된 현재 포인트 클라우드는 직선 벽을 경사진 띠로 변환합니다. 많은 매핑 오류는 클록 및 프레임 오류에서 비롯됩니다.

베이지안 및 로그 오즈 업데이트

셀 $m_i$ 의 점유율을 $O_i$ , 시간에 따른 관측값을 $t$ , 포즈를 $z_{1:t}$ 이라고 합시다. 지도는 다음 정보를 저장합니다.

p_{t,i}=P(O_i\mid z_{1:t},x_{1:t})

고전적인 그리드는 계산의 용이성을 위해 셀 독립성을 가정하고 역 센서 모델 $P(O_i\mid z_t,x_t)$ 을 사용합니다. 이는 벽의 연속성과 같은 공간적 상관관계를 무시하지만 효율적인 로컬 업데이트를 가능하게 합니다.

로그 오즈를 정의합니다.

l_{t,i}=\log\frac{p_{t,i}}{1-p_{t,i}}

재귀적 업데이트는 다음과 같습니다.

l_{t,i}=l_{t-1,i} +\log\frac{P(O_i\mid z_t,x_t)}{1-P(O_i\mid z_t,x_t)} -l_{0,i}

$p_0=0.5$ 및 $l_0=0$ 과 함께 사용됩니다. 점유 증거는 양의 증가분을, 자유 증거는 음의 증가분을 더합니다. 확률은 다음을 통해 복구됩니다.

p_{t,i}=\frac{1}{1+\exp(-l_{t,i})}

실제로는 $l_{min}\le l_{t,i}\le l_{max}$ 으로 클램핑합니다. 포화가 발생하지 않으면 몇 시간 동안 관찰된 객체가 이동 후 사라지려면 수백 번의 자유 관찰이 필요할 수 있습니다. 클램핑은 수치적 정확성뿐만 아니라 시스템이 이력을 얼마나 강력하게 수정할 수 있는지에 대한 결정입니다.

역 센서 모델

2D 스캔의 경우 Bresenham 또는 DDA는 빔을 따라 셀을 열거합니다. 유효한 끝점은 점유를 표시하고 그 이전 셀은 자유 증거를 받습니다. 반환 상태에 따라 다른 정책이 필요합니다.

유효한 반환은 끝점을 표시하고 그 이전 셀을 지울 수 있습니다.
최대 범위 또는 반환 없음 샘플은 장치 의미론에 따라 검증된 범위 내에서 지울 수 있습니다.
최소 범위 미만의 데이터는 지워서는 안 됩니다. 근거리 사각지대.
비, 눈, 곤충, 먼지는 공간적 및 시간적 일관성 필터의 이점을 활용합니다.
유리 및 저반사 표면은 안전하지 않은 자유 공간 증거를 반환하지 않을 수 있습니다.

카메라 깊이, 스테레오 및 의미론적 분할은 지면에 투영될 수 있습니다. 단안 카메라의 클래스 출력만으로는 정확한 범위를 알 수 없습니다. 투영이 도로 평면, 학습된 깊이 또는 객체 크기를 가정하는 경우 해당 불확실성을 확산합니다. Visual SLAM에서 사용되는 희소 특징 맵과 충돌 그리드는 서로 다른 역할을 합니다.

포즈 불확실성 및 루프 클로저

$g(x,z)$ 함수를 센서 포인트 $z$ 를 포즈 $x$ 을 통해 월드 좌표로 변환한다고 가정합니다. 포즈 공분산 $P_x$ 및 측정 공분산 $R_z$ 을 사용할 때, 1차 전파는 다음과 같습니다. 선형화된 점은 다음과 같습니다.

P_p\approx J_xP_xJ_x^T+J_zR_zJ_z^T

위치 파악이 불확실한 상태에서 아주 작은 셀 하나를 강하게 표시하면 반복적인 패스에서 벽이 두꺼워집니다. 증거를 공간적으로 분산시키거나 서브맵 좌표에서 업데이트하십시오. 루프 클로저로 인해 이전 포즈가 변경되면 하나의 전역 래스터에 영구적으로 새겨진 점은 복구하기 어렵습니다. 포즈 그래프와 서브맵은 최적화 후 재조립할 수 있습니다. LiDAR SLAM 입문을 참조하십시오.

정적, 로컬 및 동적 레이어 분리

레이어	시간 척도	예시	업데이트 정책
정적	일~년	벽, 연석, 건물	SLAM/HD 맵, 제어된 업데이트
임시	초	주차된 차량, 떨어진 물체	표시, 제거, 소멸
동적	1/10초~초	차량, 보행자, 자전거	추적 및 미래 점유
의미론/규칙	지도 버전	차선, 정지선, 진입 금지 구역	버전 관리되는 소스

안전 여유 | 제어 주기 | 풋프린트, 정지 여유 | 속도 및 불확실성 의존 |

단순 감쇠는 다음과 같습니다.

l_i(t+\Delta t)=e^{-\Delta t/\tau}l_i(t)

$\tau$ 값이 너무 작으면 정지된 장애물이 사라지고, 너무 크면 움직이는 차량 뒤에 흔적이 남습니다. 가능한 경우 동적 객체를 별도로 추적하고 정적 구조물에 대한 관측이 영구적으로 영향을 미치지 않도록 해야 합니다.

미래 점유 $P(O_{i,k})$ 또는 점유 흐름은 미래 단계 $k$ 에서 공간이 점유될 수 있는 위치를 나타냅니다. 박스 검출기와 달리 분류되지 않은 장애물과 여러 공간 가설을 나타낼 수 있습니다. 보정은 여전히 중요합니다. 0.9의 점유 예측은 평가된 분포 내에서 약 90%의 정확도를 보여야 합니다.

2D, 고도, 복셀 및 BEV

2D 그리드는 빠르지만 자연스러운 표현이 불가능합니다. 돌출부, 나뭇가지, 트럭 아래 틈, 경사면 등 장애물을 고려해야 합니다. 2.5D 고도 맵은 셀별 높이 통계를 저장하고, 복셀 그리드는 부피를 이산화하며, OctoMap은 옥트리 구조로 점유된 부피를 압축합니다.

자율 주행 네트워크는 카메라, LiDAR, 레이더 특징을 조감도로 변환하여 점유, 의미, 움직임을 예측하는 기술을 점점 더 많이 활용하고 있습니다. 학습된 완성 기능은 가려진 영역을 추론할 수 있지만, 훈련 데이터 외에서는 확률 예측이 과대평가될 수 있습니다. 신뢰도 다이어그램, 예상 보정 오차, 거리, 날씨, 지리, 센서 오류 슬라이스 등을 평가해야 합니다.

3D 공간을 2D 계획 레이어로 축소할 때는 장애물 높이 범위를 명시적으로 정의해야 합니다. 낮은 연석, 통행 가능한 잔디밭, 머리 위 전봇대는 하나의 투영 규칙을 공유할 수 없습니다.

점유에서 비용 및 제어까지

계획에는 단순히 점유 정보만 사용하는 것이 아니라 충돌 및 근접 비용을 사용합니다. 장애물 거리 계산을 위한 확장 모델 중 하나는 $d$ 입니다.

C(d)= \begin{cases} C_{lethal}, & d\le r_{inscribed}\\ C_0e^{-\alpha(d-r_{inscribed})}, & r_{inscribed}<d<r_{inflation}\\ 0, & d\ge r_{inflation} \end{cases}

차량의 발자국과 이동 범위, 자세 및 추적 공분산, 컨트롤러 추적 오차, 정지 거리를 고려해야 합니다. 긴 차량이 회전할 때는 원형 로봇 반경으로는 충분하지 않습니다.

경로 계획 입문에서는 비용 함수 기반의 A 및 하이브리드 A 탐색 알고리즘을 설명합니다. MPC 입문에서는 차량 및 장애물 제약 조건을 고려하여 예측 궤적을 최적화합니다. 매핑이 5Hz, 제어가 50Hz로 실행되는 경우, 컨트롤러는 그리드 타임스탬프를 검사하고 오래된 데이터에서의 동작을 제한해야 합니다.

ROS 2 Nav2 Costmap2D는 플러그인을 통해 정적 지도, 장애물, 복셀, 인플레이션, 접근 금지 구역, 속도 필터를 레이어링합니다. 순서가 중요합니다. 인플레이션 이후에 장애물을 삽입하면 예상되는 여유 공간을 확보하지 못합니다.

협력적 점유 V2X

V2X는 자기 센서가 감지하기 전에 가려진 영역을 공유할 수 있습니다. 타일에는 소스 프레임, 측정 시간, 송신자 자세 공분산 및 출처 정보가 필요합니다. 여러 차량이 동일한 도로변 관측값을 전송하는 경우, 이를 독립적인 증거로 처리하면 신뢰도가 이중으로 계산됩니다.

통신 지연 시간 $\Delta t$ 동안 동적 객체는 약 $v\Delta t$ 만큼 이동합니다. 정적 콘텐츠와 동적 콘텐츠를 분리하고, 움직임을 전파하며, 패킷에 서명이 있다는 이유만으로 로컬 증거를 덮어쓰지 않아야 합니다. 손상된 송신자는 도로 전체를 차단된 것으로 표시할 수 있으므로, 인증 외에도 물리적 일관성과 소스 다양성이 필요합니다.

오류 패턴 및 안전 대응

미지의 영역을 자유로운 영역으로 처리

관측되지 않은 셀은 센서가 한 번도 본 적 없는 공간을 통과하는 경로가 없는 것으로 초기화합니다. 탐사 로봇은 미지의 영역 진입 가치에 별도의 비용을 할당할 수 있으며, 도로 차량은 정지 거리 내의 미지의 영역을 보수적으로 처리해야 합니다.

영역 정리 공격적으로

"돌아올 수 없음" 관측 한 번으로 목표물이 유리이거나 비가 신호를 약화시킨 경우 벽이 사라질 수 있습니다. 점유 및 자유 증거에 대해 서로 다른 업데이트 크기를 사용하고, 반복적인 확인을 요구하며, 센서 유형별로 신뢰도를 할당합니다.

오래된 지도 사용

새로운 전송 타임스탬프가 최신 정보를 보장하는 것은 아닙니다. 상위 추정기가 중지되었다가 동일한 데이터를 재전송할 수 있습니다. 생성 시간, 시퀀스 번호, 업데이트된 영역 및 입력 센서 하트비트를 모니터링합니다.

속도에 맞지 않는 팽창

느린 창고 로봇에 맞춰 조정된 고정 반경은 빠른 차량에 충분한 정지 여유를 제공하지 못합니다. 응답 지연 $T$ , 속도 $v$ 및 사용 가능한 감속도 $a$ 에 대해,

d_{safe}=vT+\frac{v^2}{2a}+d_{margin}.

방향에 따라 달라지는 여유를 사용하거나 예측된 전체 스캔 영역에 대해 충돌 검사를 수행합니다.

측정 지표 및 실험 절차

셀 측정 지표에는 다음이 포함됩니다. 점유/자유 영역 정밀도 및 재현율, IoU, 브라이어 점수, 음의 로그 우도, 그리고 보정을 측정합니다. 자유 영역이 대부분을 차지하기 때문에 전체 정확도는 오해의 소지가 있습니다. 거리, 가림, 클래스, 날씨, 그리고 관측 이후 경과 시간에 따라 데이터를 분할합니다.

시스템 지표에는 충돌 및 근접 충돌, 계획 실패, 불필요한 정지, 최소 장애물 간격, 지도 지연 시간, CPU, 메모리, 대역폭이 포함됩니다. 물리적 장애물 출현부터 감지, 매핑, 계획, 제어에 이르는 전체 시간을 측정합니다.

하나의 광선에 대한 단위 테스트를 수행하고, 알려진 형상에 대해 의미론, 경계, 프레임 변환을 표시/삭제합니다.
녹화된 데이터를 재생하여 결정론적 출력과 완전한 구성 로깅을 검증합니다.
타임스탬프 오프셋, 포즈 오류, 장애물, 강수 노이즈, 통신 손실을 주입합니다.
정적 장애물, 횡단하는 보행자, 추월하는 차량, 정지 후 이동 상황을 테스트합니다.
계획과 제어를 연결하고, 오래된 그리드, 알 수 없는 공간, 부분 업데이트를 테스트합니다.
각 테스트 후 고정된 회귀 코퍼스를 재생합니다. 래스터 IoU뿐만 아니라 궤적과 안전 여유를 업데이트하고 비교합니다.

연구 방향

시맨틱 그리드는 도로, 보도, 차량, 보행자 및 식생에 대한 분포를 연결합니다. 4D 점유 및 흐름은 미래 시간의 흐름에 따른 부피와 움직임을 예측합니다. 신경 암묵적 필드는 고정된 래스터 해상도를 연속적인 쿼리로 대체합니다. 협력 그리드는 시야를 확장합니다. 이 모든 것은 확률 보정, 분포 이탈 동작, 제한된 충돌 쿼리 시간, 소스 상관 관계 및 공격 복원력과 같은 새로운 질문을 제기합니다.

요약

점유 그리드는 단순히 색칠하는 것이 아닙니다. 타임스탬프 및 포즈 불확실성과 연관된 자유 공간, 점유 공간 및 관찰되지 않은 공간에 대한 베이지안 증거입니다. 로그 확률 업데이트, 역 센서 모델, 레이 클리어링, 클램프 및 감쇠는 "유령 장애물"과 사라지는 벽을 모두 설명합니다.

그리드 자체만으로는 완전하지 않습니다. SLAM은 프레임을 제공하고, 인식은 동적 및 시맨틱 증거를 제공하며, 계획 및 MPC는 풋프린트 및 정지 정보를 활용합니다. 비용. 최종 테스트는 아름다운 지도가 아니라, 시스템이 안전하게 멈추고, 불필요한 동작을 피하며, 보이지 않는 공간을 이미 확보된 것으로 간주하지 않는지 여부입니다.

이해력 점검

낮은 점유 확률이 통행 가능성을 보장합니까?

해상도, 미지의 공간, 차량 형태, 움직이는 장애물은 여전히 중요합니다. 통행 가능성은 점유 확률 추정 이상의 결정을 요구합니다.

참고 문헌

Try it in the browser

Lab Change the conditions in a browser experimentNav2는 경로는 있지만 움직이지 않습니다: 진단 워크플로