In this paper, we describe an algorithm for acquiring occupancy grid maps with mobile robots. The standard occupancy grid mapping developed by Elfes and Moravec in the mid-eighties decomposes the high-dimensional mapping problem into many one-dimensional estimation problems which are then tackled independently. Because of the independencies between neighboring grid cells, it often generates maps that are inconsistent with the sensor data. To overcome it, we propose the concept of the cluster which is a set of cells. The cells in the clusters are tackled dependently with another occupancy grid mapping with EM algorithm. The occupancy grid mapping with EM algorithm yields more consistent maps in the cluster, but it find out the maximized map for the whole environments. Hence, it takes more time and gets the map to be inaccurate partly. Instead of this, our approach use the EM algorithm only in the clusters. As we use mapping algorithm adaptively with clusters according to the sensor measurements and we emphasize not the cells but the clusters , the maps generated by our approach have less calculation time and are more accurate than the previous mapping algorithms.
본 논문에서는 이동 로봇을 이용한 점유적 지도 작성을 위한 알고리즘을 제시한다. 기존의 Elfes와 Moravec가 제안한 점유적 지도 작성 방법은 전체 환경을 작은 격자로 나누어 그 각각의 격자의 점유확률을 독립적으로 구하였다. 이 방법의 단점은 이웃한 격자 간의 독립성으로 인해서 종종 센서 값과 일치하지 않는 지도를 작성하기도 한다는 것이다. 이를 극복하기 위해서 셀의 집합인 클러스터라는 개념을 제안한다. 클러스터 내부 격자의 점유 확률은 EM 알고리즘을 사용한 다른 점유적 지도 작성 방법을 사용하여 연관성을 고려하여 구해진다. EM 알고리즘을 사용한 점유적 지도 작성 방법은 클러스터에서는 정확한 지도를 작성하나 전체 환경에 대해서 적용될 때 EM 알고리즘으로 인해 시간이 오래 걸리고 고정된 변수로 인해 특정 지역에서는 정확한 지도 작성이 어렵다는 단점이 있다. 제안된 방법에서는 클러스터 내부에서는 EM 알고리즘을 사용한 방법을 사용하고 그 밖의 지역은 기존의 점유적 지도 작성 방법을 따른다. 기존의 방법이 격자를 중심으로 지도를 작성했지만 제안된 알고리즘은 클러스터를 중심으로 지도 작성이 이루어지기 때문에 정확하고 빠른 지도 작성을 할 수 있다. 이는 클러스터에 따라서 변수와 알고리즘을 적응적으로 변화시킬 수 있기 때문이다.
