# Investigating Routing in the VANET Network: Review and Classification of Approaches
## 2 A Review of Past Research (Related Work)
**Markov processes**  
Markov process (or Markov chain) is a stochastic (random) model 1 that describes a sequence of possible states in which the current state depends only on the previous state. This feature is also called Markov. For reinforcement learning, it means that the next stage of an AI agent depends only on the last state and not on all previous states. The Markov process is stochastic (random), which means that the transition from the current state (s) to the next state (s\({}^{\prime}\)) occurs only with a certain probability (\(P_{ss^{\prime}}\))  
\[P_{ss^{\prime}}\mathbb{P}\big{[}S_{t+1}=s\big{|}S_{t}=s^{\prime}\big{]} \tag{2}\]  
\(P_{ss^{\prime}}\) is the entry in the state transition matrix \(\mathbb{P}\), which defines the transition probabilities from all states to all successor states (s\({}^{\prime}\)). \[p=from \begin{bmatrix}P_{11}&\ldots&P_{1n}\\ \vdots&\ddots&\vdots\\ P_{n1}&\ldots&P_{m}\end{bmatrix}  \tag{3}\]  
**Markov reward process**  
The reward Markov process is a tuple \(<S,\ P,\ R>\). Here, \(\mathbb{R}\) is the reward that the agent expects to receive in state s. The AI agent is motivated by the fact that to achieve a particular goal (e.g., winning a game of chess), certain states (game configurations) are more promising than others in terms of strategy and potential for winning the game. \[R_{s}=\mathbb{E}_{\pi}[R_{t+1}|S_{t}=s] \tag{4}\]  
The main issue is the total reward (Gt) equation, which is the expected cumulative reward that the agent receives across the sequence of all states. The discount coefficient \(\gamma\in[0,1]\) measures each reward. We find discounting rewards mathematically convenient because doing so avoids infinite returns in cyclic Markov processes. In addition, the discount factor means that the further into the future we consider, the less important the rewards are to immediate satisfaction since the future is often uncertain. For example, if the reward is financial, immediate rewards may be more beneficial than delayed rewards. \[G_{t}=R_{t+1},R_{t+2},R_{t+3}+\ldots=\sum_{k=0}^{\infty}\gamma^{k}R_{t+k+1} \tag{5}\]  
**Value function**  
Another important concept is the concept of the value function \(v(s)\). This function draws a measure for each state '\(s\)'. The value of a state '\(s\)' is the total expected reward that the AI agent will receive if it starts progressing in state '\(s\)'. \[\mathbf{v(s)}=\mathbb{E}[\boldsymbol{G_{t}}|\boldsymbol{S_{t}}=\boldsymbol{s}] \tag{6}\]  
The value function can be divided into two parts:  
* The agent receives the immediate reward \(R_{t+1}\) in state '\(s\)'. * The discounted value \(v(s)_{t+1}\) of the next state after the state '\(s\)'. \[ \begin{array}{rcl}\mathbf{v(s)}&=&\mathbb{E}[\boldsymbol{G_{t}}\boldsymbol{ S_{t}}=\boldsymbol{s}]\\ &=&\mathbb{E}[\boldsymbol{R_{t+1}}+\gamma\boldsymbol{R_{t+2}}+\gamma^{2} \boldsymbol{R_{t+3}}+\ldots|\boldsymbol{S_{t}}=\boldsymbol{s}]\\ &=&\mathbb{E}[\boldsymbol{R_{t+1}}+\gamma(\boldsymbol{R_{t+2}}+\gamma \boldsymbol{R_{t+3}}+\ldots)\,|\boldsymbol{S_{t}}=\boldsymbol{s}]\\ &=&\mathbb{E}[\boldsymbol{R_{t+1}}+\gamma\boldsymbol{v(S_{t+1})}\,| \boldsymbol{S_{t}}=\boldsymbol{s}]\end{array}  \tag{7}\]  
**Bellman equation for Markov reward processes**  
The decomposed value function is considered as the Bellman equation for Markov reward processes. This function is visualized using node graph. Starting at state '\(s\)' results in the value \(v(s)\). By being in state '\(s\)', we have a certain probability (\(P_{\text{ss}}\)) to end up in the next state '\(s\)'. In this particular case, two next states may occur. To obtain the value of \(v(s)\), the values of \(v(s)\) of the possible next states weighted by the probabilities of \(P_{\text{ss}}\) should be added and then added to the immediate reward of being in state '\(s\)'.