Reinforcement learning with parameterized action space and sparse reward for UAV navigation

2.1. MDP and PAMDP

MDP is built based on a set of interactive objects, namely agents and environments. MDP consists of a state space $$ S $$, an action space $$ A $$, a state transition probability distribution $$ P(s_{t+1}|s_t, a_t) $$, and a reward function $$ R:r_t = r(s_t, a_t) $$. Where $$ P $$ satisfies the Markov property, and $$ R $$ represents the immediate reward $$ r_t $$ obtained by executing an action $$ a_t $$ in a given state $$ s_t $$. RL, which learns the optimal policy based on trial and error, provides a way to solve the MDP problem. The policies learned based on RL are divided into deterministic policy and stochastic policy. For discrete action spaces, the deterministic policy is expressed as $$ a_t=\pi(s_t) $$, which means that a certain action $$ a_t $$ can be obtained for a given state $$ s_t $$. The stochastic policy is denoted as $$ a_t \sim \mu(\cdot|s_t) $$, which means to select an action $$ a_t $$ from the probability distribution after a given state $$ s_t $$. If the action space is continuous, the corresponding policies above will be parameterized as functions $$ a_t = \pi(s_t, \theta) $$ and $$ a_t \sim \mu(\cdot|s_t, \theta) $$, where $$ \theta $$ refers to the parameters of the function. To uniform representation, we all implicitly mean that policy $$ \pi $$ (or $$ \mu $$) is a function of $$ \theta $$, and all the gradients are with respect to $$ \theta $$ in the following contexts. RL involves estimating state-value functions $$ V(s) $$ and action-value functions $$ Q(s, a) $$. Taking deterministic policy as an example, the state-value function is defined as

where $$ \gamma\in[0, 1] $$ is a discount factor, and the action-value function is defined as

The agent learns an optimal policy by maximizing the expected discounted reward (target function) as follows

If $$ \pi $$ is a stochastic policy, the corresponding state-value function, action-value function, and target function can be obtained by replacing $$ a_t = \pi(s_t) $$ by $$ a_t \sim \mu(\cdot|s_t ) $$ in (1), (2), and (3).

PAMDP is an extension of MDP on the action space, allowing decision-making using parameterized actions. Parameterized actions flexibly integrate discrete actions and continuous actions and provide richer expressiveness. In tasks such as UAV navigation, which demand precise parameter control, using parameterized actions enables finer-grained control. Moreover, from an interpretability standpoint, the structural characteristics of parameterized actions make the decision-making process of agents more understandable and explainable. The action space of PAMDP can be expressed as $$ \mathcal{H}=\left\{\left(k, x_k\right)|x_k\in\mathcal{X}_k\right\}\ for\ all\ k\in K $$, where $$ k=\left\{1, ..., K\right\} $$. $$ K $$ denotes the number of discrete actions. $$ k $$ refers to a specific discrete action (e.g., $$ k=1 $$ means movement and $$ k=2 $$ means turning). $$ x_k $$ represents the continuous parameter (e.g., acceleration or angle) associated with the discrete action $$ k $$. $$ \mathcal{X}_k $$ is the set of all continuous parameters. In the PAMDP, the agent first selects a discrete action $$ k $$, then obtains the corresponding $$ x_k $$ from $$ \mathcal{X} $$ according to $$ k $$, and finally executes the action $$ (k, x_k) $$. Therefore, PAMDP has subtle differences in the interaction process compared to standard MDP. Assuming that at step $$ t $$, PAMDP is in state $$ s_t $$, the agent executes an action by policy $$ \pi $$: $$ s_t\rightarrow \left(k_t, x_{k_t}\right) $$ and receives an immediate reward $$ r $$$$ \left(s_t, k_t, x_{k_t}\right) $$ and the next state $$ s_{t+1} \sim P\left(s_{t+1}|s_t, k_t, x_{k_t}\right) $$. The target function of the agent becomes as follows

2.2. Sparse reward problems

The sparse reward scheme is a reward mechanism that uses only binary values to indicate whether a task is eventually completed. Specifically, the agent can get a positive reward when completing the task and a negative reward during exploration. Although this mechanism reduces the effort required for human design, it brings potential learning problems. The lack of effective rewards prevents the agent from judging the pros and cons of its behavior and thus cannot optimize the policy $$ \pi $$ correctly. Under the influence of the sparse reward problem, the agent learns slowly or even fails to learn. Solving the harmful interference brought by the sparse reward scheme is one of the focuses of this paper.

3.1. UAV navigation tasks

In this paper, UAV navigation tasks are divided into the direct navigation task [Figure 1] and the relay navigation task [Figure 2]. The distinction between these tasks lies in the presence of intermediate operations that the UAV needs to perform. As a result, the flight requirements for UAVs in relay navigation tasks are more demanding. Nevertheless, the simple task is also considered to verify the effectiveness and generality of the algorithm.

Figure 1. The direct navigation task. The UAV only needs to fly from the initial point to the target area.

Figure 2. The relay navigation task. The UAV needs to operate on "catching supply" during the navigation process.

Typically, the position, direction, and motion of the UAV are determined by both the earth and the body coordinate frame. The earth coordinate frame is used to describe the position and direction of the UAV, denoted as $$ \phi=[x, y, z, \theta_x, \theta_y, \theta_z] $$. The linear and angular velocities of the UAV are denoted as $$ \psi=[v_x, v_y, v_z, \omega_x, \omega_y, \omega_z] $$ in the body coordinate frame.

For simplicity, the UAV is assumed to fly at a fixed altitude, i.e., the motion of the UAV is constrained within the x-y plane. Moreover, the steering action of the UAV takes effect immediately because the momentum is ignored. As a result, the vector describing the motion information of the UAV is simplified to $$ \xi=[x, y, v, \theta] $$, and the motion formula is expressed as follows

where $$ \Delta\theta $$ is the steering signal, $$ \Delta a $$ is the acceleration signal, $$ v $$ is the speed of the UAV, and $$ \theta $$ is the direction angle between the UAV and the target.

3.2. State representation specification

State representation is essential for the agent to perceive the surrounding environment and reach the target position. In our setting, the state vector is reduced as much as possible to avoid interference from irrelevant information and speed up training. Specifically, the observable information of the UAV has three sources. The first is the internal state of UAVs, which is represented in terms of position $$ [x, y] $$, velocity $$ v $$, and direction $$ \theta $$. The second is the relationship between UAVs and the environment. Since obstacles are not considered, the number of actions the UAV performs is used to be the unique representation, which is recorded as $$ n_{step} $$. Taking $$ n_{step} $$ as the state can encourage the UAV to complete the task with fewer steps. The last is the relationship information between the UAV and the target. Also, to simplify the representation, the distance between the UAV and the target is only used to describe this relationship, denoted as $$ d_{target} $$. By combining the three kinds of information, the final form of the state vector becomes: $$ s=[x, y, v, \theta, d_{target}, n_{step}] $$. For relay navigation tasks, UAVs need additional information about supplies. The location information of the supply can be directly obtained from the simulation environment. In this paper, the distance $$ d_{supply} $$ between the UAV and the supply is included as one of the state representations to fulfill this requirement. As a result, the state vector in the relay task is modified as follows: $$ s=[x, y, v, \theta, d_{target}, d_{supply}, n_{step}] $$.

3.3. Parameterized action design

Considering that the flight altitude of the UAV has been set as a constant above, its movement in the vertical direction can be ignored. For the direct navigation task, the optional discrete actions of the UAV are defined in the discrete set $$ \mathbb{D}=\left\lbrace k_1, k_2\right\rbrace $$. Where $$ k_1 $$ represents the "MOVE" behavior and $$ k_2 $$ represents the "TURN" behavior. In addition, the parameter set $$ \mathbb{C}=\left\lbrace(c_1), (c_2)\right\rbrace $$ defines the continuous parameters corresponding to each action in $$ \mathbb{D} $$, where $$ c_1 $$ represents the acceleration value and $$ c_2 $$ represents the rotation angle. When the UAV acts, it not only needs to select the discrete action but also needs to determine the corresponding parameter values. To sum up, the parameterized action space of UAV is represented as $$ \mathcal{H}=\left\lbrace(k_1, (c_2)), (k_2, (c_2)\right\rbrace $$. The value range of $$ c_1 $$ and $$ c_2 $$ are scaled to $$ [-1\sim1] $$. Since the UAV needs to perform intermediate operations for the relay navigation task, a new discrete action $$ k_3 $$ will be added to $$ \mathbb{D} $$ to represent the "CATCH" behavior. It should be pointed out that action $$ k_3 $$ does not set continuous parameters. This is because we focus more on learning the navigation policy rather than the specific control process. When the UAV gets close enough to the supply, it performs the "CATCH" action, allowing the supply to move with itself. However, when the UAV is far away from the supply, it will not affect the supply when it performs the "CATCH" action. In this case, the UAV advances one step based on the current speed and angle. The primary goal of the UAV is to transport the supply to the target area.

3.4. Sparse reward function

Although sparse reward setting is simple and universal, different tasks need to set corresponding reward functions, which will bring different degrees of sparsity. The direct navigation task aims to get the UAV to reach the target area, which is a single-stage task with a relatively small reward sparsity. In the relay navigation task that contains supplies, an effective reward can be obtained only when the UAV finds supplies and carries them to the target area. This task includes relay operations which significantly increase the reward sparsity. Existing baselines are not effective at handling the relay task. This phenomenon and the solution are described in detail in Section 4.2. According to the above task requirements, the reward function of the direct navigation task is defined as

and the reward function of the relay navigation task is defined as

4.1. Multi-Pass Deep Q-Network (MP-DQN)

MP-DQN is an off-policy RL algorithm that deals with parameterized action space. In MP-DQN, the goal of the agent is to optimize the policy $$ \pi:S\rightarrow A $$, which maximizes the long-term cumulative discounted rewards:

Due to the integration of DQN^[29] and DDPG^[30] algorithms, MP-DQN has a network architecture similar to the Actor-Critic architecture. In specific, the MPDQN agent has an actor-parameter network $$ \pi_{\theta_x} $$ (similar to Actor) and a Q-value network $$ Q_{\theta_Q} $$ (similar to Critic). Where $$ \theta_x $$ and $$ \theta_Q $$ are parameters of the network. The discrete action policy is implicitly learned when approximating the Q-value function.

For the actor-parameter network, the MP-DQN agent learns a deterministic mapping policy $$ \pi_{\theta_x}(s) $$ from state to continuous parameters vector as follows

where $$ \mathcal{X}^t_k=[x^t_1, x^t_2, ..., x^t_K] $$ contains all continuous parameters corresponding to the discrete actions $$ k $$. In order to decouple discrete actions and irrelevant continuous parameters, the $$ \mathcal{X}^t_k $$ becomes

Each row of the matrix is fed into the Q-value network separately, thereby eliminating the influence of irrelevant parameters on the estimation of the Q-value function.

For the Q-value network, MP-DQN evaluates actions using an action-value function similar to DDPG. Since MPDQN needs to optimize both discrete actions and continuous parameters, the Bellman equation becomes

where $$ k_t $$ is the discrete action selected at time $$ t $$, and $$ x_{k_t} $$ is the associated continuous parameter. To avoid taking supremum over continuous space $$ \mathcal{X}_k $$, equation (10) is rewritten as:

where $$ \pi_{\theta_x}:S\rightarrow \mathcal{X}_k $$ represents the mapping relationship in equation (9). This means that approximating the Q-value function needs to fix $$ \theta_Q $$ first and find $$ \theta_x $$ such that

Then, similar to DQN, $$ \theta_Q $$ is estimated by minimizing the mean-squared Bellman error. The loss function of the Q-value network is:

where

The loss of the actor-parameter network is given by the negative sum of Q-values as

4.2. Hindsight experience replay

HER is another important baseline algorithm that we consider in our method. The core idea is to expand the experience by constructing the goal variable as shown in Figure 3 (a). There are two ways to construct the goal variable:

Figure 3. Illustration of positive reward sparsity for HER. (a) In the task that does not contain the manipulated object, achieved goal is directly affected by the behavior of the agent and constantly changes in each rollout. In this case, HER can generate valuable learning experiences. (b) For the task containing the manipulated object, achieved goal remains unchanged until the agent comes into contact with the object. In this case, all the experience generated by HER includes positive rewards but has no substantial help to the learning of the agent.

$$ 1) $$ Direct construction: The agent uses the target information feedback by the environment as the goal variable at step $$ t $$, which is recorded as $$ desired\_goal_t $$. Additionally, the location of itself at step $$ t $$ is recorded as $$ achieved\_goal_t $$. In the relay navigation task, the traditional algorithm will always record the location of the supply as $$ achieved\_goal_t $$. In our method, the information represented by $$ achieved\_goal_t $$ changes with the state of the agent; see the end of this section for the specific process.

$$ 2) $$ Replacement construction: Through direct construction, an experience can be obtained at step $$ t $$, simplified as $$ (achieved\_goal_t, desired\_goal_t) $$. The HER algorithm will randomly sample 4 items from the experience obtained from step $$ t+1 $$ to step $$ T $$ and then uses the $$ achieved\_goal $$ as the goal variable to replace the $$ desired\_goal $$ in the experience at step $$ t $$. $$ T $$ is the maximum step that allows the agent to act in a single task.

The new goals constructed in the above way have the potential to be generalized to unseen real goals. Although the agent fails to achieve a given goal in the current episode, it still learns action sequences that may achieve different given goals in a future episode. Therefore, the original failure transition can be transformed into the virtual success transition by selecting a new goal from the state experienced to replace the initial goal.

However, HER tends to be less efficient in some relay tasks. As shown in Figure 3 (b), the goal of the agent is to deliver the block to the target area. It should be noted that the $$ achieved\_goal $$ (i.e., the location of the block) defined in HER has not changed when the agent is not in contact with the block. Any hindsight goal selected by HER is labeled as a "success episode". However, such a "successful episode'' cannot bring meaningful guidance to the agent. This, in part, leads to another kind of sparsity, positive reward sparsity.

To solve this problem, we propose the goal-switch mechanism (GSM). The principle of the GSM aims to generate meaningful goal variables by dynamically assigning goals during experience expansion. In the relay navigation task, the conventional HER approach always designates the target area as the $$ desired\_goal $$ and the supply point as the $$ achieved\_goal $$. GSM assists the UAV in determining the goal based on the current state: (1) Prior to acquiring the supply, the supply point is marked as the $$ desired\_goal $$, and the own position of the UAV is labeled as the $$ achieved\_goal $$. (2) After acquiring the supply, the target area is marked as the $$ desired\_goal $$, while the supply point remains as the $$ achieved\_goal $$. By assigning different goals, GSM enables the UAV to construct more effective goal variables and hindsight experiences, which helps mitigate reward sparsity. This simple idea provides an effective solution and is proved in Section 5.

4.3. HER-MPDQN

MP-DQN samples a fixed batch from an offline experience reply buffer to update the network. HER expands the original experience by goal replacement. On this basis, we further eliminate the hindsight experience without guidance significance. This means that our proposal can be effectively integrated with MP-DQN. As shown in Figure 4, the input vector of the neural network is extended in MP-DQN. In specific, the input vector of the actor-parameter network becomes

Figure 4. The network architecture of HER-MPDQN. For the symbols in the figure, $$ s $$ denotes the observed state, $$ g $$ represents the goal of the agent, $$ \theta_x $$ and $$ \theta_Q $$ refer to network parameters, and (256, 128, 64) indicates the number of neurons in the network. $$ x_k $$ is the continuous parameter corresponding to the $$ k $$th discrete action, where $$ k= 1, 2, ..., K $$. $$ K $$ is the total number of discrete actions. $$ xe_k $$ represents the expanded continuous parameter vector derived from $$ x_k $$. $$ Q_{kk} $$ denotes the Q value associated with the $$ k $$th discrete action. The selection of the discrete action $$ k $$ is determined based on the largest Q value.

Correspondingly, the input vector of the Q-value network becomes

In our method, the original experience is stored together with the hindsight experience in the replay buffer. A fixed batch of data is sampled from this buffer when the neural network needs to update. The training process in Algorithm 1 is generally divided into three steps: (1) The agent interacts with the environment to accumulate real experience; (2) Capture the original experience and hindsight experience of each time step and store all of them in the replay buffer; (3) Update the parameters of the network according to the length of each episode.

Algorithm 1: HER-MPDQN

Input: Minibatch size $$ B $$, exploration parameter $$ \epsilon $$, soft update parameter $$ \tau $$, learning rate $$ \alpha_{\theta_Q} $$ and $$ \alpha_{\theta_x} $$. Initialize the weight of Q-value network and actor-parameter network. Initialize target networks by hard update. for$$ episode=0, ..., max\_episode $$do

5.1. The direct navigation task

To our knowledge, open-source benchmark environments for UAV navigation tasks with parameterized action spaces and sparse rewards are currently lacking. Therefore, we simulate a large-scale environment inspired by the existing simulation¹. Figure 1 shows a top view of the navigation environment. The UAV can fly within four square kilometers (2$$ km $$$$ \times $$2$$ km $$). The same settings for the environment randomness are used to have a fair comparison. In each episode, the coordinate of the UAV and the target area are sampled from the uniform distribution of the entire environment. The default initial velocity of the UAV is 0. The goal of the UAV is to reach the target area in a limited number of steps. The optional actions are MOVE (acceleration) and TURN (angle). MOVE indicates that the UAV moves along the current direction with the given acceleration. TURN means that the UAV rotates at the given angle. The episode ends if the UAV reaches the target area (winning state) or the time limit exceeds.

¹https://github.com/thomashirtz/gym-hybrid.

We chose Python 3.7 as our development language due to its simplicity, flexibility, and efficient development capabilities. For algorithm development and testing, we utilize the OpenAI Gym library, which is an open-source RL library that offers convenient tools for creating custom environments. In terms of hardware, we employ an AMD Ryzen 7 5800H processor and 16GB of RAM. This configuration is relatively new and provides sufficient computing resources to support the training and testing of the algorithms developed in this study.

In the context of sparse rewards, the agent ends the current episode either when the task completion or the agent goes out of bounds which results in higher rewards. Therefore, relying solely on "episode rewards" is inadequate to assess the learning effectiveness. To evaluate algorithm performance, we utilize the "success rate" as a metric, which directly reflects the number of times the agent completes the task. Also, a higher "success rate" implies a higher "reward". The "success rate" is defined as follows:

where $$ \mathcal{SR} $$ means "success rate", $$ CT $$ is the number of times the agent completes the task, and $$ TT $$ is the number of times the agent performs the task.

We evaluated the performance of HER-MPDQN in the above environment. Besides, we also implement and test the following three baselines: HER-PDQN^[31], MP-DQN, ^[21] and P-DQN^[20]. Each algorithm uses the same network with hidden layer sizes (128, 64). The step size of each environment is limited to 100, the size of the replay buffer $$ R $$ is $$ 50, 000 $$, the mini-batch size $$ B $$ is 128, and the update frequency $$ U $$ of the network is 40. The learning rate of the Q-value network $$ \alpha_{\theta_Q} $$ and actor-parameter network $$ \alpha_{\theta_x} $$ is $$ 10^{-2} $$ and $$ 10^{-3} $$ respectively. Adam optimizer with an exponential decay rate of ($$ \beta_1=0.9 $$, $$ \beta_2=0.999 $$) is used for optimization. All algorithms run seven independent experiments and train 2, 000 episodes in each experiment.

Figure 5 provides the training process of the UAV in the direct navigation task. Table 1 shows the evaluation performance for each algorithm in 1000 episodes. The results show that HER-MPDQN has a faster convergence speed and higher average success rate. Compared to HER-PDQN, our method evaluates the Q-value more accurately and updates the actor-parameter network without bias. At the same time, the agent learns effective experience early by introducing HER, which brings stronger learning ability than the original MP-DQN. Since P-DQN has no additional mechanism to eliminate the influence of irrelevant parameters and deal with sparse rewards, its performance is not satisfactory. In addition, it can be seen that the learning curve of HER-MPDQN has a smaller shaded area. This means that HER-MPDQN has better robustness in various experiments.

Figure 5. Comparisons of the results using HER-MPDQN and other baselines. The left figure shows the periodic calculation of the task completion rate of the last 10 episodes, and the right figure shows the total success rate during the entire training process. The shaded area is the variance in multiple experiments. Smaller shading indicates that the algorithm is less sensitive to random seeds.

5.2. The relay navigation task

Considering the need for UAVs to deliver supplies, a relay navigation environment is further simulated. Compared with the previous environment setting, the following changes are made: (1) Add a supply point that requires the UAV to perform relay operations. (2) Introduce a new discrete action CATCH to represent grabbing operations. As shown in Figure 2, the UAV must deliver supply to the target area in a limited number of steps. CATCH is valid only when the UAV is in contact with the supply. Each episode ends when the supply has been transported to the target area (winning state) or the time limit exceeds.

Due to the increased complexity, the hyperparameters for this task are tuned as follows. The hidden layer size of all networks is set to (256, 128, 64). The size of the replay buffer $$ R $$ is $$ 150, 000 $$. The update frequency $$ U $$ changes according to the episode length and is limited to [1$$ \sim $$10]. The learning rate of the Q-value network $$ \alpha_{\theta_Q} $$ and actor-parameter network $$ \alpha_{\theta_x} $$ is $$ 10^{-3} $$ and $$ 10^{-5} $$, respectively. Each algorithm is trained with 30, 000 episodes in each experiment.

Figure 6 shows the learning curve in the relay task. The evaluation results are given in Table 2. It is obvious that HER-MPDQN is far superior to the other algorithms. On the one hand, more sparse rewards make it impossible for the UAV to complete tasks through random actions. Therefore, the MP-DQN and P-DQN without HER are challenging to learn. On the other hand, although many positive experiences are generated by introducing HER, they do not have guide significance. For this reason, HER-PDQN cannot learn policy effectively. By treating the relay task as a continuous multi-stage task, the goal is automatically allocated by HER-MPDQN according to the current state. Thus, the hindsight experience of different stages has the correct guiding significance. Figure 7 shows the flight trajectories of the trained UAV when performing specific relay navigation tasks. It can be seen that the UAV has learned the correct action policy. Not only that, HER-MPDQN exhibits good scalability in our experiments. The multi-goal relay navigation task can be completed by expanding the goal space. We leave this research for future work.

Figure 6. Comparisons of the results using HER-MPDQN and other baselines. The left figure shows the periodic calculation of the task completion rate of the last 100 episodes; other descriptions for evaluating algorithm performance are the same as Figure 5.

Figure 7. Illustration of flight trajectory map of the trained UAV in the relay navigation task. The red arrow represents the current direction of the UAV, and the red dotted line is the flight path.

Authors' contributions

Made contributions to the conception and design of the work, developed most associated code for the simulation environment and the reinforcement learning method, and performed data analysis and visualizations, manuscript writing, and related tasks: Feng S

Contributed to parts of the conception and design and performed the validation of the experimental design and related tasks: Li X

Contributed to the research supervision and guidance, provided environmental equipment, and performed analysis and transition of formal specifications, manuscript writing, and related tasks: Ren L

Participated in part of the experimental data analysis and visualizations and performed data collation and related tasks: Xu S

Availability of data and materials

This work is based on the Gym platform. All codes can be found at https://github.com/No-human-is-limited/HER-MPDQN. There are no additional data or materials associated with this study.

Financial support and sponsorship

This work was supported in part by the Open Project Program of Fujian Provincial Key Laboratory of Intelligent Identification and Control of Complex Dynamic System No: 2022A0001; in part by the National Natural Science Foundation of China No: 62203002; and in part by the Natural Science Foundation of Anhui Province No: 2208085QF204.

Conflicts of interest

All authors declared that there are no conflicts of interest.

Ethical approval and consent to participate

Not applicable.

Consent for publication

Not applicable.

Copyright

© The Author(s) 2023.