{'fraction_non_alphanumeric': 0.03616727941176471, 'fraction_numerical': 0.008961397058823529, 'mean_word_length': 4.784423179160021, 'pattern_counts': {'":': 0, '<': 0, '<?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': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Off-road Autonomous Vehicles Traversability Analysis and Trajectory Planning Based on Deep Inverse Reinforcement Learning

Terrain traversability analysis is a fundamental issue to achieve the autonomy of a robot at off-road environments. Geometry-based and appearance-based methods have been studied in decades, while behavior-based methods exploiting learning from demonstration (LfD) are new trends. Behavior-based methods learn cost functions that guide trajectory planning in compliance with experts' demonstrations, which can be more scalable to various scenes and driving behaviors. This research proposes a method of off-road traversability analysis and trajectory planning using Deep Maximum Entropy Inverse Reinforcement Learning. To incorporate vehicle's kinematics while solving the problem of exponential increase of state-space complexity, two convolutional neural networks, i.e., RL ConvNet and Svf ConvNet, are developed to encode kinematics into convolution kernels and achieve efficient forward reinforcement learning. We conduct experiments in off-road environments. Scene maps are generated using 3D LiDAR data, and expert demonstrations are either the vehicle's real driving trajectories at the scene or synthesized ones to represent specific behaviors such as crossing negative obstacles. Different cost functions of traversability analysis are learned and tested at various scenes of capability in guiding the trajectory planning of different behaviors. We also demonstrate the performance and computation efficiency of the proposed method.


I. INTRODUCTION AND RELATED WORKS
Terrain traversability analysis is a fundamental issue to achieve the autonomy of a robot at off-road environments. At such scenes, many methods for urban streets are not adaptive as there is no pavement or lane marking, no curb or other artificial objects to delimit road and no-road region, terrain surface is formed by natural objects that may have complex visual and geometric properties, etc. An extensive review of the challenges and literature works is given in [1]. LiDARs and cameras have been used as the major sensors of online traversability analysis, where the mainstream methods are divided by [1] into geometry-based and appearance-based ones.
Geometry-based methods generate a geometric representation of the world first using LiDAR or depth data, then assess traversability by comparing the geometric features such as height, roughness, slope, curvature and width with the vehicle's mechanical properties [2][3] [4].
Appearance-based methods assume that traversability is correlated with terrain appearance, and many learning-based approaches have been developed [5] [6]. In order to improve far-field capability, methods are developed using underfoot or   near field data to self-supervise the learning [7] [8]. Recently, deep neural networks are also employed to model the procedure [9][10] [11], where in order to solve the problem of data annotation, semi-supervised learning methods are developed by incorporating the weakly supervised labels such as the vehicles' driving path. Behavior-based method is a new trend in this field, which is inspired by the development of learning from demonstration (LfD) and promising results in recent years [12]. Mainstream algorithms in LfD area can be approximately divided into two classes, Behavior Cloning (BC) [13][14] [15] and Inverse Reinforcement Learning (IRL) [16] [17]. Behavior Cloning directly learns a mapping from observation to action while IRL recovers the essential reward function behind expert demonstrations. Although earlier IRL algorithms use simple linear reward functions [16][17] [18], deep neural networks reward structures [19] [20] are proposed later to model high-dimensional and non-linear process. Compared with handcrafted cost and supervised-learning methods, IRL has better robustness and scalability [21]. Recently, deep maximum entropy IRL has been used to learn a traversable cost map for urban autonomous driving [22] [23], and vehicle kinematics has also been considered in [24] by converting history trajectory into new data channels, which are integrated with scene features to compose the input of a CNN based cost function. However in these works, vehicle kinematics is not incorporated in the forward reinforcement learning procedure, and the methods of value iteration and state visitation frequency estimation have poor efficiency.
This research proposes a method of off-road traversability analysis and trajectory planning using Deep Maximum Entropy Inverse Reinforcement Learning. Novel contributions are that we encode vehicle kinematics into convolution kernels and propose two novel convolutional neural networks (RL ConvNet and Svf ConvNet) to achieve efficient forward reinforcement learning process, which solves the problem of exponential increase of state-space complexity. Experiments are conducted at off-road environments using real driving trajectories and synthesized ones that represent specific behaviors as demonstration. Results validate the performance and efficiency of our method. This paper is organized as follows. The proposed methodology is described in Section.II. Experimental results are shown in Section.III. Finally, conclusion and future works are given in Section. IV.

II. METHODOLOGY
As illustrated in Fig. 1, this research proposes a deep inverse reinforcement learning framework for analyzing offroad autonomous vehicle traversability and planning trajectories, which incorporates kinematics and employs RL ConvNet and Svf ConvNet for efficient computation.

A. Problem Formulation
We formulate the process of autonomous vehicles navigating through off-road environment as Markov Decision Process(MDP), which can be defined as a tuple (S, A, P, γ, R), where S denotes state space of the scene, A denotes action set of the autonomous vehicle, P denotes state transition probabilities, γ ∈ [0, 1) denotes discount factor and finally R denotes the traverse reward. Let C be traversability costs, R = −C, where the lower the costs, the higher the rewards.
Given demonstration samples set D = {V i , ξ i } 1:N D , where at scene V i , the vehicle is driven through trajectory ξ i by a human expert. A trajectory ξ is a sequence of stateaction pairs {(s 1 , a 1 ), ..., (s T , a T )}, where actions a t are taken sequentially at states s t . The reward value R(ξ) of a trajectory ξ is simply the accumulative rewards (or negative costs) over all states that the trajectory traversed.
Let f θ be a function to evaluate traversability cost C of a certain scene V with features φ(V), C = −R = f θ (φ(V)). Following Wulfmeier et al. [22], we use grid maps to represent φ(S), C and R, and a fully convolutional neural network(FCN) for f θ with a parameter set θ. It is assumed that human expert trajectories are intending to maximize rewards gain or minimizing traversability costs.
Our goal is to learn a parameter set θ for f θ from expert's demonstrations, so as to guide an autonomous agent to plan trajectories in similar ways as human drivers.

B. Maximum Entropy Deep IRL
Under the maximum entropy assumption, probability of a trajectory ξ is estimated below, where trajectories with higher reward values are exponentially more preferrable [17]. Z is an integral term which is usually referred to as partition function.
Given demonstration samples set D, learning θ can be formulated as maximizing the following log-likelihood problem.
Let µ D and µ E denote the state visiting frequencies of human expert drivers' policy and optimal policy recovered from reward function respectively, where µ D is approximated from human demonstration samples, while µ E is estimated by solving the MDP. According to Ziebart et al. [17] and Wulfmeier et al. [22], optimizing θ is conducted by backpropagating the following loss gradient.
Hence, given the current parameter set θ, the following steps are taken at each iteration for optimization. The processing flow is as follows.

C. Incorporating Vehicle Kinematics
However, the following problems remain. First, vehicle kinematics is non-holonomic. Incorporating non-holonomic constraints is vital to plan trajectories which are physically operational by vehicles. Second, traditional value iteration and state visiting frequency estimation are time-consuming. Especially, incorporating kinematics comes with more state .N. Q i j and π i j denotes Q maps and stochastic policy maps corresponding to orientation κ j and action a i respectively. E[µ(κ j )] and E[µ(κ j , a i )] denotes state visiting frequency for orientation κ j and orientation-action pair (κ j , a i ) respectively.

Algorithm 1 Value iteration (Original method)
Input: reward R, transition probability P Output: optimal stochastic policy π 1: Initialize: for a ∈ A do 5: end for 9: end for 10: π(a|s) = exp(Q K (s, a) − V K (s)) dimensions, resulting in an exponential increase in computation complexity.
Tamar et al. [25] proposed a convolutional network structure for value iteration process, where previous value V i−1 and reward R are passed through a convolution layer and max-pooling layer, each channel in the convolution output represents the Q function of a specific action, and convolution kernel weights corresponds to the discounted transition probabilities. Thus by recurrently applying a convolution layer K times, value iteration is efficiently performed with significant reduction of computation costs.
Inspired by the idea, we propose RL ConvNet and Svf ConvNet for both incorporating vehicle kinematics and achieving efficient computation at the same time.
1) RL ConvNet: We consider modeling kinematic constraints of vehicles' orientation. Let A = {a 1 , ..., a N } and K = {κ 1 , ..., κ M } be set of vehicles' discrete actions and orientations respectively. We assume that the vehicles' orientation constrains vehicles' state transition probability under a certain action, hence a set of convolutional kernels {P i j } N ×M is defined,

Algorithm 2 Computing expected state visitation frequency (Original method)
Input: stochastic policy π, transition probability P, initial state distribution D(s) Output: expected state visiting frequency µ E 1: Initialize: end for 6: end for where P i j is a kernel with the weights corresponding to the discounted transition probabilities after taking action a i under orientation κ j . To handle the exponential increase of computation complexity coming with incorporating kinematics in states without explicit performance degradation, we constrain the transition probability of vehicle orientations to be deterministic. More specific, we define the function g(κ, a) : K×A → {1, 2, ..., M }, where g(κ, a) represents the next step vehicle orientation index after taking action a under current orientation κ. For convolution purpose, grid maps are employed to represent V, Q, π for value, Q and policy functions, and a grid pixel corresponds to a 2D location at the scene. Let V j be a value map for vehicle orientation κ j , where for any pixel s, V j (s) is the expected maximal value starting from the location s with orientation κ j . Q and π are defined in similar ways, which are related to both vehicle orientation and action. Let Q i j and π i j be a Q and a policy map of vehicle orientation κ j and action a i , where for any pixel s, Q i j (s) is the expected long-term reward and π i j (s) is the stochastic policy probability if action a i is taken when the vehicle is at the location s and orientation κ j . Hence the original value iteration algorithm can be converted end for 10: end for 12: end for 13: to Algorithm 3, which incorporates vehicle kinematics and accelerates computation through convolution. As is illustrated in Fig. 2(a), for a particular orientation κ j , each V g(κj ,ai) , i = 1, ..., N is passed first through a convolution layer with kernel P i j corresponding to orientation κ j and action a i , then through a pixel-wise addition layer with R to estimate Q i j . All Q i j s of orientation κ j are then passed through a Softmax layer to obtain updated V j . These operations iterate K times until V j converges. Since then, a sequence of policy maps {π i j }, i = 1, ..., N are estimated corresponding to the particular orientation κ j and each of the actions a i , which are matrix operations. These operations are conducted for the V j of each a particular orientation κ j , j = 1, ..., M , hence a set of policy maps {π i j } N ×M are obtained corresponding to each pair of κ j and a i .
2) Svf ConvNet: State visiting frequency is also represented as a grid map. Let E t [µ(κ j , a i )] be orientation-action state visiting frequency, where each pixel value is the expected frequency that action a i is taken under current orientation κ j at the corresponding 2D location. Similarly, E t [µ(κ j )] denotes the expected state visitation frequency for vehicle orientation κ j , which is simply sum of orientation-action state visiting frequency. Denote as pixel-wise multiplication of two grid maps, E t [µ(κ j , a i )] is calculated as follows: Hence the original algorithm of computing expected state visitation frequency can be converted to Algorithm 4, which incorporates vehicle kinematics and computes efficiently through convolution. Fig. 2(b) illustrats the workflow. For any particular orientation κ j , policy π i j of action a i and orientation k j is passed through a multiplication layer with E t [µ(k j )]. The resultant orientation-action state visiting frequency grid map is then passed through a convolution layer with kernel P i j to obtain σ(κ j , a i ). All σ(κ x , a y )s, x = 1, .., M and y = 1, .., N Algorithm 4 Svf ConvNet Input: stochastic policy π i j , transition probability P i j , initial state distribution D(κ), function g(κ, a) Output: expected state visiting frequency µ E 1: Initialize: E 1 [µ(κ)] = D(κ) 2: for t = 1 : T do 3: for j = 1 : M do 4: are passed through a weighted multiplication layer to find updated orientation state visiting frequency E t+1 [µ(κ j )]s, where the weights are I g(κx,ay)=j .

III. EXPERIMENT A. Experimental Design and Dataset
As shown in Tab Data collection is conducted at off-road environments using an instrumented vehicle shown in Fig.3(a). The vehicle has a Velodyne HDL-64 LiDAR to map scene features, a GPS/IMU system to capture expert's driving trajectories, and a front-view monocular camera for visualization only.
We generate a dataset where each frame has a scene map, a demonstration trajectory crossing the scene, a start and a goal point which are defined by the trajectory points that enter and leave the scene. The scene map is a 100 × 100 2D grid one with a resolution of 0.25 meters. It is generated using LiDAR data and each grid is assigned the height value of the highest LiDAR points projected to the cell. The whole dataset has a total of 2388 scene maps, and the expert's real driving trajectories are used as the demonstrations for Exp.1 and Exp.2. Assume that we have a vehicle of stronger mobility and the expert chooses to cross all or some of the negative obstacles for efficiency. We use the real scene maps of negative obstacles, but synthesize demonstration trajectories in compliance with the defined behaviors of Exp.3 and Exp.4. There are 320 frames of straight and flat road scenes in Exp.1 and trained a cost function F onroad . There are 320 frames of negative obstacle scenes but trajectories demonstrating different behaviors in Exp.2, 3 and 4, and trained cost functions F avoid−obs , F cross−obs1 , F cross−obs2 respectively. The rest scenes are used for testing, where the focus is the comparison of different cost functions and the planned trajectories at the same scene. Illustration of part of transition convolutional kernels used in experiment. "+/-" represents forward/backward.

1) State, Action Space and Transition kernels:
In our implementation, state is the current 2D position of the vehicle in the scene map. We use discrete actions and orientations shown in Fig. 4. The orientation is discretized into eight directions with 45 degrees as interval to cover the full range. The actions are simplified to be combinations of steering angle(-45, 0, 45 degrees relative to current orientation) and driving forward or backward. The transition kernels corresponding to orientation κ 1 are illustrated in Fig. 4.
2) Network and Training Configuration: In the experiment, we adopt a simple five-layer fully convolutional network (FCN) structure which takes processed lidar feature map as input. We use size 5 × 5 and 3 × 3 for convolution kernels in FCN. As for RL ConvNet and Svf ConvNet, we set the number of value iterations K to 150 and number of svf iterations T to 120, which are experimentally observed to execute effective reinforcement learning process and svf computation. The network is trained with the Adam optimizer with initial learning rate 1e-4 and learning rate decay 0.99. The batch training is also employed with batch size 5, which proved in practice more stable than updating weights based on a single demonstration.

C. Training Results
The training process visualization is shown in Fig. 5. During the training process, we periodically evaluate the expert's trajectory reward and policy's trajectory reward using Eqn. 1. Average discounted cumulative reward of 30 trajectories randomly sampled from learned policy by simulation is used. As is shown in Fig. 5(a), the loss value decreases and tend to converge after 200 iterations. Expert's and policy's rewards are getting higher while policy reward is a little lower than expert's. Samples of expert's demonstration trajectories are shown in Fig. 5(b) while policy generated trajectories at different training stages are shown in Fig. 5(c)-(e). One can explicitly find that as iterations increase, similarity between expert's and policy's trajectories is becoming higher, which validates that learned reward guides trajectory planning successfully in compliance with human's behavior. More visual evaluation results of our four experiments can be found in Fig. 6. Four learned cost maps all successfully capture the high traverse cost feature of positive obstacles(i.e., trees or bushes) but differ in the assessment of negative obstacles(pits on the road). Demonstrated by human drivers' avoid-negative-obstacle trajectories, Exp.2 learns that negative obstacles have higher cost compared with flat roads. Exp.3 and Exp.4 have opposite results given cross-negative-obstacle trajectories as demonstration. Negative obstacles in cost maps of Exp.3 and Exp.4 have relatively lower costs compared to flat roads, resulting in cross holes behavior of planned trajectories. One interesting fact is that the result of Exp.4 assigns lower costs to holes than Exp.3, showing more preference for negative obstacles.

D. Testing Results
Visualization of testing results on different scenes are shown in Fig. 7. We demonstrate the learning capability and scalability by comparing the behavior of trajectories generated by different learned cost functions. As shown in Fig. 7, F onroad fail to handle scenes where negative obstacles exist and planned trajectories cross them. On opposite, by demonstrating avoiding obstacles behavior in Exp.2, F avoid−obs shows good performance under these scenes and successfully avoids negative obstacles. By comparison, F cross−obs1 and F cross−obs2 show strong learning capability as they produce cost maps that assign low traverse cost to negative obstacles. Compared to F cross−obs1 , F cross−obs2 assigns much lower cost to negative obstacles since it is demonstrated by trajectories more preferable for them. The results show that our method has a strong learning capability of different behaviors and is scalable to different scenes.
To evaluate the accuracy of replicating human behavior, we use the Hausdorff Distance (HD) [?] as our metric. The

E. Computation Efficiency Analysis
We choose average time of two stages(i.e. RL and Svf) spent on each sample as comparison metric. In our proposed method, Algorithm 3 and Algorithm 4 are used for RL stage and Svf stage respectively, while Deep IRL uses Algorithm 1 and Algorithm 2. Note that calculating optimal policy and replanning happens at every input sample. The experiment is conducted on an Intel Xeon E5 CPU and an NVIDIA TiTanX GPU. Results are shown in Tab. III. Compared to Deep IRL, our method using only CPU takes longer time and this time can be furthermore decreased by using GPU. However, please note that Deep IRL doesn't consider kinematics at all and has a much smaller state-action space than ours. We consider kinematics and meanwhile achieve relatively efficient computation by utilizing convolution.

IV. CONCLUSION AND FUTURE WORKS
A method of off-road traversability analysis and trajectory planning using Deep Maximum Entropy Inverse Reinforcement Learning is proposed. A major novelty is the efficient incorporating of vehicle kinematics. Two convolutional neural networks, i.e., RL ConvNet and Svf ConvNet, are developed that encode vehicle kinematics into convolution kernels, so as to solve the exponential increase of statespace complexity problem and achieve efficient computation in forward reinforcement learning. Results of conducted experiments demonstrate that the learned cost functions are able to guide trajectory planning in compliance with the expert's behaviors and the method has scalability at various scenes. The proposed method achieves improvements on trajectory prediction performance, meanwhile the computation time does not significantly increase. In future work, more extensive experimental studies will be conducted, and improvement on the accuracy of kinematic kernel will be addressed.