This thesis proposes a parallel resampling algorithm for GPU to accelerate particle filter. Particle filters have been influential filters to offer the solution of estimation problems dealing with nonlinear, non-Gaussian system. Even they work very well on the case that the nonlinearity is very massive. The particle filters have been actively researched in nonlinear filtering problem due to the simplicity and generality. However, enough particle population should be given in order to outperform other estimation solutions which leads to the weakness of the particle filter. Accordingly, the drawback has been overcome by the development of parallel processing device. Particle filter consists of propagation, update, and resampling. Most of the particle filter process is straightforward to parallelize, but the resampling step has complicated operations such as prefix sum and sorting the random number. The purpose of resampling is to overcome the degeneracy problem of SIS algorithm, and the basic principle of resampling is to duplicate high weighted particles and eliminate low weighted particles. Therefore, this thesis proposes novel resampling method well-suited to parallel algorithm. The resampling step is converted to run independently on each particle focusing on the purpose and the basic principle. In order to evaluate the proposed method, Monte-Carlo simulation is implemented in terrain referenced navigation, and the performance is evaluated under various conditions by changing the number of particles and the terrain roughness. It presents the computation time and the performance of particle filter, and these results are compared with the proposed resampling, rejection resampling, Metropolis resampling, and systematic resampling. The rejection and Metropolis resampling are proved to be effective in parallel processing. Furthermore, the proposed method shows similar or slightly better performance in terms of root mean square error, and performs faster than other resampling methods. Especially, when the number of particles is 16384, the time ratio is about 10 times for systematic resampling and about 3 times for other parallel resampling methods. As the number of particles is larger, the time ratio will increase. In addition to terrain referenced navigation, another particle filter with high computational load is expected to be efficient.
본 연구에서는 GPU 가속 파티클 필터를 위한 파티클 재추출 병렬화 알고리즘을 제안한다. 파티클 필터는 비 선형 및 비 가우시안 모델에서도 우수한 성능이 알려져 있으며 파티클 필터의 단순성과 보편성 때문에 파티클 필터를 이용한 연구가 활발히 진행되고 있다. 그러나 우수한 성능을 이루기 위해서는 충분히 많은 파티클이 필요하며 따라서 많은 파티클로 인해 필터의 수행시간이 오래 걸린다는 단점이 있다. 하지만 그래픽 카드(GPU) 기술의 향상으로 파티클 필터를 병렬 처리하여 이러한 단점들이 극복되고 있다. 파티클 필터는 파티클 전파, 파티클 갱신, 그리고 파티클 재추출로 구성되어 있다. 파티클 필터의 대부분 과정은 병렬화가 쉽고 간단하지만 파티클 재주출 과정은 구간 합 및 정렬 알고리즘과 같은 병렬화 구현이 매우 까다로운 과정들을 포함하고 있다. 파티클 재추출 과정에서는 가중치가 높은 파티클들을 분리하고 가중치가 낮은 소거하여 SIS 알고리즘에서 생기는 파티클 퇴화 문제를 극복한다. 따라서 우리는 파티클을 분리, 소거하는 기본 원리에 초점을 맞추어 파티클마다 독립적으로 실행될 수 있는 병렬화 알고리즘을 제안한다. 제안한 방법을 평가하기 위해 지형 참조 항법을 예시로 몬테 카를로 시뮬레이션을 수행하며, 지형 험준도와 파티클 수를 바꿔가며 다양한 조건에서 성능을 평가한다. 수행 시간 및 필터의 성능 결과를 병렬 처리에 효과적이라고 증명된 Rejection 재추출 방법과 Metropolis 재추출 방법 그리고 순차적 알고리즘에서 많이 사용되는 Systematic 재추출 방법의 결과와 비교한다. 필터의 성능은 평균 제곱 오차로 평가하였으며, 제안된 방법은 모든 지형에서 다른 방법들과 유사하거나 약간 더 좋은 성능을 보이며 다른 방법들에 비해 보다 빠른 수행 시간을 확인하였다. 특히 16384개의 파티클 사용시 Systematic의 경우 약 10배, 다른 병렬 재추출 방법의 경우 약 3배의 수행 시간 차이를 보였다. 파티클 개수가 더 많을 시 더 큰 시간 비가 예상되며 이는 지형 참조 항법 뿐 아니라 연산 부하가 많은 다른 파티클 필터 또한 기대해 볼 수 있다.