Guiding Search in Continuous State-Action Spaces by Learning an Action Sampler From Off-Target Search Experience

Beomjoon Kim, Leslie Pack Kaelbling, Tomás Lozano-Pérez

Abstract

Task and Motion Planning (TAMP) in continuous state-action spaces is a fundamental challenge in robotics, often hindered by the inefficiency of uniform sampling and the non-smooth nature of optimization manifolds. This paper introduces GANDI (Generative Adversarial Network with Direct Importance estimation), a framework that improves planning efficiency by learning an action sampler from a robot's entire search history. By utilizing a novel importance-sampling technique, GANDI leverages "off-target" data—failed attempts and dead-ends that are typically discarded—to train a robust GAN-based sampler. Experimental results in complex simulated environments like bin packing and stowing demonstrate that GANDI achieves higher success rates and faster learning than traditional methods.

Introduction

In robotics, planning complex tasks—such as reaching for an object at the back of a crowded shelf—requires solving both discrete logic (which item to move) and continuous geometry (where exactly to place it). This is known as Task and Motion Planning (TAMP). Standard planners often rely on uniform sampling, which is notoriously inefficient in high-dimensional spaces. Conversely, gradient-based optimization struggles with the "cliffs" in the problem landscape, where a millimeter's difference in placement can result in a catastrophic collision.

A robot performing a bin-packing task, requiring precise continuous action sampling to avoid collisions and dead-ends.

A significant missed opportunity in current TAMP research is the wealth of data generated during the search process. Most planners only learn from "on-target" samples—the successful actions that form the final plan. However, the vast majority of generated data consists of "off-target" samples: failed attempts that provide critical information about the boundaries of the feasible action space. GANDI aims to recycle this data to guide the search more effectively.

The GANDI Framework

The core of GANDI is a Generative Adversarial Network (GAN) trained to act as an action sampler. Instead of sampling randomly, the planner queries the GAN for promising actions given the current state.

Importance Ratio Estimation

To incorporate off-target data without biasing the model toward failure, GANDI employs a secondary Deep Neural Network (DNN) to estimate an importance ratio. This ratio determines how much a failed action resembles a potentially successful solution. By re-weighting off-target data based on these ratios, the GAN's discriminator is presented with a balanced set of "pseudo-successful" actions, allowing the generator to learn a more accurate distribution of high-quality actions.

Theoretical Foundation

The authors provide mathematical proofs ensuring that the resulting learned distribution (measured via KL divergence) remains bounded even when errors occur in the importance estimation. This makes the bootstrapping process stable and reliable for real-world planning scenarios.

Experimental Evaluation

GANDI was evaluated across three challenging simulated environments:

  1. Bin Packing: Packing 5–8 objects into a tight bin, where early placement mistakes lead to inevitable failure.
  2. Stowing: Placing 8 objects into cluttered bins, requiring 4D continuous action-space reasoning.
  3. Reconfiguration: Moving obstacles to reach a target, testing the ability to avoid cyclic, non-progressive movements.
Visualization of the learned action distribution (p_G) compared to the target distribution (p), demonstrating the effectiveness of the importance-sampling approach.

Key Results and Insights

  • Superior Success Rates: In bin-packing tasks, GANDI achieved a success rate exceeding 70% within a 5-second planning limit, significantly outperforming uniform samplers (~50%).
  • Data Efficiency: GANDI reached high proficiency after only 20 training episodes. In contrast, a standard GAN trained only on successful paths required 50 episodes to achieve comparable results.
  • Strategic Emergence: Qualitative analysis showed that GANDI learned sophisticated strategies autonomously. For example, in bin packing, it learned to prioritize the back and corners of the bin first, a tactic that preserves space for future objects—a strategy standard models often failed to adopt.

Conclusion and Future Work

GANDI demonstrates that "failures are features," proving that off-target search data is a valuable resource for learning efficient action samplers. By recycling this data through importance sampling, robots can learn complex strategies with far less successful demonstration data than previously required.

Future research directions include addressing the "stopping problem" inherent in GAN training and extending the framework to mobile robots where the base position is also a learned continuous variable. Additionally, integrating GANDI with learned value functions could further accelerate the planning process for even more intricate robotic tasks.

Summary updated

BibTeX
@inproceedings{kim2018guiding,
  author = {Beomjoon Kim and Leslie Pack Kaelbling and Tomás Lozano-Pérez},
  title = {{Guiding Search in Continuous State-Action Spaces by Learning an Action Sampler From Off-Target Search Experience}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.12106},
}
Figure