Particle Filter란?
노이즈가 있는 환경에서 측정된 데이터를 필터를 사용해 실제 위치를 추정하는 도구이다. 선형 시스템과 가우시안 잡음(Gaussian Noise)가 적용되는 Kalman Filter와는 달리 비선형, 가우시안 분포가 적용되지 않는 환경에서 사용된다. turtlebot에서는 위치 추정에 사용된다. 아직은 크게 와닿지 않는 개념이다. 좀 더 알아보자.
Particle Filter의 원리
Particle Filter는 이름처럼 Particle을 사용하는 필터 기법이다. 쉽게 설명하기 위해 Youtube 채널 Team Jupeter의 Particle Filter 강의에서 든 예시를 설명하겠다. 위의 링크의 재생목록은 내가 공부하기 편하게 모아놓은 것이다. 게시글은 순전히 내 공부를 위한 것이니 사실 저기에 나온 내용을 정리해 놓은 것이기에 영상을 봐도 문제는 없다.
Stage 1
| 좌표 | 1 |
|---|
| 좌표 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 벽 | 문 | 문 | 문 | |||||||
| 복도 | 로봇 |
위의 표를 복도를 이동하는 로봇을 나타낸 것이라고 가정하자. 첫번째 행이 좌표, 두번째 행이 문의 위치, 세번째 행이 로봇이 이동하는 복도이다. 처음에 로봇은 자신의 위치는 모르지만 자신이 있는 곳의 지도를 갖고있다. 따라서 지금 장님 로봇은 자신이 복도상의 어떤 지점에 존재할 확률을 모든 지점에서 균등하게 보고 있다. 자, 그럼 로봇은 파티클을 복도에 무작위로 뿌린다. 모든 파티클은 자기 자신과 같은 행동을 할 수 있는 더미라고 볼 수 있다. 이게 무슨 말이냐면 처음에 모든 곳에 자신이 있을 가능성을 가정하고, 더욱 더 자신이 있을 것 같은 곳에 가중치를 더해서 그곳에 자신을 가중치만큼 복제시키고, 그것을 반복하여 자신의 진짜 위치를 찾는 것이다. 지금은 이해하기 어렵더라도 과정을 보다 보면 이해될 것이다.
Uniform Particle Distribution
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Measurement Probability | 확률 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | (%) |
| The Importance Weight | 가중치 | o | o | o | o | o | o | o | o | o | o | 신뢰공간 |
위의 표에서 가중치를 사실상 파티클이라고 보면 된다. Stage 1은 이렇게 균등하게 파티클이 뿌려진 set 1이 생성되었다. 이 set를 Posterior Probability라고 한다.
| set 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| o | o | o | o | o | o | o | o | o | o |
Stage 2
| 좌표 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 벽 | 문 | 문 | 문 | |||||||
| 복도 | ((( | 로봇 |
로봇이 움직이기 시작한다. 문을 발견하면 자신이 위치한 곳으로 추정되는 곳을 짚어 볼 수 있다. 하지만 예상위치에 있을 확률이 올라간 만큼, 다른 지점은 확률이 떨어진다. 표로 나타내면 다음과 같다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Measurement Probability | 확률 | 7 | 7 | 17 | 7 | 17 | 7 | 7 | 17 | 7 | 7 | (%) |
| The Importance Weight | 가중치 | o | o | O | o | O | o | o | O | o | o | 신뢰공간 |
확률이 올라간 지점의 가중치 o의 크기가 조금 커진 것이 보이는가? 여기서 Importance Weight의 생성과정은 Stage 1에서의 가중치 $\times$ stage 2에서의 Measurement Probability이다.
어째서 바로 윗줄과 또 말이 다른것 같다? 그건 바로 원래 Importance Weight와 set는 사실 한몸이다. 여기서는 이해를 쉽게 하기 위해 다른 방식으로 떼어서 생각해 보았지만, 사실 Importance Weight와 set가 의미하는 바는 같다. 결국 Stage 2의 set는 다음과 같이 나타낼 수 있다.
| set 2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| o | oo | o | oo | o | oo | o |
이렇게 가중치를 Density의 형태로 나타내는 과정을 Resampling이라고 한다. 여기서 주의할 점이 있는데, 이전의 파티클의 개수와 Resampling한 파티클의 개수가 같아야 한다. 즉, 파티클은 가중치가 작다고 사라지는 게 아니라, 가중치가 높은 쪽으로 계속해서 모이는 방식으로 진행된다. 사실 위의 표에서 문이 있는 3, 5, 8번 지점을 제외한 나머지의 가중치, 즉 동그라미의 크기가 조금 작아져야 한다. 작성자의 한계로 더 작게 하지는 못했으니 10에서 7이 된 것만큼 작아졌다고 생각하고 봐주길 바란다…
실제로 데이터가 아주 많을 때
예시인 이 강의에서는 데이터가 10개 밖에 없지만 1000개 정도 된다고 가정하자. 무작위로 뽑지만 각 파티클의 Importance Weight가 클수록 높은 확률로 샘플에 잡히게 된다고 프로그래밍 한다. 이때의 set를 나타내면 다음과 같은 형태가 나올 것이다.
| set | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| o | oo | ooo | oo | ooo | oo | oo | ooo | oo | o |
연속적인 형태의 그래프가 나올 것이기 때문에 3, 5, 8번 지점을 중심으로 서서히 가중치가 올라가고 내려갈 것이다.
Stage 3
| 좌표 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 벽 | 문 | 문 | 문 | |||||||
| 복도 | ((( | 로봇 |
또 로봇이 움직였다. 하지만 이번에는 로봇이 “움직이기만” 했다고 생각해 보자. “움직인다”는 measurement와는 다른 관점에서 봐야 한다. 단순히 이동만 하는 것이므로 아직 센서를 통해 measurement를 하지 않은 상태인 것이다. 하지만 odometry를 통해 이동에 대한 정보를 알고 있으므로, 확률 정보는 업데이트될 수 있다. 그렇다면 내친김에 그냥 한칸 더 가서 업데이트해보자.
| 좌표 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 벽 | 문 | 문 | 문 | |||||||
| 복도 | ((( | 로봇 |
다시 문을 발견했다. 자 아직 measurement는 하지말고, 확률 정보만 업데이트해보자. 현재 로봇이 어떤 위치에 있을 확률과 그에 대한 가중치는 다음과 같다.
| 확률 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Measurement Probability | 확률 | 7 | 7 | 7 | 7 | 17 | 7 | 17 | 7 | 7 | 7 | (%) |
| The Importance Weight | 가중치 | o | o | o | o | O | o | O | o | o | o | 신뢰공간 |
이제 확률 정보를 업데이트했으니 다시 measurement를 해보자. measurement 결과 문을 발견한 사실을 가지고 추정한 로봇 자신이 어떤 위치에 있을 확률은 다음과 같다.
| 확률 2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Measurement Probability | 확률 | 7 | 7 | 17 | 7 | 17 | 7 | 7 | 17 | 7 | 7 | (%) |
자 이제 원래 로봇이 갖고 있던 확률 정보와 문을 발견한 사실을 토대로 추정한 위치에 있을 확률을 곱하면, 즉 확률 1 $\times$ 확률 2를 하면 새로운(이 stage의) Importance Weight가 나올 것이다. 확률이 높은 곳끼리 곱해진 곳은 더욱 커질 것이다. 따라서 새로운 Importance Weight는 다음과 같다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| The Importance Weight | 가중치 | o | o | O | o | @ | o | O | O | o | o | 신뢰공간 |
5번 지점의 가중치가 매우 큰데 어떻게 표현해야 할지 모르겠다…. 아무튼 저 지점이 현저히 높은 가중치를 가진다. 또한 원래 작았던 1, 2, 4, 6, 9, 10 지점의 가중치는 쪼그라들어 없어지려 한다. 이 가중치를 토대로 Resampling을 하면 다음과 같은 결과가 나온다.
| set 3 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| oo | oooo | oo | oo |
다시 말하지만 파티클 수는 유지된다. 가중치가 쪼그라든 지점의 파티클을 끌어다가 가중치가 높은 지점으로 뿌려주었기 때문이다. Resampling 결과를 보면 아직 몇군데 짐작 가는 부분이 남았지만 거의 현재 로봇의 위치와 결과가 근접했다. 파티클 필터는 이런식으로 작은 가중치를 채로 걸러내듯이 굵은 가중치(?)만 남기는 방식으로 로봇의 위치를 추정할 수 있다.
한눈에 보는 Particle Filter의 원리
그림을 봐도 파티클 개수는 변하지 않았다. 파티클이 로봇의 위치를 거의 추정했을 때 계산을 효율적으로 하기 위해 파티클의 개수를 줄이는 방식인 AMCL 방식도 있지만 다음 기회에 알아보기로 하자. 나도 여기까지밖에 모른다.
참고 사이트
Youtube 채널 Team Jupeter의 Particle Filter 강의 강추
Tuttlebot의 Particle Filter 적용 방식 한번에 이해된다. 강추
쉽게 설명한 파티클 필터(particle filter) 동작 원리와 예제 (사진 출처: Ryan Blog)
Comments