Overview of Bayesian sequential Monte Carlo methods for group and extended object tracking <s> Efficient real-time implementations of SMC algorithms: in distributed and parallel ways <s> Particle filter based estimation is becoming more popular because it has the capability to effectively solve nonlinear and non-Gaussian estimation problems. However, the particle filter has high computational requirements and the problem becomes even more challenging in the case of multitarget tracking. In order to perform data association and estimation jointly, typically an augmented state vector of target dynamics is used. As the number of targets increases, the computation required for each particle increases exponentially. Thus, parallelization is a possibility in order to achieve the real time feasibility in large-scale multitarget tracking applications. In this paper, we present a real-time feasible scheduling algorithm that minimizes the total computation time for the bus connected heterogeneous primary-secondary architecture. This scheduler is capable of selecting the optimal number of processors from a large pool of secondary processors and mapping the particles among the selected processors. Furthermore, we propose a less communication intensive parallel implementation of the particle filter without sacrificing tracking accuracy using an efficient load balancing technique, in which optimal particle migration is ensured. In this paper, we present the mathematical formulations for scheduling the particles as well as for particle migration via load balancing. Simulation results show the tracking performance of our parallel particle filter and the speedup achieved using parallelization. <s> BIB001 </s> Overview of Bayesian sequential Monte Carlo methods for group and extended object tracking <s> Efficient real-time implementations of SMC algorithms: in distributed and parallel ways <s> In this paper, we propose novel resampling algorithms with architectures for efficient distributed implementation of particle filters. The proposed algorithms improve the scalability of the filter architectures affected by the resampling process. Problems in the particle filter implementation due to resampling are described, and appropriate modifications of the resampling algorithms are proposed so that distributed implementations are developed and studied. Distributed resampling algorithms with proportional allocation (RPA) and nonproportional allocation (RNA) of particles are considered. The components of the filter architectures are the processing elements (PEs), a central unit (CU), and an interconnection network. One of the main advantages of the new resampling algorithms is that communication through the interconnection network is reduced and made deterministic, which results in simpler network structure and increased sampling frequency. Particle filter performances are estimated for the bearings-only tracking applications. In the architectural part of the analysis, the area and speed of the particle filter implementation are estimated for a different number of particles and a different level of parallelism with field programmable gate array (FPGA) implementation. In this paper, only sampling importance resampling (SIR) particle filters are considered, but the analysis can be extended to any particle filters with resampling. <s> BIB002 </s> Overview of Bayesian sequential Monte Carlo methods for group and extended object tracking <s> Efficient real-time implementations of SMC algorithms: in distributed and parallel ways <s> Two novel distributed particle filters with Gaussian mixer approximation are proposed to localize and track multiple moving targets in a wireless sensor network. The distributed particle filters run on a set of uncorrelated sensor cliques that are dynamically organized based on moving target trajectories. These two algorithms differ in how the distributive computing is performed. In the first algorithm, partial results are updated at each sensor clique sequentially based on partial results forwarded from a neighboring clique and local observations. In the second algorithm, all individual cliques compute partial estimates based only on local observations in parallel, and forward their estimates to a fusion center to obtain final output. In order to conserve bandwidth and power, the local sufficient statistics (belief) is approximated by a low dimensional Gaussian mixture model (GMM) before propagating among sensor cliques. We further prove that the posterior distribution estimated by distributed particle filter convergence almost surely to the posterior distribution estimated from a centralized Bayesian formula. Moreover, a data-adaptive application layer communication protocol is proposed to facilitate sensor self-organization and collaboration. Simulation results show that the proposed DPF with GMM approximation algorithms provide robust localization and tracking performance at much reduced communication overhead. <s> BIB003 </s> Overview of Bayesian sequential Monte Carlo methods for group and extended object tracking <s> Efficient real-time implementations of SMC algorithms: in distributed and parallel ways <s> A particle filter (PF) is a simulation-based algorithm used to solve estimation problems, such as object tracking. The PF works by maintaining a set of “particles” as candidate state descriptions of an object’s position. The filter determines how well the set of particles describe the observations and fit the dynamic model, in order to form an object state estimate. The drawback of the basic PF is that the algorithm functions by collecting all data at a fusion centre. This leads to high communication and energy costs in a resourcelimited network such as the sensor network. In this thesis, we analyze the PF to determine how it can be modified for efficient use in a sensor network. Our main priority is to keep communication and energy costs low since this increases the network lifetime. We propose two innovative particle filtering algorithms which minimizes the associated costs. <s> BIB004 </s> Overview of Bayesian sequential Monte Carlo methods for group and extended object tracking <s> Efficient real-time implementations of SMC algorithms: in distributed and parallel ways <s> The particle filter offers a general numerical tool to approximate the posterior density function for the state in nonlinear and non-Gaussian filtering problems. While the particle filter is fairly easy to implement and tune, its main drawback is that it is quite computer intensive, with the computational complexity increasing quickly with the state dimension. One remedy to this problem is to marginalize out the states appearing linearly in the dynamics. The result is that one Kalman filter is associated with each particle. The main contribution in this paper is the derivation of the details for the marginalized particle filter for a general nonlinear state-space model. Several important special cases occurring in typical signal processing applications will also be discussed. The marginalized particle filter is applied to an integrated navigation system for aircraft. It is demonstrated that the complete high-dimensional system can be based on a particle filter using marginalization for all but three states. Excellent performance on real flight data is reported. <s> BIB005 </s> Overview of Bayesian sequential Monte Carlo methods for group and extended object tracking <s> Efficient real-time implementations of SMC algorithms: in distributed and parallel ways <s> This paper presents a novel distributed particle filter algorithm. To solve the problem of fusing the output of multiple particle filters, a joint space over multiple realisations of the same variable is used. This approach to using particle filters to perform distributed tracking of stealthy targets requires minimal modifications to the particle filters running at the sensor nodes and does not necessitate data to be transmitted to the fusion node. <s> BIB006 </s> Overview of Bayesian sequential Monte Carlo methods for group and extended object tracking <s> Efficient real-time implementations of SMC algorithms: in distributed and parallel ways <s> Decentralized processing algorithms are attractive alternatives to centralized algorithms for target tracking applications in smart sensor networks since they provide the ability to scale, reduce vulnerability, reduce communication, and share processing responsibilities among individual nodes. Sharing the processing responsibilities allows parallel processing of raw data at the individual nodes. However, this introduces other difficulties in multi-modal smart sensor networks, such as non-observability of the targets' states at any individual node and various delays such as varying processing delays, communication delays and signal propagation delays for the different modalities. In this paper, we provide a novel algorithm to determine the initial probability distribution of multiple targets' states in a decentralized manner. The targets' state vectors consist of the targets' positions and velocities on the 2D plane. Our approach can determine the state vector distribution even if the individual sensors alone are not capable of observing it. Our approach can also compensate for varying delays among the assorted modalities. The resulting distribution can be used to initialize various tracking algorithms. Our approach is based on Monte Carlo methods, where the state distributions are represented by a weighted set of discrete state realizations. A robust weighting strategy is formulated to account for missed detections, clutter and estimation delays. To demonstrate the effectiveness of the algorithm, we simulate a network with direction-of-arrival nodes and range-Doppler nodes. <s> BIB007 </s> Overview of Bayesian sequential Monte Carlo methods for group and extended object tracking <s> Efficient real-time implementations of SMC algorithms: in distributed and parallel ways <s> Particle filtering is a sequential signal processing methodology that uses discrete random measures composed of particles and weights to approximate probability distributions of interest. The quality of approximation depends on many factors including the number of particles used for filtering and the way new particles are generated by the filter. The problem of good approximation becomes increasingly challenging as the dimension of the state space increases. In this paper, we address a possible solution for improved particle filtering in high dimensional cases by using a set of particle filters operating on partitioned subspaces of the complete state space. We provide simulation results that show the feasibility of the proposed approach. <s> BIB008 </s> Overview of Bayesian sequential Monte Carlo methods for group and extended object tracking <s> Efficient real-time implementations of SMC algorithms: in distributed and parallel ways <s> We present a case-study on the utility of graphics cards to perform massively parallel simulation of advanced Monte Carlo methods. Graphics cards, containing multiple Graphics Processing Units (GPUs), are self-contained parallel computational devices that can be housed in conventional desktop and laptop computers and can be thought of as prototypes of the next generation of many-core processors. For certain classes of population-based Monte Carlo algorithms they offer massively parallel simulation, with the added advantage over conventional distributed multi-core processors that they are cheap, easily accessible, easy to maintain, easy to code, dedicated local devices with low power consumption. On a canonical set of stochastic simulation examples including population-based Markov chain Monte Carlo methods and Sequential Monte Carlo methods, we nd speedups from 35 to 500 fold over conventional single-threaded computer code. Our findings suggest that GPUs have the potential to facilitate the growth of statistical modelling into complex data rich domains through the availability of cheap and accessible many-core computation. We believe the speedup we observe should motivate wider use of parallelizable simulation methods and greater methodological attention to their design. <s> BIB009 </s> Overview of Bayesian sequential Monte Carlo methods for group and extended object tracking <s> Efficient real-time implementations of SMC algorithms: in distributed and parallel ways <s> A practical way to implement the particle filter (PF) on a massively parallel computer is discussed. Although the PF is a useful tool for sequential Bayesian estimation, the PF tends to be computationally expensive in applying to high-dimensional problems because a enormous number of particles is required in order to appropriately approximate a PDF. One way to overcome this problem is to use large computing resources of a massively parallel computer. However, in implementing the PF on such a massively parallel computer, it is crucial to reduce the time cost for data transfer between different processing elements (PEs). In addition, in using a parallel computer with a multidimensional torus network topology, it is necessary to avoid data transfers between nodes distant from each other. The present study proposes a strategy in which the PEs in use are divided into small groups and the grouping is changed at each time step. The resampling is carried out within each group in parallel and data transfers between distant nodes never occur. Therefore, the time cost for data transfer would be greatly reduced and the efficiency is remarkably improved in comparison with the normal PF. <s> BIB010 </s> Overview of Bayesian sequential Monte Carlo methods for group and extended object tracking <s> Efficient real-time implementations of SMC algorithms: in distributed and parallel ways <s> Abstract This paper examines the problem of estimating the parameters describing system models of quite general nonlinear and multi-variable form. The approach is a computational one in which quantities that are intractable to evaluate exactly are approximated by sample averages from randomized algorithms. The main contribution is to illustrate the viability and utility of this approach by examining how high computational loads can be simply managed using commodity hardware. The proposed algorithms and solution architectures are profiled on concrete examples. <s> BIB011 </s> Overview of Bayesian sequential Monte Carlo methods for group and extended object tracking <s> Efficient real-time implementations of SMC algorithms: in distributed and parallel ways <s> Large-scale traffic systems require techniques that are able to 1) deal with high amounts of data and heterogenous data coming from different types of sensors, 2) provide robustness in the presence of sparse sensor data, 3) incorporate different models that can deal with various traffic regimes, and 4) cope with multimodal conditional probability density functions (pdfs) for the states. Often, centralized architectures face challenges due to high communication demands. This paper develops new estimation techniques that are able to cope with these problems of large traffic network systems. These are parallelized particle filters (PPFs) and a parallelized Gaussian sum particle filter (PGSPF) that are suitable for online traffic management. We show how complex pdfs of the high-dimensional traffic state can be decomposed into functions with simpler forms and how the whole estimation problem solved in an efficient way. The proposed approach is general, with limited interactions, which reduce the computational time and provide high estimation accuracy. The efficiency of the PPFs and PGSPFs is evaluated in terms of accuracy, complexity, and communication demands and compared with the case where all processing is centralized. <s> BIB012
SMC algorithms become computationally excessive when applied to large-scale systems. One can identify two major directions for speeding up the algorithms: by hardware implementations  BIB010 BIB011 BIB009 , or algorithmically, with improved distributed and parallelized methods BIB001 BIB012 , including by carrying out the resampling step in a distributed fashion BIB002  . The BIB011 sequential MCMC is implemented on high performance Graphics Processing Unit (GPU) cards in an appropriate parallel fashion. Various approaches for parallelized and distributed particle filtering are proposed in the literature BIB006 BIB003  BIB004 BIB003 . There are two main types of algorithms: (1) algorithms in which entire particle populations are exchanged amongst multiple processing units (PUs) and (2) others that communicate only statistical characteristics of the populations of particles (e.g. exchange the first and second order moments of the posterior state pdf). The methods exchanging statistical moments are more computationally efficient than the methods exchanging populations of particles and their weights. Most of these implementations have also the tendency to reduce the associated communication loads. Studies with a different number of particles are presented in BIB012 and marginalized particle filters in BIB005  . In  two methodologies for distributed particle filtering in sensor networks are presented. The first algorithm relies on likelihood factorization and training of parametric models for approximating likelihood factors. The second algorithm adds a training step into a more standard particle filtering framework, allowing adaptive encoding of the measurements. Distributed initialization of the state probability distribution of multiple targets is considered in BIB007 . The decomposition of the state space into separate subspaces can lead to efficient representations of the complex state pdf as shown in BIB008 BIB012 which reduces the computational complexity, with a different level of communications.