CN115542912B - A mobile robot path planning method based on improved Q-learning algorithm - Google Patents

Abstract

The invention relates to a mobile robot path planning method based on an improved Q-learning algorithm, which comprises the following steps: (1) The artificial potential field principle is utilized to combine with the simulation environment, a new potential field function is designed, the environment potential value is introduced as heuristic information to initialize the Q value table, so that the potential value is larger when the potential value is closer to the target point, the intelligent agent is guided to explore towards the target direction in the earlier stage, algorithm convergence is accelerated, and planning efficiency is improved. Improving blindness of the Q-learning algorithm in early exploration; (2) And adding a behavior utility function into an epsilon greedy strategy of a traditional Q-learning algorithm, evaluating the actions according to the conditions of path segments after the actions are executed, dynamically adjusting the probability of each action of the intelligent agent, improving the search efficiency and improving the path smoothness. By applying the technical scheme, the shortest path can be obtained, and meanwhile, the convergence speed of an algorithm and the smoothness of the path can be improved.

Description

A mobile robot path planning method based on improved Q-learning algorithm

Technical Field

The invention relates to the technical field of robot navigation planning, and in particular to a mobile robot path planning method based on an improved Q-learning algorithm.

Background technique

With the introduction of the "goods to person" picking model, mobile robots are widely used in smart warehouses. The introduction of mobile robots has improved the picking efficiency of warehouses, and path planning, as one of the core technologies of mobile robots, has also received more and more attention. Path planning refers to planning a collision-free and optimal path based on the environment in which the mobile robot is located, combined with evaluation criteria such as the shortest path, shortest planning time, and path smoothness.

Path planning originated in the 1960s. Dijkstra algorithm, A* algorithm, artificial potential field method, and ant colony algorithm and particle swarm algorithm are commonly used for global planning path search. However, traditional methods are complex to operate and have low efficiency in solving problems. In addition, heuristic algorithms are difficult to design and understand. In recent years, with the deepening of reinforcement learning research, some scholars have begun to apply reinforcement learning to path planning. The most widely used reinforcement learning algorithm in mobile robot path planning is the Q-learning algorithm. The Q-learning algorithm is a temporal difference reinforcement learning algorithm. The process of the Q-learning algorithm is: the mobile robot first selects action a from all possible actions under state s and executes it, and then evaluates the result of the action based on the immediate reward value of action a and the estimated value of the current state action received. By repeating all actions in all states, the mobile robot can learn the overall best behavior by judging the long-term discounted return. As a supervised learning method, the traditional Q-learning algorithm enables the mobile robot to use the learning mechanism to plan a better collision-free path through real-time interaction with the environment. It does not require an environmental model and performs well in complex environments. However, there are still problems such as the blindness of the early exploration of the algorithm, long learning time, slow convergence speed, and poor path smoothness.

Summary of the invention

In view of this, the object of the present invention is to provide a mobile robot path planning method based on an improved Q-learning algorithm, which can achieve the shortest path while improving the convergence speed of the algorithm and the smoothness of the path.

To achieve the above object, the present invention adopts the following technical solution: a mobile robot path planning method based on an improved Q-learning algorithm, comprising the following steps:

Step 1: Use the grid method to model the environment map and establish an obstacle matrix;

Step 2: The mobile robot exists as a particle in a two-dimensional environment and can only search and move in four directions, namely up, down, left, and right; the side length of each grid is one unit, and the single-step movement distance of the mobile robot is 1 step length;

Step 3: Design the reward function and establish the reward matrix R and Q value table Q;

Step 4: Use the improved potential field function to initialize the Q value table and various parameters of the algorithm, including the number of iterations, ε-exploration probability ε, learning efficiency α, reward attenuation factor γ, behavior utility attenuation coefficient p ₁ , exploration incentive coefficient p ₂ , and weight coefficient β;

Step 5: Initialize the starting point and target point;

Step 6: Start exploration, select an action to execute according to the improved ε exploration strategy, obtain the timely reward value after executing the action, calculate the distance function, and update the action utility function;

Step 7: Update the Q value table and the action execution probability according to the executed action, where the Q value table update formula is as follows:

Q(s,a)＝Q(s,a)+α[Rt+γmaxaQ(s',a')-Q(s,a)]

Where α represents the learning efficiency α∈[0,1], γ represents the discount factor γ∈[0,1], Rt is the timely reward value, s′, a′ are the next state and the next action;

The update formula for the action execution probability is as follows:

Where: n is the total number of actions executed, is the behavior utility function;

Step 8: Update the position state after the action is executed to the current position state, determine whether the current position is the end position and whether it exceeds the maximum step length, otherwise jump to step 6, if yes, go to step 9;

Step 9: Record the path of each learning and determine whether the maximum number of iterations has been reached. If so, output the optimal path. If not, jump to step 5.

In a preferred embodiment, the reward function designed in step 3 is:

Where: r ₁ and r ₂ are both positive numbers. When the agent encounters an obstacle, the reward value -r ₁ is obtained; when the agent reaches the target point, the reward value r ₂ is obtained; when the agent reaches other positions, the reward value obtained is 0.

In a preferred embodiment, the improved potential energy field function in step 4 is:

Where: C = L = X + Y, X is the horizontal length of the environment, Y is the vertical length of the environment; d _1(s) and d _2(s) are the vertical distance and horizontal distance between the current position of the agent and the target point respectively; d(s) is the Euclidean distance between the current position of the agent and the line connecting the target point and the starting point;

The function to initialize the Q value table is:

Q(s,a)＝R+γV(S)

In the formula, R is the initial reward function matrix, γ is the reward attenuation factor, and V(S) is the value function of all states initialized by the gravitational field function; the Q value table initialized by this method, the closer to the target point, the larger the Q value, and the target point has the maximum Q value, and the Q value at the obstacle is 0.

In a preferred embodiment, the specific steps of the improved ε exploration strategy in step 6 are as follows: when the random value is less than the greedy factor, the action with the highest probability of execution is selected; when the random value is greater than the greedy factor, the Q value of the current state to the next state is updated according to the probability of each execution action, and the action with the highest Q value is selected for execution. The random value is between 0 and 1, and the update formula is:

T _Q =Q+β×(P ₁ ,P ₂ ,P _i )(i∈(1,n))

Where: T _Q is the Q value updated according to the new action execution probability, β is the weight coefficient, P ₁ , P ₂ , _Pi is the probability of each action being executed; the improved behavior selection strategy enables the agent to use the already explored environmental information for multi-step exploration when selecting the execution action in each state, comprehensively considers the distance information between the previous and next states of the agent and the target point and the multi-step execution action information, and selects the "optimal" action to execute;

The distance function in step 6 is:

Where: Respectively represent the distances of the previous state and the current state from the target point;

The action utility function and its calculation rules are:

Where: _p1 is the attenuation coefficient, _p2 is the exploration incentive coefficient, and _rt is the immediate reward value; _ai is a different action, and the E value of different actions is updated according to the size of the immediate reward value and whether the consecutive actions are the same. When the immediate reward value is positive and the actions are the same for three consecutive times, When the immediate reward value is positive and the same action is performed twice in a row, /> Otherwise, the value of E is zero.

In a preferred embodiment, the environmental potential energy value is introduced as heuristic information to initialize the Q value table.

In a preferred embodiment, the behavior utility function is used as a criterion for evaluating the execution of actions, thereby improving the ε-greedy strategy, combining the environmental information that the agent has explored and the impact of the executed actions on the smoothness of the path segment, and dynamically adjusting the probability of each action of the agent being selected.

Compared with the prior art, the present invention has the following beneficial effects: the present invention proposes a mobile robot path planning method based on an improved Q-learning algorithm, which improves the shortcomings of the traditional Q-learning algorithm, such as large blindness in early exploration, long algorithm learning time, poor convergence speed, and poor path smoothness, by introducing a potential field function and a behavioral utility function to guide the intelligent agent to explore in the target direction in the early stage, so that when the intelligent agent chooses to execute an action in each state, it uses the already explored environmental information to perform multi-step exploration, comprehensively considers the distance information between the previous and next states of the intelligent agent and the target point and the multi-step execution action information, selects the "optimal" action to execute, improves the operation efficiency of the algorithm, accelerates the convergence speed of the algorithm, and improves the smoothness of the algorithm planning path.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a flow chart of a method implementation of a preferred embodiment of the present invention.

FIG. 2 is a graph showing convergence curves of a conventional method, an existing method, and the present method in a preferred embodiment of the present invention.

FIG3 is a diagram comparing the path search effects of the traditional method, the existing method and the present method in a preferred embodiment of the present invention.

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings and embodiments.

It should be noted that the following detailed descriptions are illustrative and are intended to provide further explanation of the present application. Unless otherwise specified, all technical and scientific terms used herein have the same meanings as those commonly understood by those skilled in the art to which the present application belongs.

It should be noted that the terms used herein are only for describing specific embodiments and are not intended to limit the exemplary embodiments according to the present application; as used herein, unless the context clearly indicates otherwise, the singular form is also intended to include the plural form. In addition, it should be understood that when the terms "comprise" and/or "include" are used in this specification, they indicate the presence of features, steps, operations, devices, components and/or their combinations.

A mobile robot path planning method based on an improved Q-learning algorithm is designed. The improved Q-learning algorithm is improved around the Q-value table and the ε exploration strategy. The potential energy field function is introduced as the inspiration information to initialize the Q-value table, so as to guide the intelligent agent to explore in the target direction in the early stage, thus solving the blindness of the algorithm's early exploration. At the same time, the behavioral utility function is introduced to improve the ε exploration strategy, and the probability of each action of the intelligent agent being selected is dynamically adjusted by combining the environmental information that the intelligent agent has explored and the influence of the executed actions on the smoothness of the path segment.

As shown in FIG1 , the method of the embodiment of the present invention specifically comprises the following steps:

Step 1: Use the grid method to model the environment map and establish an obstacle matrix;

Step 2: The mobile robot exists as a particle in a two-dimensional environment and can only search and move in four directions, namely up, down, left, and right; the side length of each grid is one unit, and the single-step movement distance of the mobile robot is 1 step length;

Step 3: Design the reward function and establish the reward matrix R and Q value table Q. The reward function formula is as follows:

Where: r ₁ and r ₂ are both positive numbers. When the agent encounters an obstacle, the reward value -r ₁ is obtained; when the agent reaches the target point, the reward value r ₂ is obtained; when the agent reaches other positions, the reward value obtained is 0.

Step 4: Use the improved potential field function to initialize the Q value table and various parameters of the algorithm, including the number of iterations, ε-exploration probability ε, learning efficiency α, reward attenuation factor γ, behavior utility attenuation coefficient p ₁ , exploration incentive coefficient p ₂ , weight coefficient β, etc. The traditional Q value table is generally 0 or the same initial value, which leads to large blindness in the early exploration and slow convergence speed. Therefore, the present invention combines the principle of artificial potential field and designs a new potential field function. By introducing the potential field function as heuristic information, the potential field function is as follows:

Where: C = L = X + Y, X is the horizontal length of the environment, Y is the vertical length of the environment; d1 _(s) and d2 _(s) are the vertical distance and horizontal distance between the current position of the agent and the target point respectively; d(s) is the Euclidean distance between the current position of the agent and the line connecting the target point and the starting point.

The function to initialize the Q value table is:

Q(s,a)＝R+γV(S)

In the formula, R is the initial reward function matrix, γ is the reward attenuation factor, and V(S) is the value function of all states initialized by the gravitational field function. The Q value table initialized by this method has a larger Q value the closer to the target point, and the target point has the maximum Q value, and the Q value at the obstacle is 0. This allows the agent to explore the target point in the early stage, accelerate the convergence of the algorithm, and improve planning efficiency.

Step 5: Initialize the starting point and target point;

Step 6: Start exploring, select an action to execute according to the improved ε exploration strategy, obtain the timely reward value after executing the action, calculate the distance function, and update the action utility function;

The traditional ε exploration strategy has strong randomness in action selection, which leads to slow algorithm convergence and poor path smoothness. This paper introduces the concept of behavioral utility equation and designs a behavioral utility equation to evaluate the quality of action execution and dynamically adjust the probability of each action of the agent being selected. The behavioral utility equation is as follows:

Where: _p1 is the attenuation coefficient, _p2 is the exploration incentive coefficient, and _rt is the immediate reward value; _ai is a different action, and the E value of different actions is updated according to the size of the immediate reward value and whether the consecutive actions are the same. When the immediate reward value is positive and the actions are the same for three consecutive times, When the immediate reward value is positive and the same action is performed twice in a row, /> Otherwise, the value of E is zero.

The distance function is as follows:

Where: Respectively represent the distances from the previous state and the current state to the target point.

The specific steps of the improved ε exploration strategy are as follows: When the random value (between 0 and 1) is less than the greed factor, select the action with the highest probability of executing the action. When the random value is less than the greed factor, update the Q value of the current state to the next state according to the probability of each execution action, and select the action with the highest Q value to execute. The update formula is:

T _Q =Q+β×(P ₁ ,P ₂ ,P _i )(i∈(1,n))

Where: T _Q is the Q value updated according to the new action execution probability, β is the weight coefficient, P ₁ , P ₂ , _Pi is the probability of each action being executed. The improved behavior selection strategy enables the agent to use the already explored environment information for multi-step exploration when selecting the execution action in each state, comprehensively considers the distance information between the previous and next states of the agent and the target point and the multi-step execution action information, and selects the "optimal" action to execute.

Step 7: Update the Q value table, update the action execution probability, and update the position status. The Q value table update formula is as follows:

Q(s,a)＝Q(s,a)+α[Rt+γmaxaQ(s',a')-Q(s,a)]

Where α represents the learning efficiency α∈[0,1], γ represents the discount factor γ∈[0,1], Rt is the timely reward value, s′, a′ are the next state and the next action.

The update formula for the action execution probability is as follows:

Where: n is the total number of actions executed, is the behavior utility function.

Step 8: Update the position state after the action is executed to the current position state, determine whether the current position is the end position and whether it exceeds the maximum step length, otherwise jump to step 6, if yes, go to step 9;

Step 9: Record the path of each learning and determine whether the maximum number of iterations has been reached. If so, output the optimal path. If not, jump to step 5.

Figures 2 and 3 show the difference in path planning effect between the method of the present invention and the traditional Q-learning algorithm and the existing Q-learning algorithm. (a) and (b) in Figures 2 and 3 are the traditional Q-learning algorithm and the existing algorithm (c) are the method of the present invention. It can be seen from the above figures that compared with the traditional algorithm and the existing Q-learning algorithm, the method of the present invention can effectively improve the path smoothness and accelerate the convergence of the algorithm.

Those skilled in the art will appreciate that the embodiments of the present application may be provided as methods, systems, or computer program products. Therefore, the present application may adopt the form of a complete hardware embodiment, a complete software embodiment, or an embodiment in combination with software and hardware. Moreover, the present application may adopt the form of a computer program product implemented in one or more computer-usable storage media (including but not limited to disk storage, CD-ROM, optical storage, etc.) that contain computer-usable program code.

The present application is described with reference to the flowchart and/or block diagram of the method, device (system) and computer program product according to the embodiment of the present application. It should be understood that each process and/or box in the flowchart and/or block diagram, and the combination of the process and/or box in the flowchart and/or block diagram can be realized by computer program instructions. These computer program instructions can be provided to a processor of a general-purpose computer, a special-purpose computer, an embedded processor or other programmable data processing device to produce a machine, so that the instructions executed by the processor of the computer or other programmable data processing device produce a device for realizing the function specified in one process or multiple processes in the flowchart and/or one box or multiple boxes in the block diagram.

These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing device to work in a specific manner, so that the instructions stored in the computer-readable memory produce a manufactured product including an instruction device that implements the functions specified in one or more processes in the flowchart and/or one or more boxes in the block diagram.

These computer program instructions may also be loaded onto a computer or other programmable data processing device so that a series of operational steps are executed on the computer or other programmable device to produce a computer-implemented process, whereby the instructions executed on the computer or other programmable device provide steps for implementing the functions specified in one or more processes in the flowchart and/or one or more boxes in the block diagram.

The above is only a preferred embodiment of the present invention, and does not limit the present invention in other forms. Any technician familiar with the profession may use the above disclosed technical content to change or modify it into an equivalent embodiment with equivalent changes. However, any simple modification, equivalent change and modification made to the above embodiment according to the technical essence of the present invention without departing from the technical solution of the present invention still belongs to the protection scope of the technical solution of the present invention.

Claims (4)

1. A mobile robot path planning method based on an improved Q-learning algorithm, characterized in that it comprises the following steps: Step 1: Use the grid method to model the environment map and establish an obstacle matrix; Step 2: The mobile robot exists as a particle in a two-dimensional environment and can only search and move in four directions, namely up, down, left, and right; the side length of each grid is one unit, and the single-step movement distance of the mobile robot is 1 step length; Step 3: Design the reward function and establish the reward matrix R and Q value table Q; Step 4: Use the improved potential field function to initialize the Q value table and various parameters of the algorithm, including the number of iterations, ε-exploration probability ε, learning efficiency α, reward attenuation factor γ, behavior utility attenuation coefficient p ₁ , exploration incentive coefficient p ₂ , and weight coefficient β; Step 5: Initialize the starting point and target point; Step 6: Start exploration, select an action to execute according to the improved ε exploration strategy, obtain the timely reward value after executing the action, calculate the distance function, and update the action utility function; Step 7: Update the Q value table and the action execution probability according to the executed action, where the Q value table update formula is as follows: Q(s,a)＝Q(s,a)+α[Rt+γmaxaQ(s',a')·-Q(s,a)] Where α represents the learning efficiency α∈[0,1], γ represents the discount factor γ∈[0,1], Rt is the timely reward value, s′, a′ are the next state and the next action; The update formula for the action execution probability is as follows: Where: n is the total number of actions executed, is the behavior utility function; Step 8: Update the position state after the action is executed to the current position state, determine whether the current position is the end position and whether it exceeds the maximum step length, otherwise jump to step 6, if yes, go to step 9; Step 9: Record the path of each learning and determine whether the maximum number of iterations has been reached. If so, output the optimal path. If not, jump to step 5. The improved potential energy field function in step 4 is: Where: C = L = X + Y, X is the horizontal length of the environment, Y is the vertical length of the environment; d _1(s) and d _2(s) are the vertical distance and horizontal distance between the current position of the agent and the target point respectively; d(s) is the Euclidean distance between the current position of the agent and the line connecting the target point and the starting point; The function to initialize the Q value table is: Q(s,a)＝R+γV(S) In the formula, R is the initial reward function matrix, γ is the reward attenuation factor, and V(S) is the value function of all states initialized by the gravitational field function; the Q value table initialized by this method, the closer to the target point, the larger the Q value, and the target point has the maximum Q value, and the Q value at the obstacle is 0; The specific steps of the improved ε exploration strategy in step 6 are as follows: when the random value is less than the greedy factor, the action with the highest probability of execution is selected; when the random value is greater than the greedy factor, the Q value of the current state to the next state is updated according to the probability of each execution action, and the action with the highest Q value is selected for execution. The random value is between 0 and 1, and the update formula is: T _Q =Q+β×(P ₁ ,P ₂ ,P _i )(i∈(1,n)) Where: T _Q is the Q value updated according to the new action execution probability, β is the weight coefficient, P ₁ , P ₂ , _Pi is the probability of each action being executed; the improved behavior selection strategy enables the agent to use the already explored environmental information for multi-step exploration when selecting the execution action in each state, comprehensively considers the distance information between the previous and next states of the agent and the target point and the multi-step execution action information, and selects the "optimal" action to execute; The distance function in step 6 is: Where: Respectively represent the distances of the previous state and the current state from the target point; The action utility function and its calculation rules are: Where: _p1 is the attenuation coefficient, _p2 is the exploration incentive coefficient, and _rt is the immediate reward value; _ai is a different action, and the E value of different actions is updated according to the size of the immediate reward value and whether the consecutive actions are the same. When the immediate reward value is positive and the actions are the same for three consecutive times, When the immediate reward value is positive and the same action is performed twice in a row, /> Otherwise, the value of E is zero. 2. The mobile robot path planning method based on the improved Q-learning algorithm according to claim 1, characterized in that: The reward function designed in step 3 is: Where: r ₁ and r ₂ are both positive numbers. When the agent encounters an obstacle, the reward value -r ₁ is obtained; when the agent reaches the target point, the reward value r ₂ is obtained; when the agent reaches other positions, the reward value obtained is 0. 3. According to claim 1, a mobile robot path planning method based on an improved Q-learning algorithm is characterized in that the environmental potential energy value is introduced as heuristic information to initialize the Q value table. 4. According to claim 1, a mobile robot path planning method based on an improved Q-learning algorithm is characterized in that a behavioral utility function is used as a criterion for evaluating the execution of actions, thereby improving the ε-greedy strategy, combining the environmental information that the agent has explored and the impact of the executed actions on the smoothness of the path segment, and dynamically adjusting the probability of each action of the agent being selected.