# An Improved Q-Learning-Based Sensor-Scheduling Algorithm for Multi-Target Tracking
## 4 Detailed Description of the Proposed Algorithm
### Task Allocation
#### 4.3.2 Learning Process  
In the learning process, each sensor needs to maintain a \(Q\) table, as shown in Figure 3. Initially, all entries in the \(Q\) table are zero. Sensors select an action from the action space to execute at each time step. The environment then moves to the next state based on the action taken by the agent. The update of the \(Q\) values is calculated by the following rules:  
\[Q^{(t)}=(1-\beta)Q^{(t)}+\beta[R^{(t)}+\gamma\max_{a}(Q_{a}^{(t+1)}-Q^{(t)})]. \tag{13}\]  
where \(\beta\in[0,1]\) is the learning rate that controls the learning speed; \(\gamma\) is the discount factor, which we set to 0.8 to consider the expected reward in the near future. The reward function \(\mathcal{R}\) for the agent is defined as  
\[\mathcal{R}(a_{i})=\left\{\begin{array}{ll}\left(n_{0}-n_{i}\right)(\lambda \frac{e_{res}-d_{i}}{r_{s}}+(1-\lambda)\frac{r_{s}-d_{i}}{r_{s}}),&i\
eq 0\\ (1-m_{not})\frac{e_{init}-e_{res}}{e_{init}},&i=0\end{array},\right. \tag{14}\]  
where \(\lambda\in[0,1]\) is a weight coefficient; \(e_{res}\) is the residual energy; \(e_{init}\) is the initial energy; \(r_{s}\) is sensing range; \(d_{i}\) is the distance to the \(i\)-th target; \(n_{0}\) is the number of nodes required to track a single target; \(n_{i}\) is the number of nodes that choose to track the \(i\)-th target currently; and \(m_{not}\) is the number of targets that are not allocated enough tracking nodes.  
Figure 3: \(Q\) table.  
According to Equation (14), when \(i\
eq 0\), the node chooses to track the \(i\)-th target. In this manner, if \(n_{i}<n_{0}\), then the node is qualified obtains a positive reward. Otherwise, the node is a redundant tracking node and receives no reward or one that is negative. The reward function consists of two parts: energy and distance; more rewards are given to nodes with more residual energy and closer to the target.  
On the other hand, when \(i=0\), the node chooses to go to sleep. In this manner, if \(m_{not}=0\), all targets meet tracking requirements, it is reasonable for the node to choose to sleep, and a positive reward can be obtained. Otherwise, if \(m_{not}\
eq 0\), there are targets that do not meet tracking requirements. In this case, the node should assist in the tracking task, so choosing to sleep receives zero or negative rewards. Since the node chooses to sleep, the reward function no longer includes tracking-related indicators. More rewards will be given to nodes with low residual energy.  
The agent will choose the most rewarding action in the \(Q\) table at each time step or randomly select an action to execute according to the exploration-exploitation strategy. This process repeats until the maximum number of iterations is reached. By this iterative calculation, each agent learns the \(Q\) value of performing different actions in different environmental states, and then updates the \(Q\) table. After the iteration of the \(Q\) model is completed, we simply need to look up the final \(Q\) table to obtain the agent's optimal policy \(\pi^{*}\), that is, the optimal scheduling strategy for sensor resource allocation in the multi-target-tracking scenario. \(\pi^{*}\) can be expressed as  
\[\pi^{*}==\operatorname*{argmax}_{a\in A}Q(S,a). \tag{15}\]