Particle & Kalman 필터로 사람의 위치 파악하기 | Bayesian Filtering for Location Estimation

프랑스로 교환학생을 가서 AI 석사 수업들을 들었다.

주로 2학년 수업들이라서 이해하기 쉽지 않았는데 그 중 하나가 Knowledge Representation & Reasoning 이었다.

수업 마지막에 모로코에서 온 친구와 함께 발표를 진행했는데 그 주제가 Bayesian Filtering for Location Estimation이다.

Bayesian Filtering for Location Estimation

Context

Pervasice Computing

• Ubiqutious computin이라고도 부른다.
• 여러 요소들과 효과적으로 소통하고 수행하는 것이며
• 네트워크로 연결되어 어디서든 접근 가능하다
• Any device, Any time, Any place in Any data format across Any network

Problematic

No Perfect Sensor

세상에 완벽한 센서는 없다.

그러기에 센서로 측정된 값들을 처리할 필요가 있다.

Object Location Estimation

Object location Estimation은 pervasive computing에서 주요한 센서 task이다. 

위치를 예측하기 위해서는 센서들의 정보들을 통합해야하는데

사용되는 센서들은 서로 독립적이라는 문제점이 있다.

State-of-the-art

위의 문제점을 해결하기 위해 베이지안 필터링이 어떻게 사용되었는 지와 달라진 점들은 무엇이 있는지 알아보려고 한다.

Bayesian Filtering

베이지안 필터링은 noise를 가지고 있는 현재의 측정값과 해당 시점의 시스템 제어값으로 현재 상태를 확률적으로 추정하는 것을 말한다.

Kalman filters

• 재귀적으로 (예측 -> 측정 -> 업데이트 반복) Least-Square-Method를 이용하여 센서의 노이즈를 제거해준다.
• 그래서 노이즈가 매우 많지 않고 unimodal 가우시안 분포(일반적으로 사용하는 평균과 표준편차로 표현하는 가우시안)에서 효과적이다.

2가지 stage로 구성되어있다.

1. Prediction
   1. 상태값을 예측한다.
   2. error covariance를 예측한다.
      실제값과 예측값 사이의 오차를 구하고 이것을 가지고 공분산을 구합니다.
2. Update
   1. 기존 예측값을 센서값의 범위로 바꿉니다. 예측값과 센서의 값 모두 노이즈가 포함되어있기에 둘 사이의 교집합을 보기 위해 합성합니다.
   2. 공분산으로 Kalman gain을 구합니다. Kalmain gain은 간단히 말해 계측치와 예측치 중 무엇을 더 중점적으로 반영할 지를 정하는 값입니다.
   3. 예측값을 업데이트 합니다.
   4. error covariance(오차 공분산)도 업데이트합니다.

https://gaussian37.github.io/ad-ose-lkf_basic/

선형 칼만 필터의 원리 이해

위의 페이지는 내용이 어려워 발표 준비가 힘들었던 상황에서 정말 도움이 되었던 블로그입니다.

Multi Hypothesis Tracking

가중치를 가지는 가우시안 분포로 표현되며 

가중치 값은 센서가 측정한 값의 likelihood를 따릅니다.

그러나 여전히 칼만필터의 선형성을 의존합니다.

Geopysics tracking에 많이 사용됩니다.

Grid-based approaches

이는 개별적인 표현으로 linearity가 강했던 칼만 필터의 한계를 해결했습니다.

전체를 작은 grid cell들로 나누고 각 셀에는 사람이나 물체에 대한 belief를 표현하였습니다.

업데이트 식은 베이즈 필터와 같습니다.

Topological approaches

위의 grid로 표현하는 방식은 계산적으로 비싼 방식입니다.

그래서 토폴로지컬한 접근은 전체 환경을 그래프로 표현하고 

그래프의 각 노트는 location을 표현합니다. 그리고 각 엣지는 연결 방식을 나타냅니다.

이 방식은 small discrete space에 표현하기에 정확도가 낮은 센서에 적합합니다.

Particle Filters

샘플 또는 particle이 가중치를 가지고 예측하는 방식입니다.

각 파티클은 상태이며 가중치들로 각 요소가 얼마나 중요한지를 나타냅니다.

리샘플링과 함께 연속적인 샘플링 과정으로 업데이트가 진행되고 가중치는 측정값의 likelihood에 따릅니다.

각 베이즈 필터들을 비교한 것으로 

칼만필터나 MHT는 정확한 센서가 있는 상황에서 사용되는 것이 좋고

정확한 센서가 아니라면 토폴로지 접근이 좋급니다.

만약 flexible tool, 낮은 오버헤드가 필요한 상황이라면 particle 필터가 좋습니다.

Proposed Solution

정확도가 높은 레이저 거리 측정기와 정확도는 낮지만 Identification을 잘하는 적외선, 초음파 센서들로 구성합니다.

Identification

초음파 ID 센서 : 미리 정해진 거리에서(ring 같이) 사람이나 사물이 관측될 likelihood를 나타냅니다. 

적외선 ID 센서 : 미리 정해진 거리 안에서(circle 같이) 사람이나 사물이 존재할 likelihood를 나타냅니다. 

Location Estimation

레이저 거리 측정기 : 사람의 존재를 나타내는 짧은 거리의 레이저 빔의 관측 likelihood를 측정합니다.

Experiments & Results

1. 여러 적외선과 초음파 ID 센서들 결합

State : 사람의 위치, 방향, 속도

복합적인 여러 부분들로 구성된 state이기에 Particle 필터를 사용한다.

위의 그림을 보면, 처음에는 오른쪽 위 코너에 있는 사람이 있고 적외선과 초음파 태그들이 있으며 위치를 알지 못합니다. 그래서 샘플들이 랜덤하게 여기저기에 퍼져있습니다.

사람이 움직인 후에는, 적외선 샘플들이 사람 위치 근처에 주로 퍼져있지만 여전히 센서의 부정확도를 보여줍니다.

이후 초음파 센서가 사람의 위치를 알아내어 샘플들이 더욱 정확해집니다.

이를 통해 부정확한 센서들을 이용하여 정확도를 높일 수 있습니다.

2. Anonymous 센서 추가

이번에는 더욱 정확한 예측을 위해 레이저 거리 측정기를 추가합니다.

 

레이저 거리측정기는 사람 A, B를 따라가지만 누가 A이고 B인지를 잘 구별하지 못합니다.

위에처럼 각 3, 4에서 ID 센서들을 지나간다면 이 문제는 해결됩니다.

다시 중간에서 사람들이 교차될 때 다시 레이저 거리 측정기는 누가 A이고 B인지를 모르지만

 ID 센서들이 있는 5, 6에 위치하면 이 문제는 다시 해결됩니다.

 

정학한 센서인 레이저 거리 측정기는 칼만 필터로 사람을 트래킹하며 위치를 파악하고
정확하지 않지만 ID를 구별할 수 있는 적외선과 초음파 센서들은 파티클 필터로 누구의 경로인지 알아내어 이를 보완합니다.