6.4. Likelihood Fields for Range Finders

이 글은 Sebastian thrun의 Probabilistic Robotics를 보고 내용을 정리한 글이며, 나름 쉽게 표현하기 위해서 의역을 한 부분이 있습니다.

 

 

1. Basic Algorithm

이제 likelihood field라고 하는, beam-based model의 한계점을 극복하는 모델에 대해 알아볼 것입니다. plausible physical explanation으로 이 모델을 설명하기에는 부족한 점이 있습니다. 이는 "ad hoc" 알고리즘이라고 하는데, 이 알고리즘은 센서의 물리학의 어떤 의미있는 생성 모델(any meaningful generative model of the physics of sensors)에 관련된 조건부 확률을 계산할 필요가 없지만, 실제 상황에서는 잘 작동합니다. 이 사후 확률 결과는 장애물이 모여있는 공간에서도 잘 작동하며, 계산 또한 더 효율적입니다.

 

key idea는 먼저 sensor scan $z_t$의 end point를 global coordinate space of the map에 사영(projection)하는 것입니다. 이렇게 하기 위해, 우리는 로봇의 global coordinate frame에 대해 local coordinate system이 어디에 위치했는지, 센서 빔 $z_k$의 원점이 로봇의 어느 위치에 있는지, 센서가 어디를 가리키는지를 알아야 합니다. 우리는 보통 시간 $t$에서의 로봇의 pose $x_t = (x\; y\; \theta)^T$라고 합니다. 2차원적 관점에서 바라볼 때, 우리는 로봇에 대한 센서의 상대 좌표는 고정되어있으며, local coordinate system으로 $(x_{k, sense}, y_{k, sense})^T$에 위치한다고 하고, 로봇의 진행 방향을 기준으로 센서의 각도를 $\theta _{k, sense}$라고 하겠습니다.

 

이 값들은 sensor-specific입니다. 측정값 $z_t^k$는 식 (6.32)와 같이 삼각 변환에 의해 global coordinate로 맵핑될 수 있습니다.

 

 

이 coordinates는 센서가 장애물을 감지할 때만 의미가 있습니다. 만약 거리 센서가 측정치 최대값 $z_{t}^{k} = z_{max}$를 측정하게 되면, 이 coordinates는 physical world에서 더이상 의미가 없습니다. likelihood field에서는 이런 max-range reading을 단순히 무시해버립니다.

이전에 설명했던 beam-based model과 같이, likelihood field model도 3종류의 noise와 uncertainty를 가지고 있다고 가정합니다.

 

1. Measurement noise

measurement process에서 나온 noise는 가우시안 형태로 모델링됩니다. x-y-space에서, 이 것은 지도에서 가장 가까운장애물을 찾는 것을 수반합니다. 이제 $dist$를 measurement coordinates $(x_{z_t^k}\; y_{z_t^k})^T$와 map $m$에서의 가장 가까운 장애물과의 Euclidean distance라고 하겠습니다. 그러면 이제 sensor measurement의 확률은 noise를 포함하고, 평균이 0인 가우시안 분포를 따르게 됩니다. 

 

 

 

 

 

 

그림 6.8.은 map을 나타내고, 6.8.은 이 2차원 map에서의 measurement points $(x_{z_t^k} \; y_{z_t^k})^T$에 해당되는 Gaussian likelihood를 보여줍니다. 색이 더 밝을수록, 측정된 장애물이 위치할 확률이 더 높다는 것입니다. 확률 밀도 $p_{hit}$은 그림 6.8에서의 점선으로 나타낸 센서 축과, likelihood field의 intersecting(and normalizing)을 통해 얻을 수 있습니다. 이에 대한 결과는 그림 6.9에 나타냈습니다.

 

2. Failures

이전과 같이, 우리는 max-range reading은 뚜렷하게 큰 likelihood를 가진다고 가정합니다. beam_based model과 같이, 이는 $p_{max}$로 모델링합니다.

 

3. Unexplained random measurements

마지막으로, uniform distribution $p_{rand}$는 센서 인식에서의 랜덤한 noise를 모델링하기 위해 사용됩니다.

 

 

이전의 beam-based model과 같이, 우리가 원하는 확률 $p(z_t^k | x_t, m)$은 이 모든 분포를 합치며, 이전에 사용했던 가중치도 같이 적용합니다.

 

그림 6.9 (b)는 확률 분포 $p(z_t^k | x_t, m)$를 보여줍니다. 우리가 mixing parameters를 조정하는 것에 대해 지금까지 얘기했던 것 중 많은 부분은 new sensor model로 전달됩니다. 이 값들은 직접 또는 ML estimator에 의해 조정될 수 있습니다.

 

Table 6.3.은 likelihood field를 이용하여 measurement probability를 계산하는 알고리즘을 보여줍니다.

 

위 알고리즘에서 각각의 값 $p(z_t^k | x_t, m)$을 곱하는 바깥쪽 loop는 각 센서 beam의 noise들이 독립이라는 것을 가정합니다. line 4는 sensor reading이 max range reading인지 아닌지 확인하고, 해당되는 경우에는 그냥 무시합니다. line 5부터 8은 우리가 필요로 하는 case를 다룹니다. line 7에서, x-y-space에서의 가장 가까운 장애물까지의 거리를 계산하고, 그 결과의 likelihood는 line 8에서 normal distribution과 uniform distribution을 mixing하여 얻게됩니다. 이전과 같이, 함수 $\bf prob \it (dist, \sigma _{hit})$은 표준편차가 $\sigma _{hit}$이고 zero-centered Gaussian distribution에서의 $dist$의 확률을 계산합니다.

 

map에서 가장 가까운 이웃을 탐색하는 line 7은 likelihood_field_range_finder_model 알고리즘에서 가장 많은 비용을 필요로 하는 부분입니다. 이 탐색의 속도를 높이기 위해서 pre-compute the likelihood field를 사용하면 더 빠르게 알고리즘을 처리할 수 있습니다. 따라서 measurement의 확률을 계산하는것은 단지 table lookup을 이용한 coordinate transformation에 해당됩니다. 만약 discrete grid가 사용되면, lookup의 결과는 단지 근사값일 뿐이고, 이는 잘못된 장애물의 좌표를 리턴할 수도 있습니다. 하지만, 확률 $p(z_t^k | x_t, m)$에서의 이 영향은 moderately course grids에서도 그렇게 크지 않습니다.

 

 

2. Extensions

likelihood field model의 key advantage는 smoothness입니다. Euclidean distance의 smoothness로 인해, 로봇의 pose $x_t$의 작은 변화는 $p(z_t^k | x_t, m)$에 별로 큰 영향을 주지 않습니다. 하지만, 이 모델은 3가지의 단점이 있습니다. 첫 번째, 사람이나 다른 dynamics같이 short readings를 발생시킬 수 있는 요소들을 모델링하지 못합니다. 두 번째, 센서가 마치 벽을 통과해서 볼 수 있는 것 처럼 처리합니다. 이는 ray casting operation이 nearest neighbor function으로 대체되었기 때문입니다. 이 nearest neighbor function은 map에서 어떤 특정 지점으로 가는 경로가 장애물에 의해 방해되는지 아닌지 결정할 수 없습니다. 세 번째, map uncertainty를 고려하지 않습니다. 특히, map에서 highly uncertain or unspecified한 영역인 unexplored area을 다룰 수 없습니다.

 

likelihood_field_range_finder_model은 이러한 한계점을 극복하기위해 더 확장될 수 있습니다. 예를 들어, 우리는 occupancy values를 occupied, free, unknown 이렇게 3개의 카테고리로 나눌 수 있습니다. 만약 sensor measurement $z_t^k$가 카테고리 unknown영역에 들어간다면, 이 때의 확률 $p(z_t^k|x_t, m)$은 상수 값 $\frac{1}{z_{max}}$이라고 가정합니다. 탐험되지 않은 영역에서의 이 확률적 모델의 결과는  모든 센서의 측정값이 equally likely이고, 따라서 $p(z_t^k | x_t, m)$은 확률 밀도 $\frac{1}{z_{max}}$인 uniform distribution으로 모델링 됩니다. 그림 6.10.은 그 map과 이에 대응되는 likelihood field를 보여줍니다.

 

 

우리는 이 그림에서 가장 가까운 장애물까지의 거리는 map의 안쪽, 즉 탐험된 영역에 해당되는 부분에만 있다는 것을 알 수 있으며, 바깥쪽의 likelihood $p(z_t^k | x_t, m)$은 상수이므로 모두 같은 색인것을 알 수 있습니다.