{'fraction_non_alphanumeric': 0.02251337885218675, 'fraction_numerical': 0.005978962908285662, 'mean_word_length': 4.905841325196164, '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': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Vision Based Deep Reinforcement Learning Algorithm for UAV Obstacle Avoidance

Integration of reinforcement learning with unmanned aerial vehicles (UAVs) to achieve autonomous flight has been an active research area in recent years. An important part focuses on obstacle detection and avoidance for UAVs navigating through an environment. Exploration in an unseen environment can be tackled with Deep Q-Network (DQN). However, value exploration with uniform sampling of actions may lead to redundant states, where often the environments inherently bear sparse rewards. To resolve this, we present two techniques for improving exploration for UAV obstacle avoidance. The first is a convergence-based approach that uses convergence error to iterate through unexplored actions and temporal threshold to balance exploration and exploitation. The second is a guidance-based approach using a Domain Network which uses a Gaussian mixture distribution to compare previously seen states to a predicted next state in order to select the next action. Performance and evaluation of these approaches were implemented in multiple 3-D simulation environments, with variation in complexity. The proposed approach demonstrates a two-fold improvement in average rewards compared to state of the art.


Introduction
Autonomous flight for UAVs (unmanned aerial vehicles) has become an increasingly important research area in recent years. One of the major challenges with autonomous motion planning is ensuring that an agent can efficiently explore a space while avoiding collision with objects in complex and dynamic environments. To resolve this, recent research has turned to applying deep reinforcement learning techniques to robotics and UAVs [1], [2].
Reinforcement learning is a way for an agent to navigate through an environment, interact with that environment and use the observed rewards gained for each action it takes as feedback to optimize a policy. This iterative feedback loop of receiving signals through a sensor to reflect the agents current state allows it to train an optimal policy. Part of the research in this area has focused on employing a single sensor such as a camera [1], [3] to control an agent, while others have focused on combining the signals from multiple sensors [4]. Object detection algorithms have shown tremendous success in the past few years for both detection and segmentation in computer vision. These methods have recently been incorporated with reinforcement learning and applied to UAVs for autonomous path planning [5], landing [2], and obstacle avoidance [6], [7].
The design of a robust learning algorithm to develop the agent's behavioral policy, is challenging. Particularly, when an agent navigates through an environment and learns from the state transitions, it may rarely receive any significant reward or signal from the environment in which to learn from, resulting in a significantly slower learning rate [8]. The Dueling Double Deep Q Network (D3QN) algorithm for obstacle avoidance introduced by [1] uses the -greedy or Deep Q-Network (DQN) approach introduced by Mnih et al. [9] for choosing between exploration or exploitation. That is, either exploring through a stochastic process (exploration) or exploiting the behavioral policy learned so far in order to chose the next action. In the case of -greedy exploration, choosing the next action is done through uniform random sampling, however, this choice may inevitably lead to states that are too similar or redundant to those recently visited and eventually lead to slow learning and significantly inflated training time.
In this work, we focus on solving these challenges with regards to obstacle avoidance for UAVs through improved exploration using only a stereo camera within a simulation environment. The main contributions of this paper are as follows: -Extended D3QN obstacle avoidance algorithm to UAVs from 2-dimension to 3-dimension environments.
-Integrated object detection towards improving depth estimation for obstacle avoidance of static and non-static objects. -Configured and visualized 3 dimensional simulation environments for deep reinforcement learning.
-Introduced the domain network and Gaussian mixture model for guidance exploration which exhibited more efficient learning for complex environments compared to conventional D3QN and convergence exploration.

Related Work
Here, a basic underlying background on reinforcement learning with a Q-network is provided along with milestone studies on DQN for robot exploration with remarks on obstacle avoidance.

Reinforcement Learning for Obstacle Avoidance
Deep Reinforcement learning applied to a UAV agent is a process of training to navigate the UAV through an environment with actions and corresponding rewards. An agent interacts with an environment through a Markov decision process from its current state s t by performing an action a t to transition to a new state s t+1 in order to receive reward r t . Generally, these states are represented as depth prediction images and the size of the reward influences the strength of the signal for which the UAV will alter its behavior policy. For the problem of obstacle avoidance, [1] demonstrated that deep Q-learning as introduced by [15], is effective for robotic navigation in 2-Dimensions. Alternative approaches have been tried including work by Khan et al. [22] provided a model-based approach that estimates the probability that the UAV would have a collision within an unknown environment, allowing for specific actions depending on the certainty of the prediction. However, the generalization of this approach is questionable as the tested scenarios were applied primarily to static obstacles. Additionally, Long et al. [23] worked towards the problem of collision of non-stationary objects by developing a decentralized framework for multiple robots navigating through an environment, although this approach wasn't explicitly tested for UAVs. The usefulness of deep reinforcement learning, specifically DQN for UAVs was articulated by [24], demonstrating the usefulness of combining it with a actor-critic paradigm, that is one that uses two deep learning networks, one for short and long term decision making in order to optimally choose actions as it traverses the environment. The D3QN algorithm introduced by [1] utilized DQN with the dual network approach for obstacle avoidance, which evaluated a state-action pair by its estimated Q-value (Q(s t ,a t )) reflecting its accumulated reward so far, the instantaneous reward of transitioning to the next state s t+1 and its expected future rewards from this new state. Equation 1 shows how state-action values are updated for a Q-network. Where, α is the learning rate and γ is discount factor [13].

Exploration
Making improvements to exploration for deep reinforcement learning algorithms that use the actor-critic paradigm [14] has been actively researched due to the tumultuous nature of environments having sparse rewards such as those for UAVs. Since the inception of the work by Mnih et al. on DQNs [9] various approaches have been explored to make improvements over the uniform random selection of actions (greedy) where the agent takes a random exploratory action with the probability of and exploits the policy otherwise. One of the key insights of improving exploration of an agent focuses on making improvements to the way transitions are sampled from the replay memory. With this insight Schaul et al. [25] showed that partitioning the replay memory according to temporal difference error can assist in the generation of new distributions for state transitions to sample from. This results in a more efficient learning and a faster convergence. Therefore, using a prioritized replay can lead to states that are sparse and seen more infrequent.
Leading to states that are rarer allows the agent a greater opportunity to learn than previously seen states.
Oh et al. [26] demonstrated this in his work, by producing a prediction of the next 100 possible states and choosing an action based on comparison to previously seen states using a Gaussian kernel. Similarly, Gou et al. [8] demonstrated a similar approach that uses an dynamic network to make a prediction for the next state using a multivariate Gaussian. Each demonstrated that a prediction of future states combined with a similarity metric was effective at improving learning efficiency in environments with sparse rewards.

Methodology: Towards Improving Exploration
In this section, we introduce two different exploration approaches with the goal of allowing a UAV to learn an environments dynamics quicker than -greedy exploration resulting in more efficient obstacle avoidance.

Training Setup
The purpose of our experiments is to train a UAV to move autonomously through an environment, while maximizing its flight duration and coverage area of the state space in order to sufficiently learn how to avoid collisions. To this end, we use two simulation environments for our experiments, one simple and one complex. A multi rotor drone model including its navigation, control and physics of its environment are implemented by using AirSim [27]. Typical UAV movement that uses yaw, roll and pitch have convenient methods within AirSim for transformations from inputs such as linear and angular velocity. There are a total of ten actions, two actions affect the linear velocity (v) of the UAV and the remaining actions change its angular velocity (ψ) in 3 dimensions. In our experiments our UAV can move with linear velocity of 1.2 m/s or 0.6 m/s (z-directional) and it can turn in any forward facing direction with an angular velocity of π/6. Figure  2 illustrates the angular velocity actions that it can take from its current state s t .

Fig. 2: UAV Angular Velocity Actions
Our deep learning model operates with two modules. A Policy module for our deep Q-network and object detection model, and an Interaction module for the communication between the agent and the simulation environment. The Policy module is composed of an online network and target network which follow an actor-critic paradigm as [13]. The interaction module receives camera input of an RGB image, processes it with object detection, and uses the resulting bounding box of a detected non-static objects to improve the depth estimation image used by the UAV to learn the environment. This improved depth image is processed through the Policy module to determine an estimated Q(s t , a t ) for each possible action a t in the current state s t . The agent takes the action a t from its current state with the largest Q-value, i.e. argmax a Q(s t , a t ) in order to transition to a new state s t+1 . These state-action transitions (s t , a t , r t , s t+1 ) are saved in a replay memory M , in order to optimize our target network which provides an estimated optimal Q-value that the UAV strives towards. This replay memory saves approximately 5, 000 most recent transitions.  Figure 3 shows how RGB images are pre-processed with bounding boxes of detected objects to modify the depth image received from our stereo camera in order to improve depth estimation of non-static objects (a person in our experiments). By providing the UAV with the illusion that the person is closer than it actually is, it incentives the UAV to learn to change its trajectory away from the person sooner to avoid collision. We assume in our experiments that the person is always ahead of the UAV. The goal of the UAV is to maximize expected future rewards and to do so, it tries to move through the environment as fast as possible while covering as much of the state space as it can without collision. Equation 2 gives the reward function for all the states, except if it is terminal. Each episode terminates, if the UAV collides with an object (reported by the interaction module) or if the agent takes a maximum of 500 steps.
The UAV navigates through the environment as fast as it can by being rewarded based on its distance traveled (v × cos(ψ)). It avoids a person, by being rewarded if the person appears within its field of vision and is too further away from the center (BB distance )in order to incentivise the UAV to turn away from the person. Moreover, the UAV is negatively rewarded the closer it comes to the person by measuring the aspect ratio of the bounding box (BB penalty ), the larger it is the closer the person is and the larger the negative reward will be. If the UAV does collide with an object it receives a reward of −10. The reward function is a heuristic that integrates object detection to improve avoiding obstacles. Therefore, it relies on hyper-parameters (δt, λ, ρ) that must be tuned during training to ensure rewards are adequate and learning is sufficient towards the goals of the UAV. Figure 4 shows the UAV during training.

Convergence Exploration
A fundamental issue with -greedy exploration is that it relies on random chance to choose its next action, many times resulting in an agent falling into a local minimum of repeating the same action for short sighted short-term rewards. To address this, we explore convergence exploration introduced by Masadeh et al. [28] for improving the task of obstacle avoidance. if Explore then Pick a t uniformly at random ; while (y t − Q(s t , a t |θ)) 2 < ζ do Pick a t uniformly at random; end else Pick a t = argmax a Q(s t , a|θ); end Execute a t , observe reward r t ; Transition to state s t using a t and observe reward r t ; In convergence exploration, a state-action familiarity or level of convergence is examined to decide between exploration and exploitation. Two parameter, τ and ζ act as a threshold between exploration time and minimum convergence error for exploitation. If the total training time is T , the agent is forced to explore during a duration of τ , then exploit in remaining time T − τ . During exploration, the parameter ζ checks if the convergence error of taking an action is less than ζ, indicating the action for the current state sufficiently converged. If the algorithm judged that the action has converged, i.e. been sufficiently explored, then another random action will be explored until this new action has also converged. Therefore, the agent can deal with unexplored states and untried actions by iteratively searching over each state action pair resulting in faster learning. Masadeh et al. [28] showed that convergence exploration outperforms -greedy [9] in a discreet 2-Dimensional environment. The full algorithm can be seen in algorithm 1.

Guidance Exploration
The problem of sparse rewards can be resolved in another way rather than convergence and -greedy exploration. Instead, we can utilize a guidance based approach, inspired by [8]. We introduce a new method called domain network to perform a one step ahead prediction of the next state and compare the predicted state with the previously seen states in the replay memory. Subsequently, the chosen action will be the one that leads to the state with the least similarity to the previously experienced states. Our domain network utilizes a CNN architecture inspired by the encoding network introduced by Pathak et al. [29] rather than the dynamic network utilized by Gou et al. [8] and uses a refined similarity measurement between the predicted state and previously visited states. For the similarity measurement, we applied a Bayesian Gaussian mixture in comparison to [8], [26] which utilized a joint multivariate Gaussian and Gaussian kernel respectively.

Algorithm 2: Guidance Exploration
Initialize rank based prioritized replay memory M ; Initialize Online Network Q with random weights θ; Initialize Target Network Q tar with random weights θ tar ; Initialize Domain Network D with random weights θ d ; Initialize goal ; for episode: 1 to E do while Episode is not reset do Explore = True with probability ; if Explore then Sample V from M ; Execute a t = argmin a G(D(s t , a|θ d )); else Pick a t = argmax a Q(s t , a|θ); end Execute a t , observe reward r t ; Transition to state s t using a t and observe reward r t ; M = M ∪(s t , a t , r t , s t+1 ) ; The domain network functions to provide a prediction of the future next state s t+1 from the current state s t . The network's architecture uses a state-action encoding as input into a fully connected feed-forward network to make a prediction of the next state for each available action. The weights of the network are periodically updated from previous transitions, sampled from the replay memory. As suggested by [25], we implemented a rank based prioritized replay memory. Sampling from a rank based memory replay of previously visited states ensures that the sampled states are not as similar to one another, resulting in a wider variation of less redundant states to learn from.
After a prediction of the next state s t+1 by the domain network, it is evaluated for similarity to a sample V of previously visited states. We determine the similarity of the predicted state with the states in V by deriving an estimated probability distribution G from V in order to produce a probabilistic interpretation of the next action our UAV should take. Rather than modeling this distribution as a joint Gaussian with an empirical mean and co-variance for all states in S V such as in [8], we model ours as a Bayesian Gaussian mixture (BGMM) in which each component k of S V has its own mean and co-variance. The Gaussian mixture distribution G of S V is therefore defined as: In our experiments, states are represented as pixels, hence a Gaussian distribution is fit to patches or sub-populations of these states. A Gaussian mixture is useful for modeling sub-populations of previously visited states in a dynamic environment rather than as a joint distribution across all states. Inspiration for using a Gaussian Mixture Model to model the distribution of past states was inspired by related work modeling images to aid in object tracking and tracking [30], [31].

Results and Discussion
The results of the simulation tests for the new exploration algorithms were evaluated based on the goals of the UAV, i.e. cumulative reward and covered area of the environment. To this end, we evaluated the UAV by analyzing how well it performed towards these goals by looking at average rewards and training steps covered over a block of episodes. Here we define a block of episodes as 100 training episodes per block. Moreover, in order to examine how effective these new exploration algorithms were for obstacle avoidance during training, we compared the performance to D3QN introduced by Xie et al [1].
As shown in figure 5, the guidance exploration algorithm out performs D3QN and convergence exploration for each environment in terms of average reward. In each environment, convergence exploration fails to learn an optimal policy faster than D3QN, where as guidance exploration finds an optimal policy sooner. This is likely due to guidance exploration reaching new and unseen states sooner than D3QN and convergence exploration, resulting in learning the dynamics of the environment quicker. Related to this, there are fluctuations of the average reward over the course of the duration of a block of episodes many of which are likely due to the UAV reaching new sections of the environment it either hasn't seen before or frequently enough before to learn sufficiently how to navigate the space. This is especially evident in the complex environment in figure 5b between episodes 1200 and 1500. After the environment is sufficiently explored, the UAV learns a more robust optimal policy and continues to accumulate reward.
Moreover, the results of the average reward of the complex environment is more significant than the simple environment. In the complex environment you can clearly see from figure 5b that early on that the guidance exploration algorithm is trending towards a more optimal policy sooner than the simple environment in figure 5a. One possible explanation could be that the simple environment is smaller, with less objects to collide and interact with. Therefore it is a more predictable environment such that alternative exploration  approaches aren't as beneficial compared to those with larger state spaces and even sparser rewards as is the case with the complex environment. Additionally, convergence exploration failed to learn both environments as shown in figure 5. In 2dimensional environments with discrete states, convergence-exploration was able to outperform DQN [28], however it fails to adapt to 3-dimensional environments with larger state spaces in comparison to duel deep q-networks such as D3QN and guidance exploration. Convergence exploration tends to be biased towards exploration in early stages of training until full convergence of each action is completed. Therefore, a low rate of exploitation of best actions tends to lead to poor performance during training.  The primary goal of the UAV is to explore as much of the state space as possible, for as long as possible. The UAV stops only if it collides with an object or if it reaches 500 steps and has converged during the duration of a training episode. Therefore, to evaluate how well our algorithm is tending towards this goal we evaluate the training steps taken over the course of episode blocks in figure 6.
Each environment demonstrates again that guidance exploration outpaces D3QN and convergence exploration towards the goal of exploring more of the state space. For the complex environment, one can infer from figure 6b that guidance exploration is trending towards less collisions and a significantly higher convergence rate in comparison to D3QN. Particularly for the last 100 episodes, the agent with guidance exploration policy takes and average of 350 steps per episode prior to termination when the number of steps taken for the agent with D3QN is an average of 50. This same effect is present in the simple environment but less pronounced.
An interesting observation of convergence exploration is that its steps taken and hence states explored is significantly lower than D3QN in the simple environment (figure 6a), but higher in the complex environment ( figure 6b). However, the average reward is lower in the complex environment for later episode blocks for convergence exploration as seen in figure 5b. This could be due to the algorithm learning a policy which results in lower reward but takes significantly more actions that tend towards navigating as fast as possible through the environment.
Overall, guidance exploration demonstrates nearly double the performance compared to D3QN and convergence exploration in the complex environment and roughly one and a half times the performance in the simple environment. As noted by Xie et al [1], the benefit of D3QN was to aid in the overestimation of Q values inherent in the original DQN architecture and that improving exploration may not alleviate this issue. However, given the performance of these other exploration approaches, it appears that an agent making a more refined exploration choice early on does lead to faster convergence towards an optimal policy.
The reward function presented here, is a heuristic based on goals that are defined for the UAV. The specific heuristic introduced in section 4 has hyper-parameters for the distance traveled (δ), bounding box distance (λ) and aspect ratio (ρ). These hyper-parameters reduce our ability to generalize our approach of incorporating object detection with deep reinforcement learning since applying our UAV towards other tasks could require a different reward function would need to be derived and tuned so that it tends towards those new objectives in an scalable way.
The exploration approaches were compared to the D3QN obstacle avoidance algorithm since it is one of the most recent state-of-the-art algorithm for this task. Since our algorithms improve exploration that eventually propagates to more robust exploitation for the class of deep q-network algorithms, it is easier to infer performance against DQN [9] and DDQN [14] if we compare to D3QN for obstacle avoidance. This is due to Xie et al. visualizing and comparing the performance gains against these algorithms in [1].
The early exploration choices of guidance exploration showed significant improvements in future episodes, however improvements to the dynamic network's structure and prediction capabilities might be one area that could be explored further, as also suggested by [8]. Additionally, the sub population distribution of previous states in the priority replay memory may not be as appropriately estimated by a Gaussian mixture model as expected. An alternative distribution might be a more appropriate model of these previously visited states.

Conclusion
Application of artificial intelligence on a UAV system is a challenging process for obstacle avoidance, object detection, and self-learning have to be implemented with fine adjustments. Especially, reinforcement learning algorithm faces many limitations in 3-dimensional environment due to increasing number of states. We presented an improvement on the exploration algorithms to enhance the performance of the reinforcement learning framework in large state-space in multiple 3-D simulation environments. As an immediate application, vision based navigation of a UAV in a complex environment containing a moving object, was demonstrated with a higher performance compared to the existing algorithms. In such cases, where the locations and orientations of the UAV can collectively create an uncountable pixel based state-space, the traditional exploration algorithms may fail in completing the task. The convergence exploration and guidance exploration methods were evaluated based on average rewards and number of steps taken per episode.
Overall, our simulation results demonstrated that guidance exploration outperformed -greedy exploration and convergence exploration. In the complex environment, the guidance exploration leads up to 200% improvement in terms of average reward, and demonstrated significantly faster convergence in comparison to the state-of-the-art exploration algorithms. In similar environments, the proposed framework can result in a policy which allows for substantially larger amount of steps in contrast with the conventional obstacle avoidance algorithms that lead to collision in almost every episode.
Experiments of different exploration approaches results in faster learning, however, there is still room for improvement to stabilize the performance in case of exploration in more complex and dynamic environments. Additionally, exploring other real time object detection and tracking approaches such as incorporating additional and different non-static objects, different architectures and reward function changes will be investigated in the future. Moreover, we plan to apply our algorithms to a real UAV trained with a smaller number of episodes in order to gauge how significant improved exploration is to yielding more robust exploitation.