{'fraction_non_alphanumeric': 0.03238026517543068, 'fraction_numerical': 0.009470551095878056, 'mean_word_length': 4.563472152533868, '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}}
Obstacle Avoidance and Navigation Utilizing Reinforcement Learning with Reward Shaping

In this paper, we investigate the obstacle avoidance and navigation problem in the robotic control area. For solving such a problem, we propose revised Deep Deterministic Policy Gradient (DDPG) and Proximal Policy Optimization algorithms with an improved reward shaping technique. We compare the performances between the original DDPG and PPO with the revised version of both on simulations with a real mobile robot and demonstrate that the proposed algorithms achieve better results.


INTRODUCTION
Unmanned Ground Vehicles (UGVs) and Unmanned Aerial Vehicles (UAVs) are widely used in both civil and military applications. In the civil domain, unmanned vehicles are used for aerial crop surveys, search and rescue, inspection of power lines and pipelines and more. Using UGVs and UAVs for military-based scenarios has multiple benefits including reducing the risk of death by replacing human operators. In this paper, we mainly focus on UGVs.
Navigating UGVs without being trapped by obstacles is an essential problem in both academia and industry. Traditionally, for such a problem, only simultaneous localization and mapping (SLAM) techniques are adopted. It is difficult to apply a single SLAM algorithm or scheme for all different types of environments. Recently, with the success of reinforcement learning (RL) in many applications, it has gained more and more attraction in research. It is natural to use RL to help the autonomous agents, in this case, UGVs, make decisions in complex environments instead of SLAM.
Reinforcement learning is an approach that helps an agent learn how to make optimal decisions from the environment. In general, reinforcement learning is modeled as a Markov Decision Process (MDP) 1 as shown in Fig. 1. Typically, the RL agent takes an action a t following a policy π based on the observation of the state s t and reward r t at time t. Since the action a t is applied in the environment by the agent, the new state changes to s t+1 and a reward r t+1 is assigned to the agent.
With the growth of complex environments, such as UGV applications, combining deep learning and reinforcement learning in continuous action space control has attracted increasing attention, specifically in the robotic control area. Deep Q-Learning (DQN) has been applied in robotic control successfully, however, Q-Learning is designed to deal with the discrete-time decision-making problem. Deep Deterministic Policy Gradient (DDPG) 3 methods have obtained popularity due to successful simulated applications in various robotic control tasks. However, DDPG has been benchmarked on real-world robots and performs more poorly than Proximal Policy Optimization (PPO). 4, 5 Additionally, a new reward shaping technique 6 has been applied in several simulations in OpenAI Gym 7 and was shown to improve the performance significantly in terms of accumulated reward. However, these simulations are not complex enough in reality. In this paper, we apply both DDPG and PPO algorithms equipped with the new reward shaping technique 6 in an obstacle avoidance robotic control problem. Gazebo, ROS, and Turtlebot 3 Burger R are used as a platform to demonstrate the proposed algorithms and compare the performances with/without the improved reward shaping technique when applied to the same real mobile robotic control problem.

State-of-the-art of Reinforcement Learning
There are two main approaches to solving RL problems: methods based on value functions, for instance DQN, and methods based on policy search, such as REINFORCE, 8 PPO and DDPG.
Value function based methods learn the optimal policy indirectly from value functions. For example, in Qlearning, the agent learns from the state-action value function, known as the Q-value, and updates the optimal Q-value in a Q-table as the optimal policy. When the agent completes training, the actions are chosen from the Q-table. The drawbacks of Q-learning include a Q-table exponentially exploding when handling complex tasks. Additionally, Q-learning is not suitable for continuous action tasks. Deep Q-learning solves the huge Q-table issue by embedding a neural network, however, it still suffers in continuous action tasks.
Policy search methods directly search for an optimal policy π * . Typically, a parameterized policy π θ is chosen, whose parameters are updated to maximize the expected reward E[R|θ] using either gradient-based or gradient-free optimization methods.

Deep Deterministic Policy Gradient
Deep Deterministic Policy Gradient 3 is a policy-gradient actor-critic algorithm, which combines Deterministic Policy Gradient(DPG) 9 and DQN, 10 as summarized in Algorithm 1. By applying the actor-critic framework while learning a deterministic policy, DDPG is able to solve continuous space learning tasks. An actor network is used to optimize the parameter θ for the policy and a critic network evaluates the policy generated or optimized in the actor network based on temporal difference (TD). In DDPG, the two target networks are initialized at the start of training, which save the copies of the state-action value function Q(s, a).
DDPG is a breakthrough that enables agents to choose actions in a continuous space and perform well. The main drawback of DDPG is the difficulty of choosing the appropriate step size. A small step size leads to a slow convergence rate, while a large one tends to affect the sampling from the replay buffer and the estimators of the value function, so the policy improvement is not guaranteed and gives a really poor performance.

Proximal Policy Optimization
Before PPO, in order to guarantee policy improvement, Trust Region Policy Optimization (TRPO) 11 introduced KL divergence to measure whether the new policy is better than the average performance of the old policy as an optimization constraint. With the KL divergence constraint, the policy is guaranteed to improve monotonically. However, TRPO is difficult to implement and requires more computation to execute. Initialization: Initialize a random process for action exploration.

7:
for iteration= 1, . . . , T do 8: Select action a t based on current policy, execute a t and observe both reward r t and state s t+1 ;

9:
Store (s t , a t , r t , s t+1 ) in buffer B;

10:
Sample a minibatch of N samples from B;

13:
Update target networks Q and µ simultaneously; whereÊ t [. . . ] denotes the empirical average over a finite batch of samples,Â t is the estimator of advantage functionÂ t := −V (s t ) + r t + γr t+1 + · · · + γ T −r V (s T ), and r t (θ) denotes the probability ratio between current policy and old policy r t (θ) := π θ (at|st) π θ old (at|st) . The KL divergence constraint forbids a drastic update from the old policy to the new policy, PPO applies a penalty to avoid such a huge change. The clipped surrogate objective function is given by: Compared to TRPO, the probability ratio r t (θ) is clipped between [1 − , 1 + ], in practice, we choose = 0.2, which means no matter how good the new policy, the r t (θ) only increases 20% at most.
A t ≥ 0 means the current action performs better than others under a specific state. If the new policy is better than the old one, r t (θ) should be increased so that the better action has a higher probability to be chosen. In contrast, forÂ t ≤ 0, the action should be discouraged and r t (θ) should be decreased.
Note that the loss function of PPO in Eq. 2 is the lower bound of Eq. 1. Also, the computation is reduced due to the KL divergence constraint. The PPO algorithm is summarized as Algorithm 2. Run policy π old in environment for T timesteps; Optimize L CLIP (θ) with respect to θ, with K epochs and minibatch size M ≤ N T .

Proposed Algorithms with Reward Shaping
The drawbacks of reinforcement learning include long convergence time, enormous training data size, and difficult reproduction. A reward shaping technique based on the Lyapunov stability theory 6 accelerates the convergence of RL algorithms. Inspired by such a technique, we implement the reward shaping method in Eq. 3 where η is a tuning parameter that weights the shaped term γR(s t+1 , a t+1 ) − R(s, a). The reward shaping in Eq. 3 has shown to guarantee convergence, preserve optimality and lead to an unbiased optimal policy.
In DDPG, we adopt the reward shaping technique in the actor network based on the TD error, recall TD error := r t+1 + γV (s t+1 ) − V (s t ). After equipping with reward shaping, the new TD error is given in Eq. 4 In PPO, the reward shaping is applied to the estimator of advantage functionÂ t , which is given in Eq. 5

SIMULATION
All the programs are conducted in Python, running on a computer node with Intel Core i5-9600K processor, Nvidia RTX 2070 super, 32 GB RAM, Ubuntu 16.04. We use Gazebo, ROS, and Turtlebot 3 Burger R to demonstrate both DDPG and PPO separately. The training environment set up for demonstrating the obstacle avoidance and navigation task in Gazebo is shown in Fig 2. The 4 white cylinders are the obstacles, the red square is the target for the robot, and the blue lines demonstrate the LiDAR scanning from the robot. Training details are given in Table 1. The state dimension is 26, which contains 24 LiDAR values. The action dimension is 2; one is changing the linear velocity, while the other is changing the angular velocity. The minibatch size we choose here is 32 and the Optimizer is Adam, 12 with learning rate 0.0003, β 1 = 0.9, and β 2 = 0.999. In Fig. 3, we demonstrate the neural network chosen for the PPO algorithm in actor-critic style.

RESULTS
Compareing the two algorithms, PPO is more implementation friendly than DDPG. Fig. 4a and Fig. 4b show the averaged rewards values in DDPG and PPO without any reward shaping technique. In Fig. 5a and Fig. 5b, the averaged reward values are shown for both DDPG and PPO algorithms with the improved reward shaping technique.
We divide the comparison of performance into two parts. First we compare DDPG and PPO, then we compare the effectiveness of reward shaping technique.  Comparing 4a with 4b and 5a with 5b respectively, we see that PPO converges faster than DDPG and has better averaged reward values. Comparing 4a with 5a and 4b with 5b separately, both DDPG and PPO with the reward shaping technique achieve a better performance than the original version. The experimental results are listed statistically in Table 2, where the minimum, maximum and average rewards are provided corresponding to each learning algorithm.

CONCLUSION
In this paper, we consider solving the obstacle avoidance and navigation problem for unmanned ground vehicles by applying DDPG and PPO equipped with a reward shaping technique. We compare DDPG and PPO in the same learning settings. The simulations show that PPO has a better performance than DDPG and the proposed algorithms help RL achieve better results. For future directions, we will investigate PPO applied to multi-agent robots systems and combine SLAM techniques and reinforcement learning to improve the performance.