CN114676909A - A charging path planning method for unmanned vehicles based on deep reinforcement learning - Google Patents

Abstract

The invention designs a path planning method for charging sensor nodes of an unmanned vehicle in a wireless sensor Network by using a deep reinforcement learning model Graph based Pointer Network (GAPN). The process comprises the following steps: (1) collecting each node in wireless sensor network

Position coordinate information of

And its electric quantity condition

(2) Generating a training data set and a testing data set which are distributed the same as the position information of the training data set according to the collected data; (3) using the prepared data set for GAPN model training; (4) and inputting the collected node information into the trained GAPN model, and outputting a final access node sequence through the processing of the model. The method based on deep reinforcement learning and the graph neural network provides a strategy for solving the problem of route planning of the unmanned charging vehicle, improves the working efficiency of the wireless sensor network, and prolongs the life cycle of the network.

Description

A charging path planning method for unmanned vehicles based on deep reinforcement learning

technical field

The invention belongs to the application field of machine learning, and specifically relates to model building and training, and reflects the advantages and disadvantages of the model through the solution effect of practical problems, and particularly relates to a path planning method for unmanned charging vehicles based on deep reinforcement learning.

Background technique

In most wireless sensor networks, each sensor node is fixedly deployed in one location, and supplies electricity through battery equipment or relying on ambient energy, such as wind energy, solar energy, etc., but such energy supply is uncontrollable and unstable The efficiency and stability of wireless sensor networks are also greatly affected, and the life cycle of the network is also greatly reduced.

In order to solve the energy supply problem of traditional wireless sensor networks, the scheme of using mobile devices to supplement the power of sensor nodes has become a research hotspot. Such a charging method is actually proposed based on the idea of mobility nodes. The introduction of mobility nodes can improve the flexibility of the network and provide various tasks in the sensor network, such as sensor node power replenishment, data collection, target tracking and node tracking. Positioning provides new ideas, greatly improves the fault tolerance rate of sensor networks, and prolongs the life cycle of sensor networks. In order to allow the charging vehicle to reasonably select the sensor nodes that need to be supplemented with energy, balance the energy loss between nodes, perform charging tasks more effectively, and avoid the phenomenon of node "death" due to insufficient power in the network, it is necessary to conduct Effective scheduling and reasonable path planning.

The path planning problem is one of the classic combinatorial optimization problems. In recent years, studies have shown that deep learning and reinforcement learning have unique advantages in solving combinatorial optimization problems. The model based on deep reinforcement learning usually transforms the problem into a high-dimensional space, finds and learns the relationship between variables in the high-dimensional space, and combines the processing of the graph structure with the graph neural network to obtain the optimal solution to the problem. This is not possible with traditional operations research methods. Therefore, how to design the frame structure and loss function of the neural network and optimize the training process of the model is the technical difficulty of deep reinforcement learning to solve the combinatorial optimization problem.

SUMMARY OF THE INVENTION

The technical problem to be solved by the present invention is to design a reasonable node charging path planning scheme for charging vehicles under the consideration of node location, power consumption rate, charging rate and node power capacity and other constraints, so as to avoid the nodes in the wireless sensor network. There is a "death phenomenon" caused by insufficient power, and the path cost consumed by unmanned vehicles is minimized, thereby extending the life cycle of wireless sensor networks and improving network availability.

The technical scheme of the present invention is:

The path planning method for unmanned charging vehicles based on deep reinforcement learning includes the following steps:

Step (1) Collect node S= _{ s ₀ , s ₁ , s ₂ , .

Step (2) build a model GAPN based on deep reinforcement learning, including a point encoder, a graph encoder, a decoder and an attention mechanism module;

Step (3) is based on the collected node information data, and generates a training data set and a test data set for training the GAPN model;

Step (4) Set the model training objectives to minimize the node mortality rate and minimize the path cost of the charging vehicle, define the loss function, and use the reinforcement learning actor-critic algorithm to train the GAPN to obtain the final model;

Step (5) Input the information of nodes S={s ₀ , s ₁ , s ₂ ,...,s _n } in the wireless sensor network into the GAPN model, and the model returns the scheme π={s ₀ for the charging vehicle to visit all nodes ,s′ ₁ ,s′ ₂ ,…,s′ _n }, where π is the reordering of S;

Step (6) utilizes a heuristic clustering method combined with GAPN to solve the path planning problem in multiple charging vehicle scenarios, that is, when the wireless sensor network has multiple charging vehicles, a scheme for scheduling charging vehicles and planning charging vehicle paths;

Step (7) Modify the graph topology embedding module of the model, and use the model generalization to solve the large-scale traveling salesman problem, that is, the model is trained on the small-scale traveling salesman problem dataset, and then the model is used to solve large The Traveling Salesman Problem in Scale Scenarios.

The present invention is further preferred, and the actor-critic algorithm used in step (4) is specifically:

Step 4.1: Build an actor network and a critic network based on the GAPN network structure. θ represents the actor network parameters, and θ _v represents the critic network parameters. The difference between the two networks is that the actor network uses average sampling in the decoding process. The critic network Adopt greedy sampling strategy;

Step 4.2: A batch of training data set X, with a total of B data, for each data set instance _xi , the current actor network is used to solve the final path cost L(π _i | _xi ), and the critic network is used to solve its baseline expectation value

critic网络策略梯度

Step 4.3: Use the values obtained in step 4.2 to perform two network batch policy gradient calculations, and the actor network policy gradient g _θ calculation:

critic network policy gradient

其中lr为学习率；Step 4.4: Use the gradient descent method to update the parameters of the two networks respectively. The update rules are: θ=θ+lr*g _θ ,

where lr is the learning rate;

Step 4.5: Repeat steps 4.2 to 4.4 T times, where T is the training algebra set before training.

In addition, the present invention also proposes a solution to the large-scale traveling salesman problem by using the model generalization. At present, to solve the large-scale traveling salesman problem, such as the problem of 500, 1000 or more nodes, the time cost of training the model with the same size data set is relatively high. The encoding method is modified, and the adjacency matrix of the point set is used as the input of the graph neural network, so that the model can be trained using the dataset of small-scale problems, and then used to solve the scene of large-scale problems.

The present invention is further preferred, and proposes a solution for path planning in the scenario of multiple charging vehicles, as shown in FIG. 2 , that is, when the wireless sensor network has multiple charging vehicles, the scheme of scheduling charging vehicles and planning the path of charging vehicles . The existing m charging vehicles are used to solve the charging problem of the wireless sensor network node set S, and the steps are as follows:

The specific heuristic clustering algorithm used in step (6) is as follows: (1) Using the heuristic clustering algorithm to divide the node set S into m subsets, which are respectively handed over to m charging vehicles for charging.

(2) For the m task subsets, the trained GAPN models are used for processing, and the respective charging path schemes of m charging vehicles are obtained.

Step 6.1: Define m subsets R={S ₁ , S ₂ ,..., S _m } to store the nodes to be visited by each charging vehicle; define e(S _j ) as the sum of the urgency of all nodes in S _j and;

从大到小排序；Step 6.2: For the input wireless sensor network node set S, according to the initial urgency of the node

Sort from largest to smallest;

Step 6.3: first put the first m nodes in the node set S into m subsets S ₁ , S ₂ ,..., S _m respectively;

Step 6.4: First sort the set R in the ascending order of e(S _j ), traverse the remaining nodes in the set S, and for the currently traversed node _si , if there is no node _sk and node _si in S _j to open If the time difference Ri _,k is greater than the travel time Γ _i,k , or the deadline difference _Di,k is smaller than the travel time Γ _i,k , then put _si into S _j , otherwise replace another subset until condition is satisfied;

Step 6.5: Obtain the final m subsets R={S ₁ , S ₂ , . . . , S _m }, which are used for the execution of m charging vehicle tasks.

The beneficial effects of the present invention are:

In the scenario of charging nodes in a wireless sensor network, a good charging scheduling scheme is crucial for the power replenishment of mobile charging vehicles; the present invention considers the power consumption rate of nodes, charging rate of charging vehicles and path cost Due to other constraints, a decision-making model based on deep reinforcement learning was invented to provide a better charging path scheme for mobile charging vehicles to extend the life cycle of wireless sensor networks.

Description of drawings

FIG. 1 is a schematic diagram of solving a path planning problem by a deep learning model proposed by the present invention.

FIG. 2 is a schematic diagram of a solution to the problem of path planning for multiple charging vehicles proposed by the present invention.

FIG. 3 is a schematic diagram of a frame structure of the present invention applied to an actual system.

FIG. 4 is a mobile intelligent body charging vehicle to which the present invention is actually applied.

Figure 5 is a line drawing of the mobile intelligent charging vehicle designed in Figure 4;

FIG. 6 is a flow chart of the steps of the present invention.

Detailed ways

The present invention will be further clarified below with reference to the accompanying drawings and specific embodiments. It should be understood that the following specific embodiments are only used to illustrate the present invention and not to limit the scope of the present invention. It should be noted that the words "front", "rear", "left", "right", "upper" and "lower" used in the following description refer to the directions in the drawings, and the words "inner" and "outer" ” refer to directions towards or away from the geometric center of a particular part, respectively.

As shown in Figures 1 and 6, this embodiment proposes a schematic diagram of a deep learning model to solve the path planning problem. The input data contains the data information of all nodes, and the final path planning scheme is returned through the encoding and decoding process of the model, which specifically includes the following steps :

(1) Define the node set in the wireless sensor network as S={s ₀ , s ₁ , s ₂ ,..., s _i }, where s ₀ represents the base station, that is, the starting point and the final return of the charging car the end point. Each node s _i except the base station is represented by a four-dimensional vector, s _i ={ _{ci ,[r i ,} d _i ],T _i (t),e _i (t)}, where _ci =[x _i , y _i ] represents the two-dimensional coordinates of node s _i , [ri , d _i ] represents the time window of node s _i , _ri represents the opening time, d _i represents the deadline _{, and the node s i can} only be is charged within the time window, e _i (t) and T _i (t) represent the emergency situation of node _si at time t and the required charging time, respectively, the larger e _i (t), the lower the power of _si , the longer it takes to charge.

其中L_i,j代表节点s_i和s_j之间的距离。(2) The charging vehicle moves in the network at a constant speed of v, and the travel time from node _si to _sj

where _Li,j represents the distance between nodes s _i and s _j .

其中

表示节点s_i的初始紧急状态，f(t)是一个递增项，e_i(t)存在上限值e_max，始终保持e_i(t)≤e_max。节点s_i的时间窗[r_i,d_i]取决于节点的初始紧急状态耗电速率，那么s_i的截止时间

(3) The emergency situation e _i (t) of node s _i changes with time t, and the law of change is expressed by mathematical formula as

in

Represents the initial emergency state of node s _i , f(t) is an increasing term, e _i (t) has an upper limit e _max , and always keeps e _i (t)≤e _max . The time window [r _i ,d _i ] of node _si depends on the initial emergency state power consumption rate of the node, then the deadline for _si

(4) For the charging car, if it visits outside the time window of node _si , it will be punished by a penalty, which is expressed as:

where τ _i represents the time for the charging car to reach node _si and σ is a constant that depends on the scale of the problem.

其中β是一个负常数，其大小取决于路径成本和节点死亡成本相对大小。(5) For a path planning scheme π given by the model, the function to evaluate the scheme is:

where β is a negative constant whose size depends on the relative size of path cost and node death cost.

(6) Build a deep reinforcement learning model GAPN. GAPN uses an encoder-decoder framework. The encoder encodes all nodes _si , and sets _si ={ _{ci ,[r i ,} d _i ],T _i (t), e _i (t)} is divided into static g _i ={ _{ci ,[r i ,} d _i ]} and dynamic δ _i (t)={T _i (t),e _i (t)} two Each part is encoded separately, and the encoded vector is obtained.

where relu is a nonlinear activation function, W ₁ , W ₂ and b are all trainable parameters that can be learned during training.

(8) The graph neural network in GAPN encodes all node sets S of the wireless sensor network. The encoding network has a total of N layers, and the expression of each layer is:

进行权重计算，计算结果权重最高的节点，则为下一个将要访问的点，权重计算公式如下：(9) The decoder part uses the attention mechanism to generate the hidden layer vector of the encoder

Perform weight calculation, and the node with the highest weight of the calculation result is the next point to be visited. The weight calculation formula is as follows:

Among them, o _i represents the context encoding information based on decoding, including the information encoded by the graph neural network, and q _i represents the encoding vector of node _si .

(10) After obtaining the complete neural network model, use the actor-critic method in reinforcement learning to train the model to obtain the final GAPN model.

(11) Input the set of problem nodes to be solved into the GAPN model in the form of four-dimensional features, and the model returns the order of finally visiting all nodes, that is, the path planning scheme of the charging vehicle.

Figure 3 shows the system structure diagram when deploying the model system to an agent (mobile unmanned vehicle) cluster. When the central base station processes the collected node information and processes it through the GAPN module,

The corresponding task instruction is returned and sent to the mobile agent, and the mobile agent uses the control instruction to control its motion controller to execute the corresponding task. Specifically, each agent is shown in Figures 4 and 5, and an agent agent program runs on the device. The agent agent program is first responsible for communicating with the motion controller on the agent, sending control commands to it, collecting and preliminarily processing the data sensed by the agent, and at the same time, the agent agent will make task decisions and pass the task instructions sent by the base station center. , and perform the corresponding operations.

The technical means disclosed in the solution of the present invention are not limited to the technical means disclosed in the above embodiments, but also include technical solutions composed of any combination of the above technical features.

Claims (3)

1. The unmanned charging vehicle path planning method based on deep reinforcement learning is characterized by comprising the following steps:

step (1) collecting nodes S ═ S in the wireless sensor network₀,s₁,s₂,…,s_nInformation, including location information and emergency status of the node;

step (2) building a model GAPN based on deep reinforcement learning, wherein the model GAPN comprises a point encoder, a graph encoder, a decoder and an attention mechanism module;

step (3) generating a training data set and a testing data set for training a GAPN model on the basis of the collected node information data;

setting a model training target to minimize node mortality and minimize charging vehicle path cost, defining a loss function, and training GAPN by using a reinforcement learning operator-critic algorithm to obtain a final model;

and (5) setting the node S in the wireless sensor network to be S { (S)₀,s₁,s₂,…,s_nInputting the information into the GAPN model, and returning the scheme pi ═ s of all the nodes accessed by the charging vehicle by the model₀,s′₁,s′₂,…,s′_nH, where pi is the reordering of S;

and (6) solving the path planning problem under the scene of a plurality of charging vehicles by combining a heuristic clustering method with the GAPN, namely scheduling the charging vehicles and planning the paths of the charging vehicles when the wireless sensing network has a plurality of charging vehicles.

2. The unmanned charging vehicle path planning method based on deep reinforcement learning of claim 1, characterized in that: the operator-critic algorithm used in the step (4) is specifically as follows:

step 4.1: constructing an actor network and a critic network based on the GAPN network structure, wherein theta represents actor network parameters and theta_vRepresenting critic network parameters, wherein the difference between the two networks is that an operator network uses an average sampling mode in a decoding process, and the critic network adopts a greedy sampling strategy;

step 4.2: a batch of training data sets X, with a total of B data, for each data set instance X_iAnd solving the final path cost L (pi) by applying the current actor network_i|x_i) Solving for its baseline expected value using critic's network

Step 4.3: performing two-network batch strategy gradient calculation by using the value obtained in the step 4.2, wherein the operator network strategy gradient g_θAnd (3) calculating:

critic network policy gradient

Step 4.4: and respectively updating the parameters of the two networks by using a gradient descent method, wherein the updating rules are respectively as follows: θ + lr g_θ，

Wherein lr is the learning rate;

step 4.5: and repeating the step 4.2 to the step 4.4T times, wherein T is a set training algebra before training.

3. The unmanned charging vehicle path planning method based on deep reinforcement learning of claim 1, characterized in that: the heuristic clustering algorithm used in the step (6) is specifically as follows:

step 6.1: defining m subsets R ═ S₁,S₂,…,S_mThe node is used for storing nodes to be visited by each charging vehicle; definition e (S)_j) Is S_jThe sum of the urgency levels of all nodes in the cluster;

step 6.2: wireless sensor network node for inputSet of points S, according to the initial urgency of the node

Sorting from big to small;

step 6.3: firstly, respectively putting the first m nodes in a node set S into m subsets S₁,S₂,…,S_mPerforming the following steps;

step 6.4: firstly, the set R is according to e (S)_j) Sequencing in an increasing order, traversing the rest nodes in the set S, and for the currently traversed node S_iIf S is_jIn which there is no node s_kAnd node s_iDifference R of opening time of_i,kGreater than travel time t_i,kOr difference D in cutoff time_i,kLess than travel time t_i,kThen s will_iPut in S_jOtherwise, another subset is replaced until the condition is met;

step 6.5: obtaining the final m subsets R ═ S₁,S₂,…,S_mAnd the method is used for executing m charging vehicle tasks.

Images