{'fraction_non_alphanumeric': 0.03632247601027166, 'fraction_numerical': 0.009528314637113124, 'mean_word_length': 4.763777994157741, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
TERP: Reliable Planning in Uneven Outdoor Environments using Deep Reinforcement Learning

We present a novel method for reliable robot navigation in uneven outdoor terrains. Our approach employs a novel fully-trained Deep Reinforcement Learning (DRL) network that uses elevation maps of the environment, robot pose, and goal as inputs to compute an attention mask of the environment. The attention mask is used to identify reduced stability regions in the elevation map and is computed using channel and spatial attention modules and a novel reward function. We continuously compute and update a navigation cost-map that encodes the elevation information or the level-of-flatness of the terrain using the attention mask. We then generate locally least-cost waypoints on the cost-map and compute the final dynamically feasible trajectory using another DRL-based method. Our approach guarantees safe, locally least-cost paths and dynamically feasible robot velocities in uneven terrains. We observe an increase of 35.18% in terms of success rate and, a decrease of 26.14% in the cumulative elevation gradient of the robot's trajectory compared to prior navigation methods in high-elevation regions. We evaluate our method on a Husky robot in real-world uneven terrains (~ 4m of elevation gain) and demonstrate its benefits.


I. INTRODUCTION
Autonomous mobile robots have increasingly been used for many real-world field applications such as indoor and outdoor surveillance, search and rescue, planetary/space exploration, large agricultural surveys, etc. Each of these applications requires the robot to operate in different kinds of terrains, which can be characterized by visual features such as color and texture, and geometric features such as elevation changes, slope, etc.
A robot's stability, which includes its pitch and roll angles being within certain limits, is predominantly dictated by the elevation changes/unevenness and slope of the terrain [1]. For reliable navigation, robots need to identify unsafe elevation changes and plan trajectories along planar regions to a large extent. However, sensing and navigating in uneven unstructured environments can be challenging because we do not have a complete model of the terrain with all the elevation information [2], [3]. Rather this information is gathered using camera or LiDAR sensors as the robot navigates. In addition, elevation changes cannot be adequately inferred only from visual features of the environment [4]. Prior works have addressed this by using grid-based data structures such as Octomaps [5] and elevation maps [6], which are 2D grids that contain the maximum elevation (in meters) at each grid.
Many other techniques have been proposed in the outdoor domain including semantic segmentation-based perception methods [7], [8], [9], [10], and Deep Reinforcement This work was supported in part by ARO Grants W911NF1910069, W911NF2110026 and U.S. Army Grant No. W911NF2120076. We acknowledge the support of the Maryland Robotics Center. 1   (elevation gain ≥ 3m) using four different methods: our method TERP (pink), Ego-graph (orange), DWA (Blue) and velocities from the end-to-end Attn-DRL method (violet). TERP computes an attention mask to highlight reduced-stability regions for navigation, which are then used to compute and update navigation cost-maps continuously (e.g., cost-map computed at the robot's start location is shown in the top left) , with the unsafe regions where the robot's pitch and roll angle could exceed the stability limit are highlighted in yellow and red (superimposed on the terrain). TERP then generates waypoints (pink points) that are dynamically feasible and reachable by locally least-cost paths. Other methods navigate through unsafe regions with high elevation gradients which could lead to unstable robot orientations. TERP leads to trajectories with low elevation gradients (26.14% lower than prior navigation methods), leading to higher rate of reaching the goal (35.18% increase).
Learning-based navigation methods [11], [12]. Semantic segmentation methods in this domain typically classify terrains in images based on whether they are traversable for a robot [7], [8], [9] by learning the visual features corresponding to the color and texture of different objects. However, they are trained using human annotations which may not be suitable for all types of robots with different dynamic constraints. Therefore, a terrain that is traversable for a robot could be misclassified as non-traversable. As a result, navigation methods that use these segmentation methods for perception could be overly conservative for robot navigation and may result in sub-optimal trajectories [13].
DRL-based navigation approaches [14], [15], have been used for robot navigation in crowded scenes with dynamic obstacles. However, they are mostly limited to navigation on flat surfaces and do not account for varying elevation in outdoor terrains. Moreover, these DRL methods are typically trained using simulations and may face performance degradation in real-world environments [14]. Such methods also cannot provide any optimality guarantees on the robot's trajectories.
Main contributions: We present TERP (Terrain Elevation-based Reliable Path Planning), a novel method for navigating a robot in a reliable and stable manner in uneven outdoor terrains. That is, our approach identifies unsafe regions (with high elevation gradients) and computes least-cost waypoints to avoid those regions. Our overall approach uses a continuous stream of local elevation maps, robot pose, and goal-related vectors as inputs. The novel components of our approach include: Block Attention Module (CBAM) [16] and a reward function to learn appropriate terrain features in the local elevation map that indicate reduced-stability regions in the environment. The Attn-DRL network is primarily used for perception. After training, for any given input frame, we extract an attention mask from an intermediate feature vector in the Attn-DRL network. Our attention mask is not biased by human annotations and leads to an increase of 31.9% in the success rate for reaching the goal in high-elevation environments compared to not using attention, and a decrease of up to 75% in cumulative elevation gradient of the robot's trajectory. • A 2D navigation cost-map computed using the extracted attention mask and a normalized elevation map of the environment. Our cost-map encodes a certain region's degree of planarity i.e., a measure of whether the robot's pitch and roll angles will be within safe limits, without the risk of flipping-over. Using the attentionbased navigation cost-map leads to a 35.18% higher rate of reaching the goal in high elevation terrains when compared to prior methods. • A method to compute waypoints on the cost-map that are dynamically feasible (i.e., satisfying the kinodynamic constraints of the robot) and reachable by locally least-cost trajectories. These trajectories are used as inputs to DWA-RL [17], a navigation scheme that computes dynamically feasible collision-free robot velocities. Our formulation results in a decrease in the Cumulative Elevation Gradient (CEG) of 26.14%. Decoupling perception to Attn-DRL network, and navigation to DWA-RL leads to improved overall performance, as compared to using one end-to-end network approach. (see Fig. 1 and Fig. 5). Our overall formulation has significantly lower execution times (takes one-fourth the time) than a state-of-the-art segmentation method [7] and, guarantees that the robot's trajectories are locally least-cost and dynamically feasible. We point the reader to [18] for a detailed version of our work.

II. RELATED WORK
In this section, we discuss existing work on identifying terrain features and robot navigation on uneven terrains.
Recent methods have also constructed 3D maps, identified dynamic obstacles for unstructured scene navigation [27] and in walkways [28]. Due to the advent of deep neural networks (DNN), classification techniques have been used for terrain understanding [29], [30], [31], with some methods using robot-ground interaction data to train DNNs [32]. Most of the visual features extracted by DNNs and external geometric features can vary significantly from one environment to another. Hence, elevation estimation methods were introduced to generalize the terrain understanding problem.
Recent studies such as [12] highlight the importance of terrain elevation data to perform robust outdoor navigation tasks. [33] presents a method to perform terrain semantic segmentation and mapping using point clouds and RGB images for an autonomous excavator. In our work, we utilize an elevation map of the environment computed using point clouds from a 3D LiDAR.

B. Robot Navigation on Uneven Terrains
Early works in uneven terrain navigation addressed it using binary classification (obstacle vs. free space) [34], a continuous obstacle space [35], or potential fields [36] for high-speed rough terrain navigation.
Recent developments in deep learning have led to motion planners with high-dimensional input processing capabilities [11]. For instance, [37], [38] have incorporated on-board sensory inputs and prior knowledge of the environment to estimate navigation cost functions or cost-maps. In [39], a nonlinear geometric cost function has been trained to imitate human expert's behavior in uneven terrains. Similarly, an energy-cost model was proposed in [15] to generate energyefficient robot paths on rough terrains.
Numerous end-to-end DRL methods have also been proposed for uneven terrain navigation [12], [40], [41]. These methods have used perception inputs such as elevation maps, the robot's orientation, and depth images to train an A3Cbased network [40] or have used RGB images and point clouds to train a multi-modal fusion network [41]. In [4], the effectiveness of zero to local-range sensing was compared using a rainbow DRL-based local planner. All the aforementioned DRL methods were trained and tested only on simulated uneven terrains. Hence, transferring such methods into a real robot while maintaining comparable navigation performance can be challenging [14]. In our method, we decouple perception (to Attn-DRL network) and navigation to two separate modules (see Fig.2). This ensures that our method's real-world performance is comparable to its simulation performance.

III. BACKGROUND A. Notations, and Definitions
We highlight the symbols and notation we use in Table I. For our formulation, we consider a differential drive robot mounted with a 3D LiDAR with a range of r sense , and a 360 • field of view. We assume that the robot's start and goal locations are in stable regions i.e., the robot's roll and pitch angles are within a safe limit. We use 2D elevation maps (E t ) (from processed point cloud data) obtained from a 3D LiDAR. E t (i, j) denotes elevation value at the (i, j) grid coordinate (see Fig. 4). All 2D data structures in our work (E t , E t N , A t , C t ) are regarded as n × n matrices or grids with the robot located at the center. We transform the indices (i, j) such that the robot's position corresponds to Distance between the robot and its goal α goal Angle between the robot's heading direction and the direction to the goal α relative Angle between the robot's current location and the goal w.r.t. the robot's start location g Goal location relative to the robot φ, θ Roll and pitch angles of the robot

B. Deep Reinforcement Learning
Our Attn-DRL network is based on the Deep Deterministic Policy Gradient (DDPG) algorithm [42] combined with Convolutional Neural Network layers and CBAM [16] (see Section III-C). We choose DDPG because it uses an actor-critic network, which leads to stable convergence to the optimal policy compared to policy-based or value-based methods. We briefly describe the input and action spaces of our DRL network here and our network architecture and reward function in Section IV. The perception input consists of a 2D normalized elevation map E t N (see Equation 3). The robot pose and goal related inputs include d goal , α goal , α relative , |φ|, |θ|, and the elevation gradient vector h in the robot's heading direction, defined as follows: where ∇ denotes the gradient operation resulting in an n × n G matrix and G(n/2 : 1, 0) denotes all the values in rows n/2 to 1 in the 0 th column (according to our indexing conventions). Our Attn-DRL network is end-to-end with its action space being a linear and angular robot velocity pair. Although DRL methods are useful for training certain robot behaviors in simulations, their performance degrades when transferred to real-world scenarios. In addition, the velocities computed by the end-to-end DRL network cannot guarantee dynamic feasibility or optimality (in terms of any metric). Therefore, we choose not to use the output velocities from Attn-DRL, and instead decouple perception and navigation. We use Attn-DRL purely for perception by extracting an attention mask from an intermediate feature vector F ref in the network (see Section IV-B.1 and Fig.  3), and then computing a navigation cost-map. Computing waypoints and robot velocities for navigation is performed in a separate module (see Fig. 2).

C. Convolutional Block Attention Module
To highlight reduced-stability regions in the environment's elevation map, we use CBAM, a light-weight attention module that can be integrated with any CNN architecture [16]. Given a feature vector (say an output of a CNN) with a certain number of channels, CBAM sequentially applies Fig. 2: TERP's overall system architecture. We extract an attention mask from the Attn-DRL network continuously for each frame of the input and compute the navigation cost-map. Our architecture decouples perception and navigation to different modules instead of using an end-to-end DRL network, resulting in improved performance. It also ensures that our method performs comparably in both simulated and real-world environments. The advantages of this formulation are highlighted in Section V-D.
attention modules along the channels and then along the spatial axis (different parts on the feature vector) to obtain a refined feature vector (see Fig. 3). This leads to our Attn-DRL network learning the features in the elevation map that are relevant for reliable navigation.

IV. TERP: TERRAIN ELEVATION-BASED ROBOT PATH PLANNING
We explain the three major stages of our method: 1. training the Attn-DRL network and extracting the attention mask, 2. computing a navigation cost-map and 3. generating locally least-cost trajectories.

A. Normalized Elevation Map
We use existing software packages to process raw point cloud data from a 3D LiDAR and obtain an n×n local elevation map E t around the robot. We employ nearest neighbor interpolation to interpolate values for missing points based on nearby points.
A robot with higher ground clearance c can navigate through higher degrees of unevenness than a robot with lower ground clearance. We account for this difference by computing a normalized local elevation map as, Otherwise. (3)

B. Computing Attention Masks
We use E t N and the other input vectors (Section III-B) to train the Attn-DRL network. We explain its novel network architecture and the reward function used for training in simulated environments.
1) Network Architecture: Our network architecture (Fig.  3) has two branches. On the first branch, we use a 2D convolutional (conv-) layer of dimensions 40 × 40 × 8 to process the input normalized elevation map (with n = 40). This outputs a feature vector with eight channels, which are passed on to the channel and spatial attention modules sequentially. Then, the channels are passed through another conv-layer. The channel and spatial attention modules weigh the features in the different channels and locations in each channel to identify reduced-stability regions relevant for reliable navigation. The resultant output is a refined feature vector (F ref ) with dimensions 40 × 40 × 8, which is finally passed through a dimension reduction conv-layer. On the second branch, we concatenate the other inputs (d goal , α goal , α relative , |φ|, |θ|, and h vector) to obtain a 1D vector of size n/2 + 5 (25 in this case). This is processed using a fully connected layers of dimensions shown in Fig. 3. The outputs from the two branches are concatenated through several fully connected layers to finally obtain the robot's linear and angular velocities (which are used only for training and comparison). We use ReLU activation in the hidden layers and tanh activation at the output layer.
2) Reward Functions: The reward function is used to shape the velocities of the end-to-end attn-DRL network during training, i.e., to reward desirable and penalize undesirable robot actions/velocities. This in turn trains the intermediate feature vectors (such as F ref ) in the network to learn features that are relevant for reliable navigation (leading to high rewards). The total reward collected by the robot for performing an action at any instant is given as, Here, the different β are the weighing factors for the different reward components. R dist and R head , are the penalties for the robot moving away from its goal. They are defined as, The novel terms of our reward function are R stable and R grad which encourage the network to learn features to maintain the robot's stability and avoid regions with high elevation gradients. R stable is the reward for the robot maintaining stability (having low roll and pitch angles), and R grad is the penalty for heading in a direction with a high elevation gradient. They are defined as, where w is a weight vector with weights in ascending order, and h is the heading gradient vector defined in Equation 2. The w vector weighs elevation changes that are closer to the robot higher than the ones farther away.
3) Attention Mask Extraction: As mentioned in Section III-B, we extract an attention mask A from the refined feature vector F ref . Since F ref 's different channels are already weighted by the channel and spatial attention modules, the attention mask can be obtained by an unweighted summation along the channels. This is, The attention mask weighs elevation changes in the direction the robot is moving or turning higher than all other directions. This is depicted in Fig.4(b), where the attention mask corresponds to the normalized elevation map presented in Fig.4(a). The robot turns to its right to head towards its goal, and the high elevation changes on the right are highlighted in the attention mask.

C. Computing Navigation Cost-map
Since the normalized elevation map and the attention mask represent the environment's elevation values and the weights for the different regions at a time instant t, we utilize them to compute a navigation cost-map as, represents element-wise multiplication. The computed costmap is shown in Fig.4(c). To completely avoid certain high-cost regions while navigating (costs higher than a certain threshold C max ), we perform the following operation.
(9) C max is set not only based on the elevation in a region, but also on the robot's maximum torque capabilities. Therefore, all regions not reachable by the robot are assigned infinite cost.

D. Computing Least-cost Waypoints
Consider a local cost-map C t and a goal location g that lies outside it. Choosing least-cost waypoints (some index (i, j)) inside C t (i, j) that lead the robot towards its goal is non-trivial. This is because the robot operates without any global knowledge of the environment. In addition, the chosen waypoint must be safely reachable by the robot. To address this, we formulate the following method.
Given a robot with its goal at g, we consider an approximate circle C explore in C t centered at the robot with a radius r explore < r sense . Next, we consider an arc A t 1 on the circumference of C explore that makes an angle of γ explore at the center with the goal vector g bisecting it (see Fig.4(d)). We use all locations (i, j) ∈ A t 1 as candidate waypoints. We then choose the set of least-cost waypoints as, Here, for cost((i, j)) is the cumulative cost of navigating to (i, j) from the robot's location (0, 0) in the cost-map by trajectories computed by Dijkstra's algorithm [43]. If multiple index locations exist in L t min , we choose the waypoint by transforming it to real-world coordinates (see Equation 1) as, In the highly unlikely event that L t min = ∅ (implying all trajectories have infinite cost), we expand the arc A t 1 to A t 2 , which makes an angle of 2 · γ explore at C explore 's center. We then consider (i, j) ∈ A t 2 \ A t 1 as candidate waypoints and repeat the procedure.
When the terrain is planar, the robot can safely have a larger exploration circle and choose waypoints on its circumference. This significantly reduces the number of waypoints that need to be computed before reaching the goal. Therefore, r explore is formulated as a function of the costs within the circle as, ; ∀i, j ∈ C explore .
(12) where k 1 and k 2 are constants. If the costs within C explore are low (implying a planar surface), the formulation expands the radius.
Proposition IV.1. Our method always navigates the robot in a dynamically feasible trajectory with a low cumulative elevation gradient locally.
Proof. This result follows from the fact that the waypoints computed using Equation 11 are reachable with the least trajectory cost locally. In addition, since our cost-map has infinite costs for regions that are unsafe and unreachable based on the robot's torque requirements, such regions are guaranteed to be avoided while computing trajectories.

E. Dynamic Feasibility
We use DWA-RL [17] to compute robot velocities to follow the least-cost trajectory computed by Dijkshtra's algorithm. DWA-RL guarantees that the velocities are collisionfree and obey the robot's kinodynamic constraints. Therefore, the robot can also avoid collisions with dynamic obstacles in the environment. Fig. 2 shows how the components in our method are connected. Our approach decouples perception to our DRL network with the attention modules and the navigation to our local waypoint computation and DWA-RL. This architecture leads to superior performance and guarantees least-cost waypoints and the dynamic feasibility of the final velocities.

V. RESULTS AND ANALYSIS
We explain our method's implementation in simulations and on a real-world robot. We then explain our evaluation metrics and discuss our inferences.

A. Implementation
Our Attn-DRL network is implemented in Pytorch. We use simulated uneven terrains with a Clearpath Husky robot created using ROS Melodic and Unity game engine to train the Attn-DRL network. The simulated Husky robot is mounted with a Velodyne VLP16 3D LiDAR. The network is trained in a workstation with an Intel Xeon 3.6 GHz processor and an Nvidia Titan GPU.
We replicate the simulated robot's setup on a real Husky robot. In addition to the LiDAR, the robot is mounted with a laptop with an Intel i9 CPU and an Nvidia RTX 2080 GPU.
We use the Octomap [5] and Grid-map [44] ROS packages to obtain the elevation map E t of size 40 × 40 using the point clouds from the Velodyne ROS package. Our network is computationally light enough to run real-time on the laptop along with the aforementioned ROS packages.

B. Evaluation Metrics
We use the following metrics to compare our method's navigation performance with the Dynamic Window Approach (DWA) [45], the ego-graph [46] method used in [4], and our end-to-end Attn-DRL network (without decoupling perception and navigation). The ego-graph method uses a cost function based on α goal and the terrain's cumulative elevation gradient along a set of local trajectories to find the minimum cost trajectory. We add a distance-to-goal cost to this cost function and use it for additional comparison (ego-graph+). Success Rate -The number of times the robot reached its goal while avoiding reduced-stability regions and collisions over the total number of attempts. Cumulative Elevation Gradient (CEG) -The summation of the elevation gradients experienced by the robot along a trajectory (i.e., ||∇z rob ||, where ∇z rob represents the robot's elevation at any time instant). Normalized Trajectory length -The robot's trajectory length normalized using the straight-line distance to the goal for both successful and unsuccessful trajectories. Goal Heading Deviation -The cumulative angle difference between the robot's heading and the goal along a trajectory (i.e., where t goal is the time to reach the goal).

C. Testing Scenarios
We evaluate our elevation based navigation framework and compare it with prior methods in four scenarios(see Fig.5).
• City-curb -A city environment with curbs higher than the robot's ground clearance that it must avoid.

D. Analysis and Comparison
The results are shown in Table II. We observe that all the methods perform well under low and medium elevation conditions in terms of success rate. However, TERP displays significant improvement in successfully reaching goals in highly-elevated environments. This is due to TERP's ability to navigate through the locally least-cost waypoints even (h) real-world medium-elevation with obstacle regions;. For the real-world scenarios, we show four trajectories corresponding to the aforementioned colors. We observe that TERP computes trajectories with low elevation gradients in uneven terrains and is capable of handling challenging curb scenarios.  under high elevation conditions. Our end-to-end Attn-DRL method tries to plan trajectories along low-cost regions even though the minimum cost cannot be guaranteed. Hence, the success rate is lower and the CEG is higher than our TERP method. DWA sometimes avoids the high-elevations in front of the robot by treating them as obstacles. However, when the robot reaches an elevated terrain, DWA cannot recognize the elevations to avoid during navigation. In contrast, egograph-based methods select the optimal navigation velocities based on the front elevation gradients. These methods cannot maneuver the robot along the minimum-gradient trajectory because they have a discretized action space.
The CEG values in Table II imply that our method attempts to reach the goal by following the least-cost waypoints, which eventually result in minimum elevation gradi-ents along the trajectory. However, this could lead to longer trajectories and higher deviations from the goal direction than other methods. The results in Table II validate that TERP can achieve better success rates while maintaining comparable trajectory lengths.
We observe that navigating in a city environment with curbs higher than the robot's ground clearance is a challenging task for all the methods. Comparatively small elevation gains of the curb regions could possibly lead to erroneous trajectories. However, TERP with attention outperforms all the other methods in terms of success rate (113% improvement w.r.t ego-graph) by attending to the critical elevation gradients near the curb (see Fig. 5b and f).
Ablation Study for the Attention Module: We compare navigation performance of TERP with and without the attention module. TERP without attention utilizes input elevation maps as the cost-map to find least-cost waypoints. Hence, trajectories generated by this approach select waypoints based on the locally minimum elevations. In contrast, TERP with attention follows the least-cost waypoints by attending to spatially critical elevation changes along the robot's trajectory (see Fig. 4c). Hence, the attention module improves the robot's spatial awareness to perform safe navigation tasks (See CEG in Table II, yellow and pink paths in Fig. 5).
Computational Complexity: We compare TERP's execution times with GANav [7], a state-of-the-art semantic segmentation method. TERP is computationally light enough to perform in real-time with execution times between 0.08-0.1 seconds (10-12.5Hz), while GANav takes 0.32-0.39 seconds on the same processing hardware.
Decoupled vs. end-to-end: Based on the end-to-end Attn-DRL network's trajectories in simulation (Fig. 5a to 5d) and in the real-world ( Fig. 1 and Fig. 5e to 5h), we observe a significant degradation in performance. In contrast, TERP exhibits similar performance in both cases. Additionally, TERP also guarantees least-cost dynamic feasible waypoints, while the end-to-end network cannot.

VI. CONCLUSIONS, LIMITATIONS AND FUTURE WORK
We present a novel formulation to reliably navigate a ground robot in uneven outdoor environments. Our hybrid architecture combines intermediate output from a DRL network with attention with input elevation data to obtain a cost-map to perform local navigation tasks. We generate locally least-cost waypoints on the obtained cost-map and integrate our approach with an existing DRL method that computes dynamically feasible robot velocities. We validate our approach in simulation and on real-world uneven terrains and compare it with the other navigation techniques on various navigation metrics.
Our framework has a few limitations which we expect to address in the future. The effective sensing point cloud percentage can be low especially near steep ditches due to the low reflectance of the LiDAR's rays. In such cases, additional depth sensors need to be integrated to achieve better perception. In addition, boundaries between different surfaces may not be sensed by the elevation map. Using a fusion of RGB image data and point clouds could help address this problem.