입자 필터

이 블로그 게시물에 대한 보다 기술적인 처리는 원래 Udacity 블로그 에 게시되었습니다 .

로봇은 놀라울 정도로 간단하지만 강력한 알고리즘을 사용하여 엔지니어가 현지화라고 하는 문제인 지도상의 위치를 ​​찾습니다. 입자 필터링으로 알려진 알고리즘은 놀랍도록 멋져 보입니다. 이 두 부분으로 구성된 기사의 첫 번째 부분은 여기 에 게시되었습니다 . 이 첫 번째 기사에서는 자신만의 입자 필터를 구축하는 데 필요한 수학을 설명합니다.

자율 주행차는 인간 운전자처럼 행동하도록 설계되었습니다. 일반적인 자율주행차 시스템은 6개의 구성 요소로 구성됩니다. 6가지 구성 요소 각각은 운전, 자율 주행 또는 기타에 필요한 중요한 문제를 해결합니다. 구성 요소는 다음과 같이 인간 운전자를 모방하는 기능을 수행하는 것으로 생각할 수 있습니다.

현지화 : 우리는 어디에 있습니까?
경로 계획 : 목적지에 어떻게 도달합니까?
지각 : 주변에 또 무엇이 있습니까?
예측 : 조금 후에 환경은 어떻게 될까요?
계획 : 다음 몇 초 동안 따라갈 과정은 무엇입니까?
컨트롤 : 우리가 원하는 코스를 어떻게 따라갈 것인가?

인간을 위한 현지화는 매우 쉬운 경향이 있습니다. 우리는 일반적으로 지도에서 우리의 위치를 ​​훨씬 더 정확하게 식별하는 데 도움이 되는 스마트폰과 같은 GPS 장치의 도움을 받아 우리가 세계 어디에 있는지 기억에서 기억합니다. 또한 내비게이션 표지판, 차선 표시, 다른 차량, 도로 및 주변 환경에 대한 이해와 같은 시각적 단서를 사용하여 항상 올바른 차선, 올바른 도로, 올바른 방향으로 가고 있는지 확인합니다.

위치 파악과 관련하여 자율 주행에는 차량이 이동하는 위치와 방향(헤딩이라고도 함)도 필요합니다. 그러나 인간과 달리 자율주행차가 요구하는 정밀도 수준은 매우 높다. 차량이 오른쪽 차선에 있고 차선과 평행하게 가고 있다는 것을 아는 것만으로는 충분하지 않습니다. 계획에는 높은 정밀도가 필요합니다. 현지화가 위치에 대해 몇 센티미터 이상 또는 방향에 대해 몇 도 이상 벗어난 경우 계획 구성 요소는 다른 많은 원치 않는 결과와 충돌하는 비참한 과정을 생성할 수 있습니다.

인간과 마찬가지로 자율주행차는 GPS에서 위치와 방향에 대한 첫 번째 추정치를 얻습니다. GPS 수신기는 스마트폰에 있는 아주 작은 수신기일지라도 매우 정확한 경향이 있습니다. 그러나 GPS로부터 수신되는 위치정보의 정확도는 안전한 자율주행 에 적합하지 않다 . 예를 들어, 보고된 위치는 1미터에서 몇 미터까지 또는 최악의 경우에는 그 이상까지 벗어날 수 있습니다.

정밀도는 수신기에 보이는 위성의 수, 건물과 같은 대형 물체에서 반사되는 위성 빔의 반사, 대기 요소에 의한 흡수와 같은 요인에 따라 자주 그리고 크게 변동합니다.

그것이 충분히 나쁘지 않다면 GPS가 현지화 정보를 업데이트하는 속도도 1–10Hz 범위로 매우 느립니다. 10Hz에서도 느린 20Kmph로 움직이는 차량은 두 번의 GPS 업데이트 사이에 약 0.5미터를 움직였을 것입니다.

자율주행차는 움직임으로 인한 위치 파악의 불확실성을 완화하기 위해 관성 측정 장치(IMU)를 사용합니다. IMU는 빠르고 정확하며 차량의 가속도와 회전율을 측정합니다. 그런 다음 이 정보를 사용하여 두 번의 연속적인 GPS 업데이트 사이에 차량의 위치를 ​​확인할 수 있습니다. IMU는 시간이 지남에 따라 작은 근사 오차를 축적하는 경향이 있지만 여기서 다루는 문제는 아닙니다.

현지화 시스템이 해결해야 할 핵심 문제는 GPS 업데이트가 본질적으로 부정확하다는 것입니다. 예를 들어 GPS는 정확한 위치를 보고하는 대신 GPS가 자체적으로 업데이트될 때 차량이 존재할 가능성이 있는 지상의 작은 영역을 보고합니다. 이 영역을 GPS 지점이라고 합니다.

정확한 위치 파악을 수행하는 문제는 GPS 지점의 영역을 줄이는 문제로 축소됩니다.

덜 정확한 것부터 시작하여 정확한 위치 파악을 위해 로봇 공학에서 사용된 기술 중 하나는 입자 필터링 으로 알려져 있습니다. 환경에 여러 랜드마크, 즉 위치, 모양 및 크기가 자주 변경되지 않는 크고 정지된 물체가 있는 경우에 유용합니다. 건물, 휴대폰 기지국, 교각, 전봇대 또는 교통 신호, 간판 등이 될 수 있습니다.

입자 필터링 방법을 이해하기 위해 비유를 사용합니다. 피곤해서 호텔 방으로 돌아와 불을 끄고 침대에 엎드려 엎드린다고 가정해 봅시다. 당신은 한밤중에 일어나 당신이 어디에 있는지 알고 싶어합니다. 물론, 당신은 침대에 충돌한 것을 기억하지만 당신이 어느 방향을 향하고 있는지, 전등 스위치가 어디에 있는지, 슬리퍼가 어디에 있는지 알고 싶을 것입니다. 이것은 침대에 있었던 희미한 기억보다 더 정확한 것을 요구합니다.

빠르게 방향을 잡기 위해 주변 환경을 이용합니다. 먼저 침대의 다른 위치에 있는 자신을 상상합니다. 그런 다음 주변의 '랜드마크' 개체를 터치하고 식별하여 감지합니다. 가까운 테이블에서 물병을 밀거나 의자에 발가락을 찔릴 수 있습니다. 이러한 관찰은 당신이 호텔 침대 영역에서 어디에 있을 가능성이 있는지에 대한 중요한 단서를 제공합니다. 병, 테이블, 의자가 침대와 관련된 위치를 기억하기 때문에 침대에서의 위치를 ​​보다 정확하게 유추할 수 있습니다. 각각의 새로운 관찰을 통해 침대의 특정 위치를 배제하고 다른 위치에 있을 가능성을 높일 수 있습니다.

이것이 바로 자율주행차에서 입자 필터링이 작동하는 방식입니다. 초기 GPS 지점으로 무장한 차량은 지도에서 대략적인 위치와 방향을 알고 있습니다. 이 대략적인 위치는 작은 가상 셀로 나뉩니다. 차량은 또한 대략적인 위치 주변에 어떤 랜드마크가 있는지 알고 있습니다. 그런 다음 차량은 온보드 라이더를 사용하여 이러한 랜드마크까지의 거리를 조사합니다. 그런 다음 현지화 시스템은 각 가상 셀에 대해 이러한 측정값을 집계합니다. 점점 더 많은 랜드마크가 탐색됨에 따라 대부분의 셀이 제외되고 가능성이 높은 소수의 셀만 가능한 위치로 남습니다.

입자 필터링이라는 이름은 각 가상 셀의 위치가 지도에 입자로 표시된다는 사실에서 유래되었으며 우리는 랜드마크까지의 거리를 계산하여 입자를 필터링하고 거리가 맞지 않는 것으로 보이는 입자를 폐기함으로써 입자를 배제합니다. 랜드마크.

아래 애니메이션은 여러 차선, 도로 및 개방된 영역에 걸쳐 퍼질 수 있는 상당한 영역에 걸쳐 있는 입자의 초기 위치를 보여줍니다. 환경 감지 또는 탐색은 청색 광선으로 표시됩니다. 가장 가능성이 높은 위치를 나타내는 녹색 점은 처음에는 지도 주위를 뛰어다니지만 환경을 감지하여 점점 더 많은 입자가 배제됨에 따라 매우 빠르게 자리를 잡습니다.

입자 필터링은 많은 로봇과 자율주행차를 구동하는 매우 간단한 알고리즘입니다. Nvidia Drive Labs는 현지화가 다양한 랜드마크가 있는 풍부한 지도의 이점을 얻을 수 있는 방법에 대한 짧은 비디오 를 공개했습니다. Uber ATG는 여기에서 GPS 정확도를 개선하는 방법에 대한 블로그를 게시했습니다 .