Deep Reinforcement Learning based Automatic Exploration for Navigation in Unknown Environment

According to the historical observation, this module chooses the goal point where the robot should move to. In this paper, the module input is the map of surroundings built by the mapping module. The decision module is modeled as

where $g_{t}$ is the goal point, $l_{0:t}$ are the robot positions from time 0 to $t$, and $m_{t}$ is the built surroundings map at time $t$. There are several efforts focused on figuring out the function $f_{decision}$, most methods are based on the frontier methods and with the heuristic search. Those methods are required to establish massive rules for complex environments, which results in heavy dependencies on expertise.

In this paper, we will mainly focus on finding out the more concise and the general function $f_{decision}$. We propose a DRL-based decision method in the next section. Compared to the frontier-based method, our method learns the visual feature for exploration automatically. Instead of stacking the rules for exploration, our method learns the feasible strategy from trial and error and cover more complex scenes.

This module aims to ascertain the feasible trajectory from the current position to the goal point. The planning module is modeled as

where $\tau_{t:t+T}$ is the planning trajectory for robot control. The widely-investigated framework for many planning approaches which implement the planning function includes the global planning method and the local planning method. The aim of the former is to determine the shortest path from the current position to the goal position on the map, and the latter attempts to convert the path to a trajectory and adjust the trajectory based on the real-time sensor data. It should be mentioned that recent studies related to the planning module have shown different frameworks. Those particular methods modeled as deep neural networks take the sensor data and goal point as the input and build the mapping from the input to the control.

Considering that $A^{*}$[25] is a simple and efficient search method, we apply $A^{*}$ as the global planner. The results of $A^{*}$ search is a path composed of the discrete points. And the path cannot control the robot directly. We employ timed-elastic-band(TEB) method[26] as the local planner which convert the path to the robot velocity. Compared to the pure tracking, this method can avoid obstacles which are not in the built map(such as moving objects) according to the real-time point cloud from light detection and ranging(LiDAR).

Mapping module processes the sensor data in sequence and produces the robot pose and surroundings map at each timestamp, which is also known as SLAM. The function of the SLAM can be written as

Here $u_{t}$ and $z_{t}$ are the control and observation at time $t$, respectively. The major SLAM methods can be divided into two categories: filter-based methods and graph-based methods. Filter-based methods make use of Kalman filter or expand Kalman filter to update the estimation of the robot and landmark(map) pose. Graph-based methods collect the control and the observation to construct a pose graph and take advantage of nonlinear optimization to estimate the robot pose. Moreover, Parisotto[27] proposed a neural SLAM method which exploited deep neural network fitting the function $f_{mapping}$.

We utilize a graph-based method named Karto SLAM. It is simple to implement and works well in most scenes. Compared to the filter-based method, the graph-based method can diminish the error and obtain the extract solution consistently. Therefore, more and more papers focus on graph-based methods recently[17].

In this paper, we place great emphasis on constructing the DRL algorithm for the decision module to implement efficient exploration. Compared with traditional decision methods, the DRL-based decision algorithm can eliminate trivial details of complicated rules. Different from end-to-end methods, the approaches based on this framework have a higher degree of modularity, and it is more flexible and interpretable.

The objective of the robot exploration is to build an environment map which is most similar to the real environment. Considering the battery capacity, the robot is designed to select a shorter path to explore the environment. Then, we give the following objective function

Here $\hat{m}$ is the estimation map, $m$ is the real map, and $L(\cdot)$ is the path length during exploration from $t=0$ to $t=T$.

However, since the actual map is non-available due to the unknown environment, it is hard to handle the objective function and find the minimum solution. Inspired by the Shannon entropy for evaluation of the exploration[2], we exploit the occupancy grid map to represent the environment. Note that $p(m_{i,j})$ is the occupied probability of the cross grid of $i$-th column and $j$-th row. Each grid has three possible states: unknown, free and occupied. And the entropy of the map is

This objective function evaluates the uncertainty of the built map.

We take exploration as a sequence decision-making task. A Markov decision process defined as a tuple $<S,A,T,R,\gamma>$ is a framework for decision making. $S$ denotes a finite set of states. $A$ is the set of the actions that the agent can take. $T(s^{\prime}|s,a)$ is the transform distribution over the next state $s^{\prime}$ given the agent took the action $a$ with the state $s$. $R(s,a)$ is the reward the agent receives after taking action $a$ in state $s$. $\gamma$ is the discount factor. The goal of the agent is to maximize the expectation of long-term cumulative reward $V(s)$

RL is an intelligent method for robot control[28]. Q-learning is a popular method to learn an optimal policy from samples generated from interactions with the environment. The key to Q-learning is calculating the Q-value function which evaluates the action took in the state. And the optimal Q-value obeys the Bellman optimal equation as follows

Since this optimization problem is nonlinear, it is difficult to obtain the analytic solution. The common iterative method for this problem is the value iteration as follows:

Note that recent advances in DL have facilitated investigation of feature extraction. Mnih et al.[7] took a deep neural network as a function approximation for Q-value function and trained the networks by minimizing the mean squared error(MSE)

where $(S_{t},A_{t},R_{t+1},S_{t+1})$ are sampled from the experience replay buffer collected by the agent. This DQN algorithm achieved a huge success in many games such as Go, Atari, etc.

Recently, many researchers introduce DQN algorithm for robot navigation. Most of them apply the original sensor data as the algorithm inputs, such as point clouds of LiDAR[29], images[30][31][32][33]. With the powerful representation of deep neural networks, these methods can extract key features without expert experiences. Nevertheless, compared to the empirical features, the original sensor data has a higher dimension which increases state space sharply. From this perspective, the agent has to take massive trial and error to cover all the potential state-action combination, which takes a long time. In view of the safety and lifetime of the real robots, it is impossible to take the extensive trials in the real environment. Hence, most researches trained the agent in a simulated environment. However, there are two common problems in transferring the virtual agent into a real agent. First, since the error functions of the sensors are different between virtual and real environment, It is hard to guarantee the good generalization of the DRL algorithm from virtual to real. Second, due to the mechanical error, it is uncertain that the real robots will have an excellent performance with the control law learned in a virtual environment.

As discussed above, we introduce the hierarchy decision framework in the last section. We separate the decision module from the planning module. Decision module provides the next goal point. And planning module plans the path from the current position to the goal point. In this way, the control policy derived from the traditional optimal control has a good match with the real robot.

In this section, we aim to design a novel DRL algorithm for decision module. The input of the decision module is a map, current and historical robot positions obtained from the mapping module. We obtain the optimal decision sequence

Therefore, we can define the reward function for exploration as follows

where $\alpha$ is coefficient to make the training process more stable.

In view of the safety, we attach the heuristic reward function such as

To stop the exploration in time, we introduce the terminal action and define the reward for this action

Remark 1: The target of automatic exploration is to build the map of the unknown environment based on the navigation and mapping technique. Note that the logic of reward signal is designed based on the safety and efficiency. As the robot cannot confirm the dangerous status of the unknown space which may be the obstacle, wall and so on. Therefore, a penalty signal is given to encourage the robot to choose next goal point in the free space. Besides, we hope the distance from the goal point to the obstacles will be larger than the robot geometrical radius in consideration of collision avoidance. Combined with the designed efficient exploration logic, the robot can find out the safety and efficient policy in unknown environment. It should be mentioned that the ratio $\rho$ is a hyperparameter to balance the explored region rate and explored efficiency. Here we choose it as 0.85 based on experiments

The action of exploration is selecting a point from the built map. Since we utilize the occupancy grid map, the action space is discrete. To simplify the problem and reduce the searching space, we exploit rasterized sampling on the grid map. And the action space is composed of these sampling points. Figure 2 describes the occupancy grid map and the action space for the proposed algorithm.

Since the points in action space are obtained from regularly sampling, we can design a convolutional neural network to estimate the value of each point in the map. The designed network architecture is shown in Figure 3. The lower layers are encoder layers where the output dimension is the same as action space.

To estimate the Q-values, we construct a network named fully convolutional Q-network(FCQN) based on two convolutional branches after encoder layers. The one applies convolution to calculate score map which has the same size with encoder feature maps. Each element of the score map represents the advantage function of the corresponding point in action space. The other exploits max-pooling operation to collect the feature vector of the whole map. Subsequently, the fully connection layer estimates the advantage value of the terminal action and the state value. The Q-value of each point action is derived from [34]

The terminal action Q value is

Compared with original DQNs architecture, our network makes several significant improvements. One the one hand, the FCQN is more accessible to train and has less overfitting risk due to the fewer parameters. The original DQNs employs fully connected layer after flattening feature maps and introduces massive trainable parameters. By contrast, the FCQN only has several convolutional kernel parameters. The fully connected layer in original DQNs needs the inputs to have the same dimension, which restricts its adaptability for various size environment. On the other hand, since the fully convolutional network accepts the different size inputs, the FCQN has better adaptability for changeable map size. Those properties make our network more convenient to train in a new environment continuously.

Compared with the empirical features, putting the map image as the input of DRL increases the search space rapidly. The agent needs more time to analyze every possible state-action combination, which increased difficulties in the training process.

Some researchers proposed auxiliary tasks by enhancing prior knowledge to improve training efficiency. Mirowski et al.[22] implemented depth prediction and loop closure prediction as the auxiliary task to improve the performance and training efficiency of DRL algorithms. Lei et al.[20] trained the deep convolutional network with classification task and then exploited this network to extract the features for the RL. The feature input drastically reduces the state dimension and exploration time instead of the original image input. Unfortunately, these features are usually not the task-oriented, there is no guarantee for the quality of the features.

Considering the crucial roles of the map edge in navigation and exploration, we present the edge segmentation as the auxiliary task for FCQN. Note that the edges composed of two elements. One is the contour of obstacles which is essential for avoiding the collision during navigation. The other is the boundary between free space and unknown space. This boundary is named frontier employed to produces the candidate points.

The third branch for segmentation appended in the network architecture as shown in Figure 3. And we call the whole network with segmentation branch as AFCQN (fully convolutional Q-network with an auxiliary task). We apply the decoder block which consists of twice deconvolution after lower feature maps. The output of this branch has the same dimension as the input map. The loss function for this branch is

where $p$ represents the pixel in the map, and $M$ is the set of the possible classes. In this case, $M$ includes 3 types such as the contours of the obstacle, frontiers, and others. $y_{o,c}$ is the binary indicator if the class label $c$ is the correct classification for observation $o$. And $p_{o,c}$ means that the predicted probability observation $o$ is of the class $c$.

Therefore, the lower convolutional layers update the parameters by two-part back-propagation error.

where $\epsilon$ and $\lambda$ are the learning rate and the balance parameter for the segmentation task, respectively. $w$ is the parameter of lower convolutional layers. These analytical procedures and the results are described in the next chapter.

To compare the performance of different algorithms, we define the explored region rate, average path length and exploration efficiency.

Explored region rate embodies the completeness of the map built during exploration. It is defined as

With the high explored region, we hope the agent move efficiently. Therefore, the average path length and exploration efficiency are introduced.

Where $L_{\tau_{i}}$ is the path length of the trajectory $\tau_{i}$ during $i$-th episode.

In general, a larger explored region rate leads to a longer path. So the larger explored region rate and shorter path are inconsistent. Exploration efficiency represents the entropy reduced per unit length. And it is a compromise metric for exploration.

We construct the simulation platform based on the Stage package[37] of robot operation system(ROS) for agent training. We create a virtual map for algorithms training and design the maps with different layouts and sizes for testing. Figure 5 and the Table I show the details of the maps. The kinematic model of the agent is omnidirectional, which can go left or right without rotation.

We conduct the training process on the training map. The inputs of the algorithms are the combined images including the grid map, the current position map, and the last position map. The position map draws the robot position on the blank map which has the same size as the built map.

Figure 6 shows training processes. The returns grow during the training episodes and converging to the stable value. We can see that FCQN learns faster than DQN, but the final return is slightly smaller than DQN. The possible reason for this appearance is that DQN has more parameters than FCQN and better ability to remember complex decision sequences. Since AFCQN uses more information to find out the optimal parameters, AFCQN has a better performance in convergence speed and final return.

Figure 7 describes the number of explored grids and the path length during the training episodes. From the pictures, we find out the edge segmentation task speeds up the exploration. AFCQN learns the safe strategy for movements and increases the path length quickly. However, the segmentation task also brings redundant movements which do not increase the new free cells. With the iteration of Q-values, the algorithm crops the redundant movements and achieves the better return.

To compare the trained algorithms in the training map, we conduct 50 trials by selecting initial points randomly from free space. Results are shown in Table II. All algorithms finish the exploration completely on the training map. And AFCQN has highest explored region rate while FCQN has highest exploration efficiency. The reason for high explored efficiency for FCQN is selecting the terminal action in time which avoids redundant movement. AFCQN has more attention on the completeness of the built map, which leads to the longer path. For most trials, DQN has a higher explored region rate than FCQN. But it fails in some cases. Figure 8 shows the comprehensive performance. The curve means that the proportion of the episodes which achieve the specified explored region rate within 25 meters. According to the figure, we see AFCQN has a better performance than others. And FCQN has a stable performance, where its explored region rate distributes around 0.8. Except for failed cases, the explored region rate of DQN distributes around 0.9.

In order to analyze the generalization of the algorithms, we design the test maps different from the train map. Considering the constraint of the stand DQN caused by the fully connected layers, we design two maps(test map 1 and test map 2) as shown in Figure 5 with the same size but different layouts with the train map. Our algorithms based on fully convolutional layer adapt well to variant map sizes. In addition, we design the two maps(test map 3 and test map 4) with different sizes with the train map. We test our algorithms on these maps. And the results are shown in Figure 9.

According to Figure 9, all algorithms have good generalization on the test maps which have different layouts from the train map. AFCQN has the highest explored region rate in test map 1 and FCQN follows. AFCQN and FCQN have the same explored region rate in test map 2 while FCQN has a less standard deviation. In addition, FCQN has a shorter path length. FCQN has a better performance than DQN. Compared to results in the training map, AFCQN has a higher explored region rate and the less explored region rate standard deviation than others in test maps.

Since the fully connected layers of DQN restrict its output dimension, DQN has poor adaptability for different size maps. Note that AFCQN and FCQN make use of fully convolutional layers instead of fully connected layers. They can address different size maps and adjust the output dimension adaptively with keeping a downsampling rate for generating action space. In this part, we compare the difference between AFCQN and FCQN. Although the layout and size are different from the train map, our proposed algorithms work well in new environments. AFCQN has a higher explored region rate. But FCQN has a higher exploration efficiency. The changes of layout and scale increase the standard deviation of explored region rate.

From the above two groups of experiments, AFCQN and FCQN are better than DQN in all maps. The layout of the map has an influence on the algorithms. Comparing the test map 1 and test map 2, we can find the common feature between the training map and test map 2. That is they both have many rooms and “doors”. And the layouts of the test map 1 and 3 are relatively spacious. With this special feature, FCQN has better performance in exploration efficiency. The reason for this result is that FCQN can end the exploration in time and has shorter exploration path. Note that we add the edge segmentation as the auxiliary task, AFCQN focus on the completeness of the built map(since AFCQN has higher explored region rate) and has longer exploration path which leads to lower exploration efficiency. In spacious environments such as test map 1 and test map 3, the exploration strategy is simple than in crowded environments such as test map 2 and training map. This means that it is easier to complete exploration. And AFCQN can detect the completeness of the built map and end the process in time. FCQN need more step to confirm the finish. These results show that AFCQN has better ability to detect the completeness of the built map.

Since AFCQN takes the edge segmentation as the auxiliary task, we further analyze how this task affects the decision of AFCQN. In the frontier-based methods, the frontiers which are the boundaries between free space and unknown space are the decision candidates, so we compare the decision process of AFCQN to frontier based methods. Figure 10 describes the process.

In the early decision stage, the valuable decision positions distribute around the frontiers. With expanding of the map, the frontiers speed out. AFCQN learns intuition for maximizing the increasing free cells. In step 5, the algorithm selects the center of frontiers in the left part of the map. It is more efficient than selecting a center of any frontier. In step 6, there are two frontiers on the map. The upright frontier is the candidate which increases more free grids. The upleft frontier will increase a few free grids but closer to the current position. It can be seen that AFCQN selects the upleft point firstly and the upright point secondly. This strategy is better than selecting the upright firstly for considering the completeness and the whole path length. After step 8, AFCQN selects the terminal action to stop exploration.

We also compare AFCQN to the frontier-based method. Figure 11 shows the results on the 4 test maps. The frontier-based method achieves a higher explored region rate. Since the decision point of this method is selected from frontier centers, it explores the environment continually until there are no reachable points. In other words, it usually has a long path. Although AFCQN is inspired by the built map edges, it estimates the status of the whole maps in order to select the terminal action in time. Therefore, AFCQN has higher exploration efficiency in the first three test maps.

Figure 12 presents the stability of the algorithms. With constraints of the distance, the frontier-based method is better than AFCQN. However, the frontier-based method also faces with some special cases which make exploration fail. We explain one case in Figure 13. Lidar receives the point cloud and renders to grid map. The frontier-based method detects the frontiers shown as red grids and calculates the center represented by a green ball. Unfortunately, the robot is standing at this center point, then it stops the exploration. Since the inputs of AFCQN include the robot current position and last decision position, this case never happens during conducting AFCQN method.

Since our algorithm output is the decision point instead of the robot control, it is easier to transfer to the physical robot. We employ the DJI Robomaster robot platform shown in Figure 14. The major components include the gimbal and the chassis. The chassis equips with mecanum wheel for omnidirectional movements. We fixed an RPLidar which has similar properties with simulated LiDAR on the chassis for mapping. Then, we test our algorithm with the platform in the real environment.

Here, we show the results of the physical world experiment to the simulated world. The simulated map and built real world map are shown in Figure 15. Due to the difference in sensor errors and environments, the observations of their experiments are different. Table III shows the comparing results. Frontier-based methods have highest explored region rate in both the physical world and simulated world. However, our proposed method AFCQN has best explored efficiency, since our method monitor the completeness of the built map and stop the exploration in time. It is obvious that the distinction between the two observations impacts the explored region rate. DQN is sensitive of inputs and fails to explore the physical world for several times. For other methods, the variances of the explored region rate are same. Those differences have no effect on exploration path length. The variance of the path length is decided by the local planner. And we have different local planner parameters for simulation and real experiments in order to adapt the different kinematic models. To explain AFCQN behaviour, the exploration trajectories of AFCQN in the trails are shown in Figure 16. The most trajectories of the real experiments overlap with those of the simulation experiments. And the results imply that the decision processes of the two experiments are similar.