Explicit-Implicit Subgoal Planning for Long-Horizon Tasks with Sparse Reward

Recent advancements [9, 5] in imitation learning reveal the capacity of humans to identify and learn critical points from expert demonstrations or trajectories to accomplish the final goal. For instance, Paul et al. [8] derive a mapping from current states to subgoals using labels directly acquired from expert trajectories. Jin et al. [19] propose a method enabling the robot to learn an objective function from a few sparsely demonstrated keyframes to solve long-horizon tasks. [20] learns dual-arm manipulation tasks from demonstrations generated by a teleoperation system. Joey et al. [21] first utilize representation learning with an instruction prediction loss that operates at a high level of abstraction to accelerate imitation learning results. However, since the trajectories generated by human experts cannot cover the entire region of the state space, the trained policies generalize poorly to unseen tasks. In addition, the strategies trained through imitation learning may not be optimal since the demonstration data probably is not optimal and the trained strategies are unlikely to surpass the demonstration policy. Our approach does not require expert demonstrations and instead employs Reinforcement Learning (RL) to explore the optimal policy through trial and error.

Increasing the exploration efficiency of robots is crucial for solving long-horizon tasks. Numerous studies have endeavored to enhance exploration efficiency by enriching the experience replay buffer to incorporate more unknown states. Works such as Skew-Fit [10], RIG [11], and MEGA [12] prioritize exploring low-density or sparse regions, with the intent of maximizing the likelihood of visiting fewer states, which is equivalent to maximizing the entropy of the desired goal distribution. Warde-Farly et al. [22], on the other hand, aim to learn goal-conditional policies and reward functions by maximizing the mutual information between the achieved and final goals. Conversely, Hartikainen et al. [23] chose subgoals that maximize the distance from the initial state, thereby maximizing the entropy of the desired goal distribution. In general, these methods expand the exploration space but continue to depend on uniformly distributed actions and random action noise. Thus, goal exploration remains limited to neighboring states near the explored region. Our work tackles the exploration challenge by automatically generating subgoals that can be predicted on the way to the long-horizon final goal.

Drawing inspiration from the human tendency to decompose long-horizon tasks into smaller ones, some researchers are exploring the generation of subgoals by selecting them from historical experiences [24, 15, 25] or by training subgoal models [2, 16]. The experience replay buffer, rich in valuable historical data, facilitates the extraction of valid states as subgoals in a simple and efficient manner, while also ensuring their reachability. However, some methods necessitate the explicit specification of the number of subgoals or decision layers and rely solely on the initial state to predict future subgoals [2]. And distance-based methods, like [2, 16] strive to maximize the distance between the subgoals and the initial state to obtain better subgoals. They typically assume the co-existence of states and goals within the same space. This assumption does not hold true in numerous environments. For example, in the Stack environment, the state comprises the information of blocks and gripper, whereas the goal pertains solely to the goal position of blocks.

Recently, new image editing diffusion models like SuSIE [26] and SkillDiffuser [27] have been introduced for subgoal generation. Despite their powerful capabilities, these models depend on pretrained large diffusion models and robot demonstration video data, and are confined to image-based environments. Moreover, the substantial computational resources required for these large models pose a challenge for deployment in real-world robotic tasks.

Contrary to previous work that infers subgoals exclusively using an explicit model, we restrict our policy search by employing an implicit model and the prior distribution implicitly represented in the offline dataset. Our work also adopts a divide-and-conquer manner to solve long-horizon tasks by utilizing the hierarchical architecture [28, 29, 30], where the top-level focuses on reasoning and decision-making to generate subgoals, and the low-level interacts with the environment to achieve the subgoals sequentially.

We formulate the long-horizon task as a Semi-Markov Decision Process (Semi-MDP) [31]. More precisely, we extend the general MDP by adding option policy $\psi$ and options $\mathcal{O}$. The Semi-MDP is denoted by $\langle\mathcal{S},\mathcal{A},r,\rho_{0},\rho_{g},\mathcal{T},\gamma,\mathcal{G},\mathcal{O},\psi\rangle$, where $\mathcal{S}$ is state space containing all possible state, $\mathcal{A}$ is action space and $r$ is the reward function. We use $\rho_{0}$ and $\rho_{g}$ to denote the distribution of initial state and final goal, respectively. $\mathcal{T}:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{S}$ is the transition function and $\gamma$ is the discount factor. $\mathcal{G}$ is the goal space from which final goals and subgoals can be sampled. $\mathcal{O}:\langle\mathcal{I},\pi,\mathcal{E}\rangle$ is the option consisting of three components, where $\mathcal{I}\in\mathcal{S}$ is the initial state space, $\mathcal{E}\in\mathcal{S}$ is the terminal state space, $\pi$ is the specific policy for current option, respectively.

We denote the achieved goal at time step $t$ as $ag_{t}$. Typically, $ag_{t}=\phi(s_{t})$, where $\phi:\mathcal{S}\rightarrow\mathcal{G}$ represents a known and traceable mapping that defines goal representation [32]. The subgoal is often identified as the achieved goal at the terminal state of an option. $\psi:\mathcal{S}\times\mathcal{G}\rightarrow\mathcal{G}$ is the option policy mapping from state and final goal to subgoal for inferring a sequential option $\{o_{1},o_{2},\cdots,o_{n}\}$ where each $o_{i}\in\mathcal{O}$. And for each option $o_{i}$, the policy $\pi_{i}$ is utilized when the agent encounters the initial state $s_{0}^{i}\in\mathcal{I}$ and terminates in $s_{e}^{i}\in\mathcal{E}$.

In sparse reward goal-conditioned RL, the reward function $r$ is a binary signal indicating whether the current goal is achieved, as expressed by,

Soft Actor-Critic (SAC) [33] is an off-policy reinforcement learning algorithm that attempts to maximize the expected return and increase the policy’s entropy. The underlying idea is that increasing entropy leads to more exploration and effectively prevents the policy from reaching a local optimum.

Let $\tau=\{s_{0},a_{0},s_{1},a_{1},\cdots\}$ be the trajectory starting from initial state $s_{0}$. We use $\rho_{\tau}=\rho_{0}\prod_{t}\pi(a_{t}|s_{t},g)\mathcal{T}(s_{t+1}|s_{t},a_{t})$ to denote the distribution of the $\tau$ induced by the policy $\pi$.

In contrast to the standard maximum expected reward used in traditional reinforcement learning, the objective of action policy $\pi$ aims to maximize its entropy at each visited state by augmenting with an entropy term,

Thus, we can obtain the optimal action policy $\pi^{*}$ by:

Hindsight Experience Replay (HER) [34] is an algorithm that improves data efficiency by relabeling data in the replay buffer. It builds on the basis that failed trajectories may still achieve other unexpected states, which could be helpful for learning a policy.

It mitigates the challenge of sparse reward settings by constructing imagined goals in a simple heuristic way to leverage previous replays. During the training process, the HER relabeled the desired goal of this trajectory by specific sampling strategies, such as future and final, which take the future achieved goal and the final achieved goal as the desired goal, respectively.

Given an initial state $s_{0}$ and a final goal $g$, we expect the robot to infer a series of subgoals $\{\hat{g}_{1},\hat{g}_{2},\cdots,\hat{g}_{n-1}\}$ to guide it to the final goal $g$. These subgoals are subsequently utilized to bootstrap the low-level action policy $\pi$, thereby generating the actions to accomplish each subgoal.

Generally, most current subgoal generators [2, 24, 15] employ an explicit feed-forward model that maps subgoals directly from the state and the final goal. These methods are inspired by the human approach to solving long-horizon tasks, wherein humans generate subgoals to decompose long-horizon tasks into smaller, more manageable ones based on the final goal and the current state. However, one critical aspect often overlooked is that humans can also predict long-term outcomes using short-term subgoals conditioned on the current state. Current research [18] in behavior cloning has demonstrated that implicit models possess a superior capacity to learn long-horizon tasks more effectively than their explicit counterparts. This evidence incites us to employ the implicit model in subgoal generators, which is anticipated to enhance the ability to solve long-horizon tasks significantly.

Based on these insights, we propose a hybrid subgoal generator, fundamentally structured as a Conditional Variational Autoencoder (CVAE) [36]. Within this framework, the encoder $\psi$ serves as an explicit model that can infer a sequence of subgoals based on the current state and the final goal, while the decoder $\psi^{\prime}$ functions as an implicit model, designed to reconstruct the final goal using the current state and the given subgoals, as depicted in Fig. 4. After preprocessing the state $s$ and the final goal $g$ through several fully connected layers, the encoder computes the mean $\mu$ and the standard deviation $\sigma$ via two fully connected networks. The subgoal is then sampled from the normal distribution modeled using these calculated values of $\mu$ and $\sigma$. The decoder takes the subgoal $\hat{g}_{i}$ as input and conditioned on the current state $s_{0}^{i}$ to generate the reconstructed final goal $g^{\prime}$. Notably, we also employ the reparameterization trick to make the encoder and decoder differentiable.

Unlike the original CVAE, where the latent space serves as a low-dimensional mapping from the inputs, we employ the CVAE structure but interpret the latent space as the subgoal space. This approach distinguishes our work from previous studies [2], which also use the CVAE structure to generate subgoals but focus on reconstructing the subgoal using a learned latent representation of the transitions. By modeling the conditional option policy $\psi$, which takes as inputs the initial state $s_{0}^{i}$ of option $i$ and the final goal $g$, we transition the subgoal generation approach from the initial planner (which infers subgoals only at the initial state) to an incremental Planner (which infers subgoals based on current state). That is, the subgoals can be inferred incrementally by:

The subgoals sampled from the ground truth subgoal distribution ensure that the transition probability from the current subgoal $\hat{g}_{i-1}$ to the next subgoal $\hat{g}_{i}$ is greater than zero. Thus, the distribution of the generated subgoals should closely approximate the true subgoal distribution, which can be achieved by minimizing the KL divergence between the distribution of the generated subgoals by $\psi$ and the true valid subgoal distribution $p_{t}(\hat{g}_{i})$. However, the primary challenge arises from the unknown ground truth subgoal distribution $p_{t}(\hat{g}_{i})$, which complicates the estimation of the KL divergence.

Empirically, the subgoal distribution within the offline dataset $\mathcal{D}$ can be approximately regarded as the ground truth subgoal distribution. Therefore, we adopt the subgoal distribution of the offline dataset as our prior distribution and aim to minimize the KL divergence between them. To this end, we present a Hindsight Sampler, an approach based on the Hindsight Experience Replay buffer [34], designed to sample valid subgoals from an offline dataset. The core idea is to regard the achieved goal reached at the end of the trajectory as the final goal and recalculate the rewards for all states in the current trajectory. This revised trajectory is then employed to train the option policy. As shown in Fig. 5, during the training period, we first sample the trajectory $\tau_{D}$ with total time step $T_{\tau}$ from the offline dataset $\mathcal{D}$, and take the final achieved goal of this trajectory as the desired goal $g$ of the current trajectory. We then select waypoints from the trajectory as subgoals at intervals of $T_{\tau}/n$, denoted as $\left\{\hat{g}_{1}^{\prime},\hat{g}_{2}^{\prime},\cdots,\hat{g}_{n-1}^{\prime}\right\}$.

We utilize the maximum likelihood estimation (MLE) [38], which is a method estimating the parameters of an assumed probability distribution given some observed data, to maximize the log-likelihood of the valid subgoals sampled from the offline dataset under the unknown option policy $\psi$. The objective of the Hindsight Sampler $L_{HS}$ is as follows:

The Universal Value Function Approximator (UVFA) plays a critical role in goal-conditioned RL. It functions as a mapping from the goal-conditioned state space to a nonlinear value function approximator [39]. We denote the state value function as $V$. In the context of goal-conditioned RL, it is typically utilized to assess the current state under the condition of the goal. The value function $V$ of SAC in goal-conditioned RL involves the extra entropy bonuses from every time step utilized to assess the state, denoted as follows:

where $s_{0}=s$. In our algorithm, $V$ serves a dual purpose: guides the updates of low-level policy and selects optimal subgoals for the high-level planner. To generate subgoal $\hat{g}$ at current state $s_{t}$, conditioned on the final goal $g$, we initially sample $K$ candidates $\left\{\hat{g}_{1},\hat{g}^{2},\cdots,\hat{g}^{k},\cdots,\hat{g}^{K}\right\}$ using the Hybrid Subgoal Generator, where $\hat{g}^{k}\sim\psi(s_{t},g)$. As shown in Fig. 3, the candidates are then ranked using the state value function $V$, where higher state values represent better subgoals. Hence, the subgoal state corresponding to the highest value will be selected as the optimal subgoal $\hat{g}^{*}$ for the action policy, that is,

The optimal subgoal $\hat{g}^{*}$ is subsequently utilized to guide the low-level action policy. The value function may not be optimal during the initial stages of training as the low-level policy may not be sufficiently trained. However, as the training of the value function progresses and improves, the selected subgoals also tend towards optimality.

Alg. 1 offers a detailed description of the process of collecting rollout experience for the experience replay buffer. The function $D(g_{1},g_{2})$ is employed to estimate the distance between goals $g_{1}$ and $g_{2}$. We will initially infer a set of potential subgoal candidates via the Hybrid Subgoal Generator when the current subgoal is achieved or the time limit $T$ is expirated. Then, the optimal subgoal is selected using the Value Selector. By replacing the final goal with the selected subgoal continuously, we can obtain trajectories of transitions $(s_{t},a_{t},r_{t},s_{t+1},\hat{g}^{*})$ and store it to the replay buffer $\mathcal{D}$.

The entire training process of EISP is shown in Alg. 2. At first, a mini-batch $\mathcal{B}$ is sampled from $\mathcal{D}$, consisting of $N-1$ transitions of $(s_{t},a_{t},r_{t},s_{t+1},g)$, where $t\in[1,N]$. For each transition, the final goal $g$ is relabeled by the future achieved goal, and valid subgoals $\hat{g}^{\prime}$ will be sampled by using the Hindsight Sampler. Then, the objective of the EISP is formulated as:

Since the off-policy RL algorithms are used to train the low-level action policy, we collect trajectories by using scripted policies to pre-train the subgoal generator and then fine-tune it during the low-level training process. The proposed subgoal inference algorithm is entirely compatible with other off-policy algorithms, owing to its exclusive focus on high-level planning. We employ the SAC method to train the low-level policy.

We evaluate EISP in four tasks: 1) Stack, 2) Push, 3) OpenDrawer, and 4) Store, as depicted in Fig. 6. The left and right columns present the simulation tasks and real-world tasks. All simulation environments are created using the Gymnasium Robotics [40] Framework. The dimensional information of the state space $\mathcal{S}$, action space $\mathcal{A}$, goal space $\mathcal{G}$, and the episode length $L$ are provided in Table I.

The Hybrid Subgoal Generator is based on the CVAE structure and consists of an encoder $\psi$ and a decoder $\psi^{\prime}$. The encoder takes the current state and the desired goal as inputs and uses two probabilistic neural networks to output the mean $\mu$ and deviation $\sigma$. We then parameterize the Laplace distribution with the above outputs. We implement two probabilistic neural networks using one layer of fully connected network mapping from the encoder output to the subgoal space. The decoder has the opposite structure to the encoder. It takes as inputs the encoder-generated subgoals and the current state and outputs the reconstructed desired goal. The SAC is used as the underlying RL algorithm for action policy training and then fine-tuned online. We use a fixed temperature parameter $\alpha=0.01$ for all tasks. Table I presents the specifications of various parameters including the size of the replay buffer $\mathcal{D}$ and the mini-batch $\mathcal{B}$, the network structure, and the learning rates of SAC and EISP. We set the number of subgoals used in Hindsight Sampler as Table I. The weight $\beta$ used in (13) refer to Table I. Both the option and action strategies use the Adam optimizer to update the network parameters. During the training process, we set a time limit of $T=30$ to update the subgoal when the current subgoal is not reached. For image-based observations, we employ a vector quantized variational autoencoder (VQ-VAE) [42] to extract features, which are subsequently used as input for subgoal generation. Detailed training procedures and results of the VQ-VAE can be found in Appendix -C and -D.

This section demonstrates the feasibility and optimality of inferred subgoals through the qualitative results.

It should be noted that many inferred subgoals are still noisy, indicating that certain subgoals may be unreachable within a given time step. This phenomenon is expected, as these subgoals typically provide the direction to aim for rather than the precise position the robot should achieve. The robot can ultimately achieve the final goal as this direction is progressively updated. Furthermore, EISP demonstrates robustness against non-optimal or unfeasible subgoals that may emerge during strategy execution, as it infers subgoals based on the current observation. For instance, the third subgoal generated in the Stack task seems not optimal since it is not directly on the path to the final goal. However, it still provides directional guidance for the robot. As time progresses and the time budget for the current option expires, the next subgoal will offer more accurate information for the robot to achieve its objective.

Additionally, we perform qualitative experiments to demonstrate the superiority of our proposed methods. We conduct two ablation experiments, with the Hindsight Sampler and the Value Selector components being excluded respectively, to isolate their individual contributions to the overall performance. We also conduct comparative experiments against current state-of-the-art subgoal-generator algorithms, namely RIS (Reinforcement learning with Imaged subgoals) [24], HP (Hindsight Planner) [15], and LEAP (Latent Embeddings for Abstracted Planning) [16].

• •

  RIS aims to identify subgoals that are maximally distant from the initial state and final goal.

• •

  HP employs the LSTM [44] architecture to sequentially generate subgoals by continuously integrating previously generated subgoals.

• •

  LEAP learns the goal-conditioned policy predicated on the latent embedding of original complex observations.

To ensure a fair comparison, all methods employ SAC as the underlying RL algorithm with identical network architecture. The trained policies are tested on four long-horizon tasks, inclusive of our method and the aforementioned baselines, with success rates depicted in Fig. 10. The results demonstrate that the EISP algorithm, which utilizes both the Hindsight Sampler and the Value Selector module, yields the highest success rates. The strategy without the Hindsight Sampler, labeled EISP w/o HS, encounters difficulties in rendering the subgoals generated by the RL agent feasible, resulting in low success rates across all four environments. Conversely, the strategy lacking the Value Selector module, denoted as EISP w/o VS, still manages to achieve a measure of success (for instance, approximately a 60% success rate on the Stack task). This suggests that the optimization module primarily functions as a facilitator to expedite the training of the subgoal generator, enabling the strategy to converge more rapidly and attain a higher success rate. When compared to other state-of-the-art subgoal-oriented reinforcement learning methods, EISP consistently demonstrates a superior success rate. On the Push task, EISP achieves a success rate exceeding 70%, while LEAP achieves a success rate of approximately 38%, and other methods yield success rates of less than 20%.

After conducting five tests on four tasks using distinct seeds, the expected returns recorded for all the training policies are presented in Table II, with the highest return for each task emphasized in bold and the second highest return emphasized in underlining. A higher expected return indicates a superior policy. While all policies can potentially lead to higher expected returns, our approach produces the most substantial improvements in expected returns. The LEAP and HP methods rely solely on the initial state to infer subgoals, which proves insufficient for tasks with varying desired goals. These methods lack robustness for complex long-horizon tasks in most scenarios, and a change in the desired goal results in the generated subgoals becoming less accurate, leading to task failure. Furthermore, sampling subgoals randomly from the experience buffer can result in inaccurate subgoals, impeding the generation of optimal lower-level action policies. For detailed information on episodic returns throughout the entire training procedure, you can refer to Appendix -E.

To demonstrate the adaptability of our algorithms in the real world, we employ the Tiago++ robotic arm [45] to execute Stack and Push tasks, and the UR3 robotic arm for OpenDrawer and Store tasks. The setups of these four environments are the same as in the simulation. Our experiments utilize Pinocchio [46] for both motion planning and inverse kinematics. As depicted in Fig. 11, red cubes are manipulated by the robotic arm to complete the assigned task, with the number of red blocks used in Stack and Push being 3 and 4, respectively. We mount a calibrated Intel RealSense D435i RGB-D camera on the top of the table to facilitate top-view observation. We also fix a soft beam to the end of the gripper to mitigate potential collisions between the gripper, the table, and the blocks during the execution of the Push task.

The strategy employed to guide the robot is identical to that used in the simulation. To gather environmental observations, we utilize Aruco markers for the detection of each object’s and gripper’s position. Fig. 12 illustrates the subgoals inferred from the initial state to the desired goals for four manipulation tasks. The desired goals are denoted as green spherical shades and the subgoals as transparent squares. During execution, the Aruco markers may be occluded by the robotic arm, causing the top-view camera unable to detect the markers at certain time steps, primarily in the Stack and Push task. To address this problem, we maintain the last known position of the markers and update it when markers become detectable again. Additionally, the robot arm is reset to a specific pose to observe the current state after achieving each subgoal. We also conducted robustness tests and failed case studies, with the results presented in Appendix -F and -G.