# Temperature Control Unit--Modeling and Implementation of a Particle Filter on a Microcontroller
## 2 Particle Filter  
The particle filter is a state estimation algorithm that can be used on linear or non-linear discrete-time systems, including systems with non-Gaussian noises. The system is represented by the following equations:  
\[\left\{\begin{array}{l}\mathbf{x}^{(k+1)}=\mathbf{f}(\mathbf{x}^{(k)}, \mathbf{u}^{(k)};k)+\mathbf{v}^{(k)}\\ \mathbf{y}^{(k)}=\mathbf{g}(\mathbf{x}^{(k)})+\mathbf{n}^{(k)}\end{array} \right., \tag{1}\]where \(k\) denotes the time step number, \(\mathbf{x}^{(k)}\) is the state vector, \(\mathbf{u}^{(k)}\) is the control inputs vector, \(\mathbf{y}^{(k)}\) is the vector of measurement outputs, \(\mathbf{f}(\cdot)\) is the transition functions vector, and \(\mathbf{g}(\cdot)\) is the measurement functions vector, \(\mathbf{v}^{(k)}\) and \(\mathbf{n}^{(k)}\) are the process and measurement noises, respectively. The transition and measurement model can be linear or nonlinear. In the latter case, the equations of state cannot be written in a matrix form [27].  
The main purpose of the state estimation is to obtain internal variables \(\mathbf{x}^{(k)}\) that cannot be directly measured and to filter out measurement noise from the signals \(\mathbf{y}^{(k)}\).  
The basis of the particle filter is the recursive Bayesian filter algorithm [28; 29]  
\[p\Big{(}\mathbf{x}^{(k)}|\mathbf{Y}^{(k)}\Big{)}=\frac{p\Big{(}\mathbf{y}^{(k) }|\mathbf{x}^{(k)}\Big{)}p\Big{(}\mathbf{x}^{(k)}|\mathbf{Y}^{(k-1)}\Big{)}}{ p\big{(}\mathbf{y}^{(k)}|\mathbf{Y}^{(k-1)}\big{)}}, \tag{2}\]  
where:  
* \(\mathbf{Y}^{(k)}=\{\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(k)}\}\)--the set of output vectors,
* \(p\Big{(}\mathbf{x}^{(k)}|\mathbf{Y}^{(k)}\Big{)}\)--the posterior Probability Density Function (PDF);
* \(p\Big{(}\mathbf{y}^{(k)}|\mathbf{x}^{(k)}\Big{)}\)--the likelihood;
* \(p\Big{(}\mathbf{x}^{(k)}|\mathbf{Y}^{(k-1)}\Big{)}\)--the prior PDF;
* \(p\Big{(}\mathbf{y}^{(k)}|\mathbf{Y}^{(k-1)}\Big{)}\)--the evidence which is given by equation \[p\Big{(}\mathbf{y}^{(k)}|\mathbf{Y}^{(k-1)}\Big{)}=\int p\Big{(}\mathbf{y}^{(k )}|\mathbf{x}^{(k)}\Big{)}p\Big{(}\mathbf{x}^{(k)}|\mathbf{Y}^{(k-1)}\Big{)} dx^{(k)}.\] (3)  
The posterior PDF in the particle filter is represented by a set of particles, and its weights are given by \(\{\mathbf{x}^{i},q^{i}\}\), where each particle \(\mathbf{x}^{i}\) has a weight \(q^{i}\), for \(i=\{1,\ldots,N_{p}\}\). The approximation of posterior PDF for a large number of particles can be written as  
\[p\Big{(}\mathbf{x}^{(k)}|\mathbf{Y}^{(k)}\Big{)}\overset{N_{p}\to\infty}{=} \hat{p}\Big{(}\mathbf{x}^{(k)}|\mathbf{Y}^{(k)}\Big{)}=\sum_{i=1}^{N_{p}}q^{i,(k)}\delta\Big{(}\mathbf{x}^{(k)}-\mathbf{x}^{i,(k)}\Big{)}, \tag{4}\]  
where \(\delta(\cdot)\) denotes a Dirac Delta function.  
The first proposed particle filter algorithm is the bootstrap algorithm [4; 28] presented in Algorithm 1 and in Figure 1.  
1. Initialization. Draw \(N_{p}\) initial values from the posterior PDF \(\mathbf{x}^{i,(0)}\sim p(\mathbf{x}^{(0)})\). Set time step \(k:=1\). Do this step only once.  
2. Prediction. Draw the new particles \(\mathbf{x}^{i,(k)}\sim p\big{(}\mathbf{x}^{(k)}|\mathbf{x}^{i,(k-1)}\big{)}\), where \(i=\{1,\ldots,N_{p}\}\) from the transition model.  
3. Update. Determine the weights of the \(N_{p}\) particles based on the measurement model  
\[q^{i,(k)}=p(\mathbf{y}^{(k)}|\mathbf{x}^{i,(k)}). \tag{5}\]  
4. Normalization. Scale values of the weights in such a way that their sum equals 1.  
5. Resampling. Draw \(N_{p}\) particles from among those that already exist. The PDF for drawing is defined by the set of normalized weights (the systematic resampling is applied [30]).  
6. End of the iteration. Estimate the state vector at \(k\)-th time step, increase the time step \(k=k+1\). Jump to the 2 nd step.  
Figure 1: Flow chart of the Bootstrap particle filter algorithm with systematic resampling.