CN115311860A - An Online Federated Learning Approach for Traffic Flow Prediction Models - Google Patents

Abstract

The invention provides an online federal learning method of a traffic flow prediction model for a traffic control system, which comprises the following steps: d1, updating the traffic flow prediction model of each road side unit for preset times, wherein each updating comprises the following steps: d11, acquiring a traffic flow sequence to be predicted of the current road side unit as the coding input of a traffic flow prediction model of the road side unit to obtain a coding hidden state of the road side unit; d12, the server calculates the spatial relationship between the current road side unit and other road side units, updates the coding hidden state of the current road side unit, and takes the updated coding hidden state as the decoding input of a traffic flow prediction model of the current road side unit to obtain predicted traffic flow; d13, updating the parameters of the traffic flow prediction model of the current road side unit according to the loss between the actual traffic flow and the predicted traffic flow; d2, fusing parameters of all traffic flow prediction models by the server; and D3, issuing the fused model parameters to each road side unit to update the model parameters of each road side unit.

Description

An Online Federated Learning Method for Traffic Flow Prediction Model

technical field

The present invention relates to the field of machine learning, in particular to the field of federated learning in the field of machine learning, and more specifically to an online federated learning method for a traffic flow prediction model.

Background technique

With the vigorous development of the social economy and the increasing number of cars in the country, residents are facing more and more traffic problems when traveling by car. Especially with the improvement of people's living standards, the number of private cars is increasing. How to solve the problem? Drivers provide route planning to avoid traffic jams and reduce commuting time has become an urgent problem to be solved. Route planning is inseparable from accurate traffic flow forecasting. Therefore, good traffic flow forecasting is conducive to providing drivers with reasonable route planning. and ease road traffic congestion.

The methods for predicting traffic flow in the prior art mainly include non-parametric methods and parametric methods, wherein the non-parametric methods mainly refer to KNN (K-Nearest Neighbor, K-Nearest Neighbor), SVM (Support Vector Mechnism, Support vector machine), NN (Neural Network, neural network) and other machine learning methods, the parameterization method mainly refers to the ARIMA (Autoregressive Integrated Moving Average model, integrated moving average autoregressive model) method and its related variants, and these two In the specific processing process of this method, the original traffic flow data collected by all roadside units (RSU, Roadside Unit) in the traffic control system will be uploaded to the cloud server. Among them, in the parametric method, the original traffic flow is assumed to be in a state of stationary distribution, but this will cause the traffic flow predicted by the method to be unable to reflect the actual traffic flow of nonlinear changes. The application in the control system does not work well. Objectively speaking, although these two methods have improved the accuracy of traffic flow prediction in the future to a certain extent, in the actual traffic control system, because all roadside units need to upload their massive original traffic flow data to cloud server for processing, so in the process of uploading the original traffic flow data to the server, there will be problems such as network congestion, transmission delay and the inability to meet the real-time requirements of traffic flow forecasting, and because the data collected by the roadside unit Traffic flow data may contain private information such as license plate numbers and passenger portraits, so when the traffic flow data is directly uploaded to the cloud server for processing, there is still a risk of leaking user privacy information.

The latest method is to predict the traffic flow in the future based on the federated learning architecture. In the federated learning architecture, each roadside unit performs multiple rounds of federated learning under the cooperation of the server to train an overall traffic flow prediction model. In one round of federated learning, each roadside unit saves its original traffic flow data locally to train the traffic flow prediction model corresponding to each roadside unit, and uploads the parameters of the trained traffic flow prediction model to the server at a certain frequency , the server fuses the parameters of the traffic flow prediction models of all roadside units, and then distributes the fused traffic flow prediction models to corresponding roadside units as the initial training model for the next round of federated learning. Although this method protects user privacy and reduces network load by only transmitting the parameters of the traffic flow prediction model to the server, this method uses an offline method to train the traffic flow prediction model, that is, when the traffic flow prediction model When there is heterogeneity between the test set data and the training set data, the trained traffic flow prediction model may not be suitable for the test data. Therefore, in this case, the offline trained traffic flow prediction model has the risk of being retrained. Being retrained would be a huge waste of computing resources.

Contents of the invention

Therefore, the object of the present invention is to overcome the defects of the above-mentioned prior art, and provide an online federated learning method of a traffic flow prediction model that can meet real-time requirements.

The purpose of the present invention is achieved through the following technical solutions:

According to a first aspect of the present invention, there is provided an online federated learning method for a traffic flow prediction model of a traffic control system, the traffic control system includes a server and a plurality of roadside units, wherein each roadside unit is configured with There is a traffic flow prediction model with codec structure, the method includes performing multiple rounds of federated learning on the traffic flow prediction models of all roadside units until the maximum number of rounds is satisfied, wherein each round of federated learning includes: D1, for each The traffic flow prediction model of a roadside unit is updated for a preset number of times, wherein each update includes: D11. Acquiring the traffic flow sequence to be predicted in the road where the current roadside unit is located as the traffic flow prediction model of the current roadside unit Coding input to obtain the coding hidden state of the current roadside unit; D12, the server updates the current roadside unit according to the coding hidden state of the current roadside unit obtained in step D11 and the spatial relationship between the current roadside unit and other roadside units coding hidden state, and use the updated coding hidden state as the decoding input of the traffic flow prediction model of the current roadside unit to obtain the predicted traffic flow corresponding to the traffic flow sequence to be predicted; D13, according to the traffic flow to be predicted The loss between the actual traffic flow corresponding to the sequence and the predicted traffic flow obtained in step D12 updates the parameters of the traffic flow forecasting model of the current roadside unit; D2, the server fuses the parameters of the traffic flow forecasting model of all roadside units to Obtain the fused model; D3. Send the fused model parameters to each roadside unit to update the model parameters of each roadside unit.

In some embodiments of the present invention, in the step D12, the spatial relationship between the current roadside unit and other roadside units is determined in the following manner: based on the geographic location between the current roadside unit and other roadside units , to determine whether there is adjacency between the current RSU and other RSUs, wherein all RSUs adjacent to the current RSU form the adjacency set of the current RSU; based on the coding hidden state of the current RSU, Calculate the degree of association between each roadside unit in the adjacency set of the current roadside unit and the current roadside unit; based on the degree of association between each roadside unit in the adjacency set and the current roadside unit, calculate the current roadside unit The weight relationship between each roadside unit in its adjacency set.

In some embodiments of the present invention, whether there is adjacency between the current roadside unit and other roadside units is judged as follows:

Among them, s _n , s _x represent the nth roadside unit and the xth roadside unit respectively, dist(s _n , s _x ) represents the distance between s _n and s _x , ε, τ ² are two control The hyperparameter of the degree of association, ex _{, n} = 1 means that there is adjacency between the nth roadside unit and the xth roadside unit, e _{x, n} = 0 means that the nth roadside unit and the xth roadside unit There is no adjacency, otherwise means otherwise, and exp means an exponential function with the natural constant e as the base.

In some embodiments of the present invention, the weight relationship between the current roadside unit and each roadside unit in its adjacency set is calculated as follows:

表示在第t轮联邦学习中第n个路侧单元与其邻接集合中第m个路侧单元之间的权重关系，

表示在第t轮联邦学习中采用图注意网络计算的第n个路侧单元与其邻接集合中第m个路侧单元之间的关联程度，

表示在第t轮联邦学习中采用信息几何方式计算的第n个路侧单元与其邻接集合中第m个路侧单元之间的关联程度，

表示

和

之间的权重，N_n表示第n个路侧单元的邻接集合，i表示N_n中第i个路侧单元，

表示在第t轮联邦学习中采用图注意网络计算的第n个路侧单元与其邻接集合中第i个路侧单元之间的关联程度，

表示在第t轮联邦学习中采用信息几何方式计算的第n个路侧单元与其邻接集合中第i个路侧单元之间的关联程度，exp表示以自然常数e为底的指数函数。in,

Indicates the weight relationship between the nth roadside unit and the mth roadside unit in the adjacency set in the t-th round of federated learning,

Indicates the degree of association between the n-th RSU and the m-th RSU in its adjacency set calculated by graph attention network in round t of federated learning,

Indicates the degree of association between the nth roadside unit and the mth roadside unit in the adjacency set calculated by the information geometry method in the t-round federated learning,

express

and

The weight between , N _n represents the adjacency set of the nth roadside unit, i represents the i-th roadside unit in N _n ,

Indicates the degree of association between the n-th RSU and the i-th RSU in its adjacency set calculated by the graph attention network in the t-round federated learning,

Indicates the degree of correlation between the nth roadside unit and the ith roadside unit in the adjacency set calculated by the information geometry method in the t-round federated learning, and exp represents the exponential function with the natural constant e as the base.

In some embodiments of the present invention, in the step D12, the server updates the encoding hidden state of the traffic flow prediction model of the current roadside unit as follows:

表示在第t轮联邦学习中第n个路侧单元与其邻接集合中第m个路侧单元之间的权重关系，sigmoid(·)表示激活函数。Among them, h′ _{t, n} represents the coded hidden state of the traffic flow prediction model of the nth roadside unit in the t-th round of federated learning, N _n represents the adjacency set of the nth roadside unit, and s _m represents the N The m-th roadside unit in _n , h _{t, m} represents the encoding hidden state of the traffic flow prediction model of s _m in the t-th round of federated learning,

Indicates the weight relationship between the nth roadside unit and the mth roadside unit in the adjacency set in the t-th round of federated learning, and sigmoid(·) represents the activation function.

In some embodiments of the present invention, in the step D13, the actual traffic flow corresponding to the traffic flow sequence to be predicted by the current roadside unit and the predicted traffic corresponding to the traffic flow sequence to be predicted by the current roadside unit are calculated as follows Loss between flows:

l _{t, n} (w _{t, n} ) = l _{t, n} (y _{t, n} , y′ _{t, n} ; w _{t, n} )

Among them, l _{t, n} (·) represents the loss function of the nth roadside unit in the t-round federated learning, w _{t, n} represents the traffic flow prediction model of the nth roadside unit in the t-round federated learning , y _{t, n} represents the actual traffic flow corresponding to the traffic flow sequence of the nth roadside unit to be predicted in the t-round federated learning, y′ _{t, n} represents the n-th road in the t-round federated learning The predicted traffic flow corresponding to the to-be-predicted traffic flow sequence of the side unit.

In some embodiments of the present invention, in the step D13, the parameters of the traffic flow prediction model of the current roadside unit are updated as follows:

Among them, w′ _{t, n} represents the updated parameters of the traffic flow prediction model of the nth roadside unit in the t-round federated learning, w _{t, n} represents the parameter of the nth roadside unit in the t-round federated learning The parameters of the traffic flow forecasting model before updating, l _{t, n} represents the loss function of the nth roadside unit in the t-round federated learning, and η represents the learning rate.

In some embodiments of the present invention, in the step D2, model fusion is performed as follows:

When the number of current rounds is less than the cycle length, the fused model is obtained as follows:

Among them, w _t represents the fused model parameters in the t-round federated learning, N represents the number of all roadside units, w′ _{t, n} represents the traffic flow forecast of the nth roadside unit in the t-round federated learning the updated parameters of the model; or

When the number of current rounds is greater than the cycle length, the fused model is obtained as follows:

Among them, w _t represents the fused model parameters in the t-th round of federated learning, T represents the cycle length, w′ _{t, n} represents the updated traffic flow prediction model of the nth roadside unit in the t-th round of federated learning The parameter, α _{tT, n} represents the weight of the updated parameters of the traffic flow prediction model of the nth roadside unit in the fused model in the tT round of federated learning.

According to a second aspect of the present invention, there is provided a system for predicting traffic flow, the system comprising: a plurality of roadside modules, wherein each roadside module comprises: a roadside unit for obtaining information on the road where it is located The traffic flow sequence to be predicted; the traffic flow prediction model trained according to the method described in the first aspect of the present invention is used to predict the corresponding predicted traffic flow based on the traffic flow sequence to be predicted acquired by the roadside unit where it is located.

According to a third aspect of the present invention, a traffic route planning method is provided, the method comprising: T1, obtaining all roads between the user's origin and destination; T2, adopting any one of claims 1-9 The traffic flow prediction model trained by the method predicts the traffic flow of each road between the starting point and the destination; T3, based on the predicted traffic flow, plans the optimal path between the starting point and the destination for the user, and the optimal A path is a path with the least congestion between the origin and the destination.

Compared with the prior art, the present invention has the advantages of:

1. The present invention aims at the problem that the federated learning method in the prior art cannot meet the real-time requirements when predicting traffic flow, and proposes an online federated learning method to train the traffic flow prediction model, which obtains the traffic flow of roadside units in real time Flow data, real-time update of the encoding hidden state of the roadside unit's traffic flow prediction model, and the way of real-time update of the roadside unit's traffic flow prediction model meet the high real-time requirements in the actual traffic environment.

2. The present invention aims at the slow convergence speed of the federated learning method in the prior art when aggregating the global model, by utilizing the spatial correlation between different roadside units and the temporal correlation of traffic flow information of the same roadside unit at different times , to adaptively aggregate the global model, improving the convergence speed.

Description of drawings

Embodiments of the present invention will be further described below with reference to the accompanying drawings, wherein:

Fig. 1 is a traffic control system diagram according to an embodiment of the present invention;

2 is an example diagram of predicting traffic flow data to be predicted for each roadside unit in each round of federated learning according to an embodiment of the present invention;

Fig. 3 is a flow chart of updating the traffic flow prediction model of each roadside unit in each round of federated learning according to an embodiment of the present invention.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail through specific examples below. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.

As mentioned in the background technology, the federated learning method of the prior art is not suitable for the real-time traffic environment when predicting traffic flow, faces the risk of model retraining and wastes computing resources, etc., in order to solve these problems in the prior art Problem, the present invention proposes an online federated learning solution to train the traffic flow prediction model, so that the trained model can meet the real-time requirements of traffic flow prediction.

In order to better understand the present invention, first introduce the basic structure of the traffic control system. As shown in Figure 1, the traffic control system includes a server and multiple roadside units, wherein S1, S2, and S3 represent roadside units, and Y represents a server. The traffic flow data of the road where it is located, and each roadside unit S1, S2, S3 is configured with a traffic flow prediction model with codec structure. According to an embodiment of the present invention, the traffic flow forecasting model of the present invention adopts GRU (Gated Recurrent Unit, gated recurrent unit) model, it should be noted that the method for training the traffic flow forecasting model of the present invention is not limited to training The GRU model can also train other models that also have a codec structure, such as LSTM (Long Short Term Memory, long short-term memory) model, Transformer model, etc. In the prior art, the traffic flow prediction model in the roadside unit is trained by offline federated learning, which has problems such as not being able to meet real-time requirements, facing the risk of model retraining, and wasting computing resources. However, the present invention is The traffic flow prediction model is trained by online federated learning.

The online training process of the traffic flow prediction model of the present invention will be described in detail below in conjunction with the accompanying drawings and embodiments.

Firstly, the main technical idea of the present invention is briefly introduced. In view of the existing problems in the traffic flow prediction of the federated learning method in the prior art, the present invention uses online federated learning to perform multiple rounds of federated learning on the traffic flow prediction models of all roadside units in the traffic control system until the maximum number of rounds is met. Constraints, in each round of federated learning, each roadside unit encodes its own traffic flow to obtain the hidden state, and then each roadside unit transmits the encoded hidden state of its traffic flow prediction model to the server, and is determined by The server updates the coded hidden state corresponding to each roadside unit based on the spatial relationship between the roadside units, and then the server distributes the updated coded hidden state to the corresponding roadside unit for decoding calculation to obtain the traffic flow of the corresponding roadside unit Based on the predicted results of each roadside unit, the corresponding traffic flow forecasting model is updated based on the loss between the traffic flow forecasting result corresponding to each roadside unit and the actual traffic flow. After each roadside unit completes the traffic flow forecasting model update, all roadside units The parameters of the traffic flow prediction model updated by the side unit are transmitted to the server, and the server performs dynamic weighted aggregation, and distributes the aggregated model parameters to each roadside unit to update the traffic flow prediction model of each roadside unit.

In order to better understand the present invention, an example will be used below to illustrate the principle of each round of federated learning. As shown in Figure 2, an example scenario of one server and three RSUs (S1, S2, S3) in a traffic control system is shown, where each RSU is configured with a GRU with an encoder-decoder structure Model. Since each roadside unit performs the same steps in each round of federated learning, for the convenience of description, only the roadside unit S1 is used to introduce the relevant process below. First, the roadside unit S1 uses its traffic flow sequence to be predicted as a GRU model The encoder input for encoding calculation, the encoder outputs the encoded hidden state of the GRU model, and transmits the encoded hidden state of the GRU model to the server. Next, the server updates the encoding hidden state of the GRU model based on the spatial relationship between RSU S1 and other RSUs, and sends the updated encoding hidden state to the decoder of the GRU model of RSU S1 for decoding calculation The predicted traffic flow corresponding to the traffic flow sequence to be predicted of the roadside unit S1 is obtained. Finally, the GRU model is updated based on the loss between the predicted traffic flow corresponding to the roadside unit S1 and the actual traffic flow. For those of ordinary skill in the art, the working principle of the encoder-decoder in the prior art is usually to directly use the hidden layer state vector of the encoder as the input of the decoder, while the present invention uses the hidden layer state vector of the encoder The state vector is transmitted to the server for updating, and the server's updated hidden layer state vector is sent to the decoder for decoding, so as to achieve the purpose of federated online learning.

According to one embodiment of the present invention, as shown in Figure 3, the step of updating the traffic flow prediction model of the roadside unit in each round of federated learning includes the following stages: obtaining the coding hidden state of the roadside unit, updating the coding hidden state of the server 1. Calculating traffic flow forecasting results, updating traffic flow forecasting models, and server aggregation of all traffic flow forecasting models. The implementation process of each stage in each round of federated learning will be introduced respectively in five aspects according to the process of FIG. 3 and combined with embodiments. Among them, the t-th round of federated learning and the traffic control system including N roadside units are taken as an example to expand the description, and t and N represent natural numbers greater than zero.

1. Obtain the coding hidden state of the roadside unit

N roadside units in the traffic control system are represented by S={s ₁ , s ₂ ,...s _n ,...,s _N }, where S represents the set of all roadside units, and N represents greater than zero A natural number of , Sn represents the nth roadside unit, and n is greater than or equal to 1 and less than or equal to N. For each roadside unit, the present invention obtains the traffic flow sequence to be predicted in the road where the roadside unit is located, and encodes the traffic flow sequence to be predicted as the input of the encoder of the traffic flow prediction model of the roadside unit To obtain the encoded hidden state of the roadside unit's traffic flow prediction model. Preferably, the present invention obtains the encoding hidden state of the traffic flow prediction model of the roadside unit as follows:

h _{t, n} = f _{t, n, e} (x _{t, n} ; w _{t, n, e} )

Among them, h _{t, n} represents the coding hidden state of the traffic flow prediction model of the nth roadside unit in the t-round federated learning, x _{t, n} represents the waiting time of the nth roadside unit in the t-round federated learning Forecast traffic flow sequence, f _{t, n, e} ( ) represents the encoder model function of the nth roadside unit in the t-round federated learning, w _{t, n, e} represents the n-th roadside unit in the t-round federated learning Encoder model parameters of the RSU.

2. The server updates the code hidden state

Using the above method, the present invention obtains the coding hidden states of the traffic flow prediction models of all roadside units, and transmits them to the server, and the server calculates the spatial relationship between each roadside unit and other roadside units and based on the Spatial relationships update the encoded hidden state of the traffic flow prediction model for each roadside unit. It should be pointed out that the spatial relationship here is finally a weight relationship in a series of calculation processes, that is, the weight relationship between each roadside unit and other roadside units. Preferably, the present invention calculates the weight relationship between each roadside unit and other roadside units as follows:

表示在第t轮联邦学习中第n个路侧单元与其邻接集合中第m个路侧单元之间的权重关系，

表示在第t轮联邦学习中采用图注意网络计算的第n个路侧单元与其邻接集合中第m个路侧单元之间的关联程度，

表示在第t轮联邦学习中采用信息几何方式计算的第n个路侧单元与其邻接集合中第m个路侧单元之间的关联程度，N_n表示第n个路侧单元的邻接集合，i表示N_n中第i个路侧单元，

表示在第t轮联邦学习中采用图注意网络计算的第n个路侧单元与其邻接集合中第i个路侧单元之间的关联程度，

表示在第t轮联邦学习中采用信息几何方式计算的第n个路侧单元与其邻接集合中第i个路侧单元之间的关联程度，exp表示以自然常数e为底的指数函数，

表示

和

之间的权重，其值为0.5。需要说明的是，此处

的值不仅限于0.5，可以根据实际交通流量预测的场景设置，本发明不做具体限定。in,

Indicates the weight relationship between the nth roadside unit and the mth roadside unit in the adjacency set in the t-th round of federated learning,

Indicates the degree of association between the n-th RSU and the m-th RSU in its adjacency set calculated by graph attention network in round t of federated learning,

Indicates the degree of association between the nth roadside unit and the mth roadside unit in the adjacency set calculated by the information geometry method in the t-round federated learning, N _n denotes the adjacency set of the nth roadside unit, i Indicates the i-th roadside unit in N _n ,

Indicates the degree of association between the n-th RSU and the i-th RSU in its adjacency set calculated by the graph attention network in the t-round federated learning,

Indicates the degree of association between the nth roadside unit and the i-th roadside unit in the adjacent set calculated by information geometry in the t-round federated learning, exp represents the exponential function with the natural constant e as the base,

express

and

Between the weights, its value is 0.5. It should be noted that here

The value of is not limited to 0.5, and can be set according to the scene of actual traffic flow prediction, which is not specifically limited in the present invention.

的计算公式中，

表示在第t轮联邦学习中采用图注意网络计算的第n个路侧单元与其邻接集合中第m个路侧单元之间的关联程度，需要指出的是，此处的第n个路侧单元泛指任一路侧单元，根据本发明的一个实施例，本发明通过执行步骤A1-A3来计算

下面详细说明

的计算过程：in the above

In the calculation formula,

Indicates the degree of association between the nth roadside unit and the mth roadside unit in the adjacency set calculated by using the graph attention network in the t-th round of federated learning. It should be pointed out that the nth roadside unit here Generally refers to any roadside unit, according to an embodiment of the present invention, the present invention calculates by performing steps A1-A3

Details below

The calculation process:

A1. Based on the geographical location between the current roadside unit and other roadside units, judge whether there is adjacency between the current roadside unit and other roadside units, and all other roadside units adjacent to the current roadside unit form the current roadside unit. The adjacency set of side units, specifically, the present invention judges whether there is adjacency between the current roadside unit and other roadside units in the following manner:

Among them, s _n , s _x represent the nth roadside unit and the xth roadside unit respectively, dist(s _n , s _x ) represents the distance between s _n and s _x , ex _{, n} = 1 represents the There is adjacency between the nth roadside unit and the xth roadside unit, e _{x, n} = 0 means that there is no adjacency between the nth roadside unit and the xth roadside unit, otherwise means otherwise, and exp means the natural constant The exponential function with base e, ε and τ2 are ^two hyperparameters controlling the degree of association, and their values are 0.5 and 10, respectively. It should be noted that the values of ε and τ2 here are not limited to 0.5 and ¹⁰ , and can be set according to the scene of actual traffic flow prediction, which is not specifically limited in the present invention;

A2. Based on the adjacency set of the current RSU obtained in step A1, calculate the correlation between the coding hidden states corresponding to the current RSU and the coding hidden states corresponding to other RSUs in the adjacency set as follows:

用于衡量h_t，n和h_t，m之间的关联性，h_t，n表示在第t轮联邦学习中第n个路侧单元的交通流量预测模型的编码隐藏状态，h_t，m表示在第t轮联邦学习中第n个路侧单元的邻接集合中第m个路侧单元的交通流量预测模型的编码隐藏状态，s_m表示第n个路侧单元的邻接集合中第m个路侧单元，W表示增强隐藏状态特征的矩阵，N_n表示第n个路侧单元的邻接集合，[·||·]表示矩阵的拼接操作，a(·)表示映射函数，其用于将拼接后的矩阵映射为一个常数；in,

Used to measure the correlation between h _t,n and h _t,m , h _t,n represents the encoded hidden state of the traffic flow prediction model of the nth roadside unit in the t-th round of federated learning, h _t,m Indicates the coding hidden state of the traffic flow prediction model of the mth roadside unit in the adjacency set of the nth roadside unit in the t-round federated learning, s _m represents the mth one in the adjacency set of the nth roadside unit Roadside unit, W represents the matrix of enhanced hidden state features, N _n represents the adjacency set of the nth roadside unit, [·||·] represents the splicing operation of the matrix, a(·) represents the mapping function, which is used to The spliced matrix is mapped to a constant;

本发明采用图注意网络计算当前路侧单元与其邻接集合中其他路侧单元之间的关联程度，具体来说，采用图注意网络计算所述关联程度的公式为：A3. Based on the relevance obtained in step A2

In the present invention, the graph attention network is used to calculate the degree of association between the current roadside unit and other roadside units in its adjacency set. Specifically, the formula for calculating the degree of association using the graph attention network is:

表示在第t轮联邦学习中采用图注意网络计算的第n个路侧单元与其邻接集合中第m个路侧单元之间的关联程度，N_n表示第n个路侧单元的邻接集合，i表示N_n中第i个路侧单元，

表示在第t轮联邦学习中第n个路侧单元的交通流量预测模型的编码隐藏状态与N_n中第m个路侧单元的交通流量预测模型的编码隐藏状态之间的关联性，

表示在第t轮联邦学习中第n个路侧单元的交通流量预测模型的编码隐藏状态与Nn中第i个路侧单元的交通流量预测模型的编码隐藏状态之间的关联性，exp表示以自然常数e为底的指数函数，LeakyReLU(·)表示激活函数。in,

Indicates the degree of association between the n-th roadside unit and the m-th roadside unit in the adjacency set calculated by the graph attention network in the t-round federated learning, N _n denotes the adjacency set of the n-th roadside unit, i Indicates the i-th roadside unit in N _n ,

Indicates the correlation between the encoding hidden state of the traffic flow prediction model of the nth roadside unit in the t-round federated learning and the encoding hidden state of the traffic flow prediction model of the mth roadside unit in N _n ,

Indicates the correlation between the coding hidden state of the traffic flow prediction model of the nth roadside unit in the t-round federated learning and the coding hidden state of the traffic flow prediction model of the i-th roadside unit in Nn, exp represents the The natural constant e is an exponential function with the base, and LeakyReLU(·) represents the activation function.

的计算公式中，

表示在第t轮联邦学习中采用信息几何方式计算的第n个路侧单元与其邻接集合中第m个路侧单元之间的关联程度。需要指出的是，此处的第n个路侧单元泛指任一路侧单元。根据本发明的一个实施例，本发明通过执行步骤B1-B3来计算

in the above

In the calculation formula,

Indicates the degree of association between the nth roadside unit and the mth roadside unit in the adjacency set calculated by the information geometry method in the t-round federated learning. It should be pointed out that the nth roadside unit here generally refers to any roadside unit. According to an embodiment of the present invention, the present invention calculates by performing steps B1-B3

B1, assuming that the encoding hidden state of the traffic flow prediction model of the current roadside unit obeys Gaussian distribution, then the present invention will perform unbiased respectively on the mean value and standard deviation of the encoding hidden state of the traffic flow prediction model of the current roadside unit in the following manner estimate:

表示在第t轮联邦学习中第n个路侧单元的交通流量预测模型的编码隐藏状态在维度H中第j维对应的数值，j表示非零自然数，其最大值为维度H对应的数值；Among them, μ _{t, n} represents the mean value of the encoding hidden state of the traffic flow prediction model of the nth roadside unit in the t-round federated learning, σt _{, n} represents the nth roadside unit in the t-round federated learning The standard deviation of the coding hidden state of the traffic flow prediction model, H represents the dimension of the coding hidden state of the traffic flow prediction model of the nth roadside unit in the t-th round of federated learning,

Indicates the value corresponding to the coded hidden state of the traffic flow prediction model of the nth roadside unit in the dimension H in the t-round federated learning, j represents a non-zero natural number, and its maximum value is the value corresponding to the dimension H;

B2. Based on the mean value μ _t,n and standard deviation σ _t,n obtained in step B1, calculate the distance between the coded hidden state corresponding to the current roadside unit and the coded hidden states corresponding to other roadside units in the adjacent set as follows distance:

in,

σ ₁ =σ _t,m −σ _t,n ,

σ ₂ =σ _t,m +σ _t,n ,

μ ₁ = μ _t,m - μ _t,n '

表示h_t，n与h_t，m之间的距离，h_t，n表示在第t轮联邦学习中第n个路侧单元的交通流量预测模型的编码隐藏状态，h_t，m表示在第t轮联邦学习中第n个路侧单元的邻接集合中第m个路侧单元的交通流量预测模型的编码隐藏状态，σ_t，n表示表示在第t轮联邦学习中第n个路侧单元的交通流量预测模型的编码隐藏状态的标准差，σ_t，m表示在第t轮联邦学习中第n个路侧单元的邻接集合中第m个路侧单元的交通流量预测模型的编码隐藏状态的标准差，μ_t，n表示在第t轮联邦学习中第n个路侧单元的交通流量预测模型的编码隐藏状态的均值，μ_t，m表示在第t轮联邦学习中第n个路侧单元的邻接集合中第m个路侧单元的交通流量预测模型的编码隐藏状态的均值，G(·)表示数学函数，σ₁表示σ_t，m与σ_t，n之间的差值，σ₂表示σ_t，m与σ_t，n之间的和值，μ₁表示μ_t，m与μ_t，n之间的差值；

Indicates the distance between h _{t, n} and h _{t, m} , h _{t, n} represents the coding hidden state of the traffic flow prediction model of the nth roadside unit in the t-th round of federated learning, h _{t, m} represents the The encoding hidden state of the traffic flow prediction model of the mth roadside unit in the adjacency set of the nth roadside unit in the t-round federated learning, σ _{t, n} denotes the nth roadside unit in the t-round federated learning The standard deviation of the coding hidden state of the traffic flow prediction model, σ _{t, m} represents the coding hidden state of the traffic flow prediction model of the m-th roadside unit in the adjacency set of the n-th roadside unit in the t-round federated learning The standard deviation of , μ _{t, n} represents the mean value of the encoded hidden state of the traffic flow prediction model of the nth roadside unit in the t-round federated learning, μ _{t, m} represents the n-th road in the t-round federated learning The mean value of the coded hidden state of the traffic flow prediction model of the mth roadside unit in the adjacency set of side units, G(·) represents a mathematical function, σ1 represents the difference between σ _{t ,m} and σ _t,n , σ ₂ represents the sum value between σ _{t, m} and σ _{t, n} , and μ ₁ represents the difference between μ _{t, m} and μ _{t, n} ;

采用信息几何方式计算当前路侧单元与其邻接集合中其他路侧单元之间的关联程度。优选的，采用信息几何方式计算所述关联程度的公式为：B3, based on the distance between h _{t, n} and h _{t, m} obtained in step B2

The information geometry method is used to calculate the correlation degree between the current roadside unit and other roadside units in its adjacency set. Preferably, the formula for calculating the degree of association by means of information geometry is:

in,

表示在第t轮联邦学习中采用信息几何方式计算的第n个路侧单元与其邻接集合中第m个路侧单元之间的关联程度，

表示h_t，n与h_t，m之间的最大距离，h_t，n表示在第t轮联邦学习中第n个路侧单元的交通流量预测模型的编码隐藏状态，h_t，m表示第t轮联邦学习中第n个路侧单元的邻接集合中第m个路侧单元的交通流量预测模型的编码隐藏状态，max(·)表示最大值函数，

表示h_t，n与h_t，m之间的距离，N_n表示第n个路侧单元的邻接集合，i表示N_n中第i个路侧单元，

表示h_t，n与h_t，i之间的距离，h_t，i表示在第t轮联邦学习中第n个路侧单元的邻接集合中第i个路侧单元的交通流量预测模型的编码隐藏状态。

Indicates the degree of association between the nth roadside unit and the mth roadside unit in the adjacency set calculated by the information geometry method in the t-round federated learning,

Indicates the maximum distance between h _{t, n} and h _{t, m} , h _{t, n} represents the coded hidden state of the traffic flow prediction model of the nth roadside unit in the t-th round of federated learning, h _{t, m} represents the The encoding hidden state of the traffic flow prediction model of the m-th roadside unit in the adjacency set of the n-th roadside unit in the t-round federated learning, max( ) represents the maximum value function,

Indicates the distance between h _{t, n} and h _{t, m} , N _n represents the adjacency set of the nth roadside unit, i represents the i-th roadside unit in N _n ,

Indicates the distance between h _t,n and h _t,i , h _t,i represents the encoding of the traffic flow prediction model of the i-th roadside unit in the adjacency set of the n-th roadside unit in the t-round federated learning hidden state.

After the present invention obtains the spatial relationship between each roadside unit and other roadside units, the encoding hidden state of the traffic flow prediction model of each roadside unit is updated as follows:

表示在第t轮联邦学习中第n个路侧单元与其邻接集合中第m个路侧单元之间的权重关系，h_t，m表示在第t轮联邦学习中第n个路侧单元的邻接集合中第m个路侧单元的交通流量预测模型的编码隐藏状态，sigmoid(·)表示激活函数。Among them, h′ _{t, n} represents the coded hidden state of the traffic flow prediction model of the nth roadside unit in the t-th round of federated learning, N _n represents the adjacency set of the nth roadside unit, and s _m represents the The mth roadside unit in the adjacency set of n roadside units,

Indicates the weight relationship between the nth roadside unit and the mth roadside unit in the adjacency set in the t-round federated learning, h _{t, m} represents the adjacency of the n-th roadside unit in the t-round federated learning The encoded hidden state of the traffic flow prediction model for the mth roadside unit in the set, and sigmoid( ) represents the activation function.

3. Calculation of traffic flow forecast results

After the server updates the coded hidden state of the traffic flow prediction model of each roadside unit, the updated coded hidden state is distributed to the corresponding roadside unit for decoding calculation to obtain the traffic flow prediction result corresponding to the corresponding roadside unit, According to one embodiment of the present invention, the present invention calculates the result of the traffic flow prediction of the traffic flow sequence to be predicted for each roadside unit as follows:

y′ _{t, n} = f _{t, n, d} ([h _{t, n} , h′ _{t, n} ]; w _{t, n, d} )

Among them, y′ _{t, n} represents the predicted traffic flow corresponding to the traffic flow sequence of the nth roadside unit to be predicted in the t-th round of federated learning, f _{t, n, d} ( ) represents the predicted traffic flow in the t-th round of federated learning The decoder model function of the nth RSU, w _{t, n, d} represent the decoder model parameters of the nth RSU in the t-round federated learning, h _{t, n} represent the t-round federated learning The encoding hidden state of the traffic flow prediction model of the nth roadside unit, h′ _{t, n} represents the updated encoding hidden state of the traffic flow prediction model of the nth roadside unit in the tth round of federated learning.

4. Update the traffic flow forecasting model

According to an embodiment of the present invention, after each roadside unit obtains its respective predicted traffic flow and actual traffic flow, based on the loss between the traffic flow prediction result corresponding to each roadside unit and the actual traffic flow, this The invention updates the traffic flow prediction model corresponding to each roadside unit by performing steps C1-C2, and the process of steps C1-C2 is described in detail below:

C1, the present invention calculates the loss between the actual traffic flow corresponding to the traffic flow sequence to be predicted of each roadside unit and the predicted traffic flow in the following manner:

l _{t, n} (w _{t, n} ) = l _{t, n} (y _{t, n} , y′ _{t, n} ; w _{t, n} )

Among them, l _{t, n} (·) represents the loss function of the nth roadside unit in the t-round federated learning, Y _{t, n} represents the traffic flow to be predicted by the nth roadside unit in the t-round federated learning The actual traffic flow corresponding to the sequence, y′ _{t, n} represents the predicted traffic flow corresponding to the traffic flow sequence of the nth roadside unit to be predicted in the t-th round of federated learning, w _{t, n} represents the predicted traffic flow in the t-th round of federated learning Parameters of the traffic flow forecasting model for the nth roadside unit. It should be noted that here w _t,n = w _t-1 , that is, the parameters of the traffic flow prediction model of the nth roadside unit in the t-th round of federated learning are fused with the parameters of the t-1th round of federated learning The parameters of the traffic flow forecasting model of all roadside units are the same for the generated fused model.

C2. Based on the loss between the actual traffic flow and the predicted traffic flow corresponding to each roadside unit obtained in step C1, the OGD (Online Gradient Descent, online federated learning) method is used to update the traffic flow of each roadside unit as follows Parameters of the traffic flow forecasting model:

Among them, w′ _{t, n} represents the updated parameters of the traffic flow prediction model of the nth roadside unit in the t-round federated learning, w _{t, n} represents the parameter of the nth roadside unit in the t-round federated learning The parameters of the traffic flow forecasting model before updating, l _{t, n} represent the loss function of the nth roadside unit in the t-th round of federated learning, η represents the learning rate, its value is 0.01, it should be noted that here η The value is not limited to 0.01, and can be set according to the scene of actual traffic flow prediction, which is not specifically limited in the present invention.

According to an embodiment of the present invention, after updating the respective traffic flow prediction models of each roadside unit five times, the parameters of the traffic flow prediction models of all roadside units are uploaded to the server, and the server performs an aggregation operation. It should be noted that, in the process of specific implementation, the number of updates of the traffic flow prediction model may not be limited to 5, and it can be set according to the scene of actual traffic flow prediction, which is not specifically limited in the present invention.

5. The server aggregates all traffic flow forecasting models

After the predetermined times of updating the parameters of the traffic flow prediction models of all roadside units, the present invention uploads the parameters of the traffic flow prediction models of all roadside units to the server for global aggregation and fusion to obtain the fused model , and send the fused model parameters to each roadside unit to update the parameters of the traffic flow prediction model of each roadside unit. According to an embodiment of the present invention, since the traffic flow is periodic, the present invention obtains the corresponding cycle length according to the periodicity of the traffic flow in the road where all roadside units are located, assuming that the cycle length is T, and at the same time judges the current federated learning Whether the number of rounds is less than the cycle length, and the parameters of the traffic flow prediction model of all roadside units are fused as follows:

First, when the current number of federated learning rounds is less than the cycle length, that is, t≤T, the present invention obtains the fused model in the following way:

Among them, w _t represents the fused model parameters in the t-round federated learning, N represents the number of all roadside units, w′ _{t, n} represents the traffic flow forecast of the nth roadside unit in the t-round federated learning The updated parameters of the model.

At the same time, based on the fused model parameters, the present invention calculates the fused model parameters in the t-th round of federated learning and the updated traffic flow prediction model of the nth roadside unit in the t-1 round of federated learning in the following manner: The Euclidean distance between the parameters of :

e _{t-1, n} = ||w′ _{t-1, n} -w _t || ²

Among them, e _{t-1, n} represents the Euclidean relationship between the fused model parameters in the t-th round of federated learning and the updated parameters of the traffic flow prediction model of the nth roadside unit in the t-1 round of federated learning Distance, w′ _{t-1, n} represents the updated parameters of the traffic flow prediction model of the nth roadside unit in the t-1 round of federated learning, w _t represents the fused model parameters in the t-th round of federated learning .

Then, the present invention normalizes the Euclidean distance between the fused model parameters in the t-th round of federated learning and the updated parameters of the traffic flow prediction model of the nth roadside unit in the t-1 round of federated learning Processing:

Among them, α _{t-1, n} represents the weight of the updated parameters of the traffic flow prediction model of the nth roadside unit in the fused model in the t-1 round of federated learning, N represents the maximum number of roadside units, e _{t-1, n} represents the Euclidean distance between the fused model parameters in the t-th round of federated learning and the updated parameters of the traffic flow prediction model of the nth roadside unit in the t-1 round of federated learning, e _{t-1, m} represents the model parameters fused in the t-th round of federated learning and the traffic flow prediction model of the m-th roadside unit in the adjacency set of the n-th roadside unit in the t-1 round of federated learning Euclidean distance between updated parameters.

When the number of current federated learning rounds is greater than the cycle length, that is, t>T, the present invention obtains the fused model in the following way:

Among them, w _t represents the fused model parameters in the t-th round of federated learning, w′ _t,n represents the updated parameters of the traffic flow prediction model of the nth roadside unit in the t-th round of federated learning, α _tT,n represents The weight of the updated parameters of the traffic flow prediction model of the nth roadside unit in the fused model in the tT round of federated learning.

Compared with the prior art, the present invention has the advantages of:

1. The present invention aims at the problem that the federated learning method in the prior art cannot meet the real-time requirements when predicting traffic flow, and proposes an online federated learning method to train the traffic flow prediction model, which obtains the traffic flow of roadside units in real time Flow data, real-time update of the encoding hidden state of the roadside unit's traffic flow prediction model, and the way of real-time update of the roadside unit's traffic flow prediction model meet the high real-time requirements in the actual traffic environment.

2. The present invention aims at the slow convergence speed of the federated learning method in the prior art when aggregating the global model, by utilizing the spatial correlation between different roadside units and the temporal correlation of traffic flow information of the same roadside unit at different times , to adaptively aggregate the global model, improving the convergence speed.

It should be noted that although the steps are described above in a specific order, it does not mean that the steps must be performed in the above specific order. In fact, some of these steps can be performed concurrently, or even change the order, as long as it can be realized The required functions are sufficient.

The present invention can be a system, method and/or computer program product. A computer program product may include a computer readable storage medium having computer readable program instructions thereon for causing a processor to implement various aspects of the present invention.

A computer readable storage medium may be a tangible device that holds and stores instructions for use by an instruction execution device. A computer readable storage medium may include, for example, but is not limited to, electrical storage devices, magnetic storage devices, optical storage devices, electromagnetic storage devices, semiconductor storage devices, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of computer-readable storage media include: portable computer diskettes, hard disks, random access memory (RAM), read-only memory (ROM), erasable programmable read-only memory (EPROM), or flash memory), static random access memory (SRAM), compact disc read only memory (CD-ROM), digital versatile disc (DVD), memory stick, floppy disk, mechanically encoded device, such as a printer with instructions stored thereon A hole card or a raised structure in a groove, and any suitable combination of the above.

Having described various embodiments of the present invention, the foregoing description is exemplary, not exhaustive, and is not limited to the disclosed embodiments. Many modifications and alterations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments. The terminology used herein is chosen to best explain the principle of each embodiment, practical application or technical improvement in the market, or to enable other ordinary skilled in the art to understand each embodiment disclosed herein.

Claims (12)

1. The method is characterized by comprising the following steps of carrying out multi-round federal learning on the traffic flow prediction models of all road side units until a maximum round number constraint condition is met, wherein each round of federal learning comprises the following steps:

d1, updating the traffic flow prediction model of each road side unit for preset times, wherein each updating comprises the following steps:

d11, acquiring a traffic flow sequence to be predicted in a road where the current road side unit is located as the coding input of a traffic flow prediction model of the current road side unit to obtain a coding hidden state of the current road side unit;

d12, the server updates the coding hidden state of the current road side unit according to the coding hidden state of the current road side unit obtained in the step D11 and the spatial relationship between the current road side unit and other road side units, and uses the updated coding hidden state as the decoding input of a traffic flow prediction model of the current road side unit to obtain the predicted traffic flow corresponding to the traffic flow sequence to be predicted;

d13, updating parameters of a traffic flow prediction model of the current road side unit according to the loss between the actual traffic flow corresponding to the traffic flow sequence to be predicted and the predicted traffic flow obtained in the step D12;

d2, fusing the parameters of the traffic flow prediction models of all the road side units by the server to obtain a fused model;

and D3, issuing the fused model parameters to each road side unit to update the model parameters of each road side unit.

2. The method according to claim 1, wherein in step D12, the spatial relationship between the current road side unit and the other road side units is determined by:

judging whether the current road side unit and other road side units have adjacency or not based on the geographic position between the current road side unit and other road side units, wherein all road side units adjacent to the current road side unit form an adjacency set of the current road side unit;

calculating the association degree between each road side unit in the adjacent set of the current road side units and the current road side unit based on the coding hiding state of the current road side unit;

and calculating the weight relation between the current road side unit and each road side unit in the adjacent set thereof based on the association degree between each road side unit in the adjacent set and the current road side unit.

3. The method of claim 2, wherein the determination of whether there is adjacency between the current rsu and other rsus is made as follows:

wherein s is _n 、s _x Respectively, the nth and the xth road side units, dist(s) _n ,s _x ) Denotes s _n And s _x Distance between, ε, τ ² Two hyper-parameters controlling the degree of association, e _x,n =1 indicates that there is adjacency between the nth and the xth rsu, e _x,n =0 indicates that there is no adjacency between the nth and the xth rsu, and otherwise indicates that otherwise, exp indicates an exponential function with a natural constant e as the base.

4. A method according to claim 3, wherein the weight relationship between the current road side unit and each road side unit in its contiguous set is calculated as follows:

wherein,

representing the weight relationship between the nth road side unit and the mth road side unit in the adjacent set in the tth round of federal learning,

indicating the degree of association between the nth road side unit and the mth road side unit in the adjacent set of the nth road side unit calculated by adopting the graph attention network in the t round of federal learning,

representing the degree of association between the nth road side unit and the mth road side unit in the adjacent set of the nth road side unit calculated in the information geometric mode in the t round of federal learning,

to represent

And

weight between, N _n Representing an N-th contiguous set of roadside units, i representing N _n The (i) th roadside unit in (c),

indicating the degree of association between the nth road side unit and the ith road side unit in the adjacent set of the nth road side unit calculated by adopting the graph attention network in the t round of federal learning,

and expressing the degree of association between the nth road side unit and the ith road side unit in the adjacent set of the nth road side unit, which are calculated in the information geometric mode in the t round of federal learning, wherein exp expresses an exponential function with a natural constant e as a base.

5. The method according to claim 4, wherein in step D12, the server updates the coding hidden state of the traffic flow prediction model of the current road side unit as follows:

wherein, h' _t,n Indicating a coded hidden state after updating of the traffic flow prediction model of the nth road side unit in the t round of federal learning, N _n Representing an adjacent set of nth road side units, s _m Represents N _n Middle mth roadside unit, h _t,m Shown in the t-th round of federal learning s _m The encoded hidden state of the traffic flow prediction model of (1),

and (4) representing the weight relation between the nth road side unit and the mth road side unit in the adjacent set in the tth round of federal learning, wherein sigmoid (-) represents an activation function.

6. The method according to claim 5, characterized in that, in said step D13,

calculating the loss between the actual traffic flow corresponding to the traffic flow sequence to be predicted of the current road side unit and the predicted traffic flow corresponding to the traffic flow sequence to be predicted of the current road side unit according to the following modes:

l _t,n (w _t,n )＝l _t,n (y _t,n ,y′ _t,n ；w _t,n )

wherein l _t,n (. The) represents the loss function of the nth RSU in the t round of Federal learning, w _t,n Parameter, y, representing traffic flow prediction model of nth road side unit in the t round of federal learning _t,n Representing actual traffic flow, y 'corresponding to traffic flow sequence to be predicted of nth road side unit in t-th wheel federal learning' _t,n And the predicted traffic flow corresponding to the traffic flow sequence to be predicted of the nth road side unit in the t round of federal learning is shown.

7. The method according to claim 6, wherein in step D13, the parameters of the traffic flow prediction model of the current roadside unit are updated as follows:

wherein, w' _t,n Represents the updated parameter of the traffic flow prediction model of the nth road side unit in the t round of federal learning, w _t,n Denotes a parameter before updating of the traffic flow prediction model of the nth road side unit in the t round of federal learning,/ _t,n The loss function of the nth road side unit in the t round of federal learning is shown, and eta represents the learning rate.

8. The method according to claim 7, characterized in that in step D2, model fusion is performed as follows:

when the number of the current rounds is smaller than the period length, obtaining the fused model in the following mode:

wherein w _t Denotes model parameters fused in the t-th wheel federal learning, N denotes the number of all road-side units, w' _t,n Representing the updated parameters of the traffic flow prediction model of the nth road side unit in the t round of federal learning; or alternatively

When the number of the current rounds is larger than the cycle length, obtaining the fused model in the following mode:

wherein, w _t Represents the model parameters fused in the T-th round of federal learning, T represents the period length, w' _t,n Parameters representing traffic flow prediction model of nth road side unit in t-th round federal learningNumber, alpha _t-T,n And representing the weight of the updated parameters of the traffic flow prediction model of the nth road side unit in the T-T round of federal learning in the fused model.

9. A system for predicting traffic flow, the system comprising: a plurality of roadside modules, wherein each roadside module comprises:

the road side unit is used for acquiring a traffic flow sequence to be predicted in a road where the road side unit is located;

the traffic flow prediction model trained by the method according to any one of claims 1 to 8, which is used for predicting the corresponding predicted traffic flow based on the traffic flow sequence to be predicted acquired by the road side unit where the model is located.

10. A method of traffic path planning, the method comprising:

t1, acquiring all roads between a starting place and a destination of a user;

t2, predicting the traffic flow of each road between the origin and the destination using a traffic flow prediction model trained using the method according to any one of claims 1 to 8;

and T3, planning an optimal path between the departure place and the destination for the user based on the predicted traffic flow, wherein the optimal path is a path with the lowest congestion degree between the departure place and the destination.

11. A computer-readable storage medium, having stored thereon a computer program executable by a processor for performing the steps of the method of any one of claims 1 to 8.

12. An electronic device, comprising:

one or more processors;

storage means for storing one or more programs which, when executed by the one or more processors, cause the electronic device to carry out the steps of the method according to any one of claims 1 to 8.

Images