CPM-10 A Hybrid Resampling Algorithm Using in Parallel/Distributed Particle Filters
Abstract
Parallel/distributed particle filters estimate the states of dynamic systems by using Bayesian interference and stochastic sampling techniques with multiple processing units (PUs). The sampling procedure and the resampling procedure alternatively execute to estimate the states in particle filters. There are two basic types of resampling techniques used in parallel/distributed particle filters. They are centralized resampling and decentralized resampling. The high communication between PUs in centralized resampling lowers the speedup factor in parallel computing but improves the estimation accuracy. The decentralized resampling can avoid the communication and improve the performance. Some types of hybrid resampling techniques mainly execute the decentralized resampling and only invoke the centralized resampling with constant intervals to achieve ideal performance without losing the estimation accuracy. However, the constant intervals cannot guarantee that the centralized resamplings can be invoked timely. Based on those motivation, we propose a type of hybrid resampling with adaptive intervals to dynamically adjust the intervals between centralized resamplings. The intervals are calculated according to the measure effective sample size in recent centralized steps. The next centralized resamplings are postponed and more decentralized resamplings are executed to improve the performance if the effective sample size is large. Otherwise, the centralized resamplings will be timely invoked to guarantee the estimation accuracy. The experimental results indicate that the proposed hybrid resampling technique is able to improve the performance and the estimation accuracy.
Keywords
particle filters, sequential Monte Carlo methods, resampling, adaptive resampling
CPM-10 A Hybrid Resampling Algorithm Using in Parallel/Distributed Particle Filters
University Readiness Center Greatroom
Parallel/distributed particle filters estimate the states of dynamic systems by using Bayesian interference and stochastic sampling techniques with multiple processing units (PUs). The sampling procedure and the resampling procedure alternatively execute to estimate the states in particle filters. There are two basic types of resampling techniques used in parallel/distributed particle filters. They are centralized resampling and decentralized resampling. The high communication between PUs in centralized resampling lowers the speedup factor in parallel computing but improves the estimation accuracy. The decentralized resampling can avoid the communication and improve the performance. Some types of hybrid resampling techniques mainly execute the decentralized resampling and only invoke the centralized resampling with constant intervals to achieve ideal performance without losing the estimation accuracy. However, the constant intervals cannot guarantee that the centralized resamplings can be invoked timely. Based on those motivation, we propose a type of hybrid resampling with adaptive intervals to dynamically adjust the intervals between centralized resamplings. The intervals are calculated according to the measure effective sample size in recent centralized steps. The next centralized resamplings are postponed and more decentralized resamplings are executed to improve the performance if the effective sample size is large. Otherwise, the centralized resamplings will be timely invoked to guarantee the estimation accuracy. The experimental results indicate that the proposed hybrid resampling technique is able to improve the performance and the estimation accuracy.