# PG2Net: Personalized and Group Preferences Guided Network for Next Place
Prediction

Huifeng Li, Bin Wang∗, Fan Xia, Xi Zhai, Sulei Zhu, Yanyan Xu∗ H. Li, B. Wang,
S. Zhu are with the College of Information, Mechanical, and Electrical
Engineering, Shanghai Normal University, Shanghai 201400, China.E-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>F. Xia is with the
School of Information Science and Engineering, Shandong University, Qingdao
266237, China. E-mail<EMAIL_ADDRESS>X. Zhai is with the Shanghai
Municipal Country-rural Construction and Transportation Institute. E-mail:
<EMAIL_ADDRESS>Y. Xu is with the MoE Key Laboratory of Artificial
Intelligence and AI Institute, Shanghai Jiao Tong University, Shanghai 200240,
China. E-mail<EMAIL_ADDRESS>This work has been submitted to the IEEE
for possible publication. Copyright may be transferred without notice, after
which this version may no longer be accessible. ∗Corresponding authors.

###### Abstract

Predicting the next place to visit is a key in human mobility behavior
modeling, which plays a significant role in various fields, such as epidemic
control, urban planning, traffic management, and travel recommendation. To
achieve this, one typical solution is designing modules based on RNN to
capture their preferences to various locations. Although these RNN-based
methods can effectively learn individual’s hidden personalized preferences to
her visited places, the interactions among users can only be weakly learned
through the representations of locations. Targeting this, we propose an end-
to-end framework named personalized and group preference guided network
(PG2Net), considering the users’ preferences to various places at both
individual and collective levels. Specifically, PG2Net concatenates Bi-LSTM
and attention mechanism to capture each user’s long-term mobility tendency. To
learn population’s group preferences, we utilize spatial and temporal
information of the visitations to construct a spatio-temporal dependency
module. We adopt a graph embedding method to map users’ trajectory into a
hidden space, capturing their sequential relation. In addition, we devise an
auxiliary loss to learn the vectorial representation of her next location.
Experiment results on two Foursquare check-in datasets and one mobile phone
dataset indicate the advantages of our model compared to the state-of-the-art
baselines. Source codes are available at
https://github.com/urbanmobility/PG2Net.

###### Index Terms:

Next place prediction, human mobility, trajectory data, personalized and group
preferences, attention mechanism.

##  1 Introduction

With the rapid development of information and communication technologies,
users can share their locations almost anytime and anywhere to acquire the
location-aware services, which forms an abundant amount of trajectory data.
Location-based social networks (LBSNs), such as Foursquare and Yelp, collect a
huge amount of location data from millions of individuals [1, 2]. These
trajectory data provide an unprecedented opportunity to study human mobility
behavior at scale [3, 4]. With massive mobile phone data, González et al.
found a high degree of temporal and spatial regularity in human trajectories
[3]. Their radius of gyrations clearly follow a power law distribution,
indicating the sample reproducible patterns of human mobility. In a following
study, Song et al. measured the potential predictability of human mobility as
93% [5]. Due to the high predictability of human mobility, researchers
attempted to model the mobility behavior of the population at urban scale and
utilized it to tackle various urban challenges, including traffic congestion
mitigation [6, 7, 8], air pollution exposure estimation [9], planning of
electric vehicles charging behavior [10], control of the epidemics [11, 12].

Prediction of user’s next place to visit is a key in modeling of human
mobility, and has attracted increasing attention from researchers [13]. The
task aims to predict the destination of next trip for each user. Assuming that
a user’s next destination is highly correlated with her recently visited
locations, Rendle et al. developed a personalized transition matrix based on
the Markov chain to capture the influence of users’ recently visited venues on
the current mobility decision [14]. Researchers also notice that the users’
periodical behavior observed from long-term history trajectory plays a
critical role in the decision of next travel [15, 16]. For instance, in a
user’s daily routine, she or he is accustomed to going to the library every
weekend. Therefore, combining the influence of users’ long-term and short-term
trajectory can benefit the prediction of next location [17, 18]. Feng et al.
proposed DeepMove based on an attention mechanism to extract the influence of
the user’s history trajectory information on the current situation and provide
a personalized recommendation on locations to users [17]. Manotumruksa et al.
proposed a deep recurrent collaborative filtering framework (DRCF) to utilize
the location of users who are similar in the historical trajectory to assist
the next location prediction. More recently, researchers proposed the CNN-
based method and gated network under the RNN-based framework to extract both
long-term and short-term preferences of users [19, 20].

Figure 1: An illustration of next location prediction.

Although the prediction accuracy has been gradually improved in the fore-
mentioned literature, predicting the mobility behavior of large number of
users in complex urban environments is still significantly challenging. On one
hand, existing studies focused on modeling the mobility patterns at individual
level. The collective pattern of the interaction between the population and
the space is not clearly modeled in these methods. In the early studies,
statistical physicists used historical movement data to discover the
collective pattern of humans. For example, Schneider et al. [21] found that
more than 90% of residents’ mobile behavior conformed to one of 17 basic
network modes (Motif). Alessandretti et al. [22] found that the number of
places visited repeatedly by individuals is stable, revealing people’s stable
social relations. These studies suggest that statistical physical
characteristics are valuable for studying the movement trend of human group
level.

On the other hand, existing methods for next location prediction usually
cascade the embedding of user ID with the latent vector of locations in the
long-term historical and recent trajectories to capture the user’s
personalized preferences [23, 24, 25]. While users have various preferences to
different locations, these methods can not directly model such heterogeneity
and dynamic change of the preferences. Targeting this weakness, researchers
introduced attention mechanism to learn the personalized preference of each
user [26]. However, users’ mobility pattern in space and time is not fully
explored from their trajectory sequences. In specific, they focus mainly on
exploiting the sequential patterns of user personalised preferences without
considering the associated timestamps and geographic information that reflect
the collective mobility patterns. Therefore, how to reasonably use trajectory
data to learn user’s personalized preferences is also the main content of our
research.

Figure 2: The overall framework of our model.

To this end, we propose a novel personalized and group preference guided
network (PG2Net) to tackle the above issues. The framework is devised to
predict each user’s next place to visit via considering her preferences to
various locations at both individual and collective level. Fig. 1 illustrates
the end-to-end procedure of our learning-based model. PG2Net first learns
users’ personalized features, as well as the group characteristics from the
training data, and integrates the urban information into the prediction
module. In the testing phase, the well-trained model is used to predict the
next location given their current trajectories. Specifically, we consider
several key factors that impact the collective mobility behavior, including
geographic environment, distance attenuation, and individual spatial activity
characteristics. Among them, the geographic environment determines the spatial
distribution of potential visit locations which users can reach; the distance
attenuation indicates the relationship between user’s visit frequency and
distance; the individual spatial activity characteristics reflect people’s
potential life habits. Considering the above factors, we design a module that
combines prior statistical information and recurrent neural network, namely,
the dynamic spatio-temporal dependency module, which can learn the influence
of group preferences on users’ mobile patterns. For learning personalized
preferences of each user, we propose a module based on bidirectional long
short-term memory networks (Bi-LSTM) [27] and an attention mechanism to
capture her dynamic preference. Besides, we propose a novel graph embedding
method to represent each location and its categories, which can efficiently
learn the sequential relation between visited places. It should be mentioned
that most previous studies did not take category information into account. In
our model, we attempt to use category information to construct a statistical
model to study the characteristics of user group activities. Finally, we
propose a novel auxiliary loss function to learn the vectorial representation
of the target location and improve the prediction accuracy. The network
structure is shown in Fig. 2.

Our contributions are summarized as follows:

  1. (1)

We propose a PG2Net framework to learn the user’s personalized preferences and
group preferences and predict the next place to visit. PG2Net framework
consists of two parts: (i) dynamic spatio-temporal dependency module that
leverages temporal and spatial information to model the group preferences of
users; (ii) personalized preference module that uses Bi-LSTM and attention
mechanism to capture users’ personalized preferences.

  2. (2)

For seeking more efficient hypothesis space for location embedding, we devise
an auxiliary loss to enhance the similarity between the representations of the
predicted and actual next locations. Consequently, the final loss function is
designed to increase the probability of the actual location and decrease the
distance between the predicted and actual locations in the hypothesis space.

  3. (3)

We design a group preference module in PG2Net to model the people’s collective
preferences to variant locations during long-term and short-term periods.
PG2Net captures the long-term and short-term preferences via integrating the
prior statistical knowledge of people’s mobility behavior with the encoding of
historical and recent trajectories, respectively.

  4. (4)

We conduct extensive experiments on three real-world datasets in different
countries, including two public check-in datasets and a mobile phone dataset,
a.k.a. call detail records (CDRs). Experiments show that our model achieves
significant improvements over the state-of-the-art methods.

##  2 Related Work

The purpose of the next location prediction task is to recommend a set of
ranked locations for users, where the highest-ranking is the predicted value
of the next location. At present, there are two types of methods for this task
– conventional (non-deep learning) machine learning-based methods and deep
learning-based methods [17].

###  2.1 Conventional machine learning-based methods

The trajectory prediction task needs to mine the users’ past trajectory
information to predict where the users will go. Typically, for this sequence
prediction task, we can use a method based on the Markov model and its
variants to make predictions. The Markov-based method is mainly to calculate
the transition matrix of the location. According to transition matrix, we can
predict where the user will go next. For example, Rendle et al. [14] proposed
the factorized personalized Markov chains (FPMC), which is a method applying
personalized Markov and matrix factorization to learn users’ transition matrix
and overall preference. Cheng et al. [28] proposed a method FPMC-LR to obtain
users’ personalized preference and realize the prediction of the next
location. Excepted for Markov-based model, Alhasoun et al. utilized
information from similar strangers for next place Prediction [13]. In this
model, they proposed several human mobility similarity metrics used to
identify other users with similar mobility characteristics, and proposed
dynamic Bayesian network (DBN) model that incorporates the mobility patterns
of similar strangers towards better predicting next locations.

###  2.2 Deep learning-based methods

In recent years, deep learning has developed rapidly. Especially, RNN-based
methods have attracted increasing attention and been successfully applied to
many sequential problems, such as natural language processing, voice
recognition, image annotation, and machine translation. So far, researchers
have tried to use the RNN-based method for travel information prediction and
achieve inspiring results [29, 17, 30, 20, 31]. For example, Liu et al. [29]
proposed the ST-RNN network, which takes users’ adjacent time and space
information as the input of the RNN module to capture the spatio-temporal
influence. Yao et al. [32] established a recursive model of semantic
perception (SERM), which learned the embedding of multiple factors (user,
location, time) and captured the time and spatial transition regularity of
semantic perception.

Recently, the attention mechanism has been widely used in various fields. Feng
et al. [17] proposed a model named DeepMove based on attention mechanism and
recurrent neural network to capture human mobility. In DeepMove, a multi-
module embedding method is adopted to convert sparse features (user, location,
time) into a dense representation, and then the historical attention module is
used to obtain the most relevant historical trajectory information. However,
this method fails to capture the user’s dynamic personalized preferences and
barely considers the temporal and spatial dependence of the actual users. Gao
et al. [33] proposed a variation-attention-based next location prediction
model to overcome the sparsity problem of trajectory data. Wu et al. [26]
proposed a model named PLSPL to learn the specific preference for each user.
This method attempts to model category information to predict the next
location, but the method does not consider the specific regularities of human
mobility and the sequence interaction influences. At present, the latest model
for predicting the next location is the LSTPM model proposed by [20], which
uses context-aware non-local network and geo-dilated RNN to obtain users’
long-term and short-term preferences respectively.

Figure 3: Personalized Preference Modeling.

##  3 Problem Formulation

We define userset=$\\{U_{1},U_{2},U_{3},...,U_{n}\\}$ as a set of LBSN users,
and locationset=$\\{l_{1},l_{2},l_{3},...,l_{m}\\}$ as a set of trajectories,
each of which is geocoded by a (longitude, latitude) tuple representing urban
information. Each user contains a large number of trajectories. Taking user
$U_{1}$ as an example,
$\\{l_{2}^{U_{1}},l_{5}^{U_{1}},l_{4}^{U_{1}},...,l_{k}^{U_{1}}\\}$ represents
all trajectory data of $U_{1}$ in a period. Because each trajectory
corresponds to a category $c_{i}$ and a timestamp $t_{i}$, it can be expressed
as $\\{q_{1},q_{2},q_{3},...,q_{k}\\}$, where $q_{i}$ contains three
attributes $(l_{i},c_{i},t_{i})$. Then we divide each user’s trajectories into
multiple sub-trajectories in order, for example,
$\\{S_{1}^{U_{1}},S_{2}^{U_{1}},S_{3}^{U_{1}},...,S_{j}^{U_{1}}\\}$ is the
trajectory sequence of ${U_{1}}$, where
$\\{S_{1}^{U_{1}},S_{2}^{U_{1}},S_{3}^{U_{1}},...,S_{j-1}^{U_{1}}\\}$ is his
historical trajectory sequence and $S_{j}$ is his recent trajectory. $S_{j}$
can be expressed as $\\{q_{1},q_{2},q_{3},...,q_{t-1}\\}$, where $q_{t-1}$ has
three attributes $(l_{t-1},c_{t-1},t_{t-1})$, and represents recent situation.
$l_{t-1}$ is the location that $U_{1}$ has been recently visited. The purpose
of this paper is to study the influence of historical trajectories and recent
trajectories on the current situation $q_{t-1}$, and predict the top-N of the
possible locations of $U_{1}$ at the next timestamp $t$.

##  4 Our model

In this part, we propose our PG2Net model. We begin with an overview, before
zooming into the details.

###  4.1 Overview

The overall framework of PG2Net is depicted in Fig. 2. Our PG2Net
characterizes the user’s preference to various places at both personalized and
group level, and fuses them into a unified framework. Specially, we learn the
personalized preference of user U from his historical trajectory
$\\{S_{1}^{U},S_{2}^{U},S_{3}^{U},...,S_{j-1}^{U}\\}$, which contains longer
trajectory data reflecting the general preference of U. And different users
have different preferences for the same location. Thus we use user-location
attention to learn the latent vectors of user U and location $l_{i}$. Firstly,
we learn the latent vectors for user U and POI $q_{i}$ (which contains
location $l_{i}$, category $c_{i}$, and timestamp $t_{i}$) in the multi-modal
trajectory embedding module. Then we use Bi-LSTM to learn the historical
trajectory’s transition relationship, and we compute the important $a_{i}$ of
each POI $q_{i}$ to users. Finally, we integrate the sequence information of
POIs to present the user’s personalized preference.

As human’s decision of moving is impacted by her periodic lifestyle and recent
travel behavior, we use historical trajectory to capture her lifestyle while
recent trajectory to capture instant decision. Specifically, we firstly learn
the latent vectors for $S_{j}^{U}=\\{q_{1},q_{2},q_{3},...,q_{t-1}\\}$ in the
embedding layer, where $q_{i}$ contains the location $l_{i}$, category
$c_{i}$, and timestamp $t_{i}$. To better understand user’s check-in
behaviors, we feed the concatenated embeddings of $(l_{i},c_{i},t_{i})$ into
Long Short-Term Memory (LSTM). Then we use a statistical spatio-temporal
physical module to model a user’s historical trajectory and recent trajectory
to learn his group preferences. Finally, concat layer is used to combine the
outputs of the personalized preference, long and short-term group preference
and feed them into the output layer to generate the final probabilities of
candidate locations. It is a remarkable fact that we proposed a novel graph
embedding method to learn the latent vectors of locations and categories. At
the same time, in the output layer, we propose an auxiliary loss function to
supervise the vectorial representation of the next location and improve the
prediction accuracy.

###  4.2 Multi-modal Trajectory Embedding Module

Trajectory sequence usually contains a large amount of human mobility
information. Due to the mobile device or the user itself, the trajectory
sequence has strong sparseness. Targeting this weakness, we use sequence
embedding for this kind of data. For example, in check-in sequence, it
contains four different types of attributes, namely user ID, timestamp,
location, and location category. We will adopt different embedding methods for
these different types of attributes in trajectory sequences.

user ID and timestamp. The original user ID and timestamp cannot be directly
inputted into the model. We refer to the embedding method mentioned in [17,
34] for these two attributes. As each timestamp $t_{i}$ is continuous, which
is difficult to embed, we map it into discrete hours. Firstly, we divide one
week into 48 slots, where 0-23 slots represent weekdays, and 24-47 represent
weekends. Then each hour is represented as a one-hot 48-dimensional vector,
where the non-zero entry denotes the index for the hour. Because one-hot
encoding can’t reflect the correlation between sequences, we transform them
into $D_{t}$ dimensional dense vectors and represent them as $\bm{{\rm
V}}^{t}\in{\bm{{\rm R}}^{48\times{D_{t}}}}$. For a user ID sequence, we
utilize the same embedding method to map it into a dense vector, the dimension
of which is $D_{u}$. The embedding vector is represented as $\bm{{\rm
V}}^{u}\in{\bm{{\rm R}}^{N\times{D_{u}}}}$.

location and location category. In recent years, graph embedding (also known
as network embedding) has been applied to many graph related research areas,
such as text classification [35], detecting an anomaly in financial networks
or social networks [36, 37], etc. The task of our paper is to predict the
user’s next location, and all potential locations that the user could reach
can construct a graph. Therefore, we attempt to adopt a graph embedding method
to learn the location representation. Firstly, we use the training dataset to
construct a directed weighted graph, where the direction is sequential, and
weight refers to the frequency of the two consecutively visited locations.
Then we use the graph embedding method node2vec [38] to map each location into
a low dimensional vector, the dimension of which is $D_{l}$. The embedding
vector is represented as $\bm{{\rm V}}^{l}\in{\bm{{\rm R}}^{M\times{D_{l}}}}$.
We adopt the same embedding method for the location category sequence. The
embedding vector is represented as $\bm{{\rm V}}^{c}\in{\bm{{\rm
R}}^{K\times{D_{c}}}}$, the dimension of which is $D_{c}$ . Through this
method, we can capture the characteristics of group mobility patterns and
location interaction. In the following network training, location and location
category embedding will no longer be trained.

The embedding of each POI (which contains location, location category, and the
timestamp) can be represented as:

$\bm{{\rm E}}_{i}=[\bm{{\rm V}}_{i}^{l}\oplus{\bm{{\rm
V}}_{i}^{t}}\oplus{\bm{{\rm V}}_{i}^{c}}]$ (1)

where $\oplus{}$ denotes concatenation, $\bm{{\rm E}}_{i}$ represents the
latent vector for each POI. Different from [17, 20] which only learn the
latent vector of location, we further consider the context information such as
the category of location and the check-in time.

###  4.3 Personalized Preference Modeling

When modeling personalized preferences, an intuitive idea is to learn each
user’s location preference. Motivated by this, we propose a user-location
attention structure followed by Bi-LSTM to learn the latent representation
$\bm{{\rm P}}_{u}$ of the target user’s personalized preference. As shown in
Fig. 3, we firstly embed all POIs in each historical trajectory
$S_{h}\in\\{S_{1},S_{2},S_{3},...,S_{j-1}\\}$, and user embedding into a low-
dimensional vector for a user U. Then a Bi-LSTM layer is used to learn each
POI’s high-level representation and sequential dependency. Finally, we compute
the importance $\bm{{\rm a}}_{i}$ of each POI $q_{i}$ to users and integrate
the sequence information of POIs to present the user’s personalized
preference.

To capture the user’s high-level representations and sequential dependencies
of different locations, it is beneficial to learn future trajectories as well
as past context. Different from [17], which used RNN-based variant network
LSTM process sequences in sequence order and ignore future context, the Bi-
LSTM network can exploit information both from the past and the future. This
is important to learn user’s personalized preferences.

The calculation process of user’s personalized preferences can be summarized
as follows:

$\mathop{\bm{{\rm h}}_{i}}\limits^{\rightarrow}=LSTM(\bm{{\rm
E}}_{i},{\mathop{\bm{{\rm h}}}\limits^{\rightarrow}}_{i-1}),i\in{S_{h}}$ (2)

$\mathop{\bm{{\rm h}}_{i}}\limits^{\leftarrow}=LSTM(\bm{{\rm
E}}_{i},{\mathop{\bm{{\rm h}}}\limits^{\leftarrow}}_{i-1}),i\in{S_{h}}$ (3)

$\bm{{\rm h}}_{i}=[\mathop{\bm{{\rm
h}}_{i}}\limits^{\rightarrow}\oplus{\mathop{\bm{{\rm
h}}_{i}}\limits^{\leftarrow}}]$ (4)

$\bm{{\rm a}}_{i}=\frac{exp(\bm{{\rm h}}_{i}^{T}\bm{{\rm
V}}^{u})}{\Sigma^{k}_{i=1}{exp(\bm{{\rm h}}_{i}^{T}\bm{{\rm V}}^{u})}}$ (5)

$\bm{{\rm P}}_{i}=\Sigma{\bm{{\rm a}}_{i}\bm{{\rm h}}_{i}}$ (6)

where $\bm{{\rm V}}^{u}$ represents the user’s latent vector, $\oplus{}$
denotes concatenation representing the combination of the forward and backward
outputs, $\bm{{\rm h}}_{i}$ represents the hidden information of the user’s
historical trajectory, $\bm{{\rm a}}_{i}$ denotes the importance of each POI,
$\bm{{\rm P}}_{u}$ is the final representation of personalized preferences of
a user U.

Figure 4: Dynamic Spatio-Temporal Dependency Modeling.

###  4.4 Group Preference Modeling

When predicting the user’s next location, her personalized preferences can
reflect the user’s general preference. However, the user’s interest in the
next trajectory not only follows her personalized preference but also is
affected by the group behavior pattern. At the same time, the user’s
preference for the next location changes dynamically with time and space.
Therefore, we use trajectory data to construct a statistical physical model
named dynamic spatio-temporal dependency module, which uses time and spatial
information to model user’s group preferences and realizes the prediction of
the next location. See Fig. 4 for the illustration of the proposed model. The
dynamic spatio-temporal dependency module is comprised of three parts: the
dynamic spatial dependency module, the dynamic time dependency module, and the
dynamic activity preference module.

Figure 5: The statistical analysis of the distance factors on users’ spatial
preference. Represents the distance distribution between the adjacent location
in the three datasets.

Dynamic spatial dependency module. Generally, the distance between geographic
locations has a great impact on the user’s next location prediction [20]. The
statistical analysis of the distance between adjacent locations is shown in
Fig. 5. We can observe that the user’s travel patterns completely follow the
distance attenuation rule of group mobility. And the higher the cost of long-
distance travel, the lower the probability people choose it. That is to say,
users tend to visit nearby locations. Based on this observation, this paper
proposes a dynamic spatial dependency module to characterize the changing
spatial preferences of users when they move. The module can understand the
user’s dynamic interest in geographic locations, rather than her preference is
fixed over time [39]. When we model the distance preference of users, the key
issue is to select the trajectory that has the greatest impact on the recent
situation from the history trajectories based on the distance among different
locations. Specifically, we firstly generate a geo-distance matrix based on
the real-world geographic locations and the historical trajectory data, whose
values represent the distance between any locations. Then we generate the
weight vector between the recent situation and the historical trajectory based
on the distance matrix as follows,

$\alpha(l_{c},l_{h})=\frac{exp^{1/d(l_{c},l_{k})}}{\Sigma^{n}_{k=1}exp^{1/d(l_{c},l_{k})}}$
(7)

where $d(l_{c},l_{k})$ is the distance between $l_{c}$ and $l_{k}$. Finally,
we utilize the above generated weight vector to integrate the sequence
information of POIs.

Specifically, for the recent situation $q_{i-1}$ of a user, we first learn its
latent embedding vector before modeling spatial preference. Considering that
the historical and recent trajectory have different influences on the current
situation of users, we utilize geo-distance to model long and short-term
spatial group preference,

$\bm{{\rm P}}^{s}_{L}=\bm{{\rm H}}_{h}\alpha(l_{c},l_{h})^{T}$ (8) $\bm{{\rm
P}}^{s}_{S}=\bm{{\rm H}}_{c}\alpha(l_{c},l_{h})^{T}$ (9)

where $\bm{{\rm H}}_{h}$ and $\bm{{\rm H}}_{c}$ are the outputs of Bi-LSTM and
LSTM respectively, representing historical trajectory and recent trajectory
information. $\bm{{\rm P}}^{s}_{L}$ and $\bm{{\rm P}}^{s}_{S}$ represent long
and short-term spatial group preference of a user.

Figure 6: The visualization of the time-correlation matrix.

Dynamic time dependency module. Traditional methods always consider the
influence of time factors on the next location prediction [17, 26]. However,
these methods simply learn the semantic relationship of the timestamp
sequences and ignore the interaction between the time sequences. For example,
most users are accustomed to eating in the cafeteria at 12:00 and 18:00, and
drinking coffee in a coffee shop at 15:00 and 20:00. For the users, the
location at 12:00 is more related to that at 18:00 rather than 15:00, because
both 12:00 and 18:00 are the user’s mealtime. This reflects some group
regularities in human movement. Moreover, as the user moves, the user’s
location preferences at different timestamps are also dynamically changing.
Therefore, we propose a dynamic time dependency module to capture the
influence of the user’s historical trajectory information on the recent state
in the time dimension.

We first divide one week into 48 slots, where 0-23 slots represent weekdays,
and 24-47 slots represent weekends. We construct a location set to represent
the location preference of each slot. For example,
$T_{i}=(l_{1},l_{3},l_{8},...,l_{N}),i\in{(0,47)}$ means all locations where
the i-th slot appears. Then we calculate the time-correlation matrix. As shown
in Fig. 6, time correlation of any two slots is expressed as follows,

$\Gamma_{i,j}=\frac{\lvert{T_{i}\cap{T_{j}}}\rvert}{\lvert{T_{i}\cup{T_{j}}}\rvert{}}$
(10)

Finally, we generate the weight vector between the recent state and the
historical trajectory based on the time-correlation matrix, and utilize the
weight vector to integrate the sequence information of POIs,

$\alpha{(t_{c},t_{h})}=\frac{exp^{\Gamma_{c,k}}}{\Sigma^{47}_{k=0}exp^{\Gamma_{c,k}}}$
(11)

where $\Gamma_{c,k}$ is the time correlation between c-th and k-th time slots,
$\alpha({t_{c},t_{h}})$ is the weight vector between recent state and the
historical trajectory. Similar to modeling users’ spatial preferences, we
utilize time information to model the long and short-term time group
preference of the user,

$\bm{{\rm P}}^{t}_{L}=\bm{{\rm H}}_{h}\alpha(t_{c},t_{h})^{T}$ (12)

$\bm{{\rm P}}^{t}_{S}=\bm{{\rm H}}_{c}\alpha(t_{c},t_{h})^{T}$ (13)

where $\bm{{\rm P}}^{t}_{L}$ and $\bm{{\rm P}}^{t}_{S}$ represent long-term
and short-term time group preference of the user.

Figure 7: The statistical analysis of location categories in the NYC dataset.

Dynamic activity preference module. Users usually tend to have different
activities at different time. Fig. 7(a) and (b) tell us users more tend to
work and commute on workdays, while (c) and (d) present users are more
inclined to relax on weekends. Users also have different activity preferences
at different time on the same day. Based on this, we propose a framework that
can characterize the user’s activity preference at different time. It is worth
to mention that it is the first time to use graphical representation to define
this problem. We attempt to construct a bipartite graph, of which location
category and time are the two end nodes, while the correlation between them is
the edges of the nodes at both ends. See details in Fig. 8.

Figure 8: Using the bipartite graph to construct the activity preference
matrix.

We define a bipartite graph as $G=(V,E)$, where $V$ is a set containing two
types of vertices: $V=V_{c}\cup{V_{t}}$,
$V=\\{c_{1},c_{2},c_{3},...,c_{n},t_{1},t_{2},t_{3},...t_{m}\\}$.
$E=\\{(c_{i},t_{j},w_{c_{i},t_{j}})\\}$, where the weight of the edge is
$w_{c_{i},t_{j}}$. $w_{c_{i},t_{j}}$ represents the weight of $c_{i}$ at time
$t_{j}$. It is a collection of edges with two different types of vertices at
both ends. The task is to learn the user’s activity preference at each
timestamp. However, it would be expensive to directly iterate over the
bipartite graph. To alleviate this problem, we generate a candidate list of
all activities at each moment, and get the correlation between each timestamp
and all location categories. Then we generate the weight vector between the
recent state and the historical trajectory based on the bipartite graph.

$w_{c_{i},t_{j}}=f(c\wedge{t})$ (14)

$\alpha{(c,t)}=\frac{exp^{w_{c,t}}}{\Sigma^{47}_{t=0}exp^{w_{c,t}}}$ (15)

where $w_{c,t}$ is the weight of activity $c$ at timestamp $t$ in activity
preference bipartite graph. $\alpha({c,t})$ is the weight vector between
recent state and the historical trajectory.

Finally, we utilize the activity preference bipartite graph to model the long
and short-term activity group preference of the user,

$\bm{{\rm P}}^{c}_{L}=\bm{{\rm H}}_{h}\alpha(c,t)^{T}$ (16)

$\bm{{\rm P}}^{c}_{S}=\bm{{\rm H}}_{c}\alpha(c,t)^{T}$ (17)

where $\bm{{\rm P}}^{c}_{L}$ and $\bm{{\rm P}}^{c}_{S}$ represent long and
short-term activity group preference of a user.

Using the dynamic spatio-temporal dependency module, we can capture the
influence of spatio-temporal factors on users’ long and short-term group
preferences, which are represented as follows respectively,

$\bm{{\rm P}}_{L}=\bm{{\rm P}}^{s}_{L}+\bm{{\rm P}}^{t}_{L}+\bm{{\rm
P}}^{c}_{L}$ (18)

$\bm{{\rm P}}_{S}=\bm{{\rm P}}^{s}_{S}+\bm{{\rm P}}^{t}_{S}+\bm{{\rm
P}}^{c}_{S}$ (19)

###  4.5 Multi-supervised Prediction Module

After obtaining the representations for personalized preferences, long and
short-term group preference, we make use of the softmax function to compute
the probability distribution p of the next location as follows:

$\bm{{\rm p}}=softmax(\bm{{\rm W}}_{p}(\bm{{\rm P}}_{u}\oplus{\bm{{\rm
P}}_{L}}\oplus{\bm{{\rm P}}_{S}}\oplus{\bm{{\rm V}}^{u}}))$ (20)

where $\oplus{}$ represents the concatenation of personalized preferences with
long and short-term group preference, $\bm{{\rm W}}_{p}$ is a trainable
matrix. Consequently, the index of the largest probability is used as the
predicted value of the next location. When training the model, we use negative
log likelihood as the loss function. However, in the sequence structure model,
the outputted hidden state can more effectively represent the user’s potential
interest [40]. As a result, in order to improve the network’s prediction
accuracy, we propose an auxiliary loss function to supervise the hidden state
of the user’s target location. Our proposed loss function shown in Fig. 9 is
defined as follows:

$L=\frac{1}{N}(-\Sigma^{N}_{i=1}log(p_{i})+\varepsilon{\Sigma^{N}_{i=1}(v^{l}_{i}-\hat{h_{i}})^{2})})$
(21)

where N represents the numbers of the training set, and $\varepsilon$ is a
hyperparameter. We choose the L2 loss as our auxiliary loss function.
$\varepsilon$ is used to balance the weight of the prediction and auxiliary
loss function. With the help of the auxiliary loss function, the generated
hidden vector can better express the user’s interest and increase the accuracy
of network prediction.

Figure 9: Multi-supervised loss function

##  5 Experiments

In this section, we proceed to evaluate the PG2Net model on three real-world
data (two check-in data and one CDRs data). We compare our proposed approach
with state-of-the-art next location prediction models, and discuss the
experimental results.

###  5.1 Datasets

We evaluate our model on the publicly available Foursquare check-in data
collected from New York City (NYC) and Tokyo (TKY), which are widely used in
related studies. In addition, we leverage CDRs data collected from Shanghai to
evaluate our model. The check-in data contains the anonymized user ID,
location id and its coordinate, location category and timestamp, while CDRs
data contains the anonymized user ID, the base station ID and its coordinate,
and the timestamp. Thus, we remove the embedding of category information when
testing our model on CDRs data. And due to the lack of category information
for CDRs, our model cannot be compared with PLSPL method. The check-in dataset
collected about 10 months records in NYC and TKY via Foursquare from 12 April
2012 to 16 February 2013. Note that the temporal visitors are removed in
check-in datasets via eliminating users those presented for less than two
weeks. The CDRs are collected during March 2014 from 1,000 anonymized users.
Table I presents the details of the three datasets. For the sparse check-in
data, we first filter out the users with less than 10 records. Then, we split
the trajectory of each user into multiple sub-trajectories at an interval of
three days, and merge the two consecutive locations if their time interval is
less than 10 mins. Next, we limit the number of sub-trajectories for each user
to between 5 and 10. Sub-trajectories with less than 5 records are filtered
out, and the sub-trajectories with more than 10 records are further divided
into multiple trajectories. Finally, we use 80% of each users’ trajectories as
the training set and the rest as testing set.

TABLE I: Statistics of the evaluation datasets.

City | # users | # locations | Timespan
---|---|---|---
New York | 1083 | 227420 | 10 months
Tokyo | 2293 | 573703 | 10 months
Shanghai | 1000 | 44476 | 1 months

More information about the three datasets is shown in Fig. 10, where (a)
represents the distribution of the number of trajectories for each user, and
(b) represents the proportion of the number of trajectories in each hour. We
can observe from (a) that the NYC and TKY dataset are more sparse than the
CDRs dataset. And (b) shows the distributions of TKY and CDRs dataset behave
similarly, reflecting similar living habits of the inhabitants in Shanghai and
Tokyo.

Figure 10: the statistical distribution of the number of trajectories in the
check-in data and CDRs data about each user and each hour respectively.

###  5.2 Metrics

For comparing our model with the baselines, we utilize two evaluation
indicators: Recall@K and normalized discounted cumulative gain (NDCG@K).
Recall@K measures whether there is a correct location among the top K
recommended locations. NDCG@K measures the quality of top-K recommended
location list. In this paper, we choose K={1,5,10} for comprehensive
evaluation. The definitions Recall@K and NDCG@K are given as follows,

$Recall@k=\frac{1}{N}\Sigma^{N}_{u=1}\frac{\lvert{S^{k}_{u}}\cap{S^{visited}_{u}}\rvert}{\lvert{S^{visited}_{u}}\rvert}$
(22)
$NDCG@k=\frac{1}{N}\Sigma^{N}_{u=1}\frac{1}{z_{u}}\Sigma^{k}_{j=1}\frac{2^{I(\\{S^{j}_{u}\\}\cap{S^{visited}_{u}})}-1}{log_{2}(j+1)}$
(23)

where $S^{k}_{u}$ denotes the top-k locations recommended for user u,
$S^{visited}_{u}$ represents the list of locations visited in the test set,
$I(\cdot)$ is an index function, $S^{j}_{u}$ represents the j-th location
recommended in $S^{k}_{u}$, $z$ is the maximum value in $DCG@k$, which is a
standardized constant.

###  5.3 Baselines and Settings

To verify the effectiveness of our proposed method, we compare PG2Net with a
classic traditional method and some mainstream deep learning methods:

Markov Chain (MC): It is widely used to predict human trajectories. It builds
a transition matrix based on past trajectories to generate the probability of
future location. In our paper, we use the first-order MC method.

LSTM: A neural network-based model, which is a variant model of the recurrent
neural network, and can efficiently process sequence data.

Deepmove [17]: A neural network model based on the attention mechanism that
leverage each user’s historical and recent trajectory data to learn her
preferences. An attention mechanism is used to capture the correlation between
long-term and short-term trajectory data.

PLSPL [26]: A neural network model to learn the specific preference for each
user, which considers category information into the network for the first
time.

LSTPM [20]: It is the state-of-the-art model for next location prediction,
which uses context-aware non-local network structure and geo-dilated RNN to
capture users’ long and short-term preferences respectively.

For our method, we set the embeddings dimension of users and locations to be
$D^{u}=40$ and $D^{l}=500$ respectively, and set categories to be $D^{c}=50$
and $D^{t}=10$. The dimension of the hidden state is 500. In our model we use
Adam which is a gradient descent optimization algorithm to learn all the
parameters. We set the initial learning rate and weight of regularization to
0.0001 and 1e-5 respectively. In the training process, we adopt the method of
gradient cutting and adjust the learning rate to ensure that the model has the
best performance. We take TKY dataset as an example to show the training
process of the proposed model. See details in Fig. 11. For other baseline
models, we set their parameters to the default values that come with the
original paper.

Figure 11: Loss in train and test process of TKY dataset.

###  5.4 Result and Analysis

TABLE II: Performance comparison with five baselines on three datasets.The
best method is shown in bold.

Datasets | Methods | Rec@1 | Rec@5 | Rec@10 | NDCG@1 | NDCG@5 | NDCG@10
---|---|---|---|---|---|---|---
| Markov | 0.1356 | 0.2732 | 0.3441 | 0.1356 | 0.2078 | 0.2306
| LSTM | 0.1545 | 0.3300 | 0.3860 | 0.1545 | 0.2482 | 0.2665
NYC | DeepMove [17] | 0.1828 | 0.3978 | 0.4678 | 0.1828 | 0.2967 | 0.3195
| PLSPL [26] | 0.1820 | 0.3947 | 0.4753 | 0.1820 | 0.2949 | 0.3210
| LSTPM [20] | 0.1864 | 0.4302 | 0.5230 | 0.1864 | 0.3143 | 0.3446
| PG2Net | 0.2120 | 0.4585 | 0.5326 | 0.2120 | 0.3437 | 0.3679
| Markov | 0.1286 | 0.2500 | 0.3037 | 0.1286 | 0.1929 | 0.2102
| LSTM | 0.1440 | 0.3051 | 0.3650 | 0.1440 | 0.2293 | 0.2488
TKY | DeepMove [17] | 0.1658 | 0.3609 | 0.4526 | 0.1658 | 0.2733 | 0.3034
| PLSPL [26] | 0.1631 | 0.3516 | 0.4294 | 0.1631 | 0.2615 | 0.2867
| LSTPM [20] | 0.1773 | 0.4052 | 0.4917 | 0.1773 | 0.2977 | 0.3258
| PG2Net | 0.1994 | 0.4336 | 0.5105 | 0.1994 | 0.3240 | 0.3490
| Markov | 0.2234 | 0.4715 | 0.5520 | 0.2234 | 0.3549 | 0.3811
| LSTM | 0.2337 | 0.5516 | 0.6724 | 0.2337 | 0.3996 | 0.4390
CDRs | DeepMove [17] | 0.2360 | 0.5724 | 0.6800 | 0.2360 | 0.4126 | 0.4479
| LSTPM [20] | 0.2248 | 0.5742 | 0.7016 | 0.2248 | 0.4047 | 0.4462
| PG2Net | 0.2346 | 0.5981 | 0.7021 | 0.2346 | 0.4262 | 0.4604

The experimental results are reported in Table II. The best results in each
column are highlighted in boldface. It shows that,

(1) The proposed model PG2Net is compared with the baselines on three
datasets, and the overall performance is superior. All the metrics on NYC and
TKY datasets are better than the baseline method. On the CDRs dataset, the
four measurement indicators are better than all comparison methods.
Concretely, for Rec@k on NYC datasets, our method is almost 7.64%-18.85%
higher than Markov, 5.75%-14.66% higher than LSTM, 2.92%-6.48% higher than
DeepMove, 0.96%-2.83% higher than LSTPM. For NDGC@10, our model outperforms
Markov, LSTM, DeepMove, LSTPM by 13.73%, 10.14%, 4.84%, 2.33% respectively.
Our model also shows better performance than other baselines under all metrics
on the TKY dataset. On the CDRs dataset, the DeepMove model performs best on
Rec@1 and NDCG@1, and our model followed. Our model is the best under other
metrics. The quantitative evaluation demonstrates the superior effectiveness
of our method.

(2) Among all the methods, the Markov model has the worst performance compared
with other deep learning methods on the three datasets. This also shows that
the neural network-based method has great advantages compared with the
traditional method.

(3) PLSPL shows better performance than LSTM on all metrics on NYC and TKY
datasets. That is because PLSPL considers the context information such as
category to learn the specific preference for each user. However, it shows
slightly poor performance than DeepMove on NYC and TKY datasets. This
phenomenon can be explained that PLSPL doesn’t gather useful information from
history trajectory based on the current situation.

(4) Among the baseline methods, the LSTPM model performs best in terms of most
metrics, followed by DeepMove. Compared with the DeepMove model, both our
model and the LSTPM model take spatio-temporal factors into consideration,
which strongly illustrates that the importance of considering the user’s time
and spatial factors when predicting the user’s next location.

(5) Although the deep learning method performs well on the check-in datasets,
these methods don’t improve the Rec@1 much when comparing with the Markov
method on the CDRs dataset. We argue this probably be related to the sparsity
of the trajectory data. The check-in datasets are much sparser than CDRs. For
sparse data, deep learning methods can capture high-level semantic information
while the traditional methods may be limited in this.

###  5.5 Comparison of model variants

TABLE III: The performance comparison of next place prediction models on three
datasets.

Datasets | Methods | Rec@1 | Rec@5 | Rec@10 | NDCG@1 | NDCG@5 | NDCG@10
---|---|---|---|---|---|---|---
| PG2Net | 0.2120 | 0.4585 | 0.5326 | 0.2120 | 0.3437 | 0.3679
NYC | GNet | 0.1795 | 0.4304 | 0.5176 | 0.1795 | 0.3116 | 0.3400
| PNet | 0.1851 | 0.4107 | 0.4932 | 0.1851 | 0.3098 | 0.3364
| L-PG2Net | 0.1918 | 0.4245 | 0.5003 | 0.1918 | 0.3159 | 0.3407
| S-PG2Net | 0.2019 | 0.4462 | 0.5227 | 0.2019 | 0.3299 | 0.3550
| PG2Net | 0.1994 | 0.4336 | 0.5105 | 0.1994 | 0.3240 | 0.3490
TKY | GNet | 0.1645 | 0.4103 | 0.4852 | 0.1645 | 0.3065 | 0.3223
| PNet | 0.1782 | 0.3951 | 0.4762 | 0.1782 | 0.3027 | 0.3203
| L-PG2Net | 0.1848 | 0.3997 | 0.4801 | 0.1848 | 0.3099 | 0.3247
| S-PG2Net | 0.1890 | 0.4224 | 0.4981 | 0.1890 | 0.3134 | 0.3379
| PG2Net | 0.2346 | 0.5981 | 0.7021 | 0.2346 | 0.4262 | 0.4604
CDRs | GNet | 0.2302 | 0.5956 | 0.6995 | 0.2302 | 0.4232 | 0.4573
| PNet | 0.2320 | 0.5926 | 0.6954 | 0.2320 | 0.4207 | 0.4545
| L-PG2Net | 0.2325 | 0.5936 | 0.6975 | 0.2325 | 0.4214 | 0.4595
| S-PG2Net | 0.2337 | 0.5970 | 0.6993 | 0.2337 | 0.4229 | 0.4565

In this section, we analyze four variants of PG2Net to further evaluate the
effectiveness of our model. The four variants are shown as follows.

GNet: a variant model which only engages the group preference of users,
containing long-term group preference and short-term group preference.

PNet: a variant model which only engages the personalized preference of users,
removing dynamic spatio-temporal dependency module.

L-PG2Net: a variant model which engages the personalized preference and long-
term group preference of users.

S-PG2Net: a variant model which engages the personalized preference and short-
term group preference of users.

Figure 12: The weight proportion of different parts on three datasets.

The experimental results of the ablation tests are shown in Table III. Our
PG2Net outperforms the four variants. Specifically, (1) PNet performs better
than GNet on Rec@1 and NDCG@1, while GNet performs better on other indicators.
The reason is mainly on that GNet learns the group behavior pattern of all
users. This pattern is generalized and can achieve a rough prediction of the
next trajectory, so it performs better on Rec@5, Rec@10, NDCG@5, NDCG@10,
while has a poor performance on Rec@1 and NDCG@1. For PNet, it can learn the
precise and personalized preference information of each user, so the
performances is better on Rec@1 and NDCG@1. This also shows that GNet and PNet
can respectively achieve accurate and rough predictions of user trajectories.
To further demonstrate the effectiveness of personalized preference and group
preference, we compare the weight proportion of them in predicting the next
location. As shown in Fig. 12, the user’s personalized preference
characteristics have a greater influence on the user trajectory prediction
than the group characteristics. (2) S-PG2Net always performs better than
L-PG2Net. The reason is mainly on that S-PG2Net can better capture user’s
group preferences based on her recent state. It also shows that the recent
trajectory has a greater impact on the current situation. (3) The proposed
model PG2Net, which is the combination of PNet and GNet, achieves the best
performance on all test datasets. It shows that both personalized preference
and group preference have positive impact on the user’s choice of the next
location.

###  5.6 Importance of key components in PG2Net

To better understand the influence of the node2vec embedding method and
auxiliary loss function on network training, we use the NYC dataset to
evaluate the performance of each module. As shown in Fig. 13, PG2Net is our
proposed complete model, PG2Net-Node2vec denotes no graph embedding (node2vec)
to embed user location and location category in the model, and PG2Net-
Auxiliary Loss represents that the influence of the hidden state of the target
location is not considered in the prediction module. Fig. 13 shows that our
complete model performs best, and other variant models have decreased
performance. Among them, the performance of the PG2Net-Auxiliary Loss model
drops the most, with a drop of 2.68% in Rec@5, indicating that the hidden
vector of the target position has a great influence on the prediction accuracy
of the next position. The second is the performance of the PG2Net-Node2vec
model, which shows that graph embedding training on location and location
category can improve model performance.

Figure 13: Analyzing on the impact of node2vec embedding and auxiliary loss

###  5.7 Analysis of spatial distribution of predicted locations

Figure 14: Distance distribution between the current situation and the next
predicted location

To show the ability of our model to predict next locations at different
distances, we examine the distance distribution between the current and the
next predicted locations on the three datasets. For each dataset, we compare
the actual distances with the distances predicted by the LSTM, DeepMove, and
PG2Net respectively. Fig. 14 shows that when the prediction distance is short,
PG2Net has a similar prediction performance with LSTM and DeepMove. While when
performing long-distance prediction, PG2Net outperforms the LSTM and DeepMove
model, and can effectively predict long-distance locations. In addition,
DeepMove always outperforms LSTM on the three datasets. CDRs data can
especially reflect this phenomenon. For the next places locating in less than
20 km, the performance of LSTM and DeepMove is comparable to our model. When
the next places are far away, e.g., over 40 km, the performance of LSTM and
DeepMove gradually deteriorates. For places locating over 80 km, the distance
predicted by the LSTM model has completely deviated from the real distance
distribution, and the performance is the worst, followed by DeepMove. In this
scenario, the distance distribution of the predicted locations by PG2Net
matches well with the empirical data. The reasons are mainly that two
locations at a long distance may be more similar for the recent state. The
LSTM and DeepMove models only learn the sequence relationship of the
trajectory and fails to take into account the user’s personalized
characteristics, the temporal and spatial information that reflects the
regularities of group behavior. This could lead to LSTM and DeepMove model
being unable to distinguish the two locations, resulting in long-distance
jumping of the prediction locations.

##  6 Conclusion and future work

In this paper, we propose a novel end-to-end deep neural network, PG2Net, to
predict the next place to visit via considering users’ preferences to various
locations at both individual and collective level. In the personalized
preference module, we use Bi-LSTM and the attention mechanism to capture the
users’ personalized long-term mobility tendency. In the group preference
module, we use spatio-temporal and categorical information of the visited
places to represent users’ long-term and short-term group preferences. In
addition, we utilize a graph embedding method, node2vec, to capture the
sequential relation of users’ visited locations and propose an auxiliary loss
function to learn the vectorial representation of the target location. The
extensive experimental results on three real-world datasets demonstrate the
effectiveness of our proposed model. In future work, we will model more
heterogeneous information and use graph neural networks to learn the
interaction between them to further improve the next POI recommendation
performance.

## Acknowledgments

This work was jointly supported by the Shanghai Municipal Science and
Technology Major Project (2021SHZDZX0102), the Science and Technology
Commission of Shanghai Municipality Project (2051102600), and the National Key
Research and Development Program of China (2020YFC2008701).

## References

  * [1] Z. Zhang, C. Li, Z. Wu, A. Sun, D. Ye, and X. Luo, “Next: a neural network framework for next poi recommendation,” _Frontiers of Computer Science_ , vol. 14, no. 2, pp. 314–333, 2020.
  * [2] Y. Xu, R. Di Clemente, and M. C. González, “Understanding vehicular routing behavior with location-based service data,” _EPJ Data Science_ , vol. 10, no. 1, pp. 1–17, 2021.
  * [3] M. C. Gonzalez, C. A. Hidalgo, and A.-L. Barabasi, “Understanding individual human mobility patterns,” _nature_ , vol. 453, no. 7196, pp. 779–782, 2008\.
  * [4] S. Jiang, Y. Yang, S. Gupta, D. Veneziano, S. Athavale, and M. C. González, “The timegeo modeling framework for urban mobility without travel surveys,” _Proceedings of the National Academy of Sciences_ , vol. 113, no. 37, pp. E5370–E5378, 2016.
  * [5] C. Song, Z. Qu, N. Blumm, and A.-L. Barabási, “Limits of predictability in human mobility,” _Science_ , vol. 327, no. 5968, pp. 1018–1021, 2010.
  * [6] S. Çolak, A. Lima, and M. C. González, “Understanding congested travel in urban areas,” _Nature Communications_ , vol. 7, no. 1, pp. 1–8, 2016.
  * [7] Y. Xu and M. C. González, “Collective benefits in traffic during mega events via the use of information technologies,” _Journal of The Royal Society Interface_ , vol. 14, no. 129, p. 20161041, 2017.
  * [8] L. E. Olmos, S. Çolak, S. Shafiei, M. Saberi, and M. C. González, “Macroscopic dynamics and the collapse of urban traffic,” _Proceedings of the National Academy of Sciences_ , vol. 115, no. 50, pp. 12 654–12 661, 2018\.
  * [9] Y. Xu, S. Jiang, R. Li, J. Zhang, J. Zhao, S. Abbar, and M. C. González, “Unraveling environmental justice in ambient PM2.5 exposure in Beijing: A big data approach,” _Computers, Environment and Urban Systems_ , vol. 75, pp. 12–21, 2019.
  * [10] Y. Xu, S. Çolak, E. C. Kara, S. J. Moura, and M. C. González, “Planning for electric vehicle needs by coupling charging profiles with urban mobility,” _Nature Energy_ , vol. 3, pp. 484–493, 2018.
  * [11] M. Tizzoni, P. Bajardi, A. Decuyper, G. K. K. King, C. M. Schneider, V. Blondel, Z. Smoreda, M. C. González, and V. Colizza, “On the use of human mobility proxies for modeling epidemics,” _PLoS Comput Biol_ , vol. 10, no. 7, p. e1003716, 2014.
  * [12] S. Chang, E. Pierson, P. W. Koh, J. Gerardin, B. Redbird, D. Grusky, and J. Leskovec, “Mobility network models of covid-19 explain inequities and inform reopening,” _Nature_ , pp. 1–8, 2020.
  * [13] F. Alhasoun, M. Alhazzani, F. Aleissa, R. Alnasser, and M. González, “City scale next place prediction from sparse data through similar strangers,” in _Proceedings of ACM KDD Workshop_ , 2017, pp. 191–196.
  * [14] S. Rendle, C. Freudenthaler, and L. Schmidt-Thieme, “Factorizing personalized markov chains for next-basket recommendation,” in _Proceedings of the 19th international conference on world wide web_ , 2010, pp. 811–820.
  * [15] Y. Wu, K. Li, G. Zhao, and X. Qian, “Long-and short-term preference learning for next poi recommendation,” in _Proceedings of the 28th ACM international conference on information and knowledge management_ , 2019, pp. 2301–2304.
  * [16] J. Jiang, S. Tao, D. Lian, Z. Huang, and E. Chen, “Predicting human mobility with self-attention and feature interaction,” in _Asia-Pacific Web (APWeb) and Web-Age Information Management (WAIM) Joint International Conference on Web and Big Data_. Springer, 2020, pp. 117–131.
  * [17] J. Feng, Y. Li, C. Zhang, F. Sun, F. Meng, A. Guo, and D. Jin, “Deepmove: Predicting human mobility with attentional recurrent networks,” in _Proceedings of the 2018 world wide web conference_ , 2018, pp. 1459–1468.
  * [18] J. Manotumruksa, C. Macdonald, and I. Ounis, “A deep recurrent collaborative filtering framework for venue recommendation,” in _Proceedings of the 2017 ACM on Conference on Information and Knowledge Management_ , 2017, pp. 1429–1438.
  * [19] J. Chen, J. Li, and Y. Li, “Predicting human mobility via long short-term patterns,” _Computer Modeling in Engineering & Sciences_, vol. 124, no. 3, pp. 847–864, 2020.
  * [20] K. Sun, T. Qian, T. Chen, Y. Liang, Q. V. H. Nguyen, and H. Yin, “Where to go next: Modeling long-and short-term user preferences for point-of-interest recommendation,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, no. 01, 2020, pp. 214–221.
  * [21] C. M. Schneider, V. Belik, T. Couronné, Z. Smoreda, and M. C. González, “Unravelling daily human mobility motifs,” _Journal of The Royal Society Interface_ , vol. 10, no. 84, p. 20130246, 2013.
  * [22] L. Alessandretti, P. Sapiezynski, V. Sekara, S. Lehmann, and A. Baronchelli, “Evidence for a conserved quantity in human mobility,” _Nature human behaviour_ , vol. 2, no. 7, pp. 485–491, 2018.
  * [23] Q. Guo, Z. Sun, J. Zhang, and Y.-L. Theng, “An attentional recurrent neural network for personalized next location recommendation,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, no. 01, 2020, pp. 83–90.
  * [24] D. Lian, Y. Wu, Y. Ge, X. Xie, and E. Chen, “Geography-aware sequential location recommendation,” in _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2020, pp. 2009–2019.
  * [25] W. Liang and W. Zhang, “Learning social relations and spatiotemporal trajectories for next check-in inference,” _IEEE Transactions on Neural Networks and Learning Systems_ , 2020.
  * [26] Y. Wu, K. Li, G. Zhao, and Q. Xueming, “Personalized long-and short-term preference learning for next poi recommendation,” _IEEE Transactions on Knowledge and Data Engineering_ , 2020.
  * [27] Z. Huang, W. Xu, and K. Yu, “Bidirectional lstm-crf models for sequence tagging,” _arXiv preprint arXiv:1508.01991_ , 2015.
  * [28] C. Cheng, H. Yang, M. R. Lyu, and I. King, “Where you like to go next: Successive point-of-interest recommendation,” in _Twenty-Third international joint conference on Artificial Intelligence_ , 2013.
  * [29] Q. Liu, S. Wu, L. Wang, and T. Tan, “Predicting the next location: A recurrent model with spatial and temporal contexts,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 30, no. 1, 2016.
  * [30] W. Lan, Y. Xu, and B. Zhao, “Travel time estimation without road networks: an urban morphological layout representation approach,” in _Twenty-Eighth International Joint Conferences on Artifical Intelligence (IJCAI)_ , 2019, pp. 1772–1778.
  * [31] P. Zhao, A. Luo, Y. Liu, F. Zhuang, J. Xu, Z. Li, V. S. Sheng, and X. Zhou, “Where to go next: A spatio-temporal gated network for next poi recommendation,” _IEEE Transactions on Knowledge and Data Engineering_ , 2020\.
  * [32] D. Yao, C. Zhang, J. Huang, and J. Bi, “Serm: A recurrent model for next location prediction in semantic trajectories,” in _Proceedings of the 2017 ACM on Conference on Information and Knowledge Management_ , 2017, pp. 2411–2414.
  * [33] Q. Gao, F. Zhou, G. Trajcevski, K. Zhang, T. Zhong, and F. Zhang, “Predicting human mobility via variational attention,” in _The World Wide Web Conference_ , 2019, pp. 2750–2756.
  * [34] J. Chen, J. Li, M. Ahmed, J. Pang, M. Lu, and X. Sun, “Next location prediction with a graph convolutional network based on a seq2seq framework,” _KSII Transactions on Internet and Information Systems (TIIS)_ , vol. 14, no. 5, pp. 1909–1928, 2020.
  * [35] Z. Lu, P. Du, and J.-Y. Nie, “Vgcn-bert: augmenting bert with graph embedding for text classification,” in _European Conference on Information Retrieval_. Springer, 2020, pp. 369–382.
  * [36] A. Khazane, J. Rider, M. Serpe, A. Gogoglou, K. Hines, C. B. Bruss, and R. Serpe, “Deeptrax: Embedding graphs of financial transactions,” in _2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA)_. IEEE, 2019, pp. 126–133.
  * [37] K. Ding, J. Li, R. Bhanushali, and H. Liu, “Deep anomaly detection on attributed networks,” in _Proceedings of the 2019 SIAM International Conference on Data Mining_. SIAM, 2019, pp. 594–602.
  * [38] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2016, pp. 855–864.
  * [39] R. Zhang, J. Guo, H. Jiang, P. Xie, and C. Wang, “Multi-task learning for location prediction with deep multi-model ensembles,” in _2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems (HPCC/SmartCity/DSS)_. IEEE, 2019, pp. 1093–1100.
  * [40] G. Zhou, N. Mou, Y. Fan, Q. Pi, W. Bian, C. Zhou, X. Zhu, and K. Gai, “Deep interest evolution network for click-through rate prediction,” in _Proceedings of the AAAI conference on artificial intelligence_ , vol. 33, no. 01, 2019, pp. 5941–5948.


# A Machine Learning-based Digital Twin for Electric Vehicle Battery Modeling

Khaled Sidahmed Sidahmed Alamin1, Yukai Chen1, Enrico Macii2, Massimo
Poncino1, Sara Vinco1 1Department of Control and Computer Engineering,
Politecnico di Torino, Turin, Italy
2Interuniversity Department of Regional and Urban Studies and Planning,
Politecnico di Torino, Turin, Italy  Email<EMAIL_ADDRESS>
###### Abstract

The widespread adoption of EVs is limited by their reliance on batteries with
presently low energy and power densities compared to liquid fuels and are
subject to aging and performance deterioration over time. For this reason,
monitoring the battery state of charge and state of health during the EV
lifetime is a very relevant problem. This work proposes the structure of a
battery digital twin designed to reflect battery dynamics at the run time
accurately. To ensure a high degree of correctness concerning non-linear
phenomena, the digital twin relies on data-driven models trained on traces of
battery evolution over time: a state of health model, repeatedly executed to
estimate the degradation of maximum battery capacity, and a state of charge
model, retrained periodically to reflect the impact of aging. The proposed
digital twin structure will be exemplified on a public dataset to motivate its
adoption and prove its effectiveness, with a high degree of accuracy and
inference and retraining times compatible with onboard execution.

©2022 IEEE. Personal use of this material is permitted. Permission from IEEE
must be obtained for all other uses, in any current or future media, including
reprinting/republishing this material for advertising or promotional purposes,
creating new collective works, for resale or redistribution to servers or
lists, or reuse of any copyrighted component of this work in other works.
Accepted as a conference paper at the 2022 IEEE International Conference on
Omni-Layer Intelligent Systems (COINS).

##  I Introduction

Since General Motors sold the first Electric Vehicle (EV) in 1996, the market
of EVs has experienced explosive growth, and in the past five years, global
electric car sales have more than quadrupled [1]. This dramatic growth is an
effect of both environmental and economic considerations, that lead
governments to lower CO2 emissions standards and to implement increased
subsidy schemes for EVs as part of stimulus packages to counter the effects of
the pandemic [2]. However, the effectiveness of EVs is limited by their
reliance on batteries that have presently low energy and power densities
compared to liquid fuels and are subject to aging and performance
deterioration over time [3].

To partially overcome these limitations, EVs are usually powered by Lithium-
ion batteries that have high power and energy density and long cycle life
compared to other chemistry compositions [3]. Nonetheless, battery management
is critical to enhancing safety, reliability, and performance. In particular,
accurate estimation of battery _State of Charge (SOC)_ and _State of Health
(SOH)_ is crucial to deliver essential information about battery charge and
aging level, which can be used to perform maintenance or adapt management
strategies to improve performance and reliability (Figure 1) [4].

Unfortunately, both metrics must reflect complex non-linear battery dynamics,
and modern Battery Management Systems (BMS) require knowledge of historical
data of battery usage that can not be quickly processed onboard in real-time.
For this reason, _battery digital twins_ have been introduced, aiming at
building an accurate run time model of the SOC and SOH metrics to provide
accurate battery capacity degradation assessment and relevant information to
the BMS [4]. This is achieved through a combination of Internet of Things
communication protocols, cloud/edge computation, and machine learning
applications that jointly achieve an exponential increase in data storage and
computation capability [4, 5].

Figure 1:  Representation of battery SOH ans SOC metrics: SoH quantifies
battery capacity degradation and impacts on the estimation of SOC.

The main ingredient of a digital twin is a model of the process/system under
monitoring, in this case, the relevant battery SOH and SOC dynamics: the model
is used as a reference for the process under analysis to detect any
misalignment or unexpected behavior, and to foresee the future evolution. In
the literature, many battery models have been proposed, ranging from
electrochemical models to circuit-equivalent models [6]. Machine learning
techniques are becoming increasingly popular for battery SOC and SOH
estimation [7]. Finding a balance between modeling accuracy, model
responsiveness, sensitivity to battery evolution, and the architectural
constraint imposed by the EV scenario is far from trivial. Additionally, as
clarified by Figure 1, SOH and SOC are tightly interleaved: charge and
discharge cycles affect battery SOH, which reduces maximum total charge
capacity and the corresponding estimation of battery SOC. This implies that
the SOH and SOC models can not be built independently and that the SOC
dynamics must be aware of the status of the SOH metrics.

This paper discusses the challenges posed by the construction of a battery
digital twin, and _proposes a custom architecture of models for SOC and SOH to
propose a viable solution for an accurate estimation of battery dynamics and
aging effects_. In detail:

  * •

the digital twin provides a model of SOH built on historical data, that is
trained once on data of a complete charge cycle;

  * •

the model of the SOC is heavily affected by aging: for this reason, the
digital twin features a model of SOC that is retrained periodically on the
cloud on data uploaded from the EV. The model is then run either on the cloud
(to have higher performance) or on the EV (to provide the accurate estimation
to the onboard BMS);

  * •

the paper discusses the edge/cloud architecture, even if discussing the
details of the digital twin infrastructure (edge/cloud, protocols, etc.) is
out of the scope of this paper and will be part of future work;

  * •

we apply the proposed solution to model to a public dataset provided by NASA
Ames Research Centre [8], to motivate its adoption, prove the effectiveness of
the proposed solution in modeling Lithium-ion batteries, and provide
implementations of the SOC and SOH models.

The paper is organized as follows. Section II provides the necessary
background on battery dynamics and digital twins. Section III presents the
proposed solution, with a strong focus on the digital twin architecture and on
how to reproduce effectively the interconnection between SOH and SOC. Section
IV applies the digital twin concept to the NASA Ames Research Centre dataset,
and finally Section V draws our concluding remarks.

##  II Background

###  II-A Battery Dynamics

Lithium-ion batteries store and supply electric power based on the movement of
Li-ions between anode and cathode. Some irreversible reactions happening
during the repeated charges and discharges cycles (such as Li planting and
growth of solid electrolyte interface) cause performance degradation over
time, generating issues in terms of reduced available capacity and/or
increased internal resistance [9].

_State of Charge (SOC)_ estimation is a relevant metric that measures the
percentage of remaining capacity relative to the maximum capacity of the
battery. To provide robust estimates, equivalent circuit models are used that
achieve good approximation but require detailed physical knowledge of Li-ion
batteries. The complementary approach uses data-based models that reconstruct
the evolution of battery SOC given curves of, e.g., current, voltage and
temperature. Many solutions have been proposed in the literature, using e.g.,
support vector machines [10, 11] and neural networks [12, 13, 14, 15]. The
main issue of these approaches is that _they build a once-for-all model of SOC
that is applied throughout the battery lifetime, thus missing the impact of
aging on the internal evolution of battery._ This is especially critical as
one of the major impacts of aging is a reduction in battery available maximum
capacity, which impacts battery SOC calculation.

Tracking age-dependent changes in battery dynamics is thus necessary to
maintain accurate estimates of the remaining lifetime of the battery. In this
perspective, _State of Health (SOH)_ is a metric that measures the condition
of a battery compared to its ideal conditions and is typically estimated as
the ratio of the aged and rated capacity of the battery. SOH is not an
observable quantity and is non-linearly dependent on several factors,
including charge and discharge profiles, average SOC, and ambient temperature
[16]. Given the difficulty in modeling the underlying electrochemical
processes, most approaches estimate SOH models with data-driven methods,
ranging from genetic algorithms to learning- and neural network-based
algorithms [5, 17].

###  II-B Digital Twins for Battery Management

A digital twin is a virtual representation that serves as the real-time
digital counterpart of a physical object or process. In the case of batteries,
digital twins are now being used to complement BMS with high computation power
and data storage capability, reliability, and accuracy [18]. Works at state of
the art differ in terms of adopted battery model. Circuit-equivalent models
(e.g., the Thevenin model) are complicated to characterize and may even
require experimental measurements to ensure a reasonable degree of correctness
[4]. Algorithmic approaches such as genetic algorithms and particle swarm
optimization are characterized by low convergence and are computationally
expensive, thus not allowing to provide estimations at run time during EV
lifetime [5]. Data analytic strategies (like machine learning, support vector
machines, and neural networks) overcome these issues by self-learning
parameters from historical data. However, they are trained at the beginning of
battery lifetime and thus tend to diverge from the actual aged battery along
its lifetime [19, 10, 11, 12, 13, 14, 15, 20]. In this direction, an
interesting strategy has been proposed by [4], which proposes to periodically
influence the SOC model with updated SOH information, to improve prediction
accuracy. This solution improves prediction accuracy by better reflecting the
impact of aging on internal battery dynamics. However, this work adopts the
classic H-infinity filter and particle swarm optimization techniques for SOC
and SOH estimation, and they require a cumbersome parameter identification
process every time SOC and SOH estimation is performed. Moreover, the
H-infinity filter for SOC estimation is fixed all the time, only leveraging
the SOH value to affect the adaptive process in the filter.

##  III A Digital Twin for Battery Monitoring

The proposed digital twin of the EV battery storage system focuses on SOC and
SOH estimation as the most significant parameters that affect EV’s driving
experience and battery life.

###  III-A Models for Battery SOC and SOH

Figure 2 shows the conceptual diagram of our proposed model. The horizontal
arrow represents battery lifetime, from nominal conditions (SOH = 100%) to the
point when the battery is considered no longer usable (SOH = 80%). The battery
icons represent two different classes of models:

  * •

A model of SOH (on top of the arrow), built once for all on historical data
and run throughout the whole lifetime of the battery;

  * •

A model of SOC (below the arrow) that is periodically updated to reflect the
impact of SOH on the estimation of full battery charge and thus of SOC. The
multiple icons reflect the fact that different SOC models are used by the
digital twin to estimate the battery SOC in different battery operation time
intervals: the model at $T_{i}$ shown in Figure 2 represents the latest
retrained SOC model adapted to the battery conditions at the $i_{th}$ time
interval.

Figure 2: Conceptual diagram of the EV battery digital twin: the arrow is
battery lifetime, the icon on top represents the SOH data-driven model, while
the icons below the arrow represent the SOC data-driven models that are
retrained periodically during battery lifetime.

Both models are data-driven in the sense that they are built based on data
traces. It is important to note that any machine learning-based solution can
be used to build the battery SOC and SOH models [7]. The battery SOH model is
built once for all from historical data of an aging battery of the same type
as the one installed on the vehicle. The battery SOC model is initially built
on historical data of nominal battery conditions and is then retrained on data
sampled from the vehicle during its operation. Two mechanisms can trigger the
update of the SOC model: a fixed period or a decrease of SOH by a specific
value.

The reason for such a static SOH model combined with a dynamic SOC model
design is that the SOH of the battery from 100% to 80% represents the aging of
the total available capacitance over the entire operating life cycle of the
battery, where the only relationship that changes is that the total available
capacitance decreases with the time of use. On the other hand, the SOC model
should be constantly updated because the discharge characteristics of the
battery are different under different SOH conditions. More specifically, the
battery impedance and battery maximum capacity change as SOH decreases;
furthermore, the relationship between SOC and battery open-circuit voltage
during discharge differs under different SOH conditions [21].

###  III-B Digital Twin Architecture and Operation

Figure 3 illustrates more details about how to construct our proposed digital
twin and its working mechanism. The diagram shows that our proposed digital
twin has two main components, the cloud side and the EV edge side:

  * •

The cloud is used to deploy and run the SOH model, and to periodically retrain
the SOC model;

  * •

The edge node on the vehicle is used to collect and periodically upload data
to the cloud for SOC model retraining, and of running the updated SOC models;
this choice allows the vehicle BMS to be constantly aware of batter SOC
estimation.

Figure 3: Methodology to implement EV battery digital twin.

The specific steps related to the number shown in the Figure 3 for
constructing our proposed digital twin and how it works during operation are
described below.

  * •

Step 1: offline training of the SOH model using machine learning techniques on
historical measurements of an aged battery; training of the initial SOC model
by using a discharge trace of a brand new battery (at nominal battery
conditions);

  * •

Step 2: the EV continuously collects online charge and discharge measurements
data (i.e., samples of voltage, current, temperature, relative discharge and
charge time of the battery) and uploads them to the cloud;

  * •

Step 3: the SOC model is executed on edge in the EV to compute SOC estimation,
and the SOH model deployed in the cloud leverages the latest uploaded battery
measurements to compute the updated SOH;

  * •

Step 4: when the pre-defined conditions for retraining the SOC model are met
(e.g., SOH reduced by 1%, or fixed time interval elapsed), the cloud uses the
updated measurement data of the battery to retrain the SOC model;

  * •

Step 5: the retrained SOC model is transferred from the cloud to the EV edge
node;

  * •

Step 6: the EV edge node updates the deployed SOC model and goes back to step
2 to execute the following steps repeatedly.

##  IV Experiments

The goal of the proposed solution is not to propose a complete description of
the digital twin, but to rather discuss the effectiveness of the proposed SOC-
SOH models organization in the context of battery digital twin construction.
For this reason, determining the optimal machine learning algorithms or the
optimal cloud/edge architecture is beyond the scope of this work. This section
applies the proposed SOC-SOH model structure to estimate its effectiveness in
reflecting battery dynamics and the impact of aging.

###  IV-A Experiments Setup

####  IV-A1 Dataset Description

The dataset used in this work is a NASA Ames Prognostics Center of Excellence
(PCoE) dataset containing traces of 28 lithium-cobalt-oxide (LCO) 18650
batteries with 2.1Ah nominal capacity and 4.2V rated voltage that were
continuously operated using a sequence of charging and discharging currents at
different temperatures emulating random real-world battery usage [22]. The
dataset contains information about battery current, voltage, temperature,
relative time in each reference discharge and charge cycle, and time during
the whole measurements are tracked for both reference cycles and randomized
cycles (also called Random Walk, RW). Reference charging and discharging
cycles were performed periodically to provide reference points for computing
the battery’s total available capacity, which allows deriving the battery SOH
in different moments of battery lifetime.

####  IV-A2 Data Processing

In this work, we selected 10 out of the 28 battery cells in the dataset,
discarding the cells with malformed data (e.g., too low operating temperature
or nominal capacity). We keep the reference discharge data in the measurements
and remove the random walk portions. For example, after removing all the
random walk cycles, RW9 data contains 79 reference discharge cycles, and RW13
has 22 reference discharge cycles, spanning the entire lifetime of battery
measurements. We adopt all reference discharge data to construct our dataset
in this work because we can use it to build both the SOH and SOC models and
retrain the SOC model when SOH decreases.

Within each reference discharge cycle, we conduct the Coulomb Counting method
to calculate the residual capacity corresponding to each time step in the
discharge phase and compute the total available discharge capacity at the end
of the discharge cycle. Then we convert the residual capacity during one
reference discharge to the corresponding value of SOC and use each reference
discharge’s total available capacity to derive the SOH. Notice that the SOH
value in one discharge cycle keeps constant; it only updates from discharge
cycle to discharge cycle.

####  IV-A3 Motivation of The Adopted Digital Twin Strategy

Figure 4: SOH degradation profile extracted from the RW9 dataset. Arrows
points where the monotonically decreasing nature of SOH is not reflected due
to measurement errors.

Figure 4 indicates the extracted SOH decreasing profile during the whole
lifetime of battery cell RW9, and each dot on the curve corresponds to a value
of SOH computer from a reference discharge for RW9 provided in the dataset.

Each dot in Figure 4 corresponds to a different voltage discharge curve, and
different SOH values imply significant differences in the discharge curve.
Figure 5 exemplifies the discharge voltage curve for the colored points in
Figure 4 (corresponding to SOH 100%, 85% and 65%). The curves reflect that
when SOH decreases, the overall discharge time is shortened due to the
reduction of the total available capacity of the battery. Note that there is
also a change in the downward shape of the overall voltage discharge profile.
All these changes support the idea that it is necessary to retrain the SOC
model, and that a SOC model can not be accurate throughout the whole battery
lifetime.

Figure 5: Voltage profile of reference discharge at different SOH values: a
lower value of SOH leads to a reduction of overall discharge time (due to the
reduction of the total available capacity) and to a change in the downward
shape of the overall voltage discharge profile.

####  IV-A4 Data Cleaning

After computing the SOH value for each reference discharge cycle, it was
possible to identify some irregular cycles break in the monotonic decreasing
nature of SOH due to the measurement errors (e.g., the points highlighted by
the arrows in Figure 4). We removed the erroneous samples from the data traces
for all discharge cycles. For instance, over 79 reference discharge cycles,
RW9 has nine samples with these erroneous behaviors, and they have been
removed from the SOH profile to build the final dataset.

Ultimately, our dataset consists of the following columns, current, voltage,
temperature, relative time, SOC, and SOH; the first four are used as inputs to
train the models in our proposed digital twin, and the last two are used as
outputs of the models.

###  IV-B Machine Learning Techniques Used in This Work

In this work, to perform the SOH and SOC estimation, we have experimented with
different machine learning-based models. Choosing the optimal model
configuration (models types and architectures) is beyond the scope of this
work; the focus of this work is to clarify the architecture of our proposed
digital twin and its operation mechanism, and in our future work, we will
explore the optimal models’ configuration based on different design
requirements. Machine learning methods adopted in this work include:

##### Random Forest (RF)

A RF comprises many decision trees: when performing the classification task,
new input samples enter, and each decision tree in the forest classifies them
separately; the classification results chosen by most decision trees is taken
as the final result [23].

##### Light Gradient Boosting (LGB)

LGB is a gradient learning system based on decision trees and the boosting
concept [24]. It employs a leaf-wise growth approach with depth limitations
and uses histogram-based techniques to speed up the training process and
decrease memory usage.

##### Deep Neural Network (DNN)

The DNN adopted in our work is a feed-forward artificial neural network with
more than one layer of hidden units between its inputs and outputs layers.
Each hidden unit typically employs the logistic function to map its total
input from the layer below to the scalar state that it sends to the layer
above [25]. The neural network architecture used in this experiment is based
on input data connected with seven hidden layers and the output layer with a
linear activation (since it is a regression problem) function.

During the training phase of all the methods mentioned above, the verification
method uses k-fold cross-validation. The SOH and SOC estimation results are
compared based on different models’ accuracy, training time, and inference
time.

###  IV-C SOH Estimation

####  IV-C1 Feature Selection

There is a strong relationship between the relative time discharge time and
the corresponding voltage, current, and temperature values, but most of the
existing work in the literature ignores this feature [7]. In this work, we
found that the inclusion of the relative time feature significantly improved
the accuracy of the models: e.g., RF accuracy (RMSE) of SOH estimation reaches
1.773% when considering the relative time feature, while without the relative
time, it increases to 116.20%.

####  IV-C2 SOH Models Comparison

Table I clearly shows that the RF has the best performance with an RMSE =
1.773%, followed by a slightly worse accuracy of LGB. The performance of the
DNN is worse, with an RMSE = 7.114%. The low accuracy of DNN is due to the
limited size of our training dataset: machine learning generation techniques
to do data augmentation for training the deep learning models may improve the
accuracy. However, our experimental results demonstrate that simple machine
learning techniques, e.g., RF and LGB, are completely capable of estimating
the SOH.

Table I: Different SOH Models Performance Model | Time (T + I) | RMSE(%) | MAE(%)
---|---|---|---
RF | 13.704s + 0.47s | 1.773 | 0.603
LGB | 10.629s + 0.977s | 2.31 | 0.791
DNN | 399.582s + 1.439s | 7.114 | 1.696

Concerning time consumption (T represents training time, and I indicates
inference time), the LGB method took the shortest time to train the model with
only about 11 seconds, followed by the RF, that took approximately 14 seconds.
Although the SOH model in our proposed digital twin is pre-trained offline and
training time is not a decisive factor, too long training time can delay the
deployment of the digital twin. For the comparison of SOH models in terms of
time consumption, inference time is more critical than training time because
this is computed in real-time in the cloud, but inference time of the three
models is comparable (around 1s).

###  IV-D SOC Estimation

####  IV-D1 Feature Selection

The same features used to train the SOH have been used to train the SOC models
after being scaled using Min-Max normalization.

####  IV-D2 SOC Models Comparison

The SOC models investigated in this work show a similar performance as SOH
models. Table II and III show the performance of SOC models trained at the
beginning (SOH=100%) and when the SOH decreases to 70% to conduct the SOC
estimation at the same SOH level. RF and LGB show a high degree of accuracy,
followed by DNN. Furthermore, the training time of DNN is relatively too long
compared to the other two (approx. two orders of magnitude), and such a
training time will weaken the overall performance of the digital twin,
considering that the SOC model in our proposed digital twin architecture is
constantly retrained and updated. Thus, the DNN method is proved to be less
suitable than the others for the digital twin context.

Table II: SOC model performance at SOH = 100% Model | Time (T + I) | RMSE(%) | MAE(%) | Max Err.(%)
---|---|---|---|---
RF | 0.825 + 0.034 | 0.038 | 0.132 | 1.442
LGB | 0.140 + 0.005 | 0.024 | 0.125 | 1.010
DNN | 67.002 + 0.138 | 0.609 | 1.783 | 2.478
Table III: SOC model performance at SOH = 70% Model | Time (T + I) | RMSE(%) | MAE(%) | Max Err.(%)
---|---|---|---|---
RF | 0.622 + 0.017 | 0.809 | 0.624 | 3.873
LGB | 0.097 + 0.005 | 0.599 | 0.549 | 2.993
DNN | 29.97 + 0.068 | 2.775 | 1.380 | 5.071

####  IV-D3 SOC Model Estimation at Different SOH Cases

In this section, we illustrate why the SOC model needs to be retrained
periodically by comparing the results of SOC estimation for the latest trained
SOC model and the outdated SOC models.

Figure 6: SOC discharge profiles comparison among different SOC Random Forest
models trained in different SOH cases.

Figure 6 summarizes the difference in SOC values estimated using the latest
SOC RF model trained based on discharge data with SOH equal to 75% and
outdated SOC models trained based on SOH equal to 100%, 95%, 85%, and 75% when
SOC estimation is performed at the time of SOH = 75%. The solid blue dot line
is the actual SOC discharge profile, and only the green circle line is closest
to it (RMSE of these two lines is only 0.809%, and MAE is 0.624%), which is
the value obtained from the SOC model trained using the discharge data at
SOH=75%. The SOC values obtained with the outdated SOC models are far from the
correct values, and the older the model, the larger the error. This proves
that it is necessary to retrain and update the SOC model periodically.

The first row in the Table IV shows the errors of the SOC estimation at
SOH=75% when using the SOC model trained with SOH=100%, corresponding to the
difference between the orange star line and blue dot line shown in the Figure
6. The other two models also show significant errors due to the use of too
outdated SOC models. In particular, the MAE of DNN increases to 25.315%.
Considering that the range of SOH values is 0% to 100%, and the normal SOH
operating range of the battery is only 80% to 100%, an error of more than 20%
is entirely unacceptable.

Table IV: soc model trained at SOH = 100% used at SOH=75%  Model | RMSE (%) | MAE (%) | Max Error (%)
---|---|---|---
RF | 184.450 | 11.731 | 23.516
LGB | 188.917 | 11.858 | 23.666
DNN | 859.818 | 25.315 | 54.067

##  V Conclusions

This work proposed a digital twin architecture to estimate battery SOH and SOC
during the operation of an EV. The digital twin includes a model of SOH, built
once for all on historical data, and a model of SOC that is periodically
retrained to reflect the internal aging dynamics of the EV battery. The work
focused on proving the impact of the proposed models on the relevance of
preserving the relationship between SOC and SOH, and of adjusting models to
the evolving conditions of a specific EV. The proposed solution has been
exemplified on a public dataset to highlight the motivation experimentally and
to prove its effectiveness in terms of extensibility to a variety of machine
learning data-driven models and compatibility with onboard execution during EV
operation (maximum inference times in the order of 1s, and retraining time for
the SOC model lower than 1s). Future work will discuss the infrastructure
supporting these models, including edge and cloud collaborative framework
considerations.

## References

  * [1] K. Swindells, “The data behind the electric car market’s explosive growth,” 2021\. [Online]. Available: https://elitetraveler.com
  * [2] EV-Volumes, “Global EV sales for 2021,” 2022. [Online]. Available: https://www.ev-volumes.com
  * [3] International Energy Agency, “Technology roadmap – electric and plug-in hybrid vehicles,” 2009. [Online]. Available: https://www.iea.org
  * [4] W. Li, M. Rentemeister, J. Badeda, D. Jost, D. Schulte, and D. U. Sauer, “Digital twin for battery systems: Cloud battery management system with online state-of-charge and state-of-health estimation,” _Journal of Energy Storage_ , vol. 30, p. 101557, 2020.
  * [5] Z. Chen, C. C. Mi, Y. Fu, J. Xu, and X. Gong, “Online battery state of health estimation based on genetic algorithm for electric and hybrid vehicle applications,” _Journal of Power Sources_ , vol. 240, pp. 184–192, 2013\.
  * [6] Y. Chen, E. Macii, and M. Poncino, “A circuit-equivalent battery model accounting for the dependency on load frequency,” in _Design, Automation & Test in Europe Conference & Exhibition (DATE), 2017_. IEEE, 2017, pp. 1177–1182.
  * [7] C. Vidal, P. Malysz, P. Kollmeyer, and A. Emadi, “Machine learning applied to electrified vehicle battery state of charge and state of health estimation: State-of-the-art,” _IEEE Access_ , pp. 52 796–52 814, 2020.
  * [8] B. Saha and K. Goebel, “Battery data set,” Tech. Rep., 2007. [Online]. Available: http://ti.arc.nasa.gov/project/prognostic-data-repository
  * [9] H. Zhang, Q. Miao, X. Zhang, and Z. Liu, “An improved unscented particle filter approach for lithium-ion battery remaining useful life prediction,” _Microelectronics Reliability_ , vol. 81, pp. 288–298, 2018.
  * [10] J. C. Álvarez Antón, P. J. García Nieto, C. Blanco Viejo, and J. A. Vilán Vilán, “Support vector machines used to estimate the battery state of charge,” _IEEE Transactions on Power Electronics_ , vol. 28, no. 12, pp. 5919–5926, 2013.
  * [11] L. Yao, Z. Fang, Y. Xiao, J. Hou, and Z. Fu, “An intelligent fault diagnosis method for lithium battery systems based on grid search support vector machine,” _Energy_ , vol. 214, p. 118866, 2021.
  * [12] W.-Y. Chang, “Estimation of the state of charge for a LFP battery using a hybrid method that combines a RBF neural network, an OLS algorithm and AGA,” _International Journal of Electrical Power & Energy Systems_, vol. 53, pp. 603–611, 2013.
  * [13] W. He, N. Williard, C. Chen, and M. Pecht, “State of charge estimation for Li-ion batteries using neural network modeling and unscented Kalman filter-based error cancellation,” _International Journal of Electrical Power & Energy Systems_, vol. 62, pp. 783–791, 2014.
  * [14] L. Xu, J. Wang, and Q. Chen, “Kalman filtering state of charge estimation for battery management system based on a stochastic fuzzy neural network battery model,” _Energy Conversion and Management_ , vol. 53, no. 1, pp. 33–39, 2012\.
  * [15] X. Tang, K. Liu, X. Wang, F. Gao, J. Macro, and W. D. Widanage, “Model migration neural network for predicting battery aging trajectories,” _IEEE Transactions on Transportation Electrification_ , vol. 6, no. 2, pp. 363–374, 2020.
  * [16] E. Chemali, P. J. Kollmeyer, M. Preindl, Y. Fahmy, and A. Emadi, “A convolutional neural network approach for estimation of Li-Ion battery state of health from charge profiles,” _Energies_ , vol. 15, no. 3, 2022\.
  * [17] X. Sui, S. He, S. B. Vilsen, J. Meng, R. Teodorescu, and D.-I. Stroe, “A review of non-probabilistic machine learning-based state of health estimation techniques for lithium-ion battery,” _Applied Energy_ , vol. 300, p. 117346, 2021.
  * [18] B. Wu, W. D. Widanage, S. Yang, and X. Liu, “Battery digital twins: Perspectives on the fusion of models, data and artificial intelligence for smart battery management systems,” _Energy and AI_ , p. 100016, 2020.
  * [19] E. Chemali, P. J. Kollmeyer, M. Preindl, R. Ahmed, and A. Emadi, “Long short-term memory networks for accurate state-of-charge estimation of Li-ion batteries,” _IEEE Transactions on Industrial Electronics_ , vol. 65, no. 8, pp. 6730–6739, 2018.
  * [20] X. Qu, Y. Song, D. Liu, X. Cui, and Y. Peng, “Lithium-ion battery performance degradation evaluation in dynamic operating conditions based on a digital twin model,” _Microelectronics Reliability_ , vol. 114, p. 113857, 2020.
  * [21] J.-H. Lee and I.-S. Lee, “Lithium battery soh monitoring and an soc estimation algorithm based on the soh result,” _MDPI Energies_ , vol. 14, no. 15, 2021\.
  * [22] B. Bole, C. S. Kulkarni, and M. Daigle, “Adaptation of an electrochemistry-based li-ion battery model to account for deterioration observed under randomized use,” in _Annual Conference of the PHM Society_ , vol. 6, no. 1, 2014.
  * [23] L. Breiman, “Random forests,” _Machine learning_ , vol. 45, no. 1, pp. 5–32, 2001.
  * [24] G. Ke, Q. Meng, T. Finley, T. Wang, W. Chen, W. Ma, Q. Ye, and T.-Y. Liu, “Lightgbm: A highly efficient gradient boosting decision tree,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [25] G. Hinton, L. Deng, D. Yu, G. E. Dahl, and eta, “Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups,” _IEEE Signal Processing Magazine_ , vol. 29, no. 6, pp. 82–97, 2012\.