## 3 UAV Path Planning Model Based on Q-Learning Strategy  
### Q-Learning Theory  
Q-learning [25] is a reinforcement learning [26] strategy adoption rule, whereby agents learn an optimal strategy, maximizing their expected reward in the repeated game. That is to say, Q-learning describes an agent that uses unsupervised training to learn about an unknown environment. In general, we call where an agent is a \"state.\" The agent's movement from one position to another is an \"action.\" As shown in Figure 1, a \"state\" is depicted as a node, while \"action\" is represented by the arrows.  
The matrix R can be viewed as a reward table as shown in Figure 2. Suppose the agent is in state 2. From state 2, the agent can go to state 3 because state 2 is connected to 3. From state 2, however, the agent cannot directly go to state 1 because there is no direct arrow connecting state 1 and 2. From state 3, it can go either to state 1 or 4 or back to 2 (look at all the arrows around state 3). If the agent is in state 4, then the three possible actions are to go to state 0, 5 or 3. If the agent is in state 1, it can go either to state 5 or 3. From state 0, it can only go back to state 4. We can put the state diagram and the instant reward values into the following reward table, \"matrix R.\" In order to make the agent more intelligent, we add a similar matrix, \"Q,\" to the agent as a brain, representing the memory of what the agent has learned through experience. The rows of matrix Q represent the current state of the agent, and the columns represent the possible actions leading to the next state (the links between the nodes).  
Figure 1: Q-learning schematic diagram, where the circle denotes the “state” of the agent, and the dash with an arrow represent the “action” that the agent takes.  
At first, the agent starts out not knowing anything, so the matrix Q is initialized to zero. For the simplicity of explanation, we assume the number of states is known (six). If we did not know how many states were involved, the matrix Q could start out with only one element. It is a simple task to add more columns and rows in matrix Q if a new state is found. The transition rule of Q-learning is a very simple formula:  
\[Q(\text{state},\ \ \text{action})=R(\text{state},\ \ \text{action})+\gamma*Max[Q( \text{nextstate},\ \ \text{allocations})].\]  
So far, according to the above formula, a value assigned to a specific element of matrix Q is equal to the sum of the corresponding value in matrix R and the learning parameter \(\gamma\), multiplied by the maximum value of Q for all possible actions in the next state. The virtual agent will learn through experience, without a teacher (this is called unsupervised learning). The agent will explore from state to state until it reaches the goal. We will call each exploration an episode. Each episode consists of the agent moving from the initial state to the goal state. Each time the agent arrives at the goal state, the program goes to the next episode.  
Owing to the unstructured environment, the state of the environment and the actions taken by the UAV are not fully observable. So, in this problem, we assumed that the environment constituted a partially observable Markov decision process (POMDP) [27], which is a controlled dynamical process in discrete time useful for modeling resource control problems. Accordingly, UAV path planning is a highly complex problem, and can be described as a dynamical control process with a hidden Markov process. The following subsection bridges the gap between them.