Learning Flock: Enhancing Sets of Particles for Multi Sub-State Particle Filtering with Neural Augmentation

We consider a dynamic system formulated as a continuous-valued state-space model in discrete-time. The state vector at time $k$, denoted ${\boldsymbol{x}}^{k}\in\mathbb{R}^{d_{p}}$, describes the states of $t$ dynamic sub-states. Accordingly, ${\boldsymbol{x}}^{k}$ is comprised of $t$ sub-vectors $\{{\boldsymbol{x}}_{j}^{k}\}_{j=1}^{t}$ of size $d_{sp}\times 1$, with $d_{p}=t\cdot d_{sp}$, such that ${\boldsymbol{x}}^{k}=\left[{\boldsymbol{x}}_{1}^{k},{\boldsymbol{x}}_{2}^{k},..,{\boldsymbol{x}}_{j}^{k},..,{\boldsymbol{x}}_{t}^{k}\right]$. For instance, different sub-states can represent different targets in MTT [40].

Each sub-state vector evolves in time independently of the other sub-states, obeying a first-order Markov process. Specifically, we write the $j$th sub-state vector as ${\boldsymbol{x}}^{0:k}_{j}=\{{\boldsymbol{x}}_{j}^{0},\ldots,{\boldsymbol{x}}^{k}_{j}\}$, and assume that it obeys a motion model such that its conditional PDF satisfies

Accordingly, by writing ${\boldsymbol{x}}^{0:k}=\{{\boldsymbol{x}}^{0},\ldots,{\boldsymbol{x}}^{k}\}$, the overall state evolution PDF satisfies

where $p\left({\boldsymbol{x}}^{k}|{\boldsymbol{x}}^{k-1}\right)=\prod_{j=1}^{t}{p\left({\boldsymbol{x}}^{k}_{j}|{\boldsymbol{x}}^{k-1}_{j}\right)}$.

At each time-step $k$, the state is observed via noisy, possibly non-linear measurements, denoted ${\boldsymbol{z}}^{k}\in\mathbb{R}^{d_{m}}$. The relationship between the observations, i.e., the sensory data, and the state are reflected in the sensor model PDF

We particularly focus in settings where the observation model is invariant to the indexing of the sub-states. Mathematically, this indicates that the observation model in (3) is invariant to replacing ${\boldsymbol{x}}^{k}=\left[{\boldsymbol{x}}^{k}_{1},\ldots,{\boldsymbol{x}}^{k}_{t}\right]$ with $\left[{\boldsymbol{x}}^{k}_{j_{1}},\ldots,{\boldsymbol{x}}^{k}_{j_{t}}\right]$ for any permutation $j_{1},\ldots,j_{t}$ of $1,\ldots,t$.

Our objective is to design a system for recovering the state vector from all available data. Accordingly, for each time instance $k$, we are interested in providing an estimate of ${\boldsymbol{x}}^{k}$ based on all past and current measurements, i.e., ${\boldsymbol{z}}^{1:k}$. To focus on tracking tasks, we assume that the initial state is known.

We particularly consider multi sub-state tracking subject to the following requirements:

1. R1

   The state evolution PDF (2) and measurement model (3) can be non-Gaussian.

2. R2

   The measurement model (3) is given yet may be mismatched.

3. R3

   The system must operate in real-time with low latency.

4. R4

   The number of sub-states $t$ can take different values. Yet, for any given set of observations, we assume that it is known.

To cope with the above challenges, we consider settings where we have access to data for design purposes. We consider two possible settings:

1. S1

   Unsupervised settings - here the data is comprised of a set of $n_{t}$ series of measurements along $\kappa$ steps long trajectories, denoted $\mathcal{D}=\left\{\left({\boldsymbol{z}}^{1:\kappa}\right)\right\},|\mathcal{D}|=n_{t}$.

2. S2

   Supervised settings - here we also have access to the true states corresponding to the measurements as well as the measurements, i.e., $\mathcal{D}=\left\{\left({\boldsymbol{z}}^{1:\kappa},\bar{{\boldsymbol{x}}}^{1:\kappa}\right)\right\},|\mathcal{D}|=n_{t}$.

pf are a popular family of algorithms suitable for tracking in non-Gaussian dynamics [2, 41] (thus meeting R1). These Monte-Carlo algorithms [9] track a representation of the posterior $p({\boldsymbol{x}}^{k}|{\boldsymbol{z}}^{1:k})$, by approximating its Bayesian recursive formulation which holds under the Markovian model in (1) and (2). Specifically, by Bayes’ law it holds that [42]

Under model assumptions (1)-(2), the posterior at time $k$ in (4) can be related to the posterior at time $k-1$ based on Chapman–Kolmogorov equation, i.e.,

and on

turning (4) into a recursive update rule.

Direct recursive updating of the posterior based on (4)-(6) is often challenging or infeasible to compute. PFs approximate it using a set of $N$ particles ${\{{\boldsymbol{x}}^{k}_{i}\}}_{i=1}^{N}$ and their weights ${\{w^{k}_{i}\}}_{i=1}^{N}$. Each particle represents a hypothesis on the system’s state, and the weights indicate their trajectory’s relative accuracy. As the state vector represents $t$ sub-states, each particle ${\boldsymbol{x}}_{i}^{k}$ consists of $t$ sub-particles $\{{\boldsymbol{x}}^{k}_{j,i}\}_{j=1}^{t}$ that share the same weight $w^{k}_{i}$. The posterior PDF can be estimated as a weighted sum of kernel functions $\{K_{j,i}(\cdot)\}_{j,i=1}^{t,N}$ evaluated at the sub-particles [42] via

By using an adequate number of particles, PFs can approximate any probability distribution. The state is then recovered as a weighted average of the particles, i.e.,

Based on the principle of the importance sampling  [43], Algorithm 1 describes a generic PF iteration, which is comprised of two main stages: $(i)$ sampling current time-step particles $\{{\boldsymbol{x}}_{i}^{k}\}_{i=1}^{N}$ using the importance density  [43] $q\left({\boldsymbol{x}}^{k}\right)$ (Steps 1-1), and $(ii)$ update the weights $\{w_{i}^{k}\}_{i=1}^{N}$ according to the sampled density $q({\boldsymbol{x}}^{k})$ and real distribution $\pi({\boldsymbol{x}}^{k})$ to represent the relative accuracy of each trajectory with the new particles (Steps 1-1). By the Markovian nature of the signal, the real distribution satisfies $\pi({\boldsymbol{x}}^{0:k}|{\boldsymbol{z}}^{1:k})\propto\pi({\boldsymbol{z}}^{k}|{\boldsymbol{x}}^{k})\pi({\boldsymbol{x}}^{k}|{\boldsymbol{x}}^{k-1})\pi({\boldsymbol{x}}^{0:k-1}|{\boldsymbol{z}}^{1:k-1})$. The sampling distribution $q\left(\cdot\right)$ is typically chosen to be of a decomposable form [2], such that $q({\boldsymbol{x}}^{0:k}|{\boldsymbol{z}}^{1:k})=q({\boldsymbol{x}}^{k}|{\boldsymbol{x}}^{0:k-1},{\boldsymbol{z}}^{1:k})q({\boldsymbol{x}}^{0:k-1}|{\boldsymbol{z}}^{1:k-1})$. This choice of $q(\cdot)$ and $\pi(\cdot)$ leads to a generic weight update rule (Step 1) in which

For increased accuracy, PFs require more particles, and this requirement grows dramatically with the state dimension [44]. The Number of particles greatly affects the complexity of PFs, performance however is not necessarily dictated by the number of particles $N$, and is typically influenced by the effective number of particles, defined as [43]

Specifically, small ${N_{\rm eff}}$ indicates a phenomenon referred to as particles degeneracy [2, 42], where the posterior is poorly estimated due to being dominated by a small portion of the overall particles. Having a large $N_{\rm eff}$ is typically a desired property of PFs. Nonetheless, on its own it does not ensure a good representation of the posterior, as one may still encounter sample impoverishment [2, 42] (or particle collapse), where many particles converge to the same location. Applying particles resampling  [16, 2, 15] when $N_{\rm eff}$ goes below a threshold $N_{\rm th}$ tackles both phenomena to a degree.

PFs rely on stochastic procedures, and are prone to producing outliers or deformations, particularly when the number of particles $N$ is small. However, the handling of a large number of particles, even if adaptive [45], comes with additional overhead and limit real time applications imperiling R3. Moreover, the PDF induced by $N\rightarrow\infty$ particles does not necessarily converge to the true PDF, and may depend on the sampling distribution  [46, 47]. PFs thus require knowledge and the ability to approximate (2) and (3). When either is mismatched, as pointed in R2, performance considerably degrades, possibly yielding an estimation bias that cannot be rectified solely through increasing $N$.

Consequently, a main consideration when designing a PF revolves around the choice of the importance sampling function $q({\boldsymbol{x}}^{k})$, with the number of particles tuned to reach a desired performance, and different PFs incorporate various methods to that aim. Such approaches, combined with dedicated resampling procedures, are the basis of the regularized PF  [48], the APP  [7], the target resampling APP  [7], and the progressive proposal PF  [49], each with its own associated computational costs and accumulated latency. The proliferation of PF techniques, combined with availability of data in S1-S2, motivate exploring a complimentary data-aided approach to efficiently improve PDF representation; one that can be integrated into any given PF algorithm, as studied in the following section.

We build on the understanding that the key factors limiting the ability of PFs to adequately represent a PDF when $N$ is limited (R3), and in the presence of stochasticity and model mismatches (R2), are encapsulated in the complete particles-weights set. We recognize that PF algorithms typically handle each full trajectory ${\boldsymbol{x}}_{i}^{0:k}$ separately [48, 7, 49, 42, 50]. Therefore, each particle evolves with only minimal consideration of other particles through the relativity of their weights (Steps 1-1 of Algorithm 1). We thus propose to tackle the challenging factors mentioned in Subsection II-C in a manner that can be integrated into existing PF by a per iteration application of a correction term to each particle, which accounts for all particles. This methodology can prevent PFs typical deterioration of individual particles as time advances, aligning outliers and correcting inaccurate sampling, mitigating particle degeneracy and sample impoverishment. Doing so leads to a substantial improvement of the capture of the state probability distribution along the trajectory, as we demonstrate in Section IV.

In particular, we use deep learning tools as correction terms via neural augmentation [19, 21] in conjunction with the pertinent PF algorithm, to modify a flock of particles by information sharing. An augmentation example of our proposed LF into a generic PF is exemplified as Algorithm 2. There, $f_{{\boldsymbol{\theta}}}(\cdot)$ represents the LF DNN with trainable parameters ${\boldsymbol{\theta}}$. This DNN is trained to combine information of all particles in the flock in order to correct each individual particle and overcome stochastic predicaments, as well as the need to accurately implement the importance sampling and weight adjustments. We next detail on the architecture of this LF module and its training procedure.

The LF module, parameterized by ${\boldsymbol{\theta}}$, is incorporated into a given PF algorithm chosen for a specific task. As detailed in Algorithm 2 (Step 2), it maps a complete set of particles and weights $\{\breve{{\boldsymbol{x}}}_{i}^{k},\breve{w_{i}}^{k}\}_{i=1}^{N}$ into a correction term $f_{{\boldsymbol{\theta}}}(\{\breve{{\boldsymbol{x}}}_{i}^{k},\breve{w}_{i}^{k}\}_{i=1}^{N})$. The LF module design is based on the following considerations: $(i)$ every particle-weight correction should take into account all other particles and weights; $(ii)$ the particles and weights pairs, and their update, is invariant to their ordering and to the internal ordering of the sub-sates; $(iii)$ the LF block should not induce considerable latency.

Accordingly, we propose the architecture illustrated in Fig. 1. The architecture consists of $J$ flock-update blocks, each combining two parallel sub-particle embedding networks, with permutation-invariant SA architecture. In the basic flock-update block, each state particle-weight pair $[\breve{{\boldsymbol{x}}}_{i}^{k},\breve{w_{i}}^{k}]\in\mathbb{R}^{{d_{p}}+1}$ is separated to $t$ single sub-state sub-particles $\{[\breve{{\boldsymbol{x}}}_{j,i}^{k},\breve{w_{i}}^{k}]\}_{j=1}^{t}\in\mathbb{R}^{{d_{sp}}+1}$ (where the weight is shared among all sub-particles). These are transformed into two sub-particle embeddings of length $P\times 1$, main and secondary, by two separate embedding fully connected (FC) networks, coined ${\rm Emb-Net1}$ and ${\rm Emb-Net2}$, respectively. For each of the $N$ particles, each sub-particle main embedding is added to the mean of the $t-1$ other sub-particles secondary embeddings to get its $t$ full embeddings of the same dimension $P\times 1$. Note that this procedure is invariant to the order of the sub-particles, thus maintaining the desired permutation invariance. Moreover, the same two embedding networks are used for all sub-particles, and thus the architecture is invariant to the number of sub-states $t$, satisfying R4.

The full embeddings are then combined using dedicated SA blocks (e.g., in the architecture illustrated in Fig. 1, two such blocks are used). In these blocks, for each of the $t$ sub-states, all $N$ full sub-particles embeddings from all particles are updated in the same SA layer (${\rm SA-Net}$) considering all $N$ full embeddings associated with the same sub-state. This layer is followed by an FC network (${\rm FC-Net}$) applied in parallel to each of the $N\cdot t$ SA outputs, thus maintaining the particle permutation invariance of the SA layer. To get each particle update, at the output of the last FC layer, the $t$ sub-states updates are concatenated while the weights are averaged. For intermediate filtering stages applications where each particle’s sub-state is assigned with its own weight, the initial weight sharing and final weight averaging can be skipped.

Inspired by multi-head attention mechanisms [36], we apply $J$ flock-update blocks in parallel. The $J$ outputs are summed up with the initial particle-weight pairs to get the final particle. On flock-update block $J$, $J>1$, prior to the last FC network, all embeddings for each sub-state are averaged, providing a single embedding per sub-state, that is turned into a single particle correction term at the final output of the block. That single particle term acts as baseline per sub-state and is added to all particles correction terms (from all other flock-update blocks), shifting their entire induced PDF accordingly.

We note that the architecture and its trainable parameters, as well as the described particles and sub-particles processing, is invariant to the number of sub-states $t$ and to their internal ordering (thus holding R4). They are also invariant to the number of particle-weight pairs $N$ and to their ordering, while enabling parallel operation (thus facilitating R3). Accordingly, the same trained architecture can be applied in settings with different numbers of sub-states and particles, e.g., an architecture trained for MTT with a small number of targets (and/or particles) can be readily applied to track a larger number of targets (and/or particles), as we show in Section IV.

The training of $f_{{\boldsymbol{\theta}}}(\cdot)$ tunes ${\boldsymbol{\theta}}$, encourages its correction term to satisfy two main properties: $(i)$ to gauge the accuracy of the state estimate (8); $(ii)$ to align the PDF represented by a set of particles, and approximated using (7), with a desired PDF. We next formulate the proposed loss assuming supervised settings (S2), after which we show how it can be specialized to unsupervised scenarios (S1).

We note that the loss function in (11) expresses a sum of $\kappa$ time-steps components of (12), and (13), computed separately at each time-step $k$ when an LF block with parameters ${\boldsymbol{\theta}}$ is applied. We can leverage this property to enable training LF on each (or selected) time-step seperately using conventional stochastic gradient descent (SGD)-based learning, while avoiding the need for differentiability between iterations (and avoiding the need to backpropagate through sampling operators using special sampling adaptations  [52, 53], or by introducing approximated operators [29, 28]).

A candidate training method based on mini-batch SGD for an LF-PF is formulated in Algorithm 3. There, the LF-PF is executed in parallel with the reference PF flow (Steps 3, 3), that maintain particles-weights sets for each trajectory, respectively denoted $\mathcal{P}_{q}^{k},\mathcal{R}_{q}^{k}$ for the $k$th time step of the $q$th batch. Training is done by loss calculation (Steps 3-3) and its backpropagation (Step 3), while nullifying gradient propagation between iterations and through sampling operations. To achieve a fast and continuous convergence, on each time-step $k$ we mix the loss of different trajectories by running a bigger batch of trajectories $\mathcal{D}_{q}$, while training on a random subset of the batch that changes between time-steps (Step 3). For tracking stabilization during training, particularly at the beginning, once an estimated sub-state strays farther than a predetermined distance from the desired sub-state (Step 3) the whole trajectory is eliminated from $\mathcal{D}_{q}$ for the training on the following time-steps (Step 3).

The proposed trainable LF module is trained as part of a specific PF, and possibly with an additional more complex PF serving as reference. Nonetheless, once trained, it can be readily transferred into alternative PFs that meet R1, as demonstrated in Subsection IV-A. Moreover, by harnessing supervised data, the LF-PF can also cope with R2 without incorporating additional mechanisms to explicitly mitigate it as in  [54]; while enabling the pertinent PF to operate with a smaller number of particles with minimal computational cost to meet R3. As discussed in Subsection III-B, the LF architecture is invariant to the number of sub-states $t$, and, e.g., the same module can be trained and evaluated for tracking a different number of sub-states, thus meeting R4. These properties are consistently demonstrated in Subsection IV-B.

Our LF module, trained with a specific number of particles, allows PFs to operate reliably with different, and even lower values of $N$, boosting low latency filtering. However, the application of LF comes at the cost of some excessive complexity, depending on the parameters $J$, $d_{sp}$, $t$, $N$, $P$, as well as the flock-update parameters, number of sub-embeddings $E$ ($1$, or $2$ to include secondary embedding), number of SA blocks $S$, and FC width multiplier $B$. The total floating point multiplications (FPM) requirement per particle can be divided to three parts with accordance to Fig. 1: broadly speaking, $(i)$ the embedding networks ${\rm Emb-Net1/2}$ require ${JEt\cdot BP\left(P+d_{sp}+3BP\right)}$ FPM; $(ii)$ the SA networks ${\rm SA-Net0/1}$ involve $JSt\cdot 2P^{2}\left(2+N/P+B+B^{2}\right)$; and $(iii)$ the final FC layers require $t\cdot BP\left(BP+d_{sp}\right)$ FPM. While this excessive complexity varies considerably with the system parameters, it is noted that the operation of such compact DNNs is highly suitable for parallelization and hardware acceleration, that often notably reduces inference speed of PFs with similar performance, as demonstrated in Section IV.

Our proposed LF jointly corrects particles and their weights utilizing only the particles and weights (that are merely updated by the LF block). This boosts versatility and flexibility enabling a trained LF block to be conveniently integrated and apply a fix to a flock at any point on different types of PFs flow, whether classical or DNN augmented, or even to a different PF than the one it was trained on (as shown in Subsection IV-A). Nonetheless, one can potentially extend LF to process additional information when updating the particles, such as past particles (smoothing), the measurements, and data structures [55]. Moreover, the LF block can be adapted to change its output, for instance, to include an estimated state or additional embedding for other purposes. It can possibly also be integrated in PFs involving detection (e.g., track-before-detect [7]). We leave these extensions for future work.

Here, we evaluate LF-PF in comparison to state-of-the-art neural augmentation of PFs, based on algorithm unrolling  [31]. Our goal here is to showcase the performance gains of our proposed LF algorithm compared to alternative types of DNN augmentations, and that its operation is complementary to other enhancements of PFs.

We proceed to evaluating LF-PF for non-linear radar tracking, considering both a single and multiple targets. We use the non-linear settings outlined in [7, Sec. VI], which allow us to compare the performance and latency of PFs to their LF augmented versions in a scenario of practical importance.