A novel resampling algorithm based on the knapsack problem

•Resampling algorithms improve prediction performance in particle filters.•An analogy between the resampling and knapsack problem can be drawn.•The knapsack problem can be solved by dynamic programming approach efficiently.•Resampling algorithm based on the knapsack problem has a better performance....

Full description

Saved in:
Bibliographic Details
Published in:Signal processing 2020-05, Vol.170, p.107436, Article 107436
Main Authors: Bacak, Ahmet, Köksal Hocaoğlu, Ali
Format: Article
Language:English
Subjects:
Dynamic programming
Knapsack problem
Particle filters
Resampling
Target tracking
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•Resampling algorithms improve prediction performance in particle filters.•An analogy between the resampling and knapsack problem can be drawn.•The knapsack problem can be solved by dynamic programming approach efficiently.•Resampling algorithm based on the knapsack problem has a better performance. The problem of accurate tracking of targets is important both in military and civilian applications. There are different approaches to precise tracking of targets. Particle filters have been used frequently for this purpose in recent years. Different resampling algorithms have been proposed to reduce the estimation error in the particle filters. In this study, a new resampling algorithm is proposed by solving the knapsack problem. We compare the performance of the proposed algorithm with that of other resampling algorithms for target tracking problems. Simulation results show that the proposed algorithm has a better performance under various conditions such as the small number of particles, measurement noise levels and different target motion models.
ISSN:0165-1684
1872-7557
DOI:10.1016/j.sigpro.2019.107436