1.

INTRODUCTION

As robot technology¹ develops, mobile robot is more and more widely used. As the guarantee of robot movement, path planning is especially important. The goal of path planning^2-3 is finding a safe way that keeps from collision from jumping-off point to the target point in specified areas. Traditional path planning algorithms, such as artificial potential field method⁴, Dijkstra algorithm⁵ and rapidly-exploring random trees (RRT) method⁶, are easy to implement to finish the path planning in known environment, but there is a problem of poor exploration ability in path planning. In this case, there will be more space of reinforcement learning.

Reinforcement Learning (RL)^7-8 is an artificial intelligence algorithm that does not require prior knowledge and obtains feedback information through trial-and-error iteration with the environment to optimize strategies. As one of the methods of machine learning⁹, it is suitable for solving sequential decision problems. In manner of trial and error in the environment, the agent takes the maximum cumulative reward brought by doing something as its optimal learning strategy. Markov Decision Process (MDP) is used to describe reinforcement learning problem mathematically. In the whole process of reinforcement learning exploration, for each time step, the environment provides an observation state S_t for the agent, and the agent selects an action A_t according to the strategy to respond, and then gets the immediate reward R_t provided by the environment and moves to the next state S_t+1. The agent’s goal is to maximize the expected discount reward by looking for an optimal strategy.

On the basis of reinforcement learning, deep reinforcement learning increases the perceptual ability of deep learning. As one of the representatives of deep reinforcement learning, DQN algorithm^10-12 has not only been tested with good effects in Atari games, but also has excellent performance in path planning. Based on Q-learning algorithm, DQN algorithm replaces Q-table with convolutional neural network, which solves the problem of large state space. DQN breaks the correlation between data by random sampling, and uses both the target network and the current network to solve the problem of model stability. Compared with other models, DQN has strong versatility and can be used to solve different types of problems.

2.

IMPROVED ALGORITHM

2.1

Improvement of training data

DQN algorithm combines the powerful representation ability of deep neural network with Q-learning algorithm, and achieves excellent performance in a series of tasks. The success of this algorithm benefits from the target network and experience replay method used in DQN algorithm, especially experience replay method, which stores previous experiences in a container and disrupt correlations between them. DQN algorithm uses experience replay method to reduce the correlation between training experiences, improve experience utilization and reduce overfitting. The main method is to store the experience generated in the process of finding the target into the experience pool. During network training, a batch of experience is sampled without order or plan from the experience pool for updating network parameters. However, these experiences are not equally important for network model learning, and there will be repeated and similar experiences. To solve this problem, an improved experience replay method is proposed to reduce similarity, which uses an experience pool to store all experiences, and speeds up network model training by eliminating similar experiences in the training process. That is, when a batch of sample data is extracted each time, the matrix as shown in Figure 1 is designed for similarity screening.

Figure 1.

Screening matrix.

While collecting samples for training, the surrounding conditions of the current point are calculated and a 3×3 matrix representing the surrounding obstacles is returned, as shown in Figure 2.

Figure 2.

The matrix that describes the surroundings.

Take the Hadamard product of the two matrices and sum them to get a number. Through experimental verification, when the matrix representing the surrounding obstacles changes, the final result will also change, which indicates that the designed matrix can be used to calculate the similarity of training samples. Through this method, the sample data with high similarity is removed, redundant samples are reduced, and the diversity of samples is retained. This is of great help to the training of agent’s exploration ability.

2.2

Reward function settings

Deep reinforcement learning emphasizes the interaction between agent and environment, adopts the “interaction-trial-error” mechanism, and maximizes the cumulative reward through the interaction updating strategy between agent and environment. Reward is the key for agent to realize strategy update. Improper reward setting or unclear feedback will affect agent’s training effect.

According to the principle that the shorter the path, the greater the cumulative reward, this paper also improved the reward function in the original DQN algorithm, as shown in equation (1).

where a is the length from the position of the agent to the starting point, b is the length from the position of the agent to the target point, and c is the length from the starting point to the target point.

The reason why the reward function is designed in this way is that when the agent takes the action, the length from the position of the agent to the target point will also change. The closer the distance is, the bigger the reward will be, and the farther the distance is, the smaller the reward will be. In this way, the training efficiency of the model is improved and convergence speed is accelerated.

The proposed algorithm flow is as follows.

Step 1: Initialize Replay Buffer D with capacity N, state value model Q and parameter θ, Target Network Q^– and parameterθ^–, and set learning rateα, discount factor γ, degree of explorationε and other parameters.

Step 2: Initialize training environment of the agent, get the initial state s_t, explore randomly and select an action a_t with the probability of ε, or select the current optimal action with the probability of 1-ε, a_t = max_a Q*(ϕ(s_t), a;θ).

Step 3: Perform the action a_t to get a new state s_t+1 and reward r_t, save {s_t, a_t, r_t, s_t+1} in D.

Step 4: Collect training samples from D, remove samples with high similarity, and then train and calculate,

Step 5: The stochastic gradient descent method is used to calculate loss = (y_j – Q(ϕ_j, a_j; θ))²

Step 6: Repeat Steps 2 to 5 to update the Target Network after M steps.

3.

EXPERIMENTAL RESULTS AND ANALYSIS

This paper uses PyCharm development platform and TensorFlow1.x framework for programming. For the sake of illustrate sufficiently that improved algorithm is better than the original algorithm, the training process and training effect are compared.

The improved algorithm eliminates the data samples with high similarity, reduces the similarity of data samples, decreases the redundancy of sample and increases the convergence speed of training. The dashed line represents the result of the original DQN algorithm, the solid line represents the result of the improved algorithm. They are shown in Figure 3.

Figure 3.

Comparison of loss values between our improved DQN and original DQN.

As can be seen from Figure 3, both the DQN algorithm and the improved DQN algorithm have large fluctuation of loss curves at the beginning. DQN algorithm gradually flattens after 300 rounds of training, while the improved DQN algorithm has been flattening after about 200 rounds of training. Obviously, the improved DQN algorithm converges faster.

So as to fully demonstrate the performance improvement of the improved DQN algorithm on path planning, complex environment and simple environment are set up in this paper. In each environment, 20 randomly generated maps are used to test the DQN algorithm and the improved DQN algorithm respectively. Initially, the agent starts from the blue grid in the upper left corner, its destination is the green grid in the lower right corner, and the white grids are the route where the Agent can walk. In the map, 75 black squares representing obstacles are randomly generated. If the agent successfully reaches the target point without encountering obstacles, the path found is drawn. Otherwise, it will fail and the image will not be displayed.

Figures 4 and 5 show the test map and test results of DQN algorithm respectively.

Figure 4.

Test map of DQN algorithm.

Figure 5.

Test results of DQN algorithm.

Figures 6 and 7 show the test map and test results of the improved DQN algorithm respectively.

Figure 6.

Test map of improved DQN algorithm.

Figure 7.

Test results of improved DQN algorithm.

DQN algorithm is tested by using grid map of the same size. After training, its ability of path planning has been greatly improved. Of the 20 test maps, 11 agents successfully reached the target point, with success rate of 55%.

The algorithm in this paper was tested on 20 maps, and 14 agents successfully reached the target point, with success rate of 70%. In the training stage, the algorithm in this paper eliminated the data samples with high similarity, increased the diversity of training samples, and the agent learned more “ability” to deal with complex scenes. The success rate of this algorithm in complex scenes is 15% higher than that of DQN algorithm.

Next, the DQN algorithm and the improved DQN algorithm are tested in a simple environment. The number of obstacles in the simple environment has been reduced to 40. Figures 8 and 9 show the test map and test results of DQN algorithm respectively.

Figure 8.

Test map of DQN algorithm.

Figure 9.

Test results of DQN algorithm.

It is found that the success rate of DQN algorithm in simple map is higher than that in complex environment, reaching 75%.

The improved DQN algorithm was tested on grid maps of the same specification. Figures 10 and 11 show the test map and test results of the improved DQN algorithm respectively.

Figure 10.

Test map of improved DQN algorithm.

Figure 11.

Test results of improved DQN algorithm.

Both the DQN algorithm and the improved algorithm achieve good results in simple environment. The success rate of DQN algorithm for path planning is 75%, and the success rate of the improved DQN algorithm is 90%. The success rate of the improved DQN algorithm is 15% higher than the original DQN algorithm.

4.

CONCLUSION

Aiming at the existing problems of low sample training efficiency and sample redundancy of the original DQN algorithm, sample similarity screening matrix is used in this paper to solve them. The algorithm in this paper optimizes the training mode of data samples by using the designed matrix, eliminates the data samples with high similarity, obtains high-quality sample data, and improves the accuracy of the training model. In the training process, let more useful training samples be used. In addition, the proposed algorithm optimizes the reward function of the original DQN algorithm. The reward function designed in this paper comprehensively considers obstacles and the distance between agent and target point. Agent can plan a closer path while avoiding obstacles.