CN115202359A - Unmanned ship path planning method based on reinforcement learning and rapid expansion of random tree - Google Patents

Abstract

The invention discloses an unmanned ship path planning method based on reinforcement learning and rapid expansion random tree, which comprises the steps of firstly constructing a decision model for unmanned ship path planning based on a Markov decision process; then modeling the navigation environment of the unmanned ship, and determining an initial position and a target position; and then, taking the initial position as a root node, constructing an initial random tree, selecting expansion points of the initial random tree by adopting a Q-learning algorithm based on a constructed decision model for unmanned ship path planning, updating the random tree according to the selected expansion points until a path from the initial position to a target position is found, screening random sampling points according to the state of interaction with the environment model in the selection process of the expansion points, and updating a value function according to the state of the random sampling points and reward. The method of the invention can provide adaptability to the environment and improve the accuracy of path planning.

Description

A Path Planning Method for Unmanned Vehicles Based on Reinforcement Learning and Rapidly Expanding Random Trees

technical field

The invention relates to the technical field of ship path planning, in particular to an unmanned ship path planning method based on reinforcement learning and rapid expansion of random trees.

Background technique

Surface unmanned boat is an unmanned small vessel that can navigate autonomously and operate intelligently. Compared with conventional manned ships, surface unmanned boats have the advantages of smaller hull size, more flexible maneuvering, and lower cost. Path planning has been an important part of the research of surface unmanned boats since the birth of surface unmanned boats. Unmanned boats conduct human-machine interaction with the external location environment, collect current water environment information in advance, and carry out preliminary path planning according to the collected information. Dynamic environmental information is collected by built-in sensors during real-time navigation, and local path planning is performed to avoid collisions. The path planning of the unmanned boat is to find an optimal path from the starting point to the target point according to the collected environmental information, and safely reach the target point.

Therefore, in the face of complex environments, the optimization of existing path planning algorithms is crucial. When optimizing the path planning problem, at present, the constraints and the setting of the objective function are mainly used for optimization. However, the existing planning methods have poor adaptability to the environment, so the path planning effect is not good.

SUMMARY OF THE INVENTION

The present invention provides an unmanned boat path planning method based on reinforcement learning and rapid expansion of random trees, which is used to solve or at least partially solve the poor path planning effect caused by the poor adaptability of the methods in the prior art to the environment. question.

In order to solve the above technical problems, the present invention discloses an unmanned boat path planning method based on reinforcement learning and rapid expansion of random trees, including:

S1: Build a decision model for UAV path planning based on Markov decision process, the decision model includes state and reward;

S2: Model the navigation environment of the UAV, and determine the initial position and target position;

S3: Take the initial position as the root node, construct an initial random tree, and use the Q-learning algorithm to select the expansion point of the initial random tree based on the constructed decision-making model for UAV path planning, and update it according to the selected expansion point. Random tree until the path from the initial position to the target position is found, the selection process of the expansion point selects the random sampling points according to the state of interaction with the environment model, and updates the value function according to the state and reward of the random sampling point.

In one embodiment, the decision model of step S1 is:

(S,A,O,T,r, _Psa )

Among them, S={s ₁ , s ₂ ,...,s _t } represents the state space, s _t represents the state at time t, A={a ₁ , a ₂ ,..., a _t } represents the action space, and a _t ∈ A represents the action performed at time t, O represents the observation space, T represents the observation transfer function, r represents the reward function, and P _sa represents the state transfer function.

In one embodiment, step S2 includes:

S21: Evenly divide the navigation water area of the unmanned boat with grids of the same size;

S22: Judging whether the grid is occupied by obstacles, divide the grid into free grids without obstacles and obstacle grids occupied by obstacles, and the environment model is composed of free grids and obstacle grids;

S23: Normalize the water depth value of the free grid;

S24: Determine the initial position and target position of the unmanned boat.

In one embodiment, step S3 includes:

S31: Initialize the state s of the unmanned boat and the value function Q(s, a) corresponding to its arbitrary action a;

S32: Screen random sampling points according to the state of interaction with the environment model, and search for nearby nodes to obtain new states and rewards;

S33: Update the value function with Q-Learning, the calculation formula is:

Q(s _t+1 ,a _t+1 )←Q(s _t-1 ,a _t-1 )+a[r+γmax _at Q(s _t ,a _t )-Q(s _t-1 ,a _{t -1} )]

Among them, s _t is the state at time _t , at t is the action selected at time t, r is the reward feedback in the current state, α is the learning rate, γ is the discount factor, max represents the maximum value, Q(s _t-1 , a _t-1 ) represents the value function at time t-1, Q(s _t , a _t ) represents the value function at time t, ← represents the update, Q(s _t+1 , a _t+1 ) represents the updated value function, that is, the value function at time t+1;

S34: judge whether the constraint condition is satisfied, if the constraint is satisfied, execute the next step S35, and if the condition is not satisfied, execute S32 again;

S35: Expand the node that satisfies the constraint selected in S34 into a new node, and update the random tree.

In one embodiment, after step S35, the method further includes:

It is judged whether the target point is reached, and if the target point is reached, the node is backtracked to complete the path planning; if the target point is not reached, the operation of S32 is re-executed.

In one embodiment, the method further includes setting an inducement reward and a path corner reward, wherein the calculation formula of the inducement reward is:

r ₁ =kr _o +(1-k)r _g

Among them, r ₁ is the induction reward, _k is the induction coefficient, ro is the obstacle avoidance action reward, and r _g is the target action reward;

The calculation formula of the path corner reward is:

Among them, r ₂ is the corner reward, e is the corner coefficient, and θ is the corner angle.

Compared with the prior art, the advantages and beneficial technical effects of the present invention are as follows:

The invention provides an unmanned boat path planning method based on reinforcement learning and rapid expansion of random trees. When selecting expansion points of random trees, reinforcement learning selection mechanism Q-learning algorithm is used to select expansion points. During the selection process, random sampling points are screened according to the state of interaction with the environment model, and the value function is updated according to the state and reward of the random sampling point. Eligible expansion points can be filtered out. Since the interaction state with the environment model is considered, the path can be improved. For the adaptability to the environment, repeating the above process generates an optimal path from the initial position to the target position, which improves the effect of path planning.

Description of drawings

In order to illustrate the embodiments of the present invention or the technical solutions in the prior art more clearly, the following briefly introduces the accompanying drawings that need to be used in the description of the embodiments or the prior art. Obviously, the drawings in the following description are For some embodiments of the present invention, for those of ordinary skill in the art, other drawings can also be obtained according to these drawings without creative efforts.

FIG. 1 is a flowchart of an unmanned boat path planning method based on reinforcement learning and fast expanding random tree in an embodiment of the present invention.

FIG. 2 is a schematic diagram of node expansion using an RRT algorithm in an embodiment of the present invention.

3 is a schematic diagram of a corner constraint in an embodiment of the present invention;

FIG. 4 is a schematic diagram of the result of the path planning method adopted in the embodiment of the present invention.

Detailed ways

The invention solves the technical problems of poor environmental adaptability and poor path planning effect in the prior art by providing a Q-learning-based RRT surface unmanned boat path search method.

In order to make the purposes, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments These are some embodiments of the present invention, but not all embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative efforts shall fall within the protection scope of the present invention.

The embodiment of the present invention provides an unmanned boat path planning method based on reinforcement learning and rapid expansion of random trees, including:

S1: Build a decision model for UAV path planning based on Markov decision process, the decision model includes state and reward;

S2: Model the navigation environment of the UAV, and determine the initial position and target position;

S3: Take the initial position as the root node, construct an initial random tree, and use the Q-learning algorithm to select the expansion point of the initial random tree based on the constructed decision-making model for UAV path planning, and update it according to the selected expansion point. Random tree until the path from the initial position to the target position is found, the selection process of the expansion point selects the random sampling points according to the state of interaction with the environment model, and updates the value function according to the state and reward of the random sampling point.

In the specific implementation process, the rapid expansion of the random tree is the RRT algorithm. First, the random sampling points are screened according to the state of interaction with the environment model, and the value function is updated according to the state and reward of the random sampling point, and the expansion point is further obtained. To the subpath from the current node to the extension point, repeat the process until a path is found from the initial node to the target node.

In one embodiment, the decision model of step S1 is:

(S,A,O,T,r, _Psa )

Among them, S={s ₁ , s ₂ ,...,s _t } represents the state space, s _t represents the state at time t, A={a ₁ , a ₂ ,..., a _t } represents the action space, and a _t ∈ A represents the action performed at time t, O represents the observation space, T represents the observation transfer function, r represents the reward function, and P _sa represents the state transfer function.

In the specific implementation process, the general Markov decision is composed of (S, A, r, P _sa ). In order to face the uncertainty problem of some unknown environments and re-planning, the present invention solves the problem of path planning for surface unmanned boats. Defined as a partially observable Markov decision process six-tuple (S, A, O, T, r, P _sa ).

其中，折扣因子γ∈(0,1)。The reward function G _t of reinforcement learning represents the sum of reward discounts starting from time t, and the reward function expression is:

where the discount factor γ∈(0,1).

In one embodiment, step S2 includes:

S21: Evenly divide the navigation water area of the unmanned boat with grids of the same size;

S22: Judging whether the grid is occupied by obstacles, divide the grid into free grids without obstacles and obstacle grids occupied by obstacles, and the environment model is composed of free grids and obstacle grids;

S23: Normalize the water depth value of the free grid;

S24: Determine the initial position and target position of the unmanned boat.

By modeling the navigation environment of the UAV, the environment model is constructed, and the initial position and target position are determined.

In one embodiment, step S3 includes:

S31: Initialize the state s of the unmanned boat and the value function Q(s, a) corresponding to its arbitrary action a;

S32: Screen random sampling points according to the state interacting with the environment model, and search for nearby nodes to obtain a new state s _t and a reward r;

S33: Update the value function with Q-Learning, the calculation formula is:

Q(s _t+1 ,a _t+1 )←Q(s _t-1 ,a _t-1 )+a[r+γmax _at Q(s _t ,a _t )-Q(s _t-1 ,a _{t -1} )]

Among them, s _t is the state at time _t , at t is the action selected at time t, r is the reward feedback in the current state, α is the learning rate, γ is the discount factor, max represents the maximum value, Q(s _t-1 , a _t-1 ) represents the value function at time t-1, Q(s _t , a _t ) represents the value function at time t, ← represents the update, Q(s _t+1 , a _t+1 ) represents the updated value function, that is, the value function at time t+1;

S34: judge whether the constraint condition is satisfied, if the constraint is satisfied, execute the next step S35, and if the condition is not satisfied, execute S32 again;

S35: Expand the node that satisfies the constraint selected in S34 into a new node, and update the random tree.

Please refer to FIG. 2 , which is a schematic diagram of node expansion using the RRT algorithm in an embodiment of the present invention, where x _rand is a random sampling point, x _init is an initial node, x _near is an adjacent node, and x _goal is a target node.

Please refer to FIG. 4 , which is a schematic diagram of the result of the path planning method adopted in the embodiment of the present invention.

In one embodiment, after step S35, the method further includes:

It is judged whether the target point is reached, and if the target point is reached, the node is backtracked to complete the path planning; if the target point is not reached, the operation of S32 is re-executed.

Please refer to FIG. 1 , which is a flowchart of a method for planning a path of an unmanned boat based on reinforcement learning and a fast expanding random tree in an embodiment of the present invention. Initialize the expansion tree (random search tree), that is, take the initial position as the root node of the expansion tree. Update the Q table, i.e. update the value function.

In one embodiment, the method further includes setting an inducement reward and a path corner reward, wherein the calculation formula of the inducement reward is:

r ₁ =kr _o +(1-k)r _g

Among them, r ₁ is the induction reward, _k is the induction coefficient, ro is the obstacle avoidance action reward, and r _g is the target action reward;

The calculation formula of the path corner reward is:

Among them, r ₂ is the corner reward, e is the corner coefficient, and θ is the corner angle.

Specifically, for the reward mechanism of the decision-making model, in order to reduce the randomness of the RRT algorithm and improve the target tendency, the present invention introduces an induction factor to improve the random nodes (sampling points). The core idea of the induction factor is to make x _rand = x _goal (the random node is equal to the goal node) through a certain probability during the expansion of the random tree, so that the random tree will be more inclined to search in the direction of the goal.

Further, this embodiment introduces a path angle reward. Adjusting the ship at a small angle will improve its moving efficiency and save resources, while a large angle will reduce reliability. Therefore, a large angle produces a low reward, and a small angle produces a high reward. As shown in FIG. 3 , it is a schematic diagram of a corner constraint in an embodiment of the present invention.

The selection of extension points is optimized through the set inducement reward and corner reward, which further improves the accuracy of path planning.

Although the preferred embodiments of the present invention have been described, additional changes and modifications to these embodiments may occur to those skilled in the art once the basic inventive concepts are known. Therefore, the appended claims are intended to be construed to include the preferred embodiment and all changes and modifications that fall within the scope of the present invention.

Obviously, those skilled in the art can make various changes and modifications to the embodiments of the present invention without departing from the spirit and scope of the embodiments of the present invention. Thus, provided that these modifications and variations of the embodiments of the present invention fall within the scope of the claims of the present invention and their equivalents, the present invention is also intended to include such modifications and variations.

Claims (6)

1. An unmanned ship path planning method based on reinforcement learning and fast expansion random tree is characterized by comprising the following steps:

s1: constructing a decision model for unmanned ship path planning based on a Markov decision process, wherein the decision model comprises a state and an award;

s2: modeling the navigation environment of the unmanned ship, and determining an initial position and a target position;

s3: the method comprises the steps of taking an initial position as a root node, constructing an initial random tree, selecting expansion points of the initial random tree by adopting a Q-learning algorithm based on a constructed decision model for unmanned ship path planning, updating the random tree according to the selected expansion points until a path from the initial position to a target position is found, screening random sampling points according to a state of interaction with an environment model in the selection process of the expansion points, and updating a value function according to the state of the random sampling points and reward.

2. The unmanned ship path planning method based on reinforcement learning and fast expansion random tree as claimed in claim 1, wherein the decision model of step S1 is:

(S,A,O,T,r,P _sa )

wherein S = { S = ₁ ,s ₂ ,…,s _t Denotes the state space, s _t Represents the state at time t, A = { a = ₁ ,a ₂ ,…,a _t Denotes the motion space, a _t E A represents the action performed at time T, O represents the observation space, T represents the observation value transfer function, r represents the reward function, P _sa Representing the state transition function.

3. The reinforcement learning and fast propagation stochastic tree based unmanned ship path planning method of claim 1, wherein step S2 comprises:

s21: uniformly dividing the sailing water area of the unmanned ship by using grids with the same size;

s22: judging whether the grid is occupied by an obstacle, dividing the grid into a free grid without the obstacle and an obstacle grid occupied by the obstacle, wherein the environment model consists of the free grid and the obstacle grid;

s23: normalizing the water depth value of the free grid;

s24: and determining the initial position and the target position of the unmanned ship.

4. The reinforcement learning and fast propagation stochastic tree based unmanned ship path planning method of claim 1, wherein step S3 comprises:

s31: initializing a state s of the unmanned ship and a value function Q (s, a) corresponding to any action a of the unmanned ship;

s32: screening random sampling points according to the state of interaction with the environment model, and searching adjacent nodes to obtain a new state and reward;

s33: updating the cost function by using Q-Learning, wherein the calculation formula is as follows:

Q(s _t+1 ,a _t+1 )←Q(s _t-1 ,a _t-1 )+a[r+γmax _at Q(s _t ,a _t )-Q(s _t-1 ,a _t-1 )]

wherein s is _t State at time t, a _t For the action selected at time t, r is the reward fed back at the current state, α is the learning rate, γ is the discount factor, max represents the maximum value, Q(s) _t-1 ,a _t-1 ) Representing the cost function, Q(s), at time t-1 _t ,a _t ) Value function representing time t, ← representing update, Q(s) _t+1 ,a _t+1 ) Representing the updated cost function, namely the cost function at the time t + 1;

s34: judging whether constraint conditions are met, if so, executing the next step S35, and if not, re-executing S32;

s35: and expanding the nodes which are selected in the S34 and meet the constraint into new nodes, and updating the random tree.

5. The reinforcement learning and fast propagation stochastic tree based unmanned ship path planning method of claim 4, wherein after step S35, the method further comprises:

judging whether the target point is reached, if so, backtracking the node to complete path planning; if the target point is not reached, the operation of S32 is re-executed.

6. The reinforcement learning and fast propagation random tree based unmanned ship path planning method of claim 1, wherein the method further comprises setting an inducement award and a path corner award, wherein the inducement award is calculated by the formula:

r ₁ ＝kr _o +(1-k)r _g

wherein r is ₁ For inducing reward, k is the induction coefficient, r _o Reward for obstacle avoidance action, r _g Awarding a target action;

the calculation formula of the path rotation angle reward is as follows:

wherein r is ₂ The number is the corner reward, e is the corner coefficient, and theta is the corner angle.

Images