# Reinforcement-Learning-Based Path Planning: A Reward Function Strategy
## 2 Proposed Methodology
### Reinforcement Learning and Q-Learning Algorithm  
The sequence of decisions in RL is determined by the Markov decision process introduced by [PERSON] [28]. The MDP consists of a set of states of an environment, a set of actions taken by an agent, and a transition probability distribution that gives the probability of moving from one state to another after completing an action in another state. This process captures the effect of each action that has an associated trade-off. Figure 3 shows the process of RL in which the following elements interact [15; 29]:  
* An agent is an entity that perceives/explores an environment and makes decisions. * An environment includes everything surrounding an agent and is generally assumed to be stochastic. * Actions correspond to an agent's movement in an environment. * State is the representation of an agent over time. * Reward is a numerical value that an agent tries to maximize by the selection of its actions. * Policy represents a strategy used by an agent to select an action based on the present state. The following is a general presentation of the MDP, extracted from [14; 15]. If you want to estimate the expected reward considering three arguments--state, action, and next state--then \(r\,:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R}\) is expressed as follows:  
\[r\big{(}s,a,s^{\prime}\big{)}\doteq\mathbb{E}[R_{t}\,|\,S_{t-1}=s,\ A_{t-1}=a, S_{t}=s\prime]=\sum_{r\in\mathcal{R}}r\frac{p(s^{\prime},r|s,a)}{p(s^{\prime}|s,a)} \tag{5}\]  
Reward terms for the present study are shown in Equation (6), where there are two main objectives: to incentivize an agent to move as fast as possible, reducing the number of direction changes, and to increase diagonal movements, which represent movements with greater distances:  
\[r\big{(}s,a,s^{\prime}\big{)}=\left\{ \begin{array}{ll}-1.5+r_{n}&\quad if \ s=NE,\ NO,SE,SO\\ -1+r_{n}&\quad if\ s=N,\ S,\ E,O\\ 100+r_{n}&\quad\quad collision\end{array} \right. \tag{6}\]  
\[r_{n}=\left\{ \begin{array}{ll}-2&\quad if\ s=s_{t-1}\\ 0&\quad if\ s\
eq s_{t-1}\end{array} \right. \tag{7}\]  
The objective is to maximize the performance, \(G_{t}\), that corresponds to the sum of each reward for each time instant, as shown in Equation (8), where \(T\) is the final time:  
\[G_{t}\doteq R_{t+1}+R_{t+2}+R_{t+3}+\ldots+R_{T} \tag{8}\]  
A complete sequence of rewards, from the initial state to the final state, is called an episode. Although episodes conclude in terminal states, the rewards are not always the same for each episode. In this regard, the maximization of the expected performance is accomplished through the parameter \(\gamma\), which is represented as follows:  
\[G_{t}\doteq R_{t+1}+\gamma R_{t+2}+\gamma^{2}R_{t+3}+\ldots=\sum_{k=0}^{\infty }\gamma^{k}R_{t+k+1} \tag{9}\]  
where parameter \(\gamma\) is referred to as the discount rate and has values of \(0\leq\gamma\geq 1\). Several exact solutions and approximations have been developed to solve the MDP. These methods can be classified into two main groups: tabular methods and neural networks. Figure 4 shows a general diagram of the main algorithms based on the methods used. With regard to the correlation between states and actions established by the policy, the optimal policy leads to the generation of a maximum trade-off. Dynamic programming is  
Figure 4: Classification of the main methods for solving MDP control tasks [15]. based on the assumption of the ideal MDP, which allows for the calculation of the trade-off for all possible actions. The most commonly used dynamic programming algorithms are value iteration and policy iteration. In the present study, policy iteration was used, since it implies low costs of computational resources due to requiring a lower number of iterations to converge.