UNSURPERVISED CLASSIFICATION OF ENCOUNTERING SCENARIOS USING CONNECTED VEHICLE DATASETS

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
0
Assignments
First Claim
1. A method in a data processing system comprising at least one processor and at least one memory, the at least one memory comprising instructions executed by the at least one processor to implement a driving encounter recognition system, the method comprising:
 receiving an information from a one or more sensors coupled to a first vehicle;
determining, based on the information received from the one or more sensors coupled to a first vehicle, a first trajectory information associated with the first vehicle and a second trajectory information associated with a second vehicle;
extracting, based on a current driving encounter comprising the first trajectory information and the second trajectory information, a feature vector;
providing the feature vector to a trained classifier, wherein the classifier was trained using unsupervised learning based on a plurality of feature vectors corresponding to driving encounters; and
receiving, from the trained classifier, a classification of the current driving encounter in order to facilitate the first vehicle to perform a maneuver based on the current driving encounter.
0 Assignments
0 Petitions
Accused Products
Abstract
The present disclosure provides a method in a data processing system that includes at least one processor and at least one memory. The at least one memory includes instructions executed by the at least one processor to implement a driving encounter recognition system. The method includes receiving information, from one or more sensors coupled to a first vehicle, determining first trajectory information associated with the first vehicle and second trajectory information associated with a second vehicle, extracting a feature vector, providing the feature vector to a trained classifier, the classifier trained using unsupervised learning based on a plurality of feature vectors, and receiving, from the trained classifier, a classification of the current driving encounter in order to facilitate the first vehicle to perform a maneuver based on the current driving encounter.
0 Citations
No References
No References
20 Claims
 1. A method in a data processing system comprising at least one processor and at least one memory, the at least one memory comprising instructions executed by the at least one processor to implement a driving encounter recognition system, the method comprising:
receiving an information from a one or more sensors coupled to a first vehicle; determining, based on the information received from the one or more sensors coupled to a first vehicle, a first trajectory information associated with the first vehicle and a second trajectory information associated with a second vehicle; extracting, based on a current driving encounter comprising the first trajectory information and the second trajectory information, a feature vector; providing the feature vector to a trained classifier, wherein the classifier was trained using unsupervised learning based on a plurality of feature vectors corresponding to driving encounters; and receiving, from the trained classifier, a classification of the current driving encounter in order to facilitate the first vehicle to perform a maneuver based on the current driving encounter.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
 14. A method for training an autonomous vehicle, comprising:
obtaining trajectories of a plurality of vehicles; identifying each pair of vehicles from the plurality of vehicles with a betweenvehicledistance that is less than a threshold; normalizing the trajectories of each pair of vehicles; learning features of each normalized trajectory; clustering each trajectory based on the learned features; and training the autonomous vehicle based on the learned features.  View Dependent Claims (15, 16, 17, 18, 19, 20)
1 Specification
Not Applicable.
Not Applicable.
This invention relates to a method for classifying driving encounters between two vehicles.
A driving encounter in this disclosure can be a scenario where two or multiple vehicles are spatially close to and interact with each other when driving. For autonomous vehicle and/or humandriven vehicle, both are faced with various interactive scenarios in real traffic and should make proper decisions. A welldesigned decisionmaking and control system for selfdriving vehicles should fully understand and efficiently tackle with any kinds of driving encounters to guarantee road safety and traffic efficiency.
Many kinds of advanced communication techniques such as dedicated short range communications (DSRC) have been developed to gather driving encounter data for model and analysis. Interactions between multiple vehicles can be interpreted by their trajectory—a set of positional information for moving vehicles, ordered by time. The growing use of global positioning system (GPS) receivers in equipped vehicles enables to collect large amounts of highquality trajectory data at a low cost. Applying positional trajectories to dig underlying information is prevalent in many fields, for example, driver behavior pattern analysis and prediction (Ref. 1, 2), travel destination prediction (Ref. 3), anomalous driving behavior detection (Ref. 4), ecodriving (Ref. 5), vehicle behavior reconstruction (Ref. 6), etc. However, the diversity of driving encounters at variance with human drivers and driving conditions (e.g., road, traffic, and other road users) and the flood of highdimensional traffic data can overwhelm human insight and analysis (Ref. 7), thus limiting their applications.
For vehicle trajectory analysis and associated applications, many clustering algorithms and data mining techniques have been investigated, as reviewed in (Ref. 8, 9). Besse et al. (Ref. 10) proposed a distancebased algorithm to learn representations of each single vehicle trajectory and then applied a hierarchical clustering (HC) to the representations of all vehicles for categorization. Moreover, the authors in (Ref. 3) also developed a twostep procedure to predict trip destination using a densitybased clustering of destination and start initial part of trajectories. Yao et al. (Ref. 11) used a sliding window to extract a set of moving behavior features that capture space and timeinvariant characteristics of the trajectories. Zhao et al. (Ref. 12, 13) extracted lane change behavior according to vehicle'"'"'s raw movement trajectory and addressed the scene based analysis. In order to attain traffic patterns for traffic surveillance, Choong et al. (Ref. 14) implemented the longest common subsequence (LCSS) to measure similarity levels of trajectories as features and then clustered vehicle trajectories into groups using kmeans and fuzzy cmeans. Some research (Ref. 9, 1518) also applied clustering algorithms to detect 2 traffic information such as traffic hotspots, traffic patterns and traffic volume based on vehicle GPS trajectories. Pokorny et al. (Ref. 19) proposed a topological trajectory clustering by considering the relative persistent homology between motion trajectories and the experiment results demonstrate that the topological trajectory clustering method is faster and more efficient than a metric clustering by Fréchet distance. A common autoencoder has been used to extract features of characterizing driving encounters (Ref. 20).
For most of aforementioned research, they mainly aim at discovering the group of similar individual trajectories, rather than the group of similar pairs of trajectories—driving encounters. Investigating the patterns of driving encounters could be beneficial to gain insight into how human drivers make decisions when encountering with others, thereby providing external knowledge for selfdriving applications and driver assistance system design. For example, the classification of driver'"'"'s typical behaviors at unsignalized intersections and on highways offers researchers detailed information to design decisionmaking systems (Ref. 21) for autonomous vehicles with ability to harmoniously interact with surrounding road users. Towards this goal, many researchers have conducted research based on vehicletovehicle (V2V) trajectories in empirically predefined specific and typical scenarios such as changing lanes. Although they have made remarkable achievement, the specific scenarios they focused on could not fully represent all driving encounters, which strongly limits their further applications. There exist many offtheshelf algorithms to deal with a group of single trajectories, but no one efficient approach to cluster a group of pairs of vehicle trajectories.
Therefore, an improved method for training autonomous vehicles using clustered pairs of vehicle trajectories is desired.
The present invention provides a method to efficiently cluster vehicle trajectories in order to train autonomous vehicles. The method can include training an autoencoder using a plurality of vehicle trajectories in an unsupervised learning process, classifying a plurality of feature vectors extracted from the autoencoder using unsupervised learning such as clustering, and providing the classifications to an autonomous vehicle. Categorizing driving encounters into groups provides insights into each kind of driving encounter scenario and offer opportunities to test distancebased and/or clustering algorithms.
In one aspect, the present disclosure provides a method in a data processing system that includes at least one processor and at least one memory. The at least one memory includes instructions executed by the at least one processor to implement a driving encounter recognition system. The method includes receiving information from one or more sensors coupled to a first vehicle, determining, based on the information received from the one or more sensors coupled to the first vehicle, first trajectory information associated with the first vehicle and second trajectory information associated with a second vehicle, extracting, based on a current driving encounter comprising the first trajectory information and the second trajectory information, a feature vector, providing the feature vector to a trained classifier, the classifier trained using unsupervised learning based on a plurality of feature vectors corresponding to driving encounters, and receiving, from the trained classifier, a classification of the current driving encounter in order to facilitate the first vehicle to perform a maneuver based on the current driving encounter.
The method may include sensing that the first vehicle and the second vehicle are within a predetermined distance of each other. The method may include receiving information from the one or more sensors for a predetermined time. The predetermined time can be about 5 to about 20 seconds.
In the method, the classifier can be trained using a clustering technique. The classifier can be trained using kmeans clustering. The clustering technique can be a number of clusters selected in order maximize betweencluster distance and minimize withincluster distance. The method can include normalizing the first trajectory information and the second trajectory information to a predetermined number of data points. The predetermined number of data points can be about 50 to about 400 data points.
The feature vector can be extracted using an autoencoder, and the plurality of feature vectors can be extracted using the autoencoder. The autoencoder can be a longshort term memory autoencoder, a normalized Euclidean distance longshort term memory autoencoder, or a dynamic time warping convolutional autoencoder. The feature vector can be extracted using a distancebased formula, and the plurality of feature vectors can be extracted using the distancebased formula. The distancebased formula can use dynamic time warping or normalized Euclidean distance.
In another aspect, the present disclosure provides a method for training an autonomous vehicle. The method includes obtaining trajectories of a plurality of vehicles, identifying each pair of vehicles from the plurality of vehicles with a betweenvehicledistance that is less than a threshold, normalizing the trajectories of each pair of vehicles, learning features of each normalized trajectory, clustering each trajectory based on the learned features, and training the autonomous vehicle based on the learned features.
The method can include the clustering can being done using kmeans clustering. The clustering can include clustering each trajectory into one of a plurality of clusters, the number of clusters selected in order maximize betweencluster distance and minimize withincluster distance. The learning can be done using an autoencoder selected from: a longshort term memory autoencoder, a normalized Euclidean distance longshort term memory autoencoder, or a dynamic time warping convolutional autoencoder. In the method, the features can be extracted from a hidden layer of the autoencoder. The learning can be unsupervised learning based on a plurality of feature vectors corresponding to driving encounters, wherein the plurality of feature vectors are extracted by the driving encounter feature extractor. In the method for training an autonomous vehicle, the threshold can be about 100 meters.
These and other features, aspects, and advantages of the present invention will become better understood upon consideration of the following detailed description, drawings and appended claims.
Driving encounter classification and analysis can benefit autonomous vehicles to achieve a more smart decision. This disclosure presents an unsupervised learning framework to classify driving encounter which composes of two vehicles'"'"' GPS trajectories ordered by time. We developed two kinds of approaches, including deep autoencoders and distancebased approaches, to learn underlying representations in terms of both shape and distance of driving encounters. Five specific approaches were developed and evaluated by combining the deep autoencoders and the distancebased approaches. We then applied kmeans clustering to categorize driving encounters into several distinguishable groups based on the learned representations. The effectiveness of our unsupervised learning framework for driving encounter classification was demonstrated based on 2568 naturalistic driving encounters, comparing with the stateoftheart deep learning methods.
As shown in
A driving encounter can be composed of two vehicle trajectories with the same length of time, where the vehicle trajectories could be continuous or discrete. In our case we may only consider the discrete trajectories and define as follows. Given a discrete observed driving encounter
x={(p_{1}^{(1)},p_{1}^{(2)},t_{1}), . . . ,(p_{k}^{(1)},p_{k}^{(2)}t_{k}), . . . ,(p_{K}^{(1)},p_{K}^{(2)},t_{K})} (1)
where p_{k}^{(1)}∈^{2 }and p_{k}^{(2)}∈^{2 }are the positions of two vehicles in the driving encounter at discrete time t_{k}, K∈ is the length of the driving encounter x, as shown in
For some clustering algorithms, driving encounters are required to be set as a unified length so that they could be well measured. For two arbitrary driving encounters, their length may be largely different from each other in real traffic. In order to make clustering algorithms tractable for driving encounters, we need to normalize the driving encounters into the same length with little loss of information. Many mature approaches of normalizing trajectories have been developed, see review literature (Ref. 22). Some exemplary approaches are listed below.
Trajectory transformation algorithms, which projects the trajectories into another structured space with fixed parameter. Some popular methods include linear transformation, curving fitting (e.g., uniform cubic Bspline curve), discrete Fourier transformation, etc.
Resampling methods, which chooses trajectory points by sampling rule to normalize trajectory lengths with minimal information loss. The resampling method with interpolation processes can be very flexible to operate.
Trajectory substitute, which utilizes the basic components of trajectories, termed as subtrajectories, to represent describe hidden information of original trajectory data.
Points of interest, which is flexible and preferable when research focuses on some specific regions of surveillance area, termed as points of interest, rather than the points outside the regions.
Scaleinvariant features, which has been widely used to extract more robust and representative features (e.g., histograms of oriented gradients and histograms of optical flow) from image frames rather than only the position of trajectories.
Trajectory transformation algorithms and resampling methods may be implemented with less computational cost than other methods.
Since the driving encounter is represented as timeseries data sequences, it is nontrivial to directly feed the data into clustering algorithms. In order to classify driving encounters into distinguishable groups, we need to select representations capable of characterizing these driving encounters, thus allowing to minimize the difference within clusters and maximize the difference between clusters in terms of the learning representations, instead of directly operating on vehicle trajectories. There are many different approaches to extract representations of driving encounters with respect to their shape or distance, for example, by measuring the distance (Ref. 3, 10) between two trajectories or by using neural networks to learn representations of trajectories (Ref. 11, 23).
In order to distinguish driving encounters and categorize them into groups, certain features capable of capturing the underlying characteristics of the driving encounters should be carefully extracted. Improper representation can lead to unsatisfied results. Therefore, extracting representations from driving encounter is of importance to get satisfied classification performance. Unlike extracting features of images with specific and explicit labels, we can have rare knowledge about the feature space of driving encounters. Fortunately, many approaches to learning representations of timeseries trajectories have been developed, which can be taken as reference since driving encounter in nature is also timeseries data sequences. In this section, three ways to learn the representations of vehicle trajectories are presented: deep autoencoder, distancebased measure, and shapebased measure.
Our goal is to find a representation which can characterize a given driving encounter. For the autoencoder, it has been widely used to dig underlying information of timeseries data. An autoencoder is a neural network (NN), consisting of encoder and decoder (as shown in
As shown in
x_{i+1}=w_{i,i+1}^{T}x_{i}+b_{i} (2)
where w_{i,i+1}∈^{r×s }is the weight vector, b_{i}∈^{s }is the bias vector, x_{i+1}∈^{s×d}. The autoencoder 400 can include a middle layer 420, which can be the representation h of a driving encounter.
The hidden representation h from the encoder is then mapped back to z through a symmetric multilayer network.
Subsequently, an autoencoder involved simple multilayer perception can be easily derived using (2) without concerning the past information of observation, which has been investigated in (Ref. 20). For driving behavior, however, previous research demonstrates that it is dynamic process in nature with related to past information (Ref. 24), (Ref. 25). Hence, in this disclosure, we take the past information of observation into consideration by employing two advanced autoencoders: LSTMAutoencoder (LSTMAE) and convolutional autoencoder (ConvAE).
In contrast to the simplest autocoder with a multilayer perception, the LSTMAE (Ref. 26) takes advantage of the previous information by adding an information selection function, usually as a sigmoid neural net layer, to decide what information is useful and to remember this helpful information, thus transferring the observation x_{i }at the i^{th}layer to the representation at the (i+1)^{th}layer. Instead of using (2), the LSTMAE introduces four basic equations to achieve this, formulated by
z_{i}=σ(w_{z}^{T}l_{i}+u_{z}x_{i−1}+b_{z}) (3a)
y_{i}=σ(w_{y}^{T}l_{i}+u_{z}x_{i−1}+b_{y}) (3b)
{circumflex over (x)}_{i}=tan h(w_{h}^{T}l_{i}+u_{l}y_{i}x_{i−1}+b_{l}) (3c)
x_{i}=(1−z_{i})x_{i−1}+z_{i}{circumflex over (x)}_{i} (3d)
where σ(⋅) is the sigmoid function, w_{z}, w_{y}, w_{i }are the weights, b_{z}, b_{y}, b_{i }are the biases, x_{i }is the output vector of the LSTM unit. Therefore, given observation x_{i−1 }for each LSTM unit, we can get the output x_{i }to next layer.
Sharing the same structure with LSTMAE, the ConvAE describes the layer relationship using a convolutional operator, instead of using a basic multiply operator. In fact, the encoding and decoding processes can be treated as a procedure of reconstructing observations and hence we can learn hidden representation h by solving the following optimization problem of minimizing the errors between reconstructed observations ˜x and the origin inputs x with the cost function
where E(θ)=(x−{tilde over (x)})^{T}(x−{tilde over (x)}) and θ==_{i=1}^{I }for all layers, where I is the number of layers. From aforementioned discussion, the representation learning process can be transformed into an issue of training autoencoders, then recording information of the middle layer h (i.e., the layer of hidden presentation) in feature space H∈^{r×1 }for each driving encounter x, where r is the dimension of hidden layer.
In addition to treat the representation learning process as a black box, we can also use a mathematically rigorous way to capture their distance characteristics. In order to describe the distance relationship between two trajectories in a driving encounter, we need to define a measure to gauge their geometrical distance. Generally, there are two typical ways or formulas to achieve this, i.e., dynamic time warping and Euclidean distance, discussed as follows.
Given a driving encounter observation x, the objective of DTW (Ref. 27) is to measure the geometric relationship of the two vehicle trajectories
p^{(1)}=(p_{1}^{(1)}, . . . ,p_{k}^{(2)}, . . . ,p_{K}^{(1)})
p^{(2)}=(p_{1}^{(2)}, . . . ,p_{k}^{(2)}, . . . ,p_{K}^{(2)})
with a length of K. In what follows, we will introduce trajectory measure space denoted by Pε^{K×K}, with p_{m}^{(1)}, p_{n}^{(2)}∈P for m, n,∈[1, . . . , K]. To evaluate the relationship between trajectories p^{(1) }and p^{(2) }in a driving encounter, we introduce a local distance measure, defined by
f:P×P→_{≥0} (5)
Typically f(p_{m}^{(1)}, p_{n}^{(2)}) is small if p_{m}^{(1) }and p_{n}^{(2) }are close to each other, and otherwise f(p_{m}^{(1)}, p_{n}^{(2)}) is large. Thus by evaluating each pair of elements in the vehicle trajectories p^{(1) }and p^{(2)}, we can obtain the corresponding feature matrix F∈^{K×K }to represent the geometry of driving encounter x, where
F(m,n):=f(p_{m}^{(1)},p_{n}^{(2)}) (6)
Here the Euclidean distance is selected to compute the local distance and computed by
f(p_{m}^{(1)},p_{n}^{(2)})=∥p_{m}^{(1)}−p_{n}^{(2)}∥_{2} (7)
Similar to the DTW distance, other distance measures can also be selected such as LCSS, edit distance for real sequence (EDR). They discrete the trajectories of driving encounter and account the number of occurrences where the Euclidean distance between matched segments does not match a predefined spatial threshold. Compared to DTW, both of LCSS and EDR are sensitive to the spatial threshold (Ref. 10), that is, a large threshold value indicates a high acceptation of differences in trajectories and otherwise, a low tolerance of differences.
The other simple and efficient way to measure the distance between driving encounters is to apply a normalized Euclidean distance directly, which is computed by
Thus we can obtain the feature F of this driving encounter. Other kinds of distance measure could also be flexible used.
Different from the distancebased measure, the shapebased measures have also been used to capture the geometric features of two single trajectories (Ref. 3), (Ref. 10). The most wellknown shapebased measures are the Hausdorff distance (Ref. 28), the Fréchet distance (Ref. 29), and the symmetrized segmentpath distance (SSPD) developed in (Ref. 10). These methods have registered a high level of performance for describing the geometric features of a single trajectory; however, they are not suitable for the relationship between driving encounters consisting of a pair of vehicle trajectories, since their output is a metric and easy to measure the shapesimilarity level of two individual trajectories but not work for pairs of two trajectories. Because even for driving encounters with the same metric value, the driving encounters could be greatly different from each other in terms of shape. Therefore, the shapebased measure is not applied in this disclosure.
According to the above discussion, we select the neural networkbased autoencoder and distancebased measure to learn features representative of driving encounters. Besides, the autoencoder is able to uncover underlying information with dimension reduction and hence it can potentially extract meaningful representations from the results of DTW or NED. There are five combination ways to learn representations from driving encounters, listed as follows:
DTW: directly using output of DTW as representations, i.e.,
NED: directly using output of NED as representations, i.e.,
LSTMAE: Applying LSTMAE to extract underlying representations of driving encounters, i.e.,
DTWConvAE: combining ConvAE with DTW to extract underlying representations, i.e.,
NEDLSTMAE: combine LSTMAE with NED to extract underlying representations, i.e.,
To understand easily, we display and compare the input and output for each representation extraction method in Table 1. In order to follow easily, we denoted _{x}_{i }as the extracted representation F or h of driving encounter x_{i }for all approaches in Table 1, where K is the dimension of inputs and r is the dimension of the learned representations.
This section will introduce a clustering approach for the learned representations. We first detail the clustering method and then introduce the qualification criteria of clustering results.
Timeseries trajectories clustering is very ubiquitous (Ref. 30), and a wealth of clustering algorithms has been developed to solve related problems (Ref. 31). Clustering method selection is restricted by the characteristics of the driving encounter. Given the extracted representation of driving encounters in Table I, we can classify them into groups. In this disclosure, we can use kmeans clustering (kMC) (Ref. 32).
For the clustering task, we do not exactly have the prior knowledge of cluster number. Therefore, we need to define a criterion to evaluate the clustering performance. Our aim is to gather the driving encounters with similar characteristics into one group that is greatly far from other groups. Hence, the quality of clustering results can be assessed by checking the between and within variances of the obtained clusters. On the other hand, the variance of the elements in the same groups should be as small as possible. Here (according to Refs. 10, 30, 31), we should define the withincluster (WC) variance and betweencluster (BC) variance, which requires compute a mean value of extracted features.
However, in our case, directly computing the mean of driving encounters is not tractable since it is inconceivable and meaningless to calculate the mean of trajectories in driving encounters. In this disclosure, instead of directly using the vehicle trajectories to evaluate the BC and WC variances, we make the advantages of the extracted representations and introduce the mean of the extracted representations, denoted by _{χ}, which is computed by averaging all extracted representations within the cluster χ. Let χ_{1}, χ_{2}, . . . χ_{J }be the set of clusters of driving encounters x. Then the BC variance and WC variance can be derived by
In such way, the BC and WC variances between approaches become comparable through scaling their values into [0, 1] with respect to each approach. A large value of λ_{BC }indicates a far distance between clusters and otherwise, a close distance.
The following Example is provided to demonstrate and further illustrate certain embodiments and aspects of the present invention and is not to be construed as limiting the scope of the invention.
All the driving data were collected from naturalistic settings supported by the University of Michigan Safety Pilot Model Development (SPMD) program (Ref. 33). This database was conducted by the University of Michigan Transportation Research Institute (UMTRI) and provides driving data logged in the last five years in Ann Arbor area. It includes approximately 3,500 equipped vehicles and 6million trips in total. Latitude and longitude information of each vehicle was collected by the onboard GPS. The collection process starts at the ignition for each equipped vehicle. The data was collected with a sampling frequency of 10 Hz.
We searched the dataset of 100,000 trips, collected from 1900 vehicles with 12day runs. The trajectory information we extracted includes latitude, longitude, speed of the vehicles. The selection range was constricted to an urban area with the latitude in (−83.82, −83.64) and the longitude in (42.22, 42.34), as shown in
From
Setting an optimal number of layers in autoencoder is a challenging and openend problem, because there is no general design rule that can be universally used to solve all problems. We set all autoencoders with a symmetric structure according to our experiences, and more specifically,
LSTMAE: A fifthlayer (I=5) LSTMAE was designed for the deep representation, where the fourth layer (i.e., middle layer) is the hidden representation of driving encounter. The weights for each layer were initialized using random numbers between 1 and −1 following uniform distribution. The dimension of the middle layer (i.e., hidden layer) was set as 10, i.e., h∈^{r×1 }with r=10.
ConvAE: A fifthlayer ConvAE was designed to extract underlying features from outputs of DTW. The dimension of its hidden layer was also set as 10, i.e., h∈^{r×1 }with r=10. After learning the hidden feature _{x}_{i }of driving encounter x_{i }using autoencoders, we then applied the kmeans clustering (kMC) approach to these extracted hidden representations to cluster driving encounters.
Similarly to autoencoders, the length of driving encounters was unified to 100 for DTW in order to balance the model accuracy and computational burden of representation learning. Thus we can compute the representation _{x}∈^{100×100 }using (7) for each driving encounter.
For the normalized Euclidean distance approach, the representation can be directly computed through (8) based on the unified driving encounters. For all learned representations, we do not have any prior knowledge of what values of k∈^{+} pet. In order to determine k, we run clustering algorithms with different k and computed their performance metric λ_{BC }and λ_{WC}.
This section will present and analyze the experiment results, covering representation extraction results and clustering performance evaluation and comparison.
Each driving encounter endows a tendimensional representation in a vector h∈^{10×1 }via autoencoders.
Based on the extracted representations,
According to
In order to evaluate the conservativeness of the algorithm and its applicability to realtime applications, its computational costs when implemented on a standard laptop computer are presented and a comparison with other counterparts is given. All autoencoders were built using Python in Keras(https://blog.keras.io/buildingautoencodersinkeras.html) and all distancebased representation extraction algorithms were also programmed using Python. Table 2 presents the average computation time for extracting representations on a standard laptop computer with an Intel Core i7 running at 2.5 GHz, with 16 GB of RAM. It can be seen that the NED and DTW algorithms can extract feature much faster than two others, only with 120 s for 2568 driving encounters. However, the autoencoders with neural nets require few hours to extract representations.
This disclosure presents a comprehensive investigation of driving encounter classification through five approaches, which can be categorized into two types: deep learningbased and distancebased. The distancebased method outperforms all other counterparts. However, some challenges still exist in our developed approaches and discussed as follows.
For the deep learningbased approaches, we empirically set the hyperparameters of them, like the amount of decoder/encoder layers and the number of nodes between layers because there is no a general approach for all application cases to determine the optimal layers and nodes between layers. The hyperparameter selection in our disclosure mainly concerns two aspects: computational cost and model performance. Autoencoders with large numbers of layers could somewhat enhance model performance but at a significantly great computational cost. Therefore, in this disclosure we selected a moderate number of layers to learn hidden representation of driving encounters.
This disclosure mainly utilized the vehicle trajectories of GPS data without any other information to group driving encounters since GPS data is very easy to obtain at a low cost such as via mobilephone and equipped localization sensors. Our experiment validation did not consider other information such as contextual road information and vehicle speed, but it is flexible to extend our developed approach to other driving case of including highdimensional timeseries data. For instance, if more road context information could be obtained such as highway and intersections (Tshape, Yshape, and crossshape, etc.), our developed approached can help get insights into diversity of driving encounters. Therefore, considering road contextual information will be one of our future work.
This disclosure investigated the clustering problem of naturalistic driving encounters consisting of pairs of vehicle trajectories. Two kinds of representation learning ways—deep autoencoder and distancebased, including five specific approaches, were developed and evaluated. Clustering approaches, were considered, and kmeans clustering was selected and evaluated. The clustering results can provide insights into driver interactive behaviors in different scenarios and help to design a friendly and efficient decisionmaking policy for intelligent vehicles in order for intelligent vehicles such as autonomous vehicle to perform maneuvers based on driving encounters.
At step 1302, the process 1300 can determine that the first vehicle is within a predetermined distance of the second vehicle. The predetermined distance can be a distance that implies a driving encounter is occurring, such as 100 meters as described above. The process 1300 can sense the vehicles are within the predetermined distance of each other using the information received from the one or more sensors coupled to the first vehicle. If the first vehicle and second vehicle are within the predetermined distance of each other (“YES” at step 1302), the process 1300 can proceed to step 1303. If the first vehicle and second vehicle are not within the predetermined distance of each other (“NO” at step 1302), the process 1300 can proceed to 1301, forming an iterative loop.
At 1303, process 1300 can start a sampling timer. The sampling timer may be set to count down from a predetermined sampling time. The sampling time can be a minimum threshold time that a trajectory length is meaningful, such as about 10 seconds as described above. The process 1300 may need to continue to receive information from the one or more sensors until sufficient information has been obtained determine vehicle trajectory information and to classify vehicle trajectory information, as will be discussed below. The process can then proceed to 1304.
At 1304, the process 1300 can determine if the sampling timer is expired. If the process 1300 determines that the sampling timer is not expired, the (“NO”) at 1304, the process 1300 may proceed to 1304. If the process 1300 determines that the sampling timer is expired, the (“YES”) at 1304, the process may proceed to 1306.
At 1306, process 1300 can determine, using the information received from the one or more sensors coupled to the first vehicle, the trajectory, also known as first trajectory information, of the first vehicle. The one or more sensors can include any suitable sensor as described above. The process 1300 can also determine the trajectory, also known as second trajectory information, of the second vehicle as described above. The process 1300 can then proceed to 1306.
At 1308, the process 1300 can normalize the first trajectory information and second trajectory information to a predetermined number of data points. The number of data points can be the length that a driving encounter feature extractor, which will be described below, uses. In some embodiments, the number of data points can be 100200 samples. The process 1300 can use trajectory transformation, resampling methods, trajectory substitution, points of interest, scaleinvariant features, or another other suitable technique for normalizing the first trajectory information and second trajectory information to a predetermined number of data points. The process 1300 can then proceed to 1310.
At 1310, the process 1300 can extract a feature vector using the driving encounter feature extractor. A current driving encounter, which can include the first trajectory information and the second trajectory information, can be input to the driving encounter feature extractor, which can then extract the feature vector. The driving encounter feature extractor can be deeplearning approach including a trained autoencoder such as the LSTMAE, DTWConvAE, NEDLSTMAE, or other suitable autoencoder trained using unsupervised learning. The autoencoder can be trained using a plurality of suitable driving encounters unified to the predetermined number of data points, as described above. The feature vector can be the middle layer h of the autoencoder as described above. The driving encounter feature extractor can also use a distanced based approach such as DTW or NED, where the current driving encounter is input and the feature vector is directly output. The process 1300 can then proceed to 1312.
At 1312, the process 1300 can provide the feature vector to a trained classifier. The trained classifier can take an input feature vector and output a classification of the feature vector. The classifier can be trained using unsupervised learning including clustering techniques such as kmeans clustering, DBSCAN, OPTICS, or another suitable unsupervised learning method for grouping feature vectors. If clustering is used, the number of clusters may be selected by maximizing the betweencluster distance and minimizing the withincluster distance using an optimization technique known in the art. If kmeans clustering is used, the number of clusters can be about 10. If kmeans clustering is used, the classification output can be the cluster that the input feature vector belongs to. The classifier can be trained by using a plurality of feature vectors extracted from a plurality of driving encounters. If the driving encounter feature extractor is an autoencoder, the classifier can be trained using a plurality of feature vectors extracted from the plurality driving encounters used to train the autoencoder. The process 1300 can then proceed to 1314.
At 1314, the process 1300 can receive the classification output at 1312 in order to facilitate the first vehicle to perform a maneuver based on the current driving encounter.
Although the invention has been described in considerable detail with reference to certain embodiments, one skilled in the art will appreciate that the present invention can be practiced by other than the described embodiments, which have been presented for purposes of illustration and not of limitation. Therefore, the scope of the appended claims should not be limited to the description of the embodiments contained herein.
 [1] N. Deo, A. Rangesh, and M. M. Trivedi, “How would surround vehicles move? A unified framework for maneuver classification and motion prediction,” arXiv preprint arXiv:1801.06523, 2018.
 [2] J. Taylor, X. Zhou, N. M. Rouphail, and R. J. Porter, “Method for investigating intradriver heterogeneity using vehicle trajectory data: A dynamic time warping approach,” Transportation Research Part B: Methodological, vol. 73, pp. 5980, 2015.
 [3] P. C. Besse, B. Guillouet, J.M. Loubes, and F. Royer, “Destination prediction by trajectory distributionbased model,” IEEE Transactions on Intelligent Transportation Systems, 2017.
 [4] C. Piciarelli, C. Micheloni, and G. L. Foresti, “Trajectorybased anomalous event detection,” IEEE Transactions on Circuits and Systems for video Technology, vol. 18, no. 11, pp. 15441554, 2008.
 [5] Z. Sun, P. Hao, X. J. Ban, and D. Yang, “Trajectorybased vehicle energy/emissions estimation for signalized arterials using mobile sensing data,” Transportation Research Part D: Transport and Environment, vol. 34, pp. 2740, 2015.
 [6] Z.J. Chen, C.Z. Wu, Y.S. Zhang, Z. Huang, J.F. Jiang, N.C. Lyu, and B. Ran, “Vehicle behavior learning via sparse reconstruction with '"'"'2 □ '"'"'p minimization and trajectory similarity,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 2, pp. 236247, 2017.
 [7] T. Appenzeller, “The scientists'"'"' apprentice,” Science, vol. 357, no. 6346, pp. 1617, 2017.
 [8] G. Yuan, P. Sun, J. Zhao, D. Li, and C. Wang, “A review of moving object trajectory clustering algorithms,” Artificial Intelligence Review, vol. 47, no. 1, pp. 123144, 2017.
 [9] Z. Feng and Y. Zhu, “A survey on trajectory data mining: Techniques and applications,” IEEE Access, vol. 4, pp. 20562067, 2016.
 [10] P. C. Besse, B. Guillouet, J.M. Loubes, and F. Royer, “Review and perspective for distancebased clustering of vehicle trajectories,” IEEE Transactions on Intelligent Transportation Systems, vol. 17, no. 11, pp. 33063317, 2016.
 [11] D. Yao, C. Zhang, Z. Zhu, Q. Hu, Z. Wang, J. Huang, and J. Bi, “Learning deep representation for trajectory clustering,” Expert Systems, DOI: 10.1111/exsy.12252.
 [12] H. Zhao, C. Wang, Y. Lin, F. Guillemard, S. Geronimi, and F. Aioun, “Onroad vehicle trajectory collection and scenebased lane change analysis: Part I,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 1, pp. 192205, 2017.
 [13] W. Yao, Q. Zeng, Y. Lin, D. Xu, H. Zhao, F. Guillemard, S. Geronimi, and F. Aioun, “Onroad vehicle trajectory collection and scenebased lane change analysis: Part II,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 1, pp. 206220, 2017.
 [14] M. Y. Choong, L. Angeline, R. K. Y. Chin, K. B. Yeo, and K. T. K. Teo, “Modeling of vehicle trajectory clustering based on Icss for traffic pattern extraction,” in Automatic Control and Intelligent Systems (I2CACIS), 2017 IEEE 2nd International Conference on. IEEE, 2017, pp. 7479.
 [15] P. Zhao, K. Qin, X. Ye, Y. Wang, and Y. Chen, “A trajectory clustering approach based on decision graph and data field for detecting hotspots,” International Journal of Geographical Information Science, vol. 31, no. 6, pp. 11011127, 2017.
 [16] J. Wang, C. Wang, X. Song, and V. Raghavan, “Automatic intersection and traffic rule detection by mining motorvehicle gps trajectories,” Computers, Environment and Urban Systems, vol. 64, pp. 1929, 2017.
 [17] X. Zhan, Y. Zheng, X. Yi, and S. V. Ukkusuri, “Citywide traffic volume estimation using trajectory data,” IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 2, pp. 272285, 2017.
 [18] J. Kim and H. S. Mahmassani, “Spatial and temporal characterization of travel patterns in a traffic network using vehicle trajectories,” Transportation Research Part C: Emerging Technologies, vol. 59, pp. 375390, 2015.
 [19] F. T. Pokomy, K. Goldberg, and D. Kragic, “Topological trajectory clustering with relative persistent homology,” in Robotics and Automation (ICRA), 2016 IEEE International Conference on. IEEE, 2016, pp. 1623.
 [20] S. Li, W. Wang, Z. Mo, and D. Zhao, “Clustering of naturalistic driving encounters using unsupervised learning,” arXiv preprint arXiv:1802.10214, 2018.
 [21] E. Galceran, A. G. Cunningham, R. M. Eustice, and E. Olson, “Multipolicy decisionmaking for autonomous driving via changepointbased behavior prediction: Theory and experiment,” Autonomous Robots, vol. 41, no. 6, pp. 13671382, 2017.
 [22] J. Bian, D. Tian, Y. Tang, and D. Tao, “A survey on trajectory clustering analysis,” arXiv preprint arXiv: 1802.06971, 2018.
 [23] D. Yao, C. Zhang, Z. Zhu, J. Huang, and J. Bi, “Trajectory clustering via deep representation learning,” in Neural Networks (IJCNN), 2017 International Joint Conference on. IEEE, 2017, pp. 38803887.
 [24] B. M. Lake, R. Salakhutdinov, and J. B. Tenenbaum, “Humanlevel concept learning through probabilistic program induction,” Science, vol. 350, no. 6266, pp. 13321338, 2015.
 [25] M. C. Nechyba and Y. Xu, “Stochastic similarity for validating human control strategy models,” IEEE Transactions on Robotics and Automation, vol. 14, no. 3, pp. 437451, 1998.
 [26] S. Hochreiter and J. Schmidhuber, “Long shortterm memory,” Neural computation, vol. 9, no. 8, pp. 17351780, 1997.
 [27] M. Muller, “Dynamic time warping,” Information retrieval for music and motion, pp. 6984, 2007.
 [28] A. A. Taha and A. Hanbury, “An efficient algorithm for calculating the exact hausdorff distance,” IEEE transactions on pattern analysis and machine intelligence, vol. 37, no. 11, pp. 21532163, 2015.
 [29] B. Aronov, S. HarPeled, C. Knauer, Y. Wang, and C. Wenk, “Frechet distance for curves, revisited,” in European Symposium on Algorithms. Springer, 2006, pp. 5263.
 [30] T. W. Liao, “Clustering of time series data: A survey,” Pattern recognition, vol. 38, no. 11, pp. 18571874, 2005.
 [31] R. Xu and D. Wunsch, “Survey of clustering algorithms,” IEEE Transactions on neural networks, vol. 16, no. 3, pp. 645678, 2005.
 [32] T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, and A. Y. Wu, “An efficient kmeans clustering algorithm: Analysis and implementation,” IEEE transactions on pattern analysis and machine intelligence, vol. 24, no. 7, pp. 881892, 2002.
 [33] W. Wang, C. Liu, and D. Zhao, “How much data are enough? a statistical approach with case study on longitudinal driving behavior,” IEEE Transactions on Intelligent Vehicles, vol. 2, no. 2, pp. 8598, 2017.
The citation of any document is not to be construed as an admission that it is prior art with respect to the present invention.