Backward-Forward Search for Manipulation Planning

Caelan Reed Garrett, Tomás Lozano-Pérez, Leslie Pack Kaelbling

Abstract

In this paper, we address planning problems in high-dimensional hybrid configuration spaces, with a particular focus on manipulation planning problems involving many objects. We present the hybrid backward-forward (HBF) planning algorithm that uses a backward identification of constraints to direct the sampling of the infinite action space in a forward search from the initial state towards a goal configuration. The resulting planner is probabilistically complete and can effectively construct long manipulation plans requiring both prehensile and nonprehensile actions in cluttered environments.

Introduction

Robot manipulation in cluttered environments presents a significant challenge due to the "curse of dimensionality." Robots must operate in a hybrid configuration space, which combines continuous variables (such as the 3D coordinates of every object and robot joint) with discrete states (such as whether an object is being held or if a path is obstructed).

Traditional planning approaches face two primary hurdles: infinite branching and long horizons. Because there are infinitely many ways to grasp an object or move a base, random sampling is often inefficient. Furthermore, complex tasks requiring the displacement of multiple obstacles necessitate long sequences of actions, where unguided forward searches often fail to find a path to the goal. The Hybrid Backward-Forward (HBF) algorithm addresses these issues by using a simplified backward reachability analysis to guide a forward state-space search.

The Hybrid Backward-Forward (HBF) Algorithm

HBF splits the planning process into two interleaved components: a backward search to build a Reachability Graph and a forward search to find the actual plan.

Instead of solving the full, complex problem immediately, HBF builds a Reachability Graph (RG) starting from the goal and working backward. To maintain tractability, the algorithm utilizes three key strategies:

  • Independence: Goal constraints are treated independently (e.g., moving an object and clearing a path are handled as separate sub-problems).
  • Low-Dimensional Subspaces: Planning occurs in Constrained Operating Subspaces (COS). For instance, the algorithm might plan an object's path as if it were floating, temporarily ignoring the robot's specific kinematics.
  • Constraint Relaxation: Plans in these subspaces are allowed to temporarily violate constraints, such as colliding with a movable object. These violations are then flagged as new sub-goals to be resolved later.
The Reachability Graph (RG) structure used to identify useful actions and estimate distance to the goal.

The final plan is generated via a forward search from the initial state. The RG provides critical guidance by focusing sampling on actions identified as "useful" for reaching the goal. Additionally, HBF employs an adaptation of the $H_{FF}$ (Fast-Forward) heuristic from symbolic AI planning, estimating the distance to the goal based on the number of actions required within the simplified Reachability Graph.

Experimental Evaluation

The algorithm was evaluated on six high-dimensional manipulation benchmarks designed to test various planning challenges, including non-prehensile actions (pushing), non-monotonic tasks, and extreme clutter.

  • Problem 1: Retrieving an object surrounded by 8 obstacles.
  • Problem 2: Pushing a large cylinder (non-prehensile action).
  • Problem 3: A non-monotonic task requiring the robot to temporarily move an object away from its goal to reach another.
  • Problem 4: Stacking objects where the base must be moved.
  • Problem 5: Extreme clutter involving 39 cylinders crowding a target.
  • Problem 6: A large-scale sorting task involving 14 blocks and 14 obstacles.
Problem 3: A non-monotonic manipulation task requiring the robot to move objects out of the way to reach a goal.

Key Results and Insights

The researchers compared HBF using the $H_{FF}$ heuristic against an unguided version ($H_0$). The results demonstrated that factoring constraints is essential for high-dimensional planning. By identifying what needs to happen before determining how the robot must move, HBF avoids exponential state-space explosion.

  • Reliability: HBF with $H_{FF}$ achieved a near 100% success rate across all problems within a 5-minute timeout, whereas the unguided version failed on the most difficult tasks.
  • Efficiency: In the extreme clutter of Problem 5, HBF found solutions in a median of 23 seconds, visiting only 170 states.
  • Versatility: HBF successfully managed plans up to 72 actions long and unified prehensile and non-prehensile actions under a single logic framework.

Conclusion

HBF effectively ports the "delete relaxation" concept from discrete AI planning into the continuous geometric realm. While the Reachability Graph introduces some computational overhead, it provides the necessary guidance to navigate complex, cluttered environments. Future work will focus on extending this framework to handle more complex dynamics and larger environments with more sophisticated non-prehensile primitives.

Summary updated

Abstract

In this paper we address planning problems in high-dimensional hybrid configuration spaces, with a particular focus on manipulation planning problems involving many objects. We present the hybrid backward-forward (HBF) planning algorithm that uses a backward identification of constraints to direct the sampling of the infinite action space in a forward search from the initial state towards a goal configuration. The resulting planner is probabilistically complete and can effectively construct long manipulation plans requiring both prehensile and nonprehensile actions in cluttered environments.
BibTeX
@inproceedings{garrett2015backward,
  author = {Caelan Reed Garrett and Tomás Lozano-Pérez and Leslie Pack Kaelbling},
  title = {{Backward-Forward Search for Manipulation Planning}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2015},
  doi = {10.1109/iros.2015.7354287},
}
Figure