Drone coverage using deep reinforcement learning

UNIVERSIDAD DE SEVILLA FACULTAD DE MATEM ´ ATICAS DEPARTAMIENTO MATEM ´ ATICA APLICADA II Drone coverage using deep reinforcement learning Alina Kasiuk UNIVERSIDAD DE SEVILLA FACULTAD DE MATEM ´ ATICAS DEPARTAMIENTO MATEM ´ ATICA APLICADA II Drone coverage using deep reinforcement learning Alina Kasiuk Memory presented as part of the requirements to obtain a Master’s degree in Mathematics from the University of Seville. Supervised by: Prof. Dr. Jos´ e Miguel D´ ıaz B´ a˜ nez November 2020 Seville, Spain Abstract UAVs (Unmanned Aerial Vehicles) or drones have long been used to autonomously operate on a terrain and many strategies have been proposed when the environment is unknown. When the drone is tasked with a path planning problem in a unknown terrain, it must be able to correctly perceive its environment online and plan its path without human supervision. Particularly, covering or patrolling of a specific area has been a challenging optimization problem in robotics. This work addresses a particular covering task in unknown outdoor environments in which the drone has a limited power. The agent has to return to a base station when it is running out of battery. The problem is then to generate an optimal path that starts and ends at a base station and covers the target area through several tours. A covering planner based on Deep Reinforcement Learning is proposed where a Deep Q-network is trained to learn a control policy to approximate the optimal strategy at each step. Simulation results showed that the algorithm is able to learn and generalizes well to different types of environments. After multiple sequences of the training process, the virtual mobile drone gets information of the whole space with a coverage rate of over 80%. The experiments also demonstrate that the drone finds a trajectory balancing the goals of safe recharging and maximum coverage ratio. Resumen Los UAV (Veh´ ıculos A´ ereo no Tripulados) o drones se vienen utilizando desde hace tiempo para operar de forma aut´ onoma en un terreno y se han propuesto muchas estrategias para cuando el entorno es desconocido. Cuando el dron se le encomienda una tarea de planificaci´ on en un terreno desconocido, debe ser capaz de percibir correctamente su entorno en tiempo real y planificar su camino sin supervisi´ on humana. En particular, cubrir o patrullar un ´ area espec´ ıfica ha sido todo un desaf´ ıo en el campo de la optimizaci´ on en rob´ otica. Este trabajo aborda una tarea de cobertura en entornos exteriores desconocidos en los que el dron tiene un tiempo de vida limitado. Por lo tanto, el agente tiene que regresar a una estaci´ on base cuando se est´ a quedando sin bater´ ıa. El problema es generar un camino ´ optimo que comience y termine en una estaci´ on base y cubra el objetivo usando para ello varios recorridos. En esta tesis se propone un planificador de cobertura basado en el aprendizaje reforzado profundo (Deep Reinforcement Learning) donde se usa un aprendizaje de una pol´ ıtica de control para aproximar la estrategia ´ optima en cada paso. Los resultados de la simulaci´ on mostraron que el algoritmo es capaz de aprender y generaliza bien a diferentes tipos de ambiente. Despu´ es de m´ ultiples secuencias del proceso de entrenamiento, el dron m´ ovil virtual obtiene informaci´ on de todo el espacio con una tasa de cobertura del 80%. Los experimentos tambi´ en han demostrado que el dron es capaz de encontrar una trayector´ ıa equilibrando los dos objetivos planteados: recarga segura y ratio de cobertura. Acknowledgements Throughout the writing of this thesis I have received a great deal of support and assistance. I would first like to thank my thesis advisor, Prof. Dr. Jos´ e Miguel D´ ıaz B´ a˜ nez, whose dedicated support, guidance, and comments have been invaluable throughout this study. He paid close attention to the progress of my work. This project would not have been possible without his support. I would also like to thank all the members of the Galgo research group for friendly discussions on the topic and Miguel ´ Angel P´ erez Cuti˜ no in particular for his help with programming implementation. Finally, I must express my very profound gratitude to my family and to my boyfriend Alberto for providing me with unfailing support and continuous encouragement throughout this year in Spain, studying and through the process of researching and writing this thesis. Introduction Unmanned aerial vehicles (UAVs or drones) have been largely used in missions involving navigating through an unknown environment, as they can host a wide range of sensors to measure the environment with relative low operation costs and high flexibility. However, it is difficult to attain this in most realistic implementations, since the knowledge and data regarding the environment are normally limited or unavailable. Using Reinforcement Learning (RL) is a good approach to overcome this issue because it allows a UAV or a UAV team to learn and navigate through the changing environment without a model of the environment [24]. Deep reinforcement learning (DRL) is the combination of reinforcement learning and deep learning. This field of research has been able to solve a wide range of complex decision making tasks in robotics [14]. The main idea is that an agent may learn by interacting with its environment, similarly to a biological agent. Using the experience gathered, the agent should be able to optimize some objectives given in the form of cumulative rewards. In this paper we use DRL to compute a tour that enables a mobile agent to cover points of an area of interest. Then the optimal tour is iteratively used to cover the overall required zone. Thus, our problem is relating with well known NP-hard problems: Travelling Salesman Problem, the Lawn Mowing Problem and the Milling problem [3]. In the robotics area, [11] provides a survey of general (ground robotics) approaches to coverage path planning. A recent surveys for UAVs is [8]. The main constraint in UAV path planning is the battery endurance. Despite recent improvements in battery technology, the maximum flying range of small UAVs is still a severe constraint. From a computational point of view, the problem is quite different when a limited lifetime is considered. Indeed, some planning problems can be solved in polynomial time when the battery endurance is considered unlimited but could be NPhard when the power is a constraint, see [2] for an example. Then, the power constraint leads to challenging optimization problems when a drone or a team of drones are tasked to navigate in a specific scenario. In the following we mention some related work. Collecting data from sensor devices in an outdoor environment imposes challenging constraints on the trajectories design for autonomous UAVs. Battery energy restricts mission duration for the drones severely, while the complex urban environment poses challenges in obstacle avoidance. A recent tutorial covering the paradigms of trajectory planning for data collection with drones is given in [26]. Bithaset al. [6] provide a survey on machine learning techniques, including but not limited to reinforcement learning(RL), for various UAV communications scenarios. Most existing approaches to UAV data collection are not based on RL and only find a solution for one set of scenario parameters at a time. For example, Esrafilianet al. [9] proposed a two-step algorithm to optimize a UAV’s trajectory and its scheduling decisions in an urban data collection mission using a combination of dynamic and sequential convex programming. However, deep reinforcement learning has been explored in UAV drone coverage using deep reinforcement learning communication scenarios. In [5], a UAV base station serves two ground users and the goal is to show the advantages of neural networks over table-based Q-learning. However, any explicit assumptions about the environment is considered at the price of long training time. On the other hand, deep deterministic policy gradient was proposed by Qiet al. [22] to learn a continuous control policy for a UAV providing persistent communications coverage to a group of users in an environment without obstacles. A more related work is given by Liu et al. [16], where an RL multi-agent algorithm collecting data simultaneously with ground and aerial vehicles in an environment with obstacles and charging stations is proposed. Their approach also makes use of convolutional nertworks to exploit a map of the environment but, in contrast to our method, control policies have to be relearned entirely when scenario and environmental parameters change. Finally, we mention a recent paper that proposes the use of DRL to find an optimal path under the assumption that not all the areas have the same coverage requirements. Picarelli et al. [21] propose a reinforcement learning approach that, given a relevance map representing coverage requirements, a robot autonomously chooses the best actions to optimize the coverage. However, they do not consider the battery endurance constraint. To the best of our knowledge, DRL has not been considered for UAV for coverage path planning in a unknown environment under power constraints before. The main goal of this thesis is serve a first step and a basis for path planners that are based on DRL, especially those under energetic constraints. This is particularly interesting for some type of applications with UAVs. The idea is to achieve sensor-based navigation in unknown scenarios with the help of the Reinforcement Learning framework in order to succeed in covering the ground with a good coverage rate which is evaluated with appropriately defined metrics. The simple problem formulation makes it possible to quickly generalize the solution concept to various domains with little changes or adjustments in the structure. This is made possible thanks to the mathematical tools used in the scope of this thesis. The rest of the work is outlined as follows. In chapter 1, we gives an overview of the Reinforcement Learning and the underlying concepts, in Markov Decision Processes in particular. The learning problem is introduced as well as the mathematical framework and tools used to implement the proposed Deep Reinforcement Learning algorithm. Chapter 2 defines the type of neural networks used in this study as well the deep neural networks. Section 3 presents the method to solve the problem. Finally, in chapter 5, we summarize the work and draw directions for future work. 16 1 Reinforcement learning Reinforcement learning is an area of machine learning, that becomes popular recently thanks to its capabilities in solving learning problem without relying on a model of the environment. It is a computational approach to understanding and automating goaldirected learning and decision making. The RL problem can be formalized as an agent that has to choose an action in an environment to maximize a numerical signal, called reward, that measures the performance of the agent (see Figure 1.1). A learning agent must be able to interact with environment and to take actions that affect the state. The agent does not know which action to take. It deals with the exploration/exploitation dilemma while learning. The agent must try a variety of actions and progressively favor those that appear to be best. Doing this the agent is seeking for a goal or goals relating to the state of the environment. In this chapter we will introduce the basic concepts of the reinforcement learning algorithm and describe the mathematics behind it. We will base base this study on Sutton and Barto’s RL book [24]. It covers RL fundamentals and reflects new progress, e.g., in deep Q-network, AlphaGo, policy gradient methods, as well as in psychology and neuroscience. Xintian Han gives a brief summary of the the mathematical approach of the problem [12]. [20] focus his paper ”Autonomous uav navigation using reinforcement learning” on applying RL algorithm for drones. Many other papers also use RL concepts into different field of robotics ([21,18,19] and others). 1.1 Problem Setup The general RL problem is formalized as a discrete time stochastic control process where an agent interacts with its environment in the following way: the agent starts, in a given state within its environment 𝑠0∈. At each time step 𝑡, the agent receives a state 𝑠𝑡∈ and selects an action 𝑎𝑡∈, following the policy 𝜋(𝑎𝑡|𝑠𝑡), which is the agent’s behavior. Figure 1.1: The agent–environment interaction in a Markov decision process[24]. drone coverage using deep reinforcement learning The agent obtains a scalar reward 𝑟𝑡, and transitions to the next state 𝑠𝑡+1, according to the environment dynamics, or model, for reward function (𝑠, 𝑎)and state transition probability (𝑠𝑡+1|𝑎𝑡+1)respectively. In an episodic problem, this process continues until the agent reaches a terminal state and then it restarts. The return 𝑅𝑡=∑∞ 𝑘=0 𝛾𝑘𝑟𝑡+𝑘is the discounted, accumulated reward with the discount factor 𝛾∈ (0,1]. The agent aims to maximize the expectation of such long term return from each state. The problem is set up in discrete state and action spaces. It is not hard to extend it to continuous spaces. 1.2 Markov Decision Processes Reinforcement learning uses the formal framework of Markov decision processes to define the interaction between a learning agent and its environment in terms of states, actions, and rewards. First we will define the Markov process. A sequence of states is Markov if and only if the probability of moving to the next state 𝑆𝑡+1 depends only on the present state 𝑠𝑡 and not on the previous states 𝑆1, 𝑆2, ..., 𝑆𝑡−1. That is, for all 𝑡, ℙ[𝑆𝑡+1|𝑆𝑡] = ℙ[𝑆𝑡+1|𝑆1, 𝑆2, ..., 𝑆𝑡](1.1) We always talk about time-homogeneous Markov chain in RL, in which the probability of the transition is independent of 𝑡: ℙ[𝑆𝑡+1 =𝑠′|𝑆𝑡=𝑠] = ℙ[𝑆𝑡=𝑠′|𝑆𝑡−1 =𝑠](1.2) Definition 1.1 (Markov Process). A Markov Process (or Markov Chain) is a tuple (,), where •is a (finite) set of states. •state transition probability matrix. 𝑠𝑠′=ℙ[𝑆𝑡+1 =𝑠′|𝑆𝑡=𝑠]. If we introduce reward, action and discount into a Markov process, we get a Markov decision process. Definition 1.2 (Markov Decision Processes). A Markov decision process is a tuple (,,, 𝛾, ), where •is a finite set of states. •is a finite set of actions. •state transition probability matrix. 𝑎 𝑠𝑠′=ℙ[𝑆𝑡+1 =𝑠′|𝑆𝑡=𝑠, 𝐴𝑡=𝑎]. •𝛾∈ (0,1] is a discount factor. •∶×→ℝis a reward function. In the MDP, the transition to the next state 𝑆𝑡+ 1 depends not only on the current state 𝑆𝑡, but also depends on the action 𝐴𝑡you make at the current state. Also, each stateaction pair is attached with a reward function. MDPs are a mathematically idealized form of the reinforcement learning problem for which precise theoretical statements can be made. 18 1. reinforcement learning 1.2.1 Returns and Episodes We have said that the agent’s goal is to maximize the cumulative reward it receives in the long run. If the sequence of rewards received after time step 𝑡is denoted 𝑅𝑡+1, 𝑅𝑡+2, 𝑅𝑡+3, ..., than we seek to maximize the expected return, where where the return, denoted 𝐺𝑡, is defined as some specific function of the reward sequence. For reinforcement learning tasks, which break naturally into sub-sequences, called episodes (episodic task), the return function is the sum of the rewards: 𝐺𝑡 . =𝑅𝑡+1 +𝑅𝑡+2 +𝑅𝑡+3 +... +𝑅𝑇(1.3) where T is a final time step. On the other hand, in many cases the agent–environment interaction does not break naturally into identifiable episodes, but goes on continually without limit.We call these continuing tasks. The final time step would be 𝑇= ∞, and the return could itself easily be infinite. To avoid it we add an additional parameter 𝛾∈ [0,1], called the discount rate. We can define the expected discounted return as: 𝐺𝑡 . =𝑅𝑡+1 +𝛾𝑅𝑡+2 +𝛾2𝑅𝑡+3 +... = ∞ ∑ 𝑘=0 𝛾𝑘𝑅𝑡+𝑘+1 (1.4) Returns at successive time steps are related to each other: 𝐺𝑡 . =𝑅𝑡+1 +𝛾𝐺𝑡+1 (1.5) We can define the return, in general for both episodic and continuing tasks: 𝐺𝑡 . = 𝑇 ∑ 𝑘=𝑡+1 𝛾𝑘−𝑡−1𝑅𝑘(1.6) including the possibility that 𝑇= ∞ or 𝛾= 1 (but not both). 1.2.2 Policies and Value Functions. Bellman equation Formally, a policy is a mapping from states to probabilities of selecting each possible action: 𝜋∶→𝑝(=𝑎|𝑆)(1.7) If the MDP is episodic, i.e., the state is reset after each episode of length 𝑇, then the sequence of states, actions, and rewards in an episode constitutes a trajectory of the policy. The state-value function for policy 𝜋, denoted 𝑣𝜋(𝑠), is the expected return when starting in 𝑠and following 𝜋thereafter. For MDPs, we can define 𝑣𝜋(𝑠)formally by 𝑣𝜋(𝑠). =𝔼𝜋[𝐺𝑡|𝑆𝑡=𝑠] = 𝔼𝜋[∞ ∑ 𝑘=0 𝛾𝑘𝑅𝑡+𝑘+1||||| 𝑆𝑡=𝑠],for all 𝑠∈(1.8) where 𝔼denotes the expected value of a random variable given that the agent follows policy 𝜋, and 𝑡is any time step. The action-value function for policy 𝜋, denoted 𝑞𝜋(𝑠, 𝑎), as the expected return starting from 𝑠, taking the action 𝑎, and thereafter following policy 𝜋: 𝑞𝜋(𝑠, 𝑎). =𝔼𝜋[𝐺𝑡|𝑆𝑡=𝑠, 𝐴𝑡=𝑎] = 𝔼𝜋[∞ ∑ 𝑘=0 𝛾𝑘𝑅𝑡+𝑘+1||||| 𝑆𝑡=𝑠, 𝐴𝑡=𝑎].(1.9) 19 drone coverage using deep reinforcement learning We can decompose the state-value function into two parts: the immediate reward 𝑅𝑡+1 and discounted value of successor state 𝛾𝑣𝜋(𝑆𝑡+1): 𝑣𝜋(𝑠). =𝔼𝜋[𝐺𝑡|𝑆𝑡=𝑠] =𝔼𝜋[𝑅𝑡+1 +𝛾𝐺𝑡+1|𝑆𝑡=𝑠] =𝔼𝜋[𝑅𝑡+1 +𝛾𝑣𝜋(𝑆𝑡+1)|𝑆𝑡=𝑠] =𝔼𝜋[𝑅𝑡+1|𝑆𝑡=𝑠] ⏟⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏟ immediate reward +𝔼𝜋[𝛾𝑣𝜋(𝑆𝑡+1)|𝑆𝑡=𝑠] ⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟ discounted value of successor state (1.10) Similarly, the action-value function can be decomposed as follows: 𝑞𝜋(𝑠, 𝑎). =𝔼𝜋[𝐺𝑡|𝑆𝑡=𝑠, 𝐴𝑡=𝑎] = 𝔼𝜋[𝑅𝑡+1 +𝛾𝑣𝜋(𝑆𝑡+1)|𝑆𝑡=𝑠, 𝐴𝑡=𝑎](1.11) To simplify notations, we define 𝑎 𝑠=𝔼𝜋[𝐺𝑡|𝑆𝑡=𝑠, 𝐴𝑡=𝑎]. We can see the relationship between 𝑣𝜋(𝑠)and 𝑞𝜋(𝑠, 𝑎): 𝑣𝜋(𝑠) = ∑ 𝑎∈ 𝜋(𝑎|𝑠)𝑞𝜋(𝑠, 𝑎)(1.12) 𝑞𝜋(𝑠, 𝑎) = 𝑎 𝑠+𝛾∑ 𝑠′∈ 𝑎 𝑠𝑠′𝑣𝜋(𝑠′)(1.13) Expressing 𝑞𝜋(𝑠, 𝑎)in terms of 𝑣𝜋(𝑠)in the expression of 𝑣𝜋(𝑠), we get a Bellman equation for 𝑣𝜋, 𝑣𝜋(𝑠) = ∑ 𝑎∈ 𝜋(𝑎|𝑠)(𝑎 𝑠+𝛾∑ 𝑠′∈ 𝑎 𝑠𝑠′𝑣𝜋(𝑠′))(1.14) The Bellman equation relates the state-value function of one state with that of other states. Similarly, we also have a Bellman equation for 𝑞𝜋(𝑠, 𝑎), 𝑞𝜋(𝑠, 𝑎) = 𝑎 𝑠+𝛾∑ 𝑠′∈ 𝑎 𝑠𝑠′∑ 𝑎′∈ 𝜋(𝑎′|𝑠′)𝑞𝜋(𝑠′, 𝑎′)(1.15) One use for the Bellman equation is to compute the value function for a given policy. If we combine all the Bellman equations in an MDP with 𝑛states, we get 𝑛linear equations for the 𝑛unknown value functions. We can get the value functions by solving linear equations ((recursion)). However, this step may take 𝑂(𝑛3)time complexity. Other solution is to use the dynamic programming. 1.2.3 Optimal Policy and Optimal Value Functions Solving a reinforcement learning task means, roughly, finding a policy that achieves a lot of reward over the long run. A policy 𝜋defined to be better than or equal to a policy 𝜋′if its expected return is greater than or equal to that of 𝜋′for all states. In other words, 𝜋≥𝜋′if and only if 𝑣𝜋(𝑠)≥𝑣𝜋′(𝑠)for all 𝑠∈. The optimal policy is a policy that better than or equal to all other policies. We denote all the optimal policies by 𝜋∗. They share the same state-value function, called the optimal state-value function, denoted 𝑣∗, and defined as 𝑣∗(𝑠). = max 𝜋𝑣𝜋(𝑠)(1.16) for all 𝑠∈. 20 1. reinforcement learning The optimal value function specifies the best possible performance in the MDP. We say an MDP is “solved” when we know the optimal value function. Similarly, we can define the action-value function as the maximum action-value function over all policies: 𝑞∗(𝑠, 𝑎). = max 𝜋𝑞𝜋(𝑠, 𝑎)(1.17) for all 𝑠∈and 𝑎∈(𝑠). Theorem 1.1. For any Markov Decision Process, •There exists an optimal policy 𝜋∗≥𝜋, for all 𝜋 •All optimal policies achieve the optimal value function, 𝑣𝜋∗(𝑠) = 𝑣∗(𝑠). •All optimal policies achieve the optimal action-value function, 𝑞𝜋∗(𝑠, 𝑎) = 𝑞∗(𝑠, 𝑎). Because 𝑣∗is the value function for a policy, it must satisfy the self-consistency condition given by the Bellman equation for state values (1.14). We can find the relationship between the optimal state-value function and the optimal action-value function, 𝑣∗(𝑠) = max 𝑎𝑞∗(𝑠, 𝑎),(1.18) 𝑞∗(𝑠, 𝑎) = 𝑎 𝑠+𝛾∑ 𝑠′∈ 𝑎 𝑠𝑠′𝑣∗(𝑠′)(1.19) Expressing 𝑞∗(𝑠, 𝑎)in terms of 𝑣∗(𝑠)in the expression of 𝑣∗(𝑠), we get a Bellman optimality equation for 𝑣∗: 𝑣∗(𝑠) = max 𝑎(𝑎 𝑠+𝛾∑ 𝑠′∈ 𝑎 𝑠𝑠′𝑣∗(𝑠′))(1.20) We also have a Bellman equation for 𝑞∗: 𝑞∗(𝑠) = 𝑎 𝑠+𝛾∑ 𝑠′∈ 𝑎 𝑠𝑠′max 𝑎′𝑞∗(𝑠′, 𝑎′)(1.21) The Bellman optimality equations are non-linear and there is no closed form solution in general. 1.3 Dynamic Programming The term dynamic programming (DP) refers to paradigm that can be used to compute optimal policies given a perfect model of the environment as a Markov decision process (MDP). We usually assume that the environment is a finite MDP: its state, action, and reward sets, ,and are finite, and that its dynamics are given by a set of probabilities 𝑝(𝑠′, 𝑟|𝑠, 𝑎), for all 𝑠∈,𝑎∈(𝑠),𝑟∈, and 𝑠′∈++is plus a terminal state if the problem is episodic). The key idea of DP, and of reinforcement learning generally, is the use of value functions to organize and structure the search for good policies. We can write the Bellman optimality equations (1.20), (1.21) as: 𝑣∗(𝑠) = max 𝑎 𝔼[𝑅𝑡+1 +𝛾𝑣∗(𝑆𝑡+1)|𝑆𝑡=𝑠, 𝐴𝑡=𝑎] = max 𝑎∑ 𝑠′,𝑟 𝑝(𝑠′, 𝑟|𝑠, 𝑎)[𝑟+𝛾𝑣∗(𝑠′)],(1.22) 21 drone coverage using deep reinforcement learning 𝑞∗(𝑠, 𝑎) = 𝔼[𝑅𝑡+1 +𝛾max 𝑎′𝑞∗(𝑆𝑡+1, 𝑎′)|||𝑆𝑡=𝑠, 𝐴𝑡=𝑎] =∑ 𝑠′,𝑟 𝑝(𝑠′, 𝑟|𝑠, 𝑎)[𝑟+𝛾max 𝑎′𝑞∗(𝑆𝑡+1, 𝑎′)],(1.23) for all 𝑠∈,𝑎∈(𝑠),𝑟∈, and 𝑠′∈+. We will introduce three paradigms of dynamic programming in reinforcement learning: policy evaluation, policy iteration and value iteration. Policy evaluation is used to find the value function of a certain policy. Policy iteration and value iteration are used to find the optimal value function and optimal policy. 1.3.1 Policy Evaluation We consider how to compute the state-value function 𝑣𝜋for an arbitrary policy 𝜋. We start from an initial guess 𝑣1and then apply Bellman equation (1.14) iteratively to it: 𝑣1→𝑣2→𝑣3→... →𝑣𝜋. At each iteration 𝑘+ 1, for all states 𝑠∈, we update 𝑣𝑘+1(𝑠) from 𝑣𝑘(𝑠′)according to Bellman equations, where 𝑠′is a successor state of 𝑠: 𝑣𝑘+1(𝑠) = 𝔼𝜋[𝑅𝑡+1 +𝛾𝑣𝑘(𝑆𝑡+1)|𝑆𝑡=𝑠] =∑ 𝑎∈ 𝜋(𝑎|𝑠)(𝑎 𝑠+𝛾∑ 𝑠′∈ 𝑎 𝑠𝑠′𝑣𝑘(𝑠′)) =∑ 𝑎∈ 𝜋(𝑎|𝑠)∑ 𝑠′,𝑟 𝑝(𝑠′, 𝑟|𝑠, 𝑎)[𝑟+𝛾𝑣𝑘(𝑠′)], (1.24) for all 𝑠∈.𝜋(𝑎|𝑠)is the probability of taking action 𝑎in state 𝑠under policy 𝜋. Clearly, 𝑣𝑘=𝑣𝜋is a fixed point for this update rule because the Bellman equation for 𝑣𝜋 assures us of equality in this case. Indeed, the sequence {𝑣𝑘}can be shown in general to converge to 𝑣𝜋as 𝑘→∞under the same conditions that guarantee the existence of 𝑣𝜋. This algorithm is called iterative policy evaluation. Formally, iterative policy evaluation converges only in the limit, but in practice it must be halted short of this. The pseudocode tests the quantity: Algorithm 1: Iterative Policy Evaluation, for estimating 𝑉≈𝑣𝜋[24] Input 𝜋, the policy to be evaluated Algorithm parameter: a small threshold 𝜃 > 0determining accuracy of estimation Initialize 𝑉(𝑆), for all 𝑠∈+, arbitrarily except that 𝑉(𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙)=0. Δ←0 repeat for 𝑠∈do 𝑣←𝑉(𝑠) 𝑉(𝑠)←∑𝑎𝜋(𝑎|𝑠)∑𝑠′,𝑟 𝑝(𝑠′, 𝑟|𝑠, 𝑎)[𝑟+𝛾𝑉 (𝑠′)] Δ←max (Δ,|𝑣−𝑉(𝑠)|) until Δ< 𝜃 The iterative process stops when the maximum difference between value function at the current step and that at the previous step is smaller than some small positive constant. 22 1. reinforcement learning 1.3.2 Policy Iteration Suppose we have determined the value function 𝑣𝜋for an arbitrary deterministic policy 𝜋. For some state 𝑠we would like to know whether or not we should change the policy to deterministically choose an action 𝑎≠𝜋(𝑠). We know how good it is to follow the current policy, but to know is there a new policy that is better than the current one, we need to use policy iteration. If select a random action 𝑎in a state 𝑠and follow the existing policy the value: 𝑞𝜋(𝑠, 𝑎). =𝔼[𝑅𝑡+1 +𝛾𝑣𝜋(𝑆𝑡+1|𝑆𝑡=𝑠, 𝐴𝑡=𝑎] = ∑ 𝑠′,𝑟 𝑝(𝑠′, 𝑟|𝑠, 𝑎)[𝑟+𝛾𝑣𝜋(𝑠′)],(1.25) Theorem 1.2 (Policy Improvement Theorem). Let 𝜋and 𝜋′be any pair of deterministic policies such that, for all 𝑠∈, 𝑞𝜋(𝑠, 𝜋′(𝑠)) ≥𝑣𝜋(𝑠)(1.26) Then the policy 𝜋′must be as good as, or better than, 𝜋. That is, it must obtain greater or equal expected return from all states 𝑠∈: 𝑣𝜋′(𝑠)≥𝑣𝜋(𝑠)(1.27) Moreover, if there is strict inequality of (1.26)at any state, then there must be strict inequality of (1.27)at that state. Proof. Starting from (1.26) we keep expanding the 𝑞𝜋side with (1.25) and reapplying (1.26) until we get 𝑣𝜋′(𝑠): 𝑣𝜋(𝑠)≤𝑞𝜋(𝑠, 𝜋′(𝑠)) =𝔼[𝑅𝑡+1 +𝛾𝑣𝜋(𝑆𝑡+1)|𝑆𝑡=𝑠, 𝐴𝑡=𝜋′(𝑠)] =𝔼𝜋′[𝑅𝑡+1 +𝛾𝑣𝜋(𝑆𝑡+1)|𝑆𝑡=𝑠] ≤𝔼𝜋′[𝑅𝑡+1 +𝛾𝑣𝜋(𝑆𝑡+1, 𝜋′(𝑆𝑡+1))|𝑆𝑡=𝑠] =𝔼𝜋′[𝑅𝑡+1 +𝛾[𝑅𝑡+2 +𝛾𝑣𝜋(𝑆𝑡+2)|𝑆𝑡+1, 𝐴𝑡+1 =𝜋′(𝑆𝑡+1)])|𝑆𝑡=𝑠] =𝔼𝜋′[𝑅𝑡+1 +𝛾𝑅𝑡+2 +𝛾2𝑣𝜋(𝑆𝑡+2)|𝑆𝑡=𝑠] =𝔼𝜋′[𝑅𝑡+1 +𝛾𝑅𝑡+2 +𝛾2𝑅𝑡+3 +𝛾3𝑣𝜋(𝑆𝑡+3)|𝑆𝑡=𝑠] ⋮ =𝔼𝜋′[𝑅𝑡+1 +𝛾𝑅𝑡+2 +𝛾2𝑅𝑡+3 +𝛾3𝑣𝜋(𝑆𝑡+3)|𝑆𝑡=𝑠] Let us consider the new greedy policy, 𝜋′, given by 𝜋′(𝑠). = argmax 𝑎 𝑞𝜋(𝑠, 𝑎) = argmax 𝑎 𝔼[𝑅𝑡+1 +𝛾𝑣𝜋(𝑆𝑡+1)|𝑆𝑡=𝑠, 𝐴𝑡=𝑎] = argmax 𝑎∑ 𝑠′,𝑟 𝑝(𝑠′, 𝑟|𝑠, 𝑎)[𝑟+𝛾𝑣𝜋(𝑠′)], By construction, the greedy policy meets the conditions of the policy improvement theorem 1.2, so we know that it is as good as, or better than, the original policy. The process 23 drone coverage using deep reinforcement learning Algorithm 7: Sarsa (on-policy TD control) for estimating 𝑄≈𝑞∗[24] Algorithm parameters: step size 𝛼∈ (0,1], small 𝜀 > 0 Initialize 𝑄(𝑆, 𝐴), for all 𝑠∈+, 𝑎 ∈, arbitrarily except that 𝑄(𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙, ∙) = 0 for each episode do Initialize 𝑆 Choose 𝐴from 𝑆using policy derived from 𝑄(e.g., 𝜀-greedy) repeat for each step of episode do Take action 𝐴, observe 𝑅, 𝑆′ Choose 𝐴′from 𝑆′using policy derived from 𝑄(e.g., 𝜀-greedy) 𝑄(𝑠, 𝑎)←𝑄(𝑆, 𝐴) + 𝛼[𝑅+𝛾𝑄(𝑆′, 𝐴′) − 𝑄(𝑆, 𝐴)], 𝑆←𝑆′;𝐴←𝐴′ until 𝑆is terminal Q-learning: Off-policy TD Control Off-policy TD control algorithm known as Q-learning (Watkins, 1989), defined by 𝑄(𝑆𝑡, 𝐴𝑡)←𝑄(𝑆𝑡, 𝐴𝑡) + 𝛼[𝑅𝑡+1 +𝛾max 𝑎𝑄(𝑆𝑡+1, 𝑎) − 𝑄(𝑆𝑡, 𝐴𝑡)],(1.34) In this case, the learned action-value function, 𝑄, directly approximates 𝑞∗, the optimal action-value function, independent of the policy being followed. The policy still has an effect in that it determines which state–action pairs are visited and updated. However, all that is required for correct convergence is that all pairs continue to be updated. The Q-learning algorithm is shown below in procedural form. Algorithm 8: Q-learning (off-policy TD control) for estimating 𝜋≈𝜋∗[24] Algorithm parameters: step size 𝛼∈ (0,1], small 𝜀 > 0 Initialize 𝑄(𝑆, 𝐴), for all 𝑠∈+, 𝑎 ∈, arbitrarily except that 𝑄(𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙, ∙) = 0 for each episode do Initialize 𝑆 repeat for each step of episode do Choose 𝐴from 𝑆using policy derived from 𝑄(e.g., 𝜀-greedy) Take action 𝐴, observe 𝑅, 𝑆′ 𝑄(𝑠, 𝑎)←𝑄(𝑆, 𝐴) + 𝛼[𝑅+𝛾𝑄(𝑆′, 𝑎) − 𝑄(𝑆, 𝐴)], 𝑆←𝑆′; until 𝑆is terminal 30 1. reinforcement learning Fitted 𝑄-learning Franc¸ois-Lavet [10] in the book ”An introduction to deep reinforcement learning” introduces us in using deep neural network for the 𝑄-function approximation. The idea is based on the fitted Q-learning concept. In fitted Q-learning, the algorithm starts with some random initialization of the 𝑄values 𝑄(𝑠, 𝑎;𝜃)where 𝜃refers to the initial parameters (usually such that the initial Q-values should be relatively close to 0 so as to avoid slow learning). Then, an approximation of the 𝑄-values at the 𝑘-th iteration 𝑄(𝑠, 𝑎;𝜃𝑘)is updated towards the target value 𝑌𝑄 𝑘=𝑟+𝛾max 𝑎′∈𝑄(𝑠′, 𝑎′;𝜃𝑘)(1.35) where 𝜃𝑘)refers to some parameters that define the 𝑄-values at the 𝑘-th iteration. In neural fitted Q-learning (NFQ), the state can be provided as an input to the Q-network and a different output is given for each of the possible actions. This provides an efficient structure that has the advantage of obtaining the computation of max𝑎′∈𝑄(𝑠′, 𝑎′;𝜃𝑘in a single forward pass in the neural network for a given 𝑠0. The 𝑄-values are parameterized with a neural network 𝑄(𝑠, 𝑎;𝜃𝑘)where the parameters 𝜃𝑘)are updated by stochastic gradient descent (or a variant) by minimizing the square loss: 𝐿𝐷𝑄𝑁 =(𝑄(𝑠′, 𝑎′;𝜃𝑘) − 𝑌𝑄 𝑘)(1.36) Thus, the 𝑄-learning update amounts in updating the parameters: 𝜃𝑘+1 =𝜃𝑘+𝛼(𝑌𝑄 𝑘−𝑄(𝑠′, 𝑎′;𝜃𝑘))∇𝜃𝑘𝑄(𝑠, 𝑎;𝜃𝑘)(1.37) where 𝛼is a scalar step size called the learning rate. Using the square loss is not arbitrary. Indeed, it ensures that 𝑄(𝑠, 𝑎;𝜃𝑘)should tend without bias to the expected value of the random variable 𝑌𝑄 𝑘. Hence, it ensures that 𝑄(𝑠, 𝑎;𝜃𝑘)should tend to 𝑄∗(𝑠, 𝑎) after many iterations in the hypothesis that the neural network is well-suited for the task and that the experience gathered in the dataset D is sufficient (we describe the deep Qnetworks with more details in the section 2.3). 31 2 Deep neural networks The area of Artificial Neural Networks has become a matter of engineering and achieving good results in Machine Learning tasks. Among them is the idea of Q-function approximation with Deep Q-Network in Reinforcement Learning. In this chapter we will give a brief introduction to the basic concepts of Neural Networks and Deep Neural Networks in it particular case basing the investigation on the Charu C. Aggarwal [1] and Sandro Skansi [23] books. We also touch the basics of Convolutional Neural Networks (CNN) explained on Stanford university course [13]. In the end of this chapter we go deeper to the convolutional networks application in Reinforcement learning and study the Deep Q-learning concepts. Vincent Franc¸ois-Lavet [12], Yuxi Li [15], Kai Arulkumaran [4] provide an introduction to deep reinforcement learning models, algorithms and techniques. 2.1 The Basic Architecture of Neural Networks Artificial Neural Networks (ANNs) were inspired with the idea of modeling biological neural systems and proposed creating virtual neurons. As biological systems, the neurons are connected together to form a network of nodes. The type of information circulating in neural nets is of scalar type, analogously to electrical signals emitted in a brain of a living being. Any neural network is made of simple basic elements: neurons or perceptrons. In this section we see the structure of this elements. Also we will to combine them to construct a deep or multi layer networks. 2.1.1 Single Computational Layer: The Perceptron The simplest neural network is referred to as the perceptron. This neural network contains a single input layer and an output node. The basic architecture of the perceptron is shown in Figure 2.1 Consider a situation where each training instance is of the form (𝐗, 𝑦), where each 𝐗= {𝑥1, ..., 𝑥𝑑}contains d feature variables, and 𝑦∈ (−1,+1) contains the observed value of the binary class variable. The input layer contains 𝑑nodes that transmit the 𝑑features 𝐗= {𝑥1, ..., 𝑥𝑑}with edges of weight 𝐖= {𝑤1, ..., 𝑤𝑑}to an output node. The input layer does not perform any computation in its own right. The linear function 𝐗∙𝐖=∑𝑑 𝑗=1 𝑤𝑗𝑥𝑗computed at the output node. Therefore, the prediction 𝑦 is computed as follows: 𝑦 =sign{𝐗∙𝐖} = sign {𝑑 ∑ 𝑗=1 𝑤𝑗𝑥𝑗}(2.1) drone coverage using deep reinforcement learning Figure 2.1: The basic architecture of the perceptron [1]. 2.1.2 Choice of Activation Function The choice of activation function is a critical part of neural network design. In the case of the perceptron, the choice of the sign activation function is motivated by the fact that a binary class label needs to be predicted. Every activation function (or non-linearity) takes a single number and performs a certain fixed mathematical operation on it. We use the notation Φto denote the activation function: 𝑦 = Φ{𝐗∙𝐖}(2.2) The classical activation functions that were used early in the development of neural networks were the sign, sigmoid, and the hyperbolic tangent functions: Φ(𝑣) = sign(𝑣)(sign function) Φ(𝑣) = 1 1 + 𝑒−𝑣(sigmoid function) Φ(𝑣) = 𝑒2𝑣− 1 𝑒2𝑣+ 1 (tanh function) The choice of the loss function is critical in defining the outputs in a way that is sensitive to the application at hand. 2.1.3 Loss function The data loss in a supervised learning problem measures the compatibility between a prediction (e.g. the class scores in classification) and the ground truth label. The data loss takes the form of an average over the data losses for every individual example. That is, 𝐿= 1∕𝑁∑𝑖𝐿𝑖where 𝑁is the number of training data. In case of classification problem we assume a dataset of examples and a single correct label (out of a fixed set) for each example. One of two most commonly seen cost functions in this setting is the support vector machine (SVM): 𝐿𝑖= max{0,1 − 𝑦𝑖(𝐗∙𝐖)} (2.3) For example, least-squares regression with numeric outputs requires a simple squared loss of the form (𝑦−ℎ𝑎𝑡𝑦)2for a single training instance with target 𝑦and prediction 34 2. deep neural networks 𝑦. One can also use other types of loss like hinge loss for 𝑦∈ {−1,+1} and real-valued prediction 𝑦 (with identity activation): 𝐿= max{0,1 − 𝑦∙𝑦}(2.4) The second common choice is the Softmax classifier that uses the cross-entropy loss: For multiway predictions (like predicting word identifiers or one of multiple classes), the softmax output is particularly useful. However, a softmax output is probabilistic, and therefore it requires a different type of loss function. In fact, for probabilistic predictions, two different types of loss functions are used, depending on whether the prediction is binary or whether it is multiway: •Binary targets (logistic regression): In this case, it is assumed that the observed value 𝑦is drawn from {−1,+1}, and the prediction 𝑦 is a an arbitrary numerical value on using the identity activation function. In such a case, the loss function for a single instance with observed value 𝑦and real-valued prediction 𝑦 (with identity activation) is defined as follows: 𝐿= log(1 + exp(−𝑦∙𝑦)) (2.5) This type of loss function implements a fundamental machine learning method, referred to as logistic regression. Alternatively, one can use a sigmoid activation function to output 𝑦 ∈ (0,1), which indicates the probability that the observed value y is 1. Then, the negative logarithm of |𝑦∕2 − 0.5 + 𝑦|provides the loss, assuming that y is coded from {−1,1}. This is because |𝑦∕2 − 0.5 + 𝑦|indicates the probability that the prediction is correct. This observation illustrates that one can use various combinations of activation and loss functions to achieve the same result. •Categorical targets: In this case, if 𝑦1... 𝑦𝑘are the probabilities of the k classes, and the 𝑟-th class is the ground-truth class, then the loss function for a single instance is defined as follows: 𝐿= − log ( 𝑦𝑟)(2.6) This type of loss function implements multinomial logistic regression, and it is referred to as the cross-entropy loss. Note that binary logistic regression is identical to multinomial logistic regression, when the value of 𝑘is set to 2 in the latter. In practice, one rarely uses the perceptron criterion as the loss function. For discretevalued outputs, it is common to use softmax activation with crossentropy loss. For realvalued outputs, it is common to use linear activation with squared loss. Generally, crossentropy loss is easier to optimize than squared loss. 2.1.4 Multilayer Neural Networks Multilayer neural networks contain multiple computational layers; the additional intermediate layers (between input and output) are referred to as hidden layers because the computations performed are not visible to the user. The specific architecture of multilayer neural networks is referred to as feed-forward networks, because successive layers feed into one another in the forward direction from input to output. An example of multilayer network is shown in Figure 2.2 35 drone coverage using deep reinforcement learning Figure 2.2: The basic architecture of a feed-forward network with two hidden layers and a single output layer [1]. The weights of the connections between the input layer and the first hidden layer are contained in a matrix 𝐖1with size 𝑑×𝑝1whereas the weights between the 𝑟-th hidden layer and the (𝑟+ 1-th hidden layer are denoted by the 𝑝𝑟×𝑝𝑟+1 matrix denoted by 𝐖𝑟. If the output layer contains 𝑜nodes, then the final matrix 𝐖𝑘+1 is of size 𝑝𝑘×𝑜 The 𝑑-dimensional input vector 𝑥 is transformed into the outputs using the following recursive equations:  ℎ1= Φ(𝐖𝑇 1𝑥)(Input to Hidden Layer)  ℎ𝑝+1 = Φ(𝐖𝑇 𝑝+1  ℎ𝑝) ∀𝑝∈ {1...𝑘 − 1} (Hidden to Hidden Layer) 𝑜 = Φ(𝐖𝑇 𝑘+1  ℎ𝑘)(Hidden to Output Layer]) As we increase the size and number of layers in a Neural Network, the capacity of the network increases. Overfitting occurs when a model with high capacity fits the noise in the data instead of the (assumed) underlying relationship. It seems that smaller neural networks can be preferred if the data is not complex enough to prevent overfitting. However, this is incorrect – we should use as big of a neural network as your computational budget allows, and use other regularization techniques to control overfitting. 2.1.5 Training a Neural Network with Backpropagation In the single-layer neural network, the training process is relatively straightforward because the error (or loss function) can be computed as a direct function of the weights, which allows easy gradient computation. In the case of multi-layer networks, the problem is that the loss is a complicated composition function of the weights in earlier layers. The gradient of a composition function is computed using the backpropagation algorithm. The backpropagation algorithm is a direct application of dynamic programming. It contains two main phases, referred to as the forward and backward phases, respectively. The forward phase is required to compute the output values and the local derivatives at various nodes, and the backward phase is required to accumulate the products of these local values over all paths from the node to the output. 36 2. deep neural networks 2.2 Convolutional Neural Networks Convolutional Neural Networks (CNNs or ConvNets) are very similar to the neural networks that we have seen in the previous chapter: they are made up of neurons that have parameters in the form of weights and biases that can be learned. But a differential feature of CNNs is that they make the explicit assumption that the inputs are images, which allows us to encode certain properties in the architecture to recognize specific elements in the images. An important property of image data is that it exhibits a certain level of translation invariance, which is not the case in many other types of grid-structured data. For example, a banana has the same interpretation, whether it is at the top or the bottom of an image. Convolutional neural networks tend to create similar feature values from local regions with similar patterns. 2.2.1 The basic elements of CNNs A convolutional neural network is a neural network that has one or more convolutional layers. To understand let us see the 1D-convolutional layer structure. In this case the convolutional layer takes a 2D array and a small logistic regression with e.g. input size 4 (these sizes are usually 4 or 9, sometimes 16) and passes the logistic regression over the whole image. This means that the first input consists of components 1–9 of the flattened vector, the second input are the components 2–10, the third are components 3–11, and so on.You can see an overview of the process in the bottom of Figure 2.3 Figure 2.3: Building a 1D convolutional layer with a logistic regression [23]. In classical convolutional neural networks we deal with pictures. In this case the states in each layer are arranged according to a spatial grid structure. Each layer is a 3-dimensional grid structure, which has a height, width, and depth (Figure 2.4). The convolutional neural network functions much like a traditional feed-forward neural network, except that the operations in its layers are spatially organized with sparse (and carefully designed) connections between layers. The three types of layers that are commonly present in a convolutional neural network are convolution, pooling, and ReLU. The ReLU activation is no different from a traditional neural network. 37 drone coverage using deep reinforcement learning Figure 2.4: The convolution between an input layer of size 32 ×32 ×3 and a filter of size 5×5×3 produces an output layer with spatial dimensions 28 ×28. The depth of the resulting output depends on the number of distinct filters and not on the dimensions of the input layer or filter [1]. In the convolutional neural network, the parameters are organized into sets of 3dimensional structural units, known as filters or kernels. The filter is usually square in terms of its spatial dimensions, which are typically much smaller than those of the layer the filter is applied to. On the other hand, the depth of a filter is always same is the same as that of the layer to which it is applied. Assume that the dimensions of the filter in the 𝑞-th layer are 𝐹𝑞×𝐹𝑞×𝑑𝑞. The convolution operation places the filter at each possible position in the image (or hidden layer) so that the filter fully overlaps with the image, and performs a dot product between the 𝐹𝑞×𝐹𝑞×𝑑𝑞parameters in the filter and the matching grid in the input volume (with same size 𝐹𝑞×𝐹𝑞×𝑑𝑞). Each filter position defines a spatial “pixel” (or, more accurately, a feature) in the next layer. The 𝑝-th filter in the 𝑞-th layer has parameters denoted by the 3-dimensional tensor 𝑊(𝑝,𝑞)= [𝑤(𝑝,𝑞) 𝑖,𝑗,𝑘 ]. The indices 𝑖, 𝑗, 𝑘 indicate the positions along the height, width, and depth of the filter. The feature maps in the 𝑞-th layer are represented by the 3dimensional tensor 𝐻(𝑞)= [ℎ(𝑞) 𝑖,𝑗,𝑘]. When the value of 𝑞is 1, the special case corresponding to the notation 𝐻simply represents the input layer (which is not hidden). Then, the convolutional operations from the 𝑞-th layer to the (𝑞+ 1) -th layer are defined as follows: ℎ(𝑞+1) 𝑖,𝑗,𝑝 = 𝐹𝑞 ∑ 𝑟=1 𝐹𝑞 ∑ 𝑠=1 𝑑𝑞 ∑ 𝑘=1 𝑤(𝑝,𝑞) 𝑟,𝑠,𝑘ℎ(𝑞) 𝑖+𝑟−1,𝑗+𝑠−1,𝑘 ∀𝑖∈ {1..., 𝐿𝑞−𝐹𝑞+ 1} ∀𝑗∈ {1..., 𝐵𝑞−𝐹𝑞+ 1} ∀𝑝∈ {1..., 𝑑𝑞+ 1} One property of convolution is that it shows equivariance to translation. In other words, if we shifted the pixel values in the input in any direction by one unit and then applied convolution, the corresponding feature values will shift with the input values. This is because of the shared parameters of the filter across the entire convolution. 38 2. deep neural networks Padding One observation is that the convolution operation reduces the size of the (q + 1)th layer in comparison with the size of the 𝑞-th layer. This type of reduction in size is not desirable in general, because it tends to lose some information along the borders of the image (or of the feature map, in the case of hidden layers). This problem can be resolved by using padding. In padding, one adds (𝐹𝑞− 1)∕2 “pixels” all around the borders of the feature map in order to maintain the spatial footprint. Padding in 2D is simply a ‘frame’ of n pixels around the image (Figure 2.5). Note that it does not make much sense to use a padding of say 3 (pixels) if we use only a 3 by 3 local receptive field, since it will only go one pixel over the image border. Figure 2.5: An example of padding. Each of the 𝑑𝑞activation maps in the entire depth of the 𝑞-th layer are padded in this way [1]. Strides The parameter which says by how many components we move the receptive field between taking inputs is called the stride of the convolutional layer. When a stride of 𝑆𝑞is used in the 𝑞-th layer, the convolution is performed at the locations 1, 𝑆𝑞+1,2𝑆𝑞+1, and so on along both spatial dimensions of the layer. The spatial size of the output on performing this convolution1 has height of (𝐿𝑞−𝐹𝑞)∕𝑆𝑞+1 and a width of (𝐵𝑞−𝐹𝑞)∕𝑆𝑞+1. As a result, the use of strides will result in a reduction of each spatial dimension of the layer by a factor of approximately 𝑆𝑞and the area by 𝑆2 𝑞, although the actual factor may vary because of edge effects. The ReLU Layer The convolution operation is interleaved with the pooling and ReLU operations. The ReLU activation is not very different from how it is applied in a traditional neural network. For each of the 𝐿𝑞×𝐵𝑞×𝑑𝑞values in a layer, the ReLU activation function is applied to it to create 𝐿𝑞×𝐵𝑞×𝑑𝑞thresholded values. These values are then passed on to the next layer. Therefore, applying the ReLU does not change the dimensions of a layer because it is a simple one-toone mapping of activation values. 39 drone coverage using deep reinforcement learning Figure 3.1: Binary map example. space is too large to guarantee the convergence of the algorithm, in practice, normally these set will be represented as discrete finite sets approximately. Here we suppose that the camera is fixed in vertical position, in other words, the camera main axis matches Z axis of the drone. We also include the battery level 𝑝to the state. The state of the UAV is defined as the 4-tuple 𝑠= [𝑥, 𝑦, 𝑧, 𝑝] ∈ at the time step 𝑘: •𝑥∈ [0, 𝑚], 𝑌 ∈ [0, 𝑛], 𝑧 ∈ [0, ℎ]are the spatial coordinates of the UAV, assuming it cannot fly outside the range of the environment with size 𝑚×𝑛and ℎis the maximum flying height; •𝑝∈ [0, 𝑏]is the current battery level (power). The drone stars from its base station fully charged and decreases the battery level one every time step. The drone can use the following set of actions that decreases by one the power: •Forward, Backward, Left, Right: move the agent to a neighboring cell in the four main directions. •Up, Down: increment or decrease by one the flying height 𝑧. •ForwardLeft, ForwardRight, BackwardLeft, BackwardRight: move the agent to a diagonal cell. As we implement a Double DQN with soft update, as described in section 3.3, the network input consists in the relevance map and the current agent state. In this case, we cannot represent the state as a tuple as we need it as a relevance map size matrix. To fulfill this requirement we can get away from drone coordinates and start representing the current state basing on the drone camera’s field of view (FOV). If we accept an approximation letting the projection of the coordinates of the camera on the ground plane in the world reference system match the projection of the drone mass center coordinates, it is possible to define the ground projection of the image plane as a rectangular shape FOV enclosing the portion of ground plane observed by the agent, as shown in Figure 3.2 (a). That is, the four corners of the images acquired by the camera can be represented as: 46 3. a deep rl algorithm for constrained drone coverage (a) Field of view of an UAV. (b) Binary map example. Figure 3.2: Modelling the covering at a state. 𝑥 ∈[−𝑧 tan 𝜃1 ,𝑧 tan 𝜃1], 𝑦 ∈[−𝑧 tan 𝜃2 ,𝑧 tan 𝜃2] If consider the simplest case and suppose that the camera is fixed with 𝜃1=𝜃2= 45◦ we receive: 𝑥 ∈[−𝑧, 𝑧], 𝑦 ∈[−𝑧, 𝑧] Other words, one step up expand the FOV on one cell each direction and one step down shrink the FOV on one cell each direction. The FOV with other actions changes analogously (see Figure 3.2(b)). This way we represent the agent state as a matrix of the same size as the relevance map. The cells included in the FOV of the drone are represented by its power level on the moment. All the rest of the cells are represented by zeros, Figure 3.3. Figure 3.3: Drone state with its power level. 47 drone coverage using deep reinforcement learning 3.1.3 Reward function Before defining the reward function let us define the total observed relevance 𝜌of an agent in state 𝑠as the sum of all the relevance, as defined by the relevance map 𝐑, lying within the observed area FOV: 𝜌(𝑠) = ∑ (𝑥,𝑦)∈FOV 𝐑(𝑥, 𝑦)(3.1) The reward function will be defined in terms of total observed relevance, meaning that actions leading to an increase of such a value will be positively rewarded. However, we require some additional constraints, otherwise reward maximization will always lead to “extreme” agent states where the entire relevance map is enclosed in FOV, e.g. by flying at very high altitude. We thus define the Constrained Total Observed Relevance (CTOR) as: 𝜌(𝑠) = 𝑘(FOV)𝜌(𝑠)(3.2) where 𝑘is a penalty function with values in [0,1] penalizing observed areas with low resolution. We are ready to define the reward function of the Markov Decision Process that take into account the battery constraint. If the action 𝑎, applied on state 𝑠, leads to a new state 𝑠′, the local reward is: 𝑟(𝑠, 𝑎) = 𝜌(𝑠′) − 𝜌(𝑠′),(3.3) thus the action is rewarded proportionally with the CTOR increment. Now, let 𝐵𝐿(𝑠) be the battery level at the current state 𝑠, that is, the number of steps that could be done until the battery is dead. Let 𝑑𝑖𝑠𝑡(𝑠)be the distance to the base station, that is, the minimum number of steps needed to reach the base station from the current state 𝑠. The reward function that integrates battery constraint and local reward is defined as: 𝑅(𝑠, 𝑎) = (1 − 𝑃(𝑠))[𝑟(𝑠, 𝑎)(1 − 𝑁(𝑠, 𝑎)) − 100𝑁(𝑠, 𝑎)] + 𝑃(𝑠)𝐷(𝑠, 𝑎),(3.4) where 𝑃(𝑠)=1if 𝐵𝐿(𝑠) − 𝑑𝑖𝑠𝑡(𝑠)=0 𝑃(𝑠)=0if 𝐵𝐿(𝑠) − 𝑑𝑖𝑠𝑡(𝑠)>0 𝑁(𝑠, 𝑎)=1if 𝐵𝐿(𝑠) − 𝑑𝑖𝑠𝑡(𝑠′)<0 𝑁(𝑠, 𝑎)=0if 𝐵𝐿(𝑠) − 𝑑𝑖𝑠𝑡(𝑠′)<0 𝐷(𝑠, 𝑎)=(𝑑𝑖𝑠𝑡(𝑠′) − 𝑑𝑖𝑠𝑡(𝑠)) 3.2 A reinforcement learning algorithm for coverage task The agent model, described in the previous section, can be interpreted like an agentenforcement environment interaction (Figure 1.1). The agent has an objective to find a course of actions based on its states, called a policy, that ultimately maximizes its total amount of reward it receives over time. The action value function 𝑄(𝑠𝑡;𝑎𝑡)is used to determine which action to take in a given state for each time step. The agent can iteratively compute the optimal value of this function, and from which derives an optimal policy. 48 3. a deep rl algorithm for constrained drone coverage In classic Q-learning algorithms, the Q-function updates with Bellman Equation (1.34). The optimal value functions computed this way are stored into tabular databases (Qtables). In the coverage task we can deal with very big territories. Therefore, the usual approaches making use of tables storing values in large matrices are no longer practical because they do not scale-up especially in continuous (hence infinite) state spaces. In this case it is convenient to use the deep Q-learning approach because it let us use Deep Networks as function approximators for 𝑄(Deep Q-Networks). The implementation of Deep Q-Networks does not change the core concept of RL, with the exception that the the policy is now generated by a neural network. To let the network explore different actions and allow it learn new things we should maintain the exploration-exploitation balance. The exploration is guaranteed with an 𝜀 - greedy policy. At each iteration, the agent picks a random action with probability 𝜀 and an action given by the network with probability 1 − 𝜀. The problem of the classic Q-learning is that we can not use the same network parameters 𝜃both for action selection and evaluation, because this could lead to biased estimates for 𝑄. The algorithm we are proposing here adapts Double Deep Q-Network approach introduced in section 2.3.2. This way we train two independent networks for selection and evaluation tasks. In the box bellow we provide the pseudocode of the double deep Q-learning algorithm used in this work. Algorithm 10: Double Deep Q-learning algorithm for drone coverage Algorithm parameters: small exploration probability 𝜀∈ (0,1] Initialize: relevance map; base stations coordinates; battery limit; movement limit; Initialize network parameters: replay memory; main network parameters 𝑡ℎ𝑒𝑡𝑎 to random weights; target network parameters  𝜃←𝜃; for each episode do Choose initial state 𝑠0from a base station chosen randomly repeat if the object state is inside the region and the battery is charged then for each step of episode do With probability 𝜀select random action 𝑎𝑡 Otherwise select 𝑎𝑡= max𝑎𝑄(𝑠𝑡, 𝑎) Take action 𝑎𝑡, observe 𝑟𝑡, 𝑠𝑡+1 Update exploration probability 𝜀 Backpropagate and update DQN with the minibatch if C updates to DQN since last update to target network then update the target Q-network  𝑄(𝑠, 𝑎)←𝑄(𝑆, 𝐴); else Finish the episode until the territory is covered or movement limit is achieved 49 drone coverage using deep reinforcement learning 3.3 Implementation of Neural Network The input of the network is a tridimensional matrix of size (32, 32, 2). The depth 2 refers to two channels. The first channel contains the visual information of the current drone camera output. The second channel encapsulates the drone position in the environment, as well as the battery level and the base stations. Therefore, we construct a Q-Network based on convolutionals layers. Each layer reduce the two first dimensions of the matrix until we get a 1x1 matrix in the final layer. On the other hand, the number of channels is increased in the first layer and then we start to reduce it until we get as many channels as possible actions for the final layer. In this way we prevent from flattening the convolutional layer, which allows us to perform faster computations. Figure 3.4 shows the basic structure of the network. We use three convolutional blocks, each one containing a convolutional layer, a batch normalization, a relu activation and a 10% dropout. Between these we have two maxpools operations. Then we have another convolutional layer as the model output. Figure 3.4: Network architecture. The network training process is managed by the agent as defined for the environment. It uses a SmoothL1 loss criteria, and an Adam optimizer with learning rate of 0.001. In this agent, we define the current model 𝑄and the target network 𝑄′as in the q-learning technique described in [17]. We define the future reward as 𝑓(𝑠′) = 𝑟+ 0.8 ∗ arg max(𝑄′(𝑠′)) were 0.8is the 𝛾value that represents the importance of future rewards and 𝑠′is the state obtained from performing action 𝑎in state 𝑠following the policy 𝜋. Then we can define the loss function as Loss(𝑠, 𝑎) = SmoothL1(𝑄(𝑠), 𝑓(𝜋(𝑠, 𝑎))).(3.5) 50 3. a deep rl algorithm for constrained drone coverage 3.4 Experimental results 3.4.1 Simulation environment The coverage problem is formulated as a dynamic game. To implement successfully the described algorithm a custom environment was created using python libraries. The library OpenAI Gym [7] specifically made for RL applications was used to interact with the environment, start game episodes, observe states, collect rewards and perform actions. The agent can move in a two dimensional grid through action commands. Each action consumes one unit of movement budget. The initial step consists of a fixed map, a zeroinitialized coverage rate, a position at a base station and full power. Additionally, the initial movement budget is uniformly sampled from a movement budget range which is set to 200-400 for the purpose of this evaluation. The UAV’s camera field of view (FoV) depends on the height and it centered underneath the drone. After each step of the mission, algorithm marks the FoV as seen in the coverage grid map (Figure 3.3). During the training and simulation we used several binary maps on a 32 × 32 grid as relevance maps. The same algorithm can also be applied for bigger maps. To avoid the recovering and give the robot some motivation to discover new zones, the ones from the covered zones are converted to zero. When the robot leaves the area permitted by the map it receives the negative reward. Negative rewards encourage the robot to come back as quickly as possible because it makes the agent lose points when the game is still being played. At the beginning, when the agent is no trained enough, it can go too far outside and spend too much time there that slows down the learning process. To resolve this issue we decided to end the episode each time the robot goes more than two steps out the boundary any direction (𝑥, 𝑦 or 𝑧) or when the battery is less than −100. When the robot achieves the base station its battery level changes by 100. When the agent learns good to charge and do not leave the box, the episode can last the unlimited number of steps. The visual representation of the environment is shown in Figure 3.5. Figure 3.5: The simulation environment. A 32 × 32 grid map showing a base station in red, the charged agent (big green square), covered area (in blue cells) and not covered area (green cells). 51 drone coverage using deep reinforcement learning 3.4.2 Training To train the model, the input is not taken directly from the states of the observed environment. Instead, tuples (state, reward, action, next state) are collected after each interaction with the environment and stored in a replay memory which is sampled. This approach helps increase the performance of the learning by reducing the correlation between individual samples in a training batch. The training hyper-parameters used are listed in Table 3.1. They were obtained after a series of experimentations with the goal of determining the best combination of parameters. During training, the exploration factor 𝜀is varying, starting from 0.6 at the beginning and decreasing throughout the learning process until it reaches 0.1 using the following proportion: 𝜀= 0.6for 𝑖= 0 𝜀= 0.6⋅0.9𝑖∕300 for 0<𝑖<5000 𝜀= 0.1for 𝑖 > 5000 This decreasing is motivated by the fact that the agent initially has not acquired any knowledge, which forces the exploration of the free space in priority. With ongoing training, the agent will gradually exploit and rely on the accumulated knowledge and less on the exploration. The presented proportion had shown good results during the experiment but can be not the optimal one. Parameter Value Signification 𝑀5000 maximum number of training episodes 𝐻×𝑊32 × 32 length and width of the workspace 𝑍5 hight of the workspace 𝑚32 minibatch size 𝔅400 maximum movement budget 𝐵𝐿 200 maximum battary level 𝜖0.1 .. 0.6 exploration rate 𝛾0.9 discount factor Table 3.1: Hyper-parameters for the DQN training. Figure 3.6 describes the evolution of the total reward (the sum of the rewards) per episode in function of the number of training episodes. We can see that at the beginning the agent gets a lot of negative reward as making random steps. It is almost guaranteed leaves the environment and or goes opposite direction from the base when the battery is low. Throughout the training, the agent manages to collect positive reward which means it learns to stay in the restricted zone, charge the battery and discover the new territories. This shows that the learning improves and the agent gets better at covering the workspace. Figure 3.7 illustrates the progress in average number of steps per episode during training. Every episode the agent could live more steps without going out the boundary and charging the battery on time. Note that even after 5000 episodes, the average number 52 3. a deep rl algorithm for constrained drone coverage Figure 3.6: Average reward per episode during training. The statistics were computed by running an 𝜖-greedy policy. of steps is not equal to 400 (the maximum permitted number of steps). It means that the network is still not very good trained and it needs more training. But also we should take in account that the agent also can go wrong with the random steps permitted by 𝜖. Figure 3.7: Average number of steps per episode during training. 3.4.3 Simulations and Discussion For simulation purposes we have chosen two different maps to evaluate the coverage rate made by the model. In this experiment we want to see the ability of the agent to cover the field limiting the number time steps. Figure 3.8 shows the percentage of the area that was covered for two different maps in a 32 × 32 grid. The first map is full of ones (we consider that all the zones of the map have the same importance). In the second map we have the square objects 8 × 8 cells size staggered like a checkerboard. It can be clearly seen that the covered area increases with movement budget, which is expected as the drone is able to do more steps in different directions. We can also 53 drone coverage using deep reinforcement learning Figure 3.8: Coverage rate for two maps with different movement budget. note that the model perfectly adapts to the different type of the maps. Even so as the model is still not very good trained, the robot does to much inefficient steps to and back and it can not cover the whole territory with an adequate movement budget. It is important to say that the agent does not necessarily utilize the whole allocated budget if it determines that there is a risk of not returning to the base in time or the coverage goal is already fulfilled. Thus, the drone finds a tour balancing the goals of safe recharging and maximum coverage ratio. Figure 3.9: Battery level per step. Finally, the drone’s ability to plan a trajectory that comes back to the base station over the full movement budget range is evaluated through Figure 3.9, showing the battery level per step in the test mode. As we can see, when the battery level falls down to zero the robot immediately goes to recharge. The periodicity of the graphic shows us that 54 3. a deep rl algorithm for constrained drone coverage the drone learned well do not exceed the fixed number of steps in coverage mode (the power 𝑝is stated as 100 steps). As a consequence, the drone goes to charge in time and does not go around the base with random movements. 3.5 Conclusion and future work This thesis focuses the problem of coverage path planning in unknown environments using a drone with limited battery endurance, with the aim of maximizing the covered area. The task is expressed as a game played by the drone that seeks to maximize a carefully chosen reward. Although there exist similar approaches in the literature, the case in which the available power is limited is usually not considered and then it is a challenge to design a learning algorithm with this realistic constraint. In this work, we have introduced a new deep reinforcement learning approach for that optimization problem. By feeding spatial information through map, we train a Q-network to learn a UAV control policy that generalizes over varying starting positions and varying power constraints. Using this method, we observed an incremental learning process that successfully balances safe landing and coverage of the target area on two different maps. In the first environment all cells have to be visited and in the second scenario, only a distinguished area is considered as target. The first results are promising as the agent learn to come back to the base station to refuel and to avoid crossing the environment boundaries. The main drawback of the proposed method is that the training process is time consuming and the reward function could be tuned to get better results. In any case, the proposed approach can be seen as an initial step for handling the battery constraint in coverage problems on unknown maps. To complete this ongoin work, we plan to experimental show the relevance of our method compared with other naive coverage paths, for instance the zig-zag patterns. In the future we also want to investigate the possibilities of transfer learning for this problem. At first we will train the drone with easier problems, for example, considering four actions, to further accelerate the training process described in this work. From there we will examine approaches to transfer the agent learning to greater dimensions and dynamics. Finally, another interesting direction for future research is to adapt our method for a more realistic scenario in which the power consumption is variable (depending on the wind, for example), the map has different topological altitudes, there exist obstacles or forbidden zones, etc. 55