# Minimizing the Cost of Spatiotemporal Searches Based on Reinforcement Learning with Probabilistic States

Authors: Lei Han; Chunyu Tu; Zhiyong Yu; Fangwan Huang; Wenzhong Guo; Chao Chen; Zhiwen Yu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Portraying the trajectories of certain vehicles effectively is of great significance for urban public safety. Specially, we aim to determine the location of a vehicle at a specific past moment. In some situations, the waypoints of the vehicle’s trajectory are not directly available, but the vehicle’s image may be contained in massive camera video records. Since these records are only indexed by location and moment, rather than by contents such as license plate numbers, finding the vehicle from these records is a time-consuming task. To minimize the cost of spatiotemporal search (a spatiotemporal search means the effort to check whether the vehicle appears at a specified location at a specified moment), this paper proposes a reinforcement learning algorithm called Quasi-Dynamic Programming (QDP), which is an improved Q-learning. QDP selects the searching moment iteratively based on known past locations, considering both the cost efficiency of the current action and its potential impact on subsequent actions. Unlike traditional Q-learning, QDP has probabilistic states during training. To address the problem of probabilistic states, we make the following contributions: 1) replaces the next state by multiple states of a probability distribution; 2) estimates the expected cost of subsequent actions to calculate the value function; 3) creates a state and an action randomly in each loop to train the value function progressively. Finally, experiments are conducted using real-world vehicle trajectories, and the results show that the proposed QDP is superior to the previous greedy-based algorithms and other baselines.


---

## Body

## 1. Introduction

Portraying the trajectories of some vehicles in a city is important to foresee potential safety issues, for example, to infer the intention of a suspicious vehicle. We only get the locations of the vehicle at some key moments, instead of at all moments for economic efficiency. Figure1 shows a typical application scenario. The sequential numbers indicate the waypoints of the vehicle trajectory from 8 : 00 to 9 : 00 on a certain day, of which the yellow ones are the locations of some key moments. By locating a suspicious vehicle at certain times (such as target time, etc.) and marking them on a map until we can get a rough idea of its trajectory.Figure 1
Vehicle location at specific moments.To track vehicles in a city, vehicle Re-Identification (Re-Id) [1–4] focuses on how to identify the target vehicle in camera video records as accurately as possible. However, Re-Id does not consider how to select records, which are massive and only indexed by location and moment. As a result, Re-Id needs to be performed on all records exhaustively. With the rapid urbanization, there are a large number of cameras in the city. By searching within the video records of these cameras, it is possible but time-consuming to find the target vehicle at the target moment, because these records are massive and only indexed by location and moment, rather than by the contents such as the license plate number. Besides the straightforward strategy that all searches are performed at the target moment, another strategy worth exploring is to spend some searches at intermediate moments to determine the vehicle’s likely subsequent path, thus significantly narrowing the search area at the target moment. We call the effort to check whether the vehicle appears at a specified location at a specified moment as a spatiotemporal search.How to determine the location of a vehicle at the target moment with the minimumcost of spatiotemporal searches in massive camera video records? The cost of a spatiotemporal search can be considered as a constant for simplicity, regarding either human or artificial intelligence. In previous work [5], we proposed two greedy algorithms named Intermediate Searching at Heuristic Spatiotemporal Units (IHUs) and Intermediate Searching at Heuristic Moments (IHMs), and some other simple but uncompetitive baselines. Compared with the algorithm IHUs that considers both moments and location, IHMs can fully utilize the information gained from previous failed searches, performing location-by-location searches at the same time. Since IHMs is based on the greedy heuristic, it may result a locally optimal solutions. The most common way to go beyond the locally optimal solution is dynamic programming. Dynamic programming is essentially an exhaustive idea. By comparing all solutions, it can guarantee that the solution is globally optimal. However, there are too many spatiotemporal points to be considered, making the solution space too large to list all solutions. Reinforcement learning can alleviate the problem through quasi-dynamic programming process. The spatiotemporal search strategy based on reinforcement learning selects an intermediate moment according to known vehicle spatiotemporal points, taking into account the cost efficiency of the current action and its potential impact on subsequent actions. The strategy of spatiotemporal search is a standard finite Markov decision process [6]. Q-learning, a reinforcement learning algorithm, has been proved to eventually converge to the optimum action values with probability 1 so long as all actions are repeatedly sampled in all states and the action values are represented discretely [7, 8]. However, if adopting Q-learning directly to address our problem, since the next state (known spatiotemporal point of the vehicle trajectory) cannot be determined after the action (i.e., selecting an intermediate moment and performing the corresponding spatiotemporal searches), it is difficult to update the next state and the value function when training. To overcome this challenge, this paper proposes Quasi-Dynamic Programming (QDP) algorithm to improve the training phase of Q-learning. The contributions of this paper include:
(1)
We propose a reinforcement learning algorithm called QDP that can result the near optimal solution to the problem of minimizing spatiotemporal search cost(2)
To address the challenge of probabilistic state in the training phase, we propose a novel training method for QDP, which replaces the next state by multiple states with a probability distribution, estimates the expected search cost of subsequent selections to calculate the value function, and creates a state and an action randomly in each loop to train the value function progressively(3)
We evaluate the proposed QDP on real-world vehicle trajectories, and the results show that it is superior to the previous greedy-based algorithms (IHMs) and other baselinesThe contents of this paper are arranged as following: Section2 discusses some related work; Section 3 proposes the overall process of QDP, and explains the training method for QDP; then the experiments are conducted in Section 4; finally, the conclusions and future work are summarized in Section 5.


## 2. Related Work

Since this paper addresses the search problem based on reinforcement learning, we will introduce the related work from the two aspects of search theory and reinforcement learning.


### 2.1. Search Theory

The core issue of search theory is designing a search strategy to find a missing target, under constraints such as time limit, forces required, and task budget. Related work mainly comes from the field of operations research or cybernetics.Koopman [9–11] used the basic probability theory to optimize the conFigureuration of budgeted search forces to find stationary targets. Stone [12, 13] presented detailed mathematical assumptions and theoretical proofs for specific problems of moving target searching and found the necessary conditions for the optimal search strategy. Besides the above theoretical analysis, some other works adopted the search theory in practical application scenarios. Researchers [14–17] established a management framework of task planning and feedback controlling based on the classical search theory. For the task planning of satellite SPOT-5, Bensana [18, 19] and Agnese [20] compared the computational performance of complete searching algorithms (i.e., Depth-first Search, Dynamic Programming, Russian Doll Search) and incomplete searching algorithms (i.e., Greedy Search, Tabu Search) under different problem scales. To locate the target to be observed in a region by satellite scanning, Lemaitre et al. [21] discussed Greedy Search, Dynamic Programming, Constrained Programming, and Genetic Algorithms to solve the problem. Different from the existing work, we study a more realistic problem with high rate of knowledge update in the application scenario of vehicle tracking.


### 2.2. Reinforcement Learning

Reinforcement learning [22, 23] is used to describe and solve the problem that the agent learns to obtain the maximum reward or achieve a specific goal in the process of interacting with the environment. Reinforcement learning is widely used in areas such as process control, task scheduling, robotics, and smart games [24–26]. Some complex reinforcement learning algorithms can reach or even surpass the human level in certain tasks [27, 28]. Q-learning is one reinforcement learning algorithm we pay attention to in this paper. Watkins [29] proposed Q-learning first, which utilizes the reward of state-action pair for value function updating. Rummery and Niranjan [30] proposed SARSA, a reinforcement learning algorithm with online policy based on Q-learning. Harm van Seijen et al. [31] presents a theoretical and empirical analysis of Expected Sarsa, a variation on Sarsa, the classic on-policy temporal difference method for model-free reinforcement learning. DeepMind [32] proposed DQN (Deep Q-Networks) by combining convolutional neural networks and Q-learning. Different from traditional Q-learning that the next state is uniquely determined, in this paper, the next state is multiple states of a probability distribution, i.e., probabilistic states. We propose a novel training method to overcome the difficulty brought by probabilistic states.


## 2.1. Search Theory

The core issue of search theory is designing a search strategy to find a missing target, under constraints such as time limit, forces required, and task budget. Related work mainly comes from the field of operations research or cybernetics.Koopman [9–11] used the basic probability theory to optimize the conFigureuration of budgeted search forces to find stationary targets. Stone [12, 13] presented detailed mathematical assumptions and theoretical proofs for specific problems of moving target searching and found the necessary conditions for the optimal search strategy. Besides the above theoretical analysis, some other works adopted the search theory in practical application scenarios. Researchers [14–17] established a management framework of task planning and feedback controlling based on the classical search theory. For the task planning of satellite SPOT-5, Bensana [18, 19] and Agnese [20] compared the computational performance of complete searching algorithms (i.e., Depth-first Search, Dynamic Programming, Russian Doll Search) and incomplete searching algorithms (i.e., Greedy Search, Tabu Search) under different problem scales. To locate the target to be observed in a region by satellite scanning, Lemaitre et al. [21] discussed Greedy Search, Dynamic Programming, Constrained Programming, and Genetic Algorithms to solve the problem. Different from the existing work, we study a more realistic problem with high rate of knowledge update in the application scenario of vehicle tracking.


## 2.2. Reinforcement Learning

Reinforcement learning [22, 23] is used to describe and solve the problem that the agent learns to obtain the maximum reward or achieve a specific goal in the process of interacting with the environment. Reinforcement learning is widely used in areas such as process control, task scheduling, robotics, and smart games [24–26]. Some complex reinforcement learning algorithms can reach or even surpass the human level in certain tasks [27, 28]. Q-learning is one reinforcement learning algorithm we pay attention to in this paper. Watkins [29] proposed Q-learning first, which utilizes the reward of state-action pair for value function updating. Rummery and Niranjan [30] proposed SARSA, a reinforcement learning algorithm with online policy based on Q-learning. Harm van Seijen et al. [31] presents a theoretical and empirical analysis of Expected Sarsa, a variation on Sarsa, the classic on-policy temporal difference method for model-free reinforcement learning. DeepMind [32] proposed DQN (Deep Q-Networks) by combining convolutional neural networks and Q-learning. Different from traditional Q-learning that the next state is uniquely determined, in this paper, the next state is multiple states of a probability distribution, i.e., probabilistic states. We propose a novel training method to overcome the difficulty brought by probabilistic states.


## 3. Overall Process of Quasi-Dynamic Programming (QDP)

Symbols used in this paper are shown in Notations. LetO=o1,o2,⋯,oO be vehicles, L=l1,l2,⋯,lL be locations of a city, D=d1,d2,⋯,dD be days, Tr=tr1,tr2,⋯,trTr be trajectories. In this paper, a trajectory is defined as a sequence of spatiotemporal points, i.e., trox,dj=t1,lt1,t2,lt2,⋯ox,dj.Definition 1 (a spatiotemporal search).
The effort to check whether the target vehicleox appears at a specified location li at a specified moment topt in the camera records of that spatiotemporal point topt,li. If vehicle ox is found at location li at moment topt, ie topt,li∈trox,dj, it will returns 1, otherwise it returns 0. Formally,
(1)sox,topt,li=1,topt,li∈trox,dj0,elseProblem 2 (tracking an object by spatiotemporal search).
Give an objectox, a day dx, a past moment tp of that day, ox‘s location ltp at that moment, a current moment tx, camera records that make the spatiotemporal search sox,tk,li available in dx before/at tx, as well as history trajectories TR′, in which arbitrary dj<dx. When and where to execute a spatiotemporal search can base on TR′ and the outputs of previous searches. The problem is how to utilize a minimal number of searchs to find the object at current moment tx. Formally,
(2)giveox,dx,tx,tp,ltp,TR′beforesox,tk,liindxreturnlx,s.t.minsox,tx,lxs,s,⋯,sox,tx,lxThe difficulty of a spatiotemporal search is affected by many factors in the spatiotemporal point (e.g., traffic flow, road network, and building density). It needs to be quantified by professionals or artificial intelligence. LetC=cl11,cl21,⋯,clL1,⋯,cl1dx,cl2dx,⋯,clLdx contains the search cost per spatiotemporal point on day dx. It can be seen from the problem definition that we have to find the vehicle finally, so we use the cost of spatiotemporal search as the only indicator to measure the performance of different algorithms.The overall process of QDP is shown in Figure2. The process includes two phases: the training phase and executing phase. The training phase outputs the location decision model and the moment decision model. The location decision model is trained with the help of mobility prediction and basic optimal searching. This model will return the optimal searching location sequence at a given moment. The moment decision model is trained based on Monte-Carlo method and probabilistic states. This model will return the optimal moment that will be searched in the next action. The executing phase describes the online spatiotemporal search utilizing the trained moment decision model and location decision model.Figure 2
Overall Process of Quasi-Dynamic Programming (QDP).


### 3.1. Training the Location Decision Model

The location decision model is responsible to output the location decisiontopt,ξopt (the optimal searching location sequence at moment topt given by the moment decision model). It is trained with the help of mobility prediction and basic optimal searching. The mobility prediction algorithm is not the focus of this paper. In the previous work [5], we have analyzed the advantages of choosing the first-order Markov model for mobility prediction. Suppose that the transition probability matrix TPMΔtL×L represents the probabilities of a vehicle moving from one location to another after a period of time Δt=topt−ts, of which an element is pliopt, i.e., the probability of vehicle ox moves from location ls at moment ts to location li at moment topt.
(3)TPMΔtL×L=pliopt(4)pliopt=#trwithts,ls&topt,li#trwithts,ls,ts=t1,t2,⋯,tr∈TR′where the meaning of “#” is “the number of”,tr is a trajectory. Equation Equation (4) represents the ratio of “the number of trajectories that pass both ts,ls and topt,li” to “the number of trajectories of only the pass ts,ls”. TPMΔtL×L can be trained from historical vehicle trajectories. When given an original location, a row of probabilities is output as the predicted result of the destination location.The basic optimal searching theory can assign the priority of locations to search at. Suppose the searching location sequence at momenttopt is topt,ξopt=topt,l1ξopt,topt,l2ξopt,⋯,topt,liξopt,⋯,liξopt∈L.Definition 3 (probability-cost ratio).
The ratio of the probabilitypliξopt of finding the target vehicle to the cost cliξopt of the i−th spatiotemporal search in the sequence topt,ξopt, formally,
(5)ηtopt,liξopt=pliξoptcliξoptTheorem 4.
[33]: The necessary and sufficient condition for the sequence topt,ξopt to be the searching location sequence with the lowest search cost at moment topt is that the probability-cost ratios are in descending order.Consequently, the location decision can be made according to Theorem4.We need to estimate the search cost which will be used during training the moment decision model. The optimal sequencetopt,ξopt has a expected search cost:
(6)Costtopt,ξopt=∑i=1Lpliξopt×∑j=1icljξoptTo demonstrate how to calculate the expected search cost using Equation (6), we assume the spatiotemporal search costs cl13=cl23=cl33=cl43=1, the location transition probabilities pl13=1/3,pl23=0,pl33=2/3,pl43=0. Then, the descendingly sorted location sequence is t3,ξ3=t3,l3,t3,l1,t3,l2,t3,l4 at moment t3. Then the expected search cost is:
(7)Costt3,ξ3=pl33×cl33+pl13×cl33+cl13+pl23×cl33+cl13+cl23+pl43×cl33+cl13+cl23+cl43=23×1+13×1+1+0×1+1+1+0×1+1+1+1=43


### 3.2. Training the Moment Decision Model

Perform spatiotemporal searches at momenttopt should consider both the cost-efficiency of the current action and its potential impact on subsequent actions. So, how to select the next searching moment topt when knowing a spatiotemporal point ts,ls of target vehicle ox? The moment decision model is responsible to answer this question.Following reinforcement learning, the moment decision model is represented asS,A,C,Γ,Q, in which Slss∈S denotes the current state ts,ls; Alss∈A denotes the current action topt,ξopt; C:S×A⟶C denotes the search cost function Copt=Costtopt,ξopt; Γ:S×A⟶ΔS denotes the state transition function; Q denotes the value function. The next state Slss′ is obtained by performing action Alss at the state Slss, and the value function is updated using Equation (8), where α is the learning rate between (0, 1], and γ is the discount rate.
(8)QSlss,Alss=QSlss,Alss+α.Copt+γ.minAlss′QSlss′,Alss′‐QSlss,AlssThe learning rateα can control the update rate of the value function. The discount rate γ can balance the importance between the immediate and potential reward. We use QSlss′,Alss′to estimate the long-term impact of performing action Alss at state Slss.Figure3 shows how to train the moment decision model. First of all, the moment decision model is initialized. In each loop, the moment decision model decides a searching moment based on the current state, and the location decision model decides the corresponding searching location sequence. Then the value function is adjusted according to the potential impact on subsequent actions and the sensed environmental information (e.g., traffic flow, road network, and building density, which will be quantified as search cost Copt). The moment decision model will continually repeat the above loop until the determined searching moment topt at the current state Slss is optimal.Figure 3
Training of the moment decision model.To train the moment decision model in QDP, this paper proposes a training method based on Monte-Carlo method and probabilistic states to solve the problem, as shown in Figure4.Figure 4
Training of QDP.stdenotes the current state, at denotes the action performed at state st, rt+1 denotes the reward (reward is the inverse of cost) of the action at at state st, pt+1i denotes the probability distribution of next states, and rt+1i denotes the reward of the optimal action at each possible state.In the training of QDP, performing the actionAlss=topt,ξopt at the state Slss=ts,ls will result in a probability distribution pl1ξopt,pl2ξopt,⋯,plLξopt at different locations l1ξopt,l2ξopt,⋯,lLξopt at moment topt. We use Equation (9) to estimate the long-term impact of performing action Alss at state Slss, i.e., the minimum cost of subsequent searches. As shown in Figure 5, Sliξopt are the next states that can be generated by performing action Alss (i.e., spatiotemporal searches) at state Slss, and Al1ξopt, Al2ξopt, ... are actions that can be performed at state Sl1ξopt, Sl2ξopt, ..., respectively. Especially, when the agent finds the vehicle’s location at the target moment ttarget, it no longer needs to perform any action or update the state.
(9)minAlss′QSlss′,Alss′=∑i=1Lpliξopt×minAliξoptQSliξopt,AliξoptFigure 5
Estimating the subsequent search cost with probabilistic states.To solve the problem that QDP is difficult to update the state during training, we adopt the idea of Monte-Carlo method. In each loop, we randomize the current state and action, calculate the expected cost of the subsequent searches by Equation (9) for the value function updated by Equation (8), and iterate the loop until the value function converges. The pseudo code of QDP’s training method is shown as Algorithm 1.Algorithm 1: QDP’s training method
Input:ttarget, C, α, γ, TR′beforedxOutput:value function Q1 Calculate the vehicle transition probability Pts,ls,topt,: at ts,ls and at the moment topt,topt∈ts,ttarget according to TR′; //Pts,ls,topt,:=pl1topt,pl2topt,⋯,plLtopt=TPM2 Calculate the expected cost Cts,ls,topt of spatiotemporal searches according to Equation (6); //Cts,ls,topt=Copt=Costtopt,ξopt3 Initialization value functionQ;4 whileQ does not converge:5 Randomize spatiotemporal point ts,ls and the moment decision topt,topt∈ts,ttarget;6 Calculate minAlss′QSlss′,Alss′ according to Equation (9);7 Update the value function Qts,ls,topt according to Equation (8);8 end.


### 3.3. Spatiotemporal Searches at Executing Phase

The basic idea of QDP’s executing phase is greedy. At each step, the moment decision model decides the optimal searching momenttopt based on known spatiotemporal point ts,ls of the vehicle ox, and the location decision model decides the corresponding searching location sequence topt,ξopt. We perform spatiotemporal searches in camera records to find the vehicle ox‘s location liξopt at the moment topt, and update the known spatiotemporal point ts,ls=topt,liξopt. The above steps are iterated until the vehicle ox‘s location ltarget at the target moment ttarget is found. Finally, QDP outputs the accumulative search cost, i.e., the cost of spatiotemporal search. The complete steps of spatiotemporal search at QDP’s executing phase are as follows:
(1)
Quantify the search costC=cl11,cl21,⋯,clL1,⋯,cl1dx,cl2dx,⋯,clLdx at different moments and at different locations of the day dx(2)
Initialize the known spatiotemporal pointts,ls of the target vehicle ox and the target moment ttarget in the testing day dx(3)
Decide the optimal searching momenttopt,topt∈ts,ttarget, according to the moment decision model(4)
Decide the searching location sequencetopt,ξopt according to the location decision model(5)
Perform spatiotemporal searchessox,topt,l1ξopt,sox,topt,l2ξopt,⋯ until sox,topt,liξopt=1, then return the vehicle ox‘s location liξopt at moment topt(6)
Update known spatiotemporal pointts,ls=topt,liξoptRepeat steps (3), (4), (5), and (6) untilts=ttarget, output the vehicle ox‘s location ltarget at the target moment ttarget and the accumulative cost.


## 3.1. Training the Location Decision Model

The location decision model is responsible to output the location decisiontopt,ξopt (the optimal searching location sequence at moment topt given by the moment decision model). It is trained with the help of mobility prediction and basic optimal searching. The mobility prediction algorithm is not the focus of this paper. In the previous work [5], we have analyzed the advantages of choosing the first-order Markov model for mobility prediction. Suppose that the transition probability matrix TPMΔtL×L represents the probabilities of a vehicle moving from one location to another after a period of time Δt=topt−ts, of which an element is pliopt, i.e., the probability of vehicle ox moves from location ls at moment ts to location li at moment topt.
(3)TPMΔtL×L=pliopt(4)pliopt=#trwithts,ls&topt,li#trwithts,ls,ts=t1,t2,⋯,tr∈TR′where the meaning of “#” is “the number of”,tr is a trajectory. Equation Equation (4) represents the ratio of “the number of trajectories that pass both ts,ls and topt,li” to “the number of trajectories of only the pass ts,ls”. TPMΔtL×L can be trained from historical vehicle trajectories. When given an original location, a row of probabilities is output as the predicted result of the destination location.The basic optimal searching theory can assign the priority of locations to search at. Suppose the searching location sequence at momenttopt is topt,ξopt=topt,l1ξopt,topt,l2ξopt,⋯,topt,liξopt,⋯,liξopt∈L.Definition 3 (probability-cost ratio).
The ratio of the probabilitypliξopt of finding the target vehicle to the cost cliξopt of the i−th spatiotemporal search in the sequence topt,ξopt, formally,
(5)ηtopt,liξopt=pliξoptcliξoptTheorem 4.
[33]: The necessary and sufficient condition for the sequence topt,ξopt to be the searching location sequence with the lowest search cost at moment topt is that the probability-cost ratios are in descending order.Consequently, the location decision can be made according to Theorem4.We need to estimate the search cost which will be used during training the moment decision model. The optimal sequencetopt,ξopt has a expected search cost:
(6)Costtopt,ξopt=∑i=1Lpliξopt×∑j=1icljξoptTo demonstrate how to calculate the expected search cost using Equation (6), we assume the spatiotemporal search costs cl13=cl23=cl33=cl43=1, the location transition probabilities pl13=1/3,pl23=0,pl33=2/3,pl43=0. Then, the descendingly sorted location sequence is t3,ξ3=t3,l3,t3,l1,t3,l2,t3,l4 at moment t3. Then the expected search cost is:
(7)Costt3,ξ3=pl33×cl33+pl13×cl33+cl13+pl23×cl33+cl13+cl23+pl43×cl33+cl13+cl23+cl43=23×1+13×1+1+0×1+1+1+0×1+1+1+1=43


## 3.2. Training the Moment Decision Model

Perform spatiotemporal searches at momenttopt should consider both the cost-efficiency of the current action and its potential impact on subsequent actions. So, how to select the next searching moment topt when knowing a spatiotemporal point ts,ls of target vehicle ox? The moment decision model is responsible to answer this question.Following reinforcement learning, the moment decision model is represented asS,A,C,Γ,Q, in which Slss∈S denotes the current state ts,ls; Alss∈A denotes the current action topt,ξopt; C:S×A⟶C denotes the search cost function Copt=Costtopt,ξopt; Γ:S×A⟶ΔS denotes the state transition function; Q denotes the value function. The next state Slss′ is obtained by performing action Alss at the state Slss, and the value function is updated using Equation (8), where α is the learning rate between (0, 1], and γ is the discount rate.
(8)QSlss,Alss=QSlss,Alss+α.Copt+γ.minAlss′QSlss′,Alss′‐QSlss,AlssThe learning rateα can control the update rate of the value function. The discount rate γ can balance the importance between the immediate and potential reward. We use QSlss′,Alss′to estimate the long-term impact of performing action Alss at state Slss.Figure3 shows how to train the moment decision model. First of all, the moment decision model is initialized. In each loop, the moment decision model decides a searching moment based on the current state, and the location decision model decides the corresponding searching location sequence. Then the value function is adjusted according to the potential impact on subsequent actions and the sensed environmental information (e.g., traffic flow, road network, and building density, which will be quantified as search cost Copt). The moment decision model will continually repeat the above loop until the determined searching moment topt at the current state Slss is optimal.Figure 3
Training of the moment decision model.To train the moment decision model in QDP, this paper proposes a training method based on Monte-Carlo method and probabilistic states to solve the problem, as shown in Figure4.Figure 4
Training of QDP.stdenotes the current state, at denotes the action performed at state st, rt+1 denotes the reward (reward is the inverse of cost) of the action at at state st, pt+1i denotes the probability distribution of next states, and rt+1i denotes the reward of the optimal action at each possible state.In the training of QDP, performing the actionAlss=topt,ξopt at the state Slss=ts,ls will result in a probability distribution pl1ξopt,pl2ξopt,⋯,plLξopt at different locations l1ξopt,l2ξopt,⋯,lLξopt at moment topt. We use Equation (9) to estimate the long-term impact of performing action Alss at state Slss, i.e., the minimum cost of subsequent searches. As shown in Figure 5, Sliξopt are the next states that can be generated by performing action Alss (i.e., spatiotemporal searches) at state Slss, and Al1ξopt, Al2ξopt, ... are actions that can be performed at state Sl1ξopt, Sl2ξopt, ..., respectively. Especially, when the agent finds the vehicle’s location at the target moment ttarget, it no longer needs to perform any action or update the state.
(9)minAlss′QSlss′,Alss′=∑i=1Lpliξopt×minAliξoptQSliξopt,AliξoptFigure 5
Estimating the subsequent search cost with probabilistic states.To solve the problem that QDP is difficult to update the state during training, we adopt the idea of Monte-Carlo method. In each loop, we randomize the current state and action, calculate the expected cost of the subsequent searches by Equation (9) for the value function updated by Equation (8), and iterate the loop until the value function converges. The pseudo code of QDP’s training method is shown as Algorithm 1.Algorithm 1: QDP’s training method
Input:ttarget, C, α, γ, TR′beforedxOutput:value function Q1 Calculate the vehicle transition probability Pts,ls,topt,: at ts,ls and at the moment topt,topt∈ts,ttarget according to TR′; //Pts,ls,topt,:=pl1topt,pl2topt,⋯,plLtopt=TPM2 Calculate the expected cost Cts,ls,topt of spatiotemporal searches according to Equation (6); //Cts,ls,topt=Copt=Costtopt,ξopt3 Initialization value functionQ;4 whileQ does not converge:5 Randomize spatiotemporal point ts,ls and the moment decision topt,topt∈ts,ttarget;6 Calculate minAlss′QSlss′,Alss′ according to Equation (9);7 Update the value function Qts,ls,topt according to Equation (8);8 end.


## 3.3. Spatiotemporal Searches at Executing Phase

The basic idea of QDP’s executing phase is greedy. At each step, the moment decision model decides the optimal searching momenttopt based on known spatiotemporal point ts,ls of the vehicle ox, and the location decision model decides the corresponding searching location sequence topt,ξopt. We perform spatiotemporal searches in camera records to find the vehicle ox‘s location liξopt at the moment topt, and update the known spatiotemporal point ts,ls=topt,liξopt. The above steps are iterated until the vehicle ox‘s location ltarget at the target moment ttarget is found. Finally, QDP outputs the accumulative search cost, i.e., the cost of spatiotemporal search. The complete steps of spatiotemporal search at QDP’s executing phase are as follows:
(1)
Quantify the search costC=cl11,cl21,⋯,clL1,⋯,cl1dx,cl2dx,⋯,clLdx at different moments and at different locations of the day dx(2)
Initialize the known spatiotemporal pointts,ls of the target vehicle ox and the target moment ttarget in the testing day dx(3)
Decide the optimal searching momenttopt,topt∈ts,ttarget, according to the moment decision model(4)
Decide the searching location sequencetopt,ξopt according to the location decision model(5)
Perform spatiotemporal searchessox,topt,l1ξopt,sox,topt,l2ξopt,⋯ until sox,topt,liξopt=1, then return the vehicle ox‘s location liξopt at moment topt(6)
Update known spatiotemporal pointts,ls=topt,liξoptRepeat steps (3), (4), (5), and (6) untilts=ttarget, output the vehicle ox‘s location ltarget at the target moment ttarget and the accumulative cost.


## 4. Evaluation

### 4.1. Dataset

The experimental dataset (The experimental dataset of this article is provided on demand, please contact the author if necessary) is derived from the trajectories of 19,000 taxis in Chengdu, China, in August 2014. The data acquisition area is about30KM×30KM, and the duration of each trajectory is from 7 : 00 am to 21 : 59 pm.The GPS waypoints of different vehicles in the original dataset are unordered. In addition, some vehicles contain various numbers of waypoints within 1 minute while some contain no waypoints. Therefore, it is firstly necessary to preprocess the dataset. In this experiment, we generate a GPS waypoint sequence of a taxi by filtering the vehicle ID and sorting the timestamps. The time is discretized into moments, each with 1 minute, and only the waypoint with the earliest timestamp per minute indicates the location of the vehicle at that moment. Trajectories with seriously missing data are discarded. The raw data details and a complete trajectory are shown in Table1.Table 1
Detailed description of the dataset.
(a)
Raw data details
Field nameExampleRemarksVehicle ID1\Passenger or not0/1\Timestamp1501584540Unix timestamp, in secondsLongitude104.042833GCJ-02Latitude30.599851GCJ-02(b)
Complete trajectory of a vehicle in a day
VehicleDayLongitudeLatitudeMomentox2014/8/4104.03916330.5975727 : 00104.12656530.5997337 : 01.........104.04283330.59985121 : 58104.12715430.60000921 : 59The data acquisition area is divided into grids each of size1KM×1KM, and the GPS waypoints are projected into the grids, and each grid represents a location. The gird size of 1.2KM×1.2KM and 1.5KM×1.5KMare also tested in our experiments. Smaller grids are not appropriate since there is enough historical data in a smaller grid. The 99,265 trajectories of the first 14 days are used for training, and randomly selected 1000 trajectories from 21,963 trajectories in the last 3 days are used for testing, i.e., 1000 tests. In this experiment, it is assumed that the search cost C at a spatiotemporal point is 1. Finally, under different grid sizes, we perform 1000 tests and average the results.


### 4.2. Parameters

Two parameters of QDP need to be tuned: the learning rateα and the discount rate γ in Equation (8). We choose them from practical experiences.The learning rate can control the update rate of the value function. Small learning rate will reduce the convergence speed of the value function, and a large learning rate may fail to converge to the optimal solution. To find a proper learning rate, we compare the test results (i.e., the accumulative search cost) of QDP with different learning rates (α=1, 0.5, 0.3, 0.1, respectively) under the same other settings (i.e., grid size = 1KM×1KM, ttarget−ts=30min, discount rate γ=1, and start moment ts =8 : 00/10 : 00/12 : 00/14 : 00/16 : 00/18 : 00/20 : 00).The test results verify that the value function is converged with all different learning rates. As shown in Table2, QDP with different α output the same accumulative cost, which implies their value functions are converged to the same solution. Only the training time is different. The training is performed on a computer with a memory of 16 GB and a processor of Inter(R) Core(TM) i7-6700HQ. To speed up the training, we choose α=1.Table 2
Accumulative search cost of QDP with different learning rates.
Start momentTraining time8 : 0010 : 0012 : 0014 : 0016 : 0018 : 0020 : 00α =1.0,γ = 111.50 h32.8132.9034.8532.7234.0630.1534.97α = 0.5,γ = 130.36 h32.8132.9034.8532.7234.0630.1534.97α = 0.3,γ = 154.12 h32.8132.9034.8532.7234.0630.1534.97α = 0.1,γ = 198.34 h32.8132.9034.8532.7234.0630.1534.97Discount rateγ can balance the importance between the immediate and potential reward. γ>1 indicates that the immediate reward is more important than the potential reward, and vice versa. To find a proper discount rate, we compare the test results of QDP with different discount rates (γ=0.97, 0.99, 1, 1.01, 1.03, 1.05, respectively) under the same other settings (i.e., grid size = 1KM×1KM, ttarget−ts=30min, learning rate α=1, and start moment ts traverses every moment from 7 : 00 to 21 : 29 of a day).As shown in Table3, when the discount rate γ=1, the search cost of QDP is the smallest, so we set the discount rate γ to 1.Table 3
Accumulative search cost of QDP with different discount rates.
Start moment8 : 0010 : 0012 : 0014 : 0016 : 0018 : 0020 : 00α = 1,γ = 0.9734.3835.0536.5134.8635.5732.4436.61α = 1,γ = 0.9933.2533.4235.0133.2734.3130.4635.11α = 1,γ =1.0032.8132.9034.8532.7234.0630.1534.97α = 1,γ =1.0133.5932.9534.9133.0833.7230.1835.14α = 1,γ =1.0333.1533.1935.7933.2434.1030.3635.13α = 1,γ =1.0533.6833.6436.1733.9234.9631.2135.79


### 4.3. Baselines

In this section, we will describe three spatiotemporal searching algorithms as baselines: ALT, IEM, and IHMs [5]. Given the location ls of the vehicle ox at moment ts of dj, the process of the three algorithms are as follows:


#### 4.3.1. All Searching at the Last Time (ALT)

Calculate the probabilitypl1target,pl2target,⋯ that the vehicle ox moves to different locations at moment ttarget according to the spatiotemporal point ts,ls and the historical trajectories TR′; Determine the searching location sequence ttarget,ξtarget according to the location decision model; Perform spatiotemporal searches sox,ttarget,l1ξtarget,sox,ttarget,l2ξtarget,⋯ until sox,ttarget,liξtarget=1, then return the location ltarget=liξtarget of vehicle ox at moment ttarget.


#### 4.3.2. Intermediate Searching at an Estimated Moment (IEM)

Calculate probabilitypl1opt,pl2opt,⋯ that the vehicle ox moves to different locations at moment topt,topt∈ts,ttarget according to the spatiotemporal point ts,ls and the historical trajectories TR′; Determine the searching location sequence topt,ξopt according to the location decision model; Calculate probability pl1target,pl2target,⋯ that the vehicle ox moves to different locations at moment ttarget according to the spatiotemporal point topt,liξopt and TR′; Determine the searching location sequence ttarget,ξtarget. The above two steps are only used for cost estimation of different topt, but no need to perform the searches actually. Determine an intermediate search moment topt according to Equation (10); Perform spatiotemporal searches sox,topt,l1ξopt,sox,topt,l2ξopt,⋯, until sox,topt,liξopt=1, update to spatiotemporal point topt,liξopt; Perform spatiotemporal searches sox,ttarget,l1ξtarget,sox,ttarget,l2ξtarget,⋯ which correspond to the spatiotemporal point topt,liξopt, until sox,ttarget,liξtarget=1, then return the location ltarget=liξtarget of the vehicle ox at the moment ttarget.
(10)topt=argmintopt∈ts,ttargetCosttopt,ξopt+∑i=1Lpliopt×Costttarget,ξtarget


#### 4.3.3. Intermediate Searching at Heuristic Moments (IHMs)

Calculate the probabilitypl1opt,pl2opt,⋯ of ox moving to different locations at moment topt,topt∈ts,ttarget according to the spatiotemporal point ts,ls and the historical trajectories TR′; Determine the searching location sequence topt,ξopt according to the location decision model; Determine the intermediate search moment topt according to Equation (11); Perform spatiotemporal searches sox,topt,l1ξopt,sox,topt,l2ξopt,⋯, until sox,topt,liξopt=1; Update spatiotemporal point ts,ls=topt,liξopt; Iterate the above steps until ts=ttarget, and return the location ltarget=liξopt of the vehicle ox at the target time ttarget.
(11)topt=argmintopt∈ts,ttargetCosttopt,ξopttopt−tsIn summary, ALT searches only at the target moment, IEM searches at an intermediate moment and the target moment, while IHMs and QDP search at multiple intermediate moments as well as the target moment. The baselines and QDP use the same location decision model as described in Section3.1, which is not the focus of this paper. The main difference among them is how to decide the searching moment.


### 4.4. Comparison of Different Algorithms

This experiment compares four spatiotemporal searching algorithms: ALT, IEM, IHMs and QDP. When testing, instead of real camera records, we use the testing trajectories as the source of ground truth, which also can enable the functionality of Equation (1). The performance metric is the average search cost of the 1000 tests. As shown in Figure 6, QDP is better than the other three spatiotemporal searching algorithms in general. The four spatiotemporal searching algorithms have different performance under different grid sizes (1KM×1KM, 1.2KM×1.2KM, and 1.5KM×1.5KM, respectively) and time intervals (i.e., ttarget−ts= 30 min, 40 min, 50 min, respectively). The start moment ts traverses every moment from 7 : 00 to “21:59 - time_span” of the corresponding testing day.
(1)
When the grid size is1KM×1KM, IHMs and QDP are better than ALT and IEM at different time intervals. As the time interval becomes bigger, the advantage of QDP is increasing compared with IHMs(2)
When the grid size is1.2KM×1.2KM, IHMs and QDP are better than ALT when the time interval is 30 min or 40 min. There is no significant difference among ALT, IHMs, and QDP when the time interval is 50 min, but they are better than IEM(3)
When the grid size is1.5KM×1.5KM, IHMs and QDP are better than ALT when the time interval is 30 min. There is no significant difference among ALT, IHMs, and QDP when the time interval is 40 min or 50 min, but they are better than IEMFigure 6
Comparison of four spatiotemporal searching algorithms.
(a)
grid size =1KM×1KM, target moment - start moment = 30 min(b)
grid size =1KM×1KM, target moment - start moment = 40 min(c)
grid size =1KM×1KM, target moment - start moment = 50 min(d)
grid size =1.2KM×1.2KM, target moment - start moment = 30 min(e)
grid size =1.2KM×1.2KM, target moment - start moment = 40 min(f)
grid size =1.2KM×1.2KM, target moment - start moment = 50 min(g)
grid size =1.5KM×1.5KM, target moment - start moment = 30 min(h)
grid size =1.5KM×1.5KM, target moment - start moment = 40 min(i)
grid size =1.5KM×1.5KM, target moment - start moment = 50 minNo matter what the grid size and time interval is, QDP is always better than or equal to IHMs.


### 4.5. Analysis and Discussion

We perform more analysis to disclose the reason of the above results. Remind that the main difference among ALT, IEM, IHMs, and QDP is how to decide the searching momenttopt, i.e., ALT searches only at the target moment, IEM searches at an intermediate moment and the target moment, while IHMs and QDP search at multiple intermediate moments as well as the target moment. We intend to demonstrate the efficiency of different moment decisions. Because the search cost will increase as the timespan Δt=topt−ts becomes larger, the cost-timespan ratio (also the heuristic indicator of IHMs) is defined as the ratio of the estimated search cost to the timespan:
(12)CostTimespanRatiotopt−ts=Costtopt,ξopttopt−tsFigure7 shows the cost-timespan ratio under different grid sizes (1KM×1KM, 1.2KM×1.2KM, 1.5KM×1.5KM). All three ratio’s curves first decrease, then increase, and then decrease along with the timespan. Let preferred timespan Δtmid be the timespan of the first locally minimum ratio CostTimespanRatio(Δtmid). A contour timespan Δtlimit is the timespan whose cost-timespan ratio is equal to CostTimespanRatio(Δtmid).Figure 7
Cost-timespan ratio of different timespans.
(a)
grid size =1KM×1KM(b)
grid size =1.2KM×1.2KM(c)
grid size =1.5KM×1.5KMIfΔt < Δtmid or Δt> Δtlimit, the larger timespan is more efficient, thus the searching moment should be as later as possible, i.e., searching at intermediate moments cannot help to reduce the total search cost, and ALT will be better than IEM. In this situation, IHMs and QDP will also only perform searches at the target moment, which are equivalent with ALT.IfΔt is between (Δtmid, Δtlimit), since CostTimespanRatio(Δtmid) is the minimum ratio when timespan is from 0 to Δt. As a result, Δtmid is the most efficient timespan which can decide the corresponding intermediate moment, i.e., searching at intermediate moments can reduce the total search cost, and IEM, IHMs and QDP may be better than ALT. Whether the right intermediate moments are detected is up to specific algorithms.The different grid sizes will causeΔtlimit to be different.Δtlimit corresponding to grid sizes 1KM×1KM, 1.2KM×1.2KM, and 1.5KM×1.5KM are calculated to be 58 min, 46 min and 36 min, respectively. Therefore, the reason of the results in Section 4.4 can be explained as:
(1)
When the grid size =1KM×1KM, In Figures 6(a), 6(b), 6(c), since the timespans Δt = 30 min/40 min/50 min do not exceed Δtlimit (58 min), IHMs and QDP are better than ALT(2)
When the grid size =1.2KM×1.2KM, Since the timespans Δt = 30 min/40 min (Figures 6(d), 6(e)) do not exceed Δtlimit (46 min), IHMs and QDP are better than ALT. While when the timespan Δt = 50 min (Figure 6(f)) exceeds Δtlimit (46 min), there is no significant difference among ALT, IHMs, and QDP(3)
When the grid size =1.5KM×1.5KM, Since the timespan Δt = 30 min (Figure 6(g)) does not exceed Δtlimit (36 min), IHMs and QDP are better than ALT. While when the timespans Δt = 40 min/50 min exceed Δtlimit (36 min), there is no significant difference among ALT, IHMs, and QDPIEM is bound to search at an intermediate moment and cannot make a decision dynamically to adapt environment information. Therefore, IEM is almost the worst in all situations. QDP can surmount the shortage that IHMs may output a locally optimal solution. As Q-learning does, it finds the near global optimal solution in the sense that it minimizes the total cost of any and all successive searches.


## 4.1. Dataset

The experimental dataset (The experimental dataset of this article is provided on demand, please contact the author if necessary) is derived from the trajectories of 19,000 taxis in Chengdu, China, in August 2014. The data acquisition area is about30KM×30KM, and the duration of each trajectory is from 7 : 00 am to 21 : 59 pm.The GPS waypoints of different vehicles in the original dataset are unordered. In addition, some vehicles contain various numbers of waypoints within 1 minute while some contain no waypoints. Therefore, it is firstly necessary to preprocess the dataset. In this experiment, we generate a GPS waypoint sequence of a taxi by filtering the vehicle ID and sorting the timestamps. The time is discretized into moments, each with 1 minute, and only the waypoint with the earliest timestamp per minute indicates the location of the vehicle at that moment. Trajectories with seriously missing data are discarded. The raw data details and a complete trajectory are shown in Table1.Table 1
Detailed description of the dataset.
(a)
Raw data details
Field nameExampleRemarksVehicle ID1\Passenger or not0/1\Timestamp1501584540Unix timestamp, in secondsLongitude104.042833GCJ-02Latitude30.599851GCJ-02(b)
Complete trajectory of a vehicle in a day
VehicleDayLongitudeLatitudeMomentox2014/8/4104.03916330.5975727 : 00104.12656530.5997337 : 01.........104.04283330.59985121 : 58104.12715430.60000921 : 59The data acquisition area is divided into grids each of size1KM×1KM, and the GPS waypoints are projected into the grids, and each grid represents a location. The gird size of 1.2KM×1.2KM and 1.5KM×1.5KMare also tested in our experiments. Smaller grids are not appropriate since there is enough historical data in a smaller grid. The 99,265 trajectories of the first 14 days are used for training, and randomly selected 1000 trajectories from 21,963 trajectories in the last 3 days are used for testing, i.e., 1000 tests. In this experiment, it is assumed that the search cost C at a spatiotemporal point is 1. Finally, under different grid sizes, we perform 1000 tests and average the results.


## 4.2. Parameters

Two parameters of QDP need to be tuned: the learning rateα and the discount rate γ in Equation (8). We choose them from practical experiences.The learning rate can control the update rate of the value function. Small learning rate will reduce the convergence speed of the value function, and a large learning rate may fail to converge to the optimal solution. To find a proper learning rate, we compare the test results (i.e., the accumulative search cost) of QDP with different learning rates (α=1, 0.5, 0.3, 0.1, respectively) under the same other settings (i.e., grid size = 1KM×1KM, ttarget−ts=30min, discount rate γ=1, and start moment ts =8 : 00/10 : 00/12 : 00/14 : 00/16 : 00/18 : 00/20 : 00).The test results verify that the value function is converged with all different learning rates. As shown in Table2, QDP with different α output the same accumulative cost, which implies their value functions are converged to the same solution. Only the training time is different. The training is performed on a computer with a memory of 16 GB and a processor of Inter(R) Core(TM) i7-6700HQ. To speed up the training, we choose α=1.Table 2
Accumulative search cost of QDP with different learning rates.
Start momentTraining time8 : 0010 : 0012 : 0014 : 0016 : 0018 : 0020 : 00α =1.0,γ = 111.50 h32.8132.9034.8532.7234.0630.1534.97α = 0.5,γ = 130.36 h32.8132.9034.8532.7234.0630.1534.97α = 0.3,γ = 154.12 h32.8132.9034.8532.7234.0630.1534.97α = 0.1,γ = 198.34 h32.8132.9034.8532.7234.0630.1534.97Discount rateγ can balance the importance between the immediate and potential reward. γ>1 indicates that the immediate reward is more important than the potential reward, and vice versa. To find a proper discount rate, we compare the test results of QDP with different discount rates (γ=0.97, 0.99, 1, 1.01, 1.03, 1.05, respectively) under the same other settings (i.e., grid size = 1KM×1KM, ttarget−ts=30min, learning rate α=1, and start moment ts traverses every moment from 7 : 00 to 21 : 29 of a day).As shown in Table3, when the discount rate γ=1, the search cost of QDP is the smallest, so we set the discount rate γ to 1.Table 3
Accumulative search cost of QDP with different discount rates.
Start moment8 : 0010 : 0012 : 0014 : 0016 : 0018 : 0020 : 00α = 1,γ = 0.9734.3835.0536.5134.8635.5732.4436.61α = 1,γ = 0.9933.2533.4235.0133.2734.3130.4635.11α = 1,γ =1.0032.8132.9034.8532.7234.0630.1534.97α = 1,γ =1.0133.5932.9534.9133.0833.7230.1835.14α = 1,γ =1.0333.1533.1935.7933.2434.1030.3635.13α = 1,γ =1.0533.6833.6436.1733.9234.9631.2135.79


## 4.3. Baselines

In this section, we will describe three spatiotemporal searching algorithms as baselines: ALT, IEM, and IHMs [5]. Given the location ls of the vehicle ox at moment ts of dj, the process of the three algorithms are as follows:


### 4.3.1. All Searching at the Last Time (ALT)

Calculate the probabilitypl1target,pl2target,⋯ that the vehicle ox moves to different locations at moment ttarget according to the spatiotemporal point ts,ls and the historical trajectories TR′; Determine the searching location sequence ttarget,ξtarget according to the location decision model; Perform spatiotemporal searches sox,ttarget,l1ξtarget,sox,ttarget,l2ξtarget,⋯ until sox,ttarget,liξtarget=1, then return the location ltarget=liξtarget of vehicle ox at moment ttarget.


### 4.3.2. Intermediate Searching at an Estimated Moment (IEM)

Calculate probabilitypl1opt,pl2opt,⋯ that the vehicle ox moves to different locations at moment topt,topt∈ts,ttarget according to the spatiotemporal point ts,ls and the historical trajectories TR′; Determine the searching location sequence topt,ξopt according to the location decision model; Calculate probability pl1target,pl2target,⋯ that the vehicle ox moves to different locations at moment ttarget according to the spatiotemporal point topt,liξopt and TR′; Determine the searching location sequence ttarget,ξtarget. The above two steps are only used for cost estimation of different topt, but no need to perform the searches actually. Determine an intermediate search moment topt according to Equation (10); Perform spatiotemporal searches sox,topt,l1ξopt,sox,topt,l2ξopt,⋯, until sox,topt,liξopt=1, update to spatiotemporal point topt,liξopt; Perform spatiotemporal searches sox,ttarget,l1ξtarget,sox,ttarget,l2ξtarget,⋯ which correspond to the spatiotemporal point topt,liξopt, until sox,ttarget,liξtarget=1, then return the location ltarget=liξtarget of the vehicle ox at the moment ttarget.
(10)topt=argmintopt∈ts,ttargetCosttopt,ξopt+∑i=1Lpliopt×Costttarget,ξtarget


### 4.3.3. Intermediate Searching at Heuristic Moments (IHMs)

Calculate the probabilitypl1opt,pl2opt,⋯ of ox moving to different locations at moment topt,topt∈ts,ttarget according to the spatiotemporal point ts,ls and the historical trajectories TR′; Determine the searching location sequence topt,ξopt according to the location decision model; Determine the intermediate search moment topt according to Equation (11); Perform spatiotemporal searches sox,topt,l1ξopt,sox,topt,l2ξopt,⋯, until sox,topt,liξopt=1; Update spatiotemporal point ts,ls=topt,liξopt; Iterate the above steps until ts=ttarget, and return the location ltarget=liξopt of the vehicle ox at the target time ttarget.
(11)topt=argmintopt∈ts,ttargetCosttopt,ξopttopt−tsIn summary, ALT searches only at the target moment, IEM searches at an intermediate moment and the target moment, while IHMs and QDP search at multiple intermediate moments as well as the target moment. The baselines and QDP use the same location decision model as described in Section3.1, which is not the focus of this paper. The main difference among them is how to decide the searching moment.


## 4.3.1. All Searching at the Last Time (ALT)

Calculate the probabilitypl1target,pl2target,⋯ that the vehicle ox moves to different locations at moment ttarget according to the spatiotemporal point ts,ls and the historical trajectories TR′; Determine the searching location sequence ttarget,ξtarget according to the location decision model; Perform spatiotemporal searches sox,ttarget,l1ξtarget,sox,ttarget,l2ξtarget,⋯ until sox,ttarget,liξtarget=1, then return the location ltarget=liξtarget of vehicle ox at moment ttarget.


## 4.3.2. Intermediate Searching at an Estimated Moment (IEM)

Calculate probabilitypl1opt,pl2opt,⋯ that the vehicle ox moves to different locations at moment topt,topt∈ts,ttarget according to the spatiotemporal point ts,ls and the historical trajectories TR′; Determine the searching location sequence topt,ξopt according to the location decision model; Calculate probability pl1target,pl2target,⋯ that the vehicle ox moves to different locations at moment ttarget according to the spatiotemporal point topt,liξopt and TR′; Determine the searching location sequence ttarget,ξtarget. The above two steps are only used for cost estimation of different topt, but no need to perform the searches actually. Determine an intermediate search moment topt according to Equation (10); Perform spatiotemporal searches sox,topt,l1ξopt,sox,topt,l2ξopt,⋯, until sox,topt,liξopt=1, update to spatiotemporal point topt,liξopt; Perform spatiotemporal searches sox,ttarget,l1ξtarget,sox,ttarget,l2ξtarget,⋯ which correspond to the spatiotemporal point topt,liξopt, until sox,ttarget,liξtarget=1, then return the location ltarget=liξtarget of the vehicle ox at the moment ttarget.
(10)topt=argmintopt∈ts,ttargetCosttopt,ξopt+∑i=1Lpliopt×Costttarget,ξtarget


## 4.3.3. Intermediate Searching at Heuristic Moments (IHMs)

Calculate the probabilitypl1opt,pl2opt,⋯ of ox moving to different locations at moment topt,topt∈ts,ttarget according to the spatiotemporal point ts,ls and the historical trajectories TR′; Determine the searching location sequence topt,ξopt according to the location decision model; Determine the intermediate search moment topt according to Equation (11); Perform spatiotemporal searches sox,topt,l1ξopt,sox,topt,l2ξopt,⋯, until sox,topt,liξopt=1; Update spatiotemporal point ts,ls=topt,liξopt; Iterate the above steps until ts=ttarget, and return the location ltarget=liξopt of the vehicle ox at the target time ttarget.
(11)topt=argmintopt∈ts,ttargetCosttopt,ξopttopt−tsIn summary, ALT searches only at the target moment, IEM searches at an intermediate moment and the target moment, while IHMs and QDP search at multiple intermediate moments as well as the target moment. The baselines and QDP use the same location decision model as described in Section3.1, which is not the focus of this paper. The main difference among them is how to decide the searching moment.


## 4.4. Comparison of Different Algorithms

This experiment compares four spatiotemporal searching algorithms: ALT, IEM, IHMs and QDP. When testing, instead of real camera records, we use the testing trajectories as the source of ground truth, which also can enable the functionality of Equation (1). The performance metric is the average search cost of the 1000 tests. As shown in Figure 6, QDP is better than the other three spatiotemporal searching algorithms in general. The four spatiotemporal searching algorithms have different performance under different grid sizes (1KM×1KM, 1.2KM×1.2KM, and 1.5KM×1.5KM, respectively) and time intervals (i.e., ttarget−ts= 30 min, 40 min, 50 min, respectively). The start moment ts traverses every moment from 7 : 00 to “21:59 - time_span” of the corresponding testing day.
(1)
When the grid size is1KM×1KM, IHMs and QDP are better than ALT and IEM at different time intervals. As the time interval becomes bigger, the advantage of QDP is increasing compared with IHMs(2)
When the grid size is1.2KM×1.2KM, IHMs and QDP are better than ALT when the time interval is 30 min or 40 min. There is no significant difference among ALT, IHMs, and QDP when the time interval is 50 min, but they are better than IEM(3)
When the grid size is1.5KM×1.5KM, IHMs and QDP are better than ALT when the time interval is 30 min. There is no significant difference among ALT, IHMs, and QDP when the time interval is 40 min or 50 min, but they are better than IEMFigure 6
Comparison of four spatiotemporal searching algorithms.
(a)
grid size =1KM×1KM, target moment - start moment = 30 min(b)
grid size =1KM×1KM, target moment - start moment = 40 min(c)
grid size =1KM×1KM, target moment - start moment = 50 min(d)
grid size =1.2KM×1.2KM, target moment - start moment = 30 min(e)
grid size =1.2KM×1.2KM, target moment - start moment = 40 min(f)
grid size =1.2KM×1.2KM, target moment - start moment = 50 min(g)
grid size =1.5KM×1.5KM, target moment - start moment = 30 min(h)
grid size =1.5KM×1.5KM, target moment - start moment = 40 min(i)
grid size =1.5KM×1.5KM, target moment - start moment = 50 minNo matter what the grid size and time interval is, QDP is always better than or equal to IHMs.


## 4.5. Analysis and Discussion

We perform more analysis to disclose the reason of the above results. Remind that the main difference among ALT, IEM, IHMs, and QDP is how to decide the searching momenttopt, i.e., ALT searches only at the target moment, IEM searches at an intermediate moment and the target moment, while IHMs and QDP search at multiple intermediate moments as well as the target moment. We intend to demonstrate the efficiency of different moment decisions. Because the search cost will increase as the timespan Δt=topt−ts becomes larger, the cost-timespan ratio (also the heuristic indicator of IHMs) is defined as the ratio of the estimated search cost to the timespan:
(12)CostTimespanRatiotopt−ts=Costtopt,ξopttopt−tsFigure7 shows the cost-timespan ratio under different grid sizes (1KM×1KM, 1.2KM×1.2KM, 1.5KM×1.5KM). All three ratio’s curves first decrease, then increase, and then decrease along with the timespan. Let preferred timespan Δtmid be the timespan of the first locally minimum ratio CostTimespanRatio(Δtmid). A contour timespan Δtlimit is the timespan whose cost-timespan ratio is equal to CostTimespanRatio(Δtmid).Figure 7
Cost-timespan ratio of different timespans.
(a)
grid size =1KM×1KM(b)
grid size =1.2KM×1.2KM(c)
grid size =1.5KM×1.5KMIfΔt < Δtmid or Δt> Δtlimit, the larger timespan is more efficient, thus the searching moment should be as later as possible, i.e., searching at intermediate moments cannot help to reduce the total search cost, and ALT will be better than IEM. In this situation, IHMs and QDP will also only perform searches at the target moment, which are equivalent with ALT.IfΔt is between (Δtmid, Δtlimit), since CostTimespanRatio(Δtmid) is the minimum ratio when timespan is from 0 to Δt. As a result, Δtmid is the most efficient timespan which can decide the corresponding intermediate moment, i.e., searching at intermediate moments can reduce the total search cost, and IEM, IHMs and QDP may be better than ALT. Whether the right intermediate moments are detected is up to specific algorithms.The different grid sizes will causeΔtlimit to be different.Δtlimit corresponding to grid sizes 1KM×1KM, 1.2KM×1.2KM, and 1.5KM×1.5KM are calculated to be 58 min, 46 min and 36 min, respectively. Therefore, the reason of the results in Section 4.4 can be explained as:
(1)
When the grid size =1KM×1KM, In Figures 6(a), 6(b), 6(c), since the timespans Δt = 30 min/40 min/50 min do not exceed Δtlimit (58 min), IHMs and QDP are better than ALT(2)
When the grid size =1.2KM×1.2KM, Since the timespans Δt = 30 min/40 min (Figures 6(d), 6(e)) do not exceed Δtlimit (46 min), IHMs and QDP are better than ALT. While when the timespan Δt = 50 min (Figure 6(f)) exceeds Δtlimit (46 min), there is no significant difference among ALT, IHMs, and QDP(3)
When the grid size =1.5KM×1.5KM, Since the timespan Δt = 30 min (Figure 6(g)) does not exceed Δtlimit (36 min), IHMs and QDP are better than ALT. While when the timespans Δt = 40 min/50 min exceed Δtlimit (36 min), there is no significant difference among ALT, IHMs, and QDPIEM is bound to search at an intermediate moment and cannot make a decision dynamically to adapt environment information. Therefore, IEM is almost the worst in all situations. QDP can surmount the shortage that IHMs may output a locally optimal solution. As Q-learning does, it finds the near global optimal solution in the sense that it minimizes the total cost of any and all successive searches.


## 5. Conclusions

To minimize the cost of spatiotemporal search, this paper proposes a reinforcement learning algorithm called QDP.QDP selects the next searching moment based on known vehicle’s spatiotemporal point. The outcome of these searches is a new known vehicle’s spatiotemporal point, which guides the next selection iteratively. To address the challenge of probabilistic state in the training phase, we propose a novel training method for QDP, which is based on Monte-Carlo method and probabilistic states. QDP replaces the next state by multiple states of a probability distribution and estimates the expected cost of subsequent actions to calculate the value function. Finally QDP creates a state and an action randomly in each loop to train the value function progressively.We evaluate QDP on a real-world vehicle trajectory data and compare it with baseline algorithms ALT, IEM, IHMs under different grid sizes (1KM×1KM, 1.2KM×1.2KM, 1.5KM×1.5KM) and different time intervals (30 min, 40 min, 50 min). The experimental results show that QDP is better than the baseline. In addition, with the grid size decreasing, the preferred timespan Δtmid is also decreasing, but the contour timespan Δtlimit is increasing. Compared with ALT, algorithms with adaptive intermediate moment selection (i.e., IHMs and QDP) can effectively reduce the total search cost when the timespan is between Δtmid and Δtlimit. Compared with IHMs, QDP takes into account both the cost efficiency of the current selection (as well as performing search at that moment) and its potential impact on subsequent selections, and gives an approximate lower bound of the cost of spatiotemporal search to a certain extent.In the future, we will test QDP with other datasets, e.g., trajectories of pedestrians, bicycles, or ride sharing cars [34, 35]. We also wish to build new models that can take consideration of both the location decision model and the moment decision model simultaneously, or can output directly a candidate spatiotemporal point to search for next. And deep reinforcement learning algorithms are worth to explore for this problem.



---

*Source: 9402671-2022-06-08.xml*