지난 칼만필터 포스팅에 이어, 이번 포스팅에서는 particle filter에 대해 다뤄보겠습니다. cs7638 과제를 하면서 가장 재밌고 직관적으로 다가왔던 필터이기도 합니다. 이번 포스팅도 cs7638 AI4R의 유다시티 강의와, Jonathan Hui의 글에서 번역하고 리소스들을 발췌해왔습니다.
자율주행자동차는 주행하면서 센서로부터 다양한 정보를 받습니다. 아마도 초당 어마어마한 데이터들을 수집하고 있을텐데, 그 중에는 분명 현재 자동차나 기타 오브젝트의 정확한 위치를 파악하기 위해 쓰이는 landmark 정보들이 있을 것입니다. 즉, 현재 측정되고 있는 랜드마크로부터의 거리나 관련 정보들을 참조해서 상세 위치 파악에 사용하는 것입니다.
칼만필터로 landmark와의 정보를 이용해서 위치를 찾는 방식 중에 하나였습니다. 그렇다면 particle filter는 대체 뭐가 어떻게 다른걸까요?
아래 동영상은 cs7638 과제 중에 하나로, 유튜브에서 퍼온 자료입니다.
하얀 화면에 까만 점들이 흩뿌려져있고, 시간이 지날수록 점점 모이고 뭉치더니, 결과적으로 빨간 화살표(실제 위치) 근처로 모든 까만 점들이 모이는 것을 알 수 있습니다. 이게 particle filter가 동작하는 방식입니다.
- 전체 맵에 많은 particle을 흩뿌립니다. 각각이 하나의 자동차가 됩니다.
- 하나하나에 대해 랜드마크와의 거리를 측정한 뒤, 실제 센서에서 측정된 거리와 비교합니다. 거리가 비슷하면, 해당 particle은 실제 자동차의 위치와 유사한 곳에 있다라고 판단할 수 있겠죠. 다만, 그런 파티클이 한두개가 아니라 아마도 많이 있을 겁니다.
- 파티클마다 거리 정보가 유사할수록 weight 값을 높게 줍니다. 그리고 일련의 알고리즘을 통해 높은 weight가 있는 파티클쪽으로 낮은 weight를 가지는 파티클들을 움직입니다. 이런식으로 파티클이 점차 한 곳으로 뭉치게 되고, 결과적으로는 현재 자동차의 위치를 표시하게 되는 구조입니다.
맵 조건이 있어야합니다.
즉 예를들어 미리 측정된 지형 정보가 있어야 각각의 particle에서 랜드마크와의 거리를 측정할 수 있습니다. 위 동영상의 경우는 화성에 있는 글라이더라는 프로젝트였는데, 이미 지형 정보는 있고, 글라이더와 지면 간의 활공 높이를 이용하는 방식이었습니다.
상세 설명
역시나 이번에도 조나단의 글에서처럼 자동차로 사례를 들어 설명해보겠습니다. 다만 좀 더 이해가 쉬운 방식으로 구성을 바꾸고 내용을 수정했습니다.
먼저 자동차의 확실한 위치는 현재 모르는 상태입니다. 따라서 아래와 같이 파티클들이 흩뿌려져있습니다.
그리고 랜드마크로 사용될 정지신호판과의 거리를 측정합니다. 모든 파티클들에서 각각 거리를 측정하며, 실제 자동차에서 측정된 거리의 값과 비교하게 됩니다.
모든 파티클들에서 측정을 하고 나면, 어떤 파티클이 현재 자동차의 위치와 가장 가까운지를 알 수 있는데요. 그림으로 표현하면 다음과 같습니다. 유사한 위치일수록 파티클의 크기를 크게 표현해봤습니다.
해당 크기에 비례하여 파티클의 weight 정보로 각각 기록하고, 일련의 알고리즘을 통해 높은 weight를 가지는 파티클 주변으로 다른 파티클들을 옮겨옵니다. 바로 아래처럼요. 이를 Resampling 이라고 부릅니다.
정리해보면, 기존에는 흩뿌려져있던 파티클들이 이제는 약 2~3 곳의 후보로 모두 모인 것을 알 수 있습니다. 즉 localization이 진행되고 있는 것입니다. 자동차의 Motion이 일어나면, 각각의 파티클도 motion을 수행하고, 위의 방식을 반복하면서 파티클들은 현재 자동차의 위치를 추적하게 됩니다.
Noise
조나단의 글에서 설명이 불충분한 것들에 대해 간단히 서술해보고자 합니다. 가장 중요한 것은 바로 노이즈입니다. 항상 그렇듯이 measurement는 절대로 100% 정확할 수는 없습니다. 어느정도의 산포가 있기 때문에 수식적으로도 이를 반영해줄 필요가 있는데요.
만약 노이즈를 0으로 처리한다면, 자칫 잘못된 위치에 모든 파티클들이 가는 사태가 발생하기도 합니다. 그리고 파티클들이 일단 모여서 특정 점들을 이루게 되면, 아예 다른 지역으로 파티클들이 이동하기가 쉽지가 않습니다. 왜냐하면 해당 지역에는 파티클이 하나도 없기 때문입니다. 따라서 인위적으로 파티클들의 motion에 노이즈를 부여함으로써 다른 지역으로도 퍼져나가도록 설정하는 방법이 필요합니다. 또한 노이즈가 없다면 특정 위치에 파티클이 모인 이후라면, 어떤 이유로 인해 실제 자동차의 위치와 파티클의 위치가 달라졌을 때 파티클이 대응할 방법이 없습니다. 모든 파티클은 한점으로 이미 모여있을 것이고, 동일한 수식에 의해 동일한 motion이 진행되기 때문입니다. 따라서 모션에 대한 노이즈를 부여해야합니다. 각각의 파티클마다 움직임에 일종의 랜덤성이 부여되는 것입니다.
정확한 예시는 아니지만, 예를 들어 아래 그림처럼 로봇이 검은 선을 따라가고 있다고 해봅니다. 이 때 파티클들도 검은선 근처로 모일텐데, 노이즈를 일부 줘서 지속적으로 검은 선을 예측할 수 있도록 해준다고 이해해볼 수 있겠습니다. (그래프 레이블은 모두 무시해주세요..) 만약 노이즈가 없었을 때, 검은선에서 벗어나버릴 경우 다시 검은선 영역으로 돌아올 방법이 애매한 셈입니다. Weight를 업데이트하고, 계속 resampling이 된다는 관점으로 보시면 될 것 같습니다.
예를 들어 보겠습니다. 좌표가 0인 지점에 정지신호판이 있고, 현재 자동차는 남쪽으로 2m 지점에 위치해 있고, 센서는 2m 라는 거리를 측정하고 있습니다. 만약 파티클들이 북쪽으로 2m 지점에 모두 모인다면 어떻게 될까요? 분명 센서로부터 측정되고 있는 거리는 일치하지만, 실제 위치는 맞추지 못하는 상황이 발생하고 있습니다. 이를 해결하기 위한 과정의 일부로 노이즈가 필요한 것입니다. 노이즈는 인위적으로 다른 지역으로 퍼져나가려는 특성을 각각의 파티클에 부여함으로써 이러한 문제를 개선하는데 도움이 될 수 있습니다. 아래 그림은 현재 위치를 파티클이 2곳으로 추정하고 있는 상태입니다. 실제 차는 북쪽의 파티클에 있는데, 만약 파티클이 전부 남쪽으로 모인다면 어떻게될까요? 노이즈가 없으면 북쪽으로 갈 방법이 없습니다. 또한, 사진과 같이 한 곳에 뭉쳐져있지 않고 다소 퍼져있는 양상을 띌 수 없습니다. 모두 한점으로 모이는 사태가 발생하겠죠. 사실 이게 항상 맞는 표현은 아닙니다만, 직관적 이해 정도로만 봐주시면 될 것 같습니다. 과제를 하면서 느낀 점은, 필터 사용 초기에 resampling 이 매우 영향이 크다는 점입니다. 초기에 위치를 잘 잡기 위해서는 노이즈가 반드시 필요합니다.
Particle number
파티클을 몇개로 설정하느냐도 매우 중요합니다. 너무 없다면 애초에 자동차의 위치 근처에 파티클이 없을 수도 있고, 결과적으로 localization에 실패할 수도 있습니다. 반면 너무 많이 두면, 컴퓨팅 성능에 악영향을 줄 수도 있겠습니다. 따라서 튜닝이 필요하며, 파티클을 흩뿌릴 때도 정규분포로 뿌릴지, 고르게 뿌릴지 등 선택지가 많습니다만, 일반적으로 정규분포를 가지는 형태로 뿌리면 무방한 것 같습니다. (상황마다 다르겠지만요)
Fuzzing
파티클들이 점차 한곳으로 모여서, 현재 자동차의 위치와 근접해졌습니다. 그런데 정확한 위치는 파악하지 못하고, 계속 근접 위치만 파티클이 예측하는 상태라면 어떻게할까요? 별 차이가 없어보여도, 실제 상황에서는 몇 센티미터 단위로 정확한 localization이 필요할 수 있는데요.
위에서도 언급한 노이즈만으로 이를 해결하기에는 한계가 있습니다. 이를 도와주기 위한 일종의 노이즈 제 2탄 방법론이 있는데요. cs7638에서는 이를 Fuzzing이라고 불렀고, 위에서 언급한 노이즈와 함께 튜닝이 필요합니다.
사실 방법은 간단합니다. Resampling 된 이후, 각각의 파티클들에 대해서 위아래, 좌우로 약간씩 노이즈를 주고 인위적으로 파티클들을 움직이는 것입니다.
모든 파티클들에 대해서 fuzzing을 진행한다면, 다음 그림처럼 운이 좋으면 실제 자동차의 위치 근처로 파티클이 이동할 수 있게 될 겁니다. 그러면 해당 파티클의 weight값은 커지게 되고, 결과적으로 비교적 정확하게 차량의 위치를 파악하고 localization을 수행할 수 있게 될 것입니다.
아무래도 상세 위치를 맞추는 과정은, 전체적인 motion에 주어지는 노이즈와는 다르게 접근해야하기 때문에, 모션 노이즈와 파라미터 튜닝이 꼭 필요합니다.
Particle Filter 정리
글 초반에 작성한 순서에, 위 내용을 추가하면 다음과 같이 정리해볼 수 있겠습니다.
- 전체 맵에 많은 particle을 흩뿌립니다. 각각이 하나의 자동차가 됩니다.
- 하나하나에 대해 랜드마크와의 거리를 측정한 뒤, 실제 센서에서 측정된 거리와 비교합니다. 거리가 비슷하면, 해당 particle은 실제 자동차의 위치와 유사한 곳에 있다라고 판단할 수 있겠죠. 다만, 그런 파티클이 한두개가 아니라 아마도 많이 있을 겁니다.
- 파티클마다 거리 정보가 유사할수록 weight 값을 높게 줍니다. 그리고 일련의 알고리즘을 통해 높은 weight가 있는 파티클쪽으로 낮은 weight를 가지는 파티클들을 움직입니다. 이런식으로
Resampling과정을 거치면 파티클이 점차 한 곳으로 뭉치게 되고, 결과적으로는 현재 자동차의 위치를 표시하게 됩니다. - 자동차가 움직이면 파티클도 motion에 따라 같이 움직입니다. 이 때, 모션에는 노이즈를 부여함으로써 필터의 정확도를 높입니다.
- 최종적으로 Resampling 이후, 각각의 파티클에 대해
Fuzzing을 수행합니다. 즉 약간씩 인위적인 움직임을 줘서 최종 localization 정확도를 향상시킵니다.
지금까지 칼만필터와 파티클 필터에 대해 알아봤습니다. 이 두가지 필터는 사용 환경이나 방식은 다르지만 모두 오브젝트의 Localization을 위해 사용되고 있습니다. 다음 포스팅에서는 Motion control에서 사용되는 PID 제어에 대해 알아보겠습니다.
'Developer > Artificial Intelligence' 카테고리의 다른 글
| Self Driving car - Kalman Filter 칼만 필터 (0) | 2021.12.28 |
|---|
댓글