Planning with Selective Physics-based Simulation for Manipulation Among Movable Objects

Muhammad Suhail Saleem, Maxim Likhachev

TL;DR

This paper tackles the challenge of planning robot manipulation tasks in cluttered environments by selectively using computationally expensive physics simulations. They propose a method that uses a fast collision checker for most actions and only resorts to physics simulation when necessary, significantly speeding up planning while maintaining completeness.

What Problem Does This Paper Address?

Planning robot manipulation tasks, especially in cluttered environments with many movable objects, is a significant challenge. Traditional motion planners often rely on simple collision checkers, which are fast but insufficient for tasks involving complex object interactions (e.g., pushing one object to reach another). High-fidelity physics-based simulators can accurately model these interactions, but they are computationally very expensive, making them too slow for use within a typical planning loop that requires thousands of action evaluations. This disconnect between the need for accurate physics and the speed requirements of planning limits the application of physics-based simulation in robotics. The authors aim to bridge this gap by developing a method that intelligently selects which actions require physics simulation and which can be handled by a simpler, faster model.

Methods

The core of the paper's contribution lies in their "Selective Physics-based Simulation" approach. This method integrates a standard search-based planner with a modified "Get Successors" routine. Instead of always using a physics simulator, the planner first employs a fast collision checker. If the collision checker detects an interaction that doesn't violate predefined constraints, the action is considered valid, and the planner moves on. However, if a first-order interaction is detected, and it doesn't violate constraints, the system then calls an external physics simulator to evaluate the action. This selective approach significantly reduces the number of expensive physics simulations.

A key component of their method is the concept of "relevant objects." The planner starts by considering a reduced set of objects (initially none) as "relevant." It plans in this lower-dimensional space and then tests the resulting path in the full, high-dimensional space. If the path fails due to interactions with previously "irrelevant" objects, those objects are identified as "relevant" for the next planning iteration, and the process repeats. This recursive identification of relevant objects helps to progressively refine the planning space and focus computational effort where it's most needed. They also adapt the Lazy Weighted A* search algorithm to further optimize the process by deferring the full evaluation of expensive actions until they are critical for the search.

Datasets

Not discussed in the paper. The authors describe experiments conducted in simulated cluttered tabletop scenes and on real robots, but do not refer to specific named datasets.

Key Insights and Ideas

  • Selective Simulation is Key: The most impactful insight is that not all actions in a manipulation plan require full physics simulation. By intelligently distinguishing between actions that need detailed dynamic modeling and those that can be approximated by collision checking, significant computational gains are achievable.
  • Relevant Objects Focus: The concept of "relevant objects" is crucial. It allows the planner to progressively focus on the objects that actually influence the plan's validity, rather than trying to model every single object in a cluttered scene from the outset. This dramatically reduces the search space.
  • Completeness Guarantees: The method is designed to maintain completeness guarantees, meaning if a solution exists, the algorithm will find it. This is achieved by ensuring that the selective simulation process eventually considers all objects that could potentially lead to a constraint violation.
  • Bridging the Gap: The work effectively bridges the gap between the need for accurate physics-based reasoning in complex manipulation and the real-time demands of motion planning.

Key Results

The paper demonstrates significant performance improvements through experimental analysis.

  • Speedup: Selective simulation, when combined with Lazy Weighted A, achieved planning times that were over 20 times faster* than non-selective approaches.
  • Success Rate: The selective simulation approach also showed a higher success rate (0.92 vs. 0.88 for Weighted A, and 0.40 vs. 0.35 for Lazy Weighted A when comparing selective vs. non-selective with the same search algorithm).
  • Scalability: The performance of the selective simulation algorithm remained relatively constant as the total number of objects in the scene increased, whereas the performance of non-selective methods degraded significantly. This is attributed to the fact that the number of relevant objects does not scale with the total number of objects.
  • Real-World Utility: The approach was successfully demonstrated on a 7 DOF UBTech Walker robot, indicating its practical applicability.

Limitations and Future Work

  • Assumption of No Second-Order Interactions: The theoretical completeness proof relies on the assumption that if a solution exists, there is at least one solution that does not cause any second-order interactions (interactions between objects caused by the robot's action on another object). While this is a reasonable assumption for many practical scenarios, it might limit applicability in highly complex, tightly packed scenarios where such interactions are unavoidable.
  • Accuracy of Simulators: The paper acknowledges that the fidelity of physics-based simulators can affect planning outcomes. While their method focuses on speeding up planning with a given simulator, future work could involve learning from real robot experiences to address occasional inaccuracies in simulation modeling.
  • Extending to More Complex Tasks: The authors plan to extend their approach to domains beyond simple pick-and-place tasks, such as tool usage.
  • Adaptive Dimensionality: While they use relevant objects to reduce dimensionality, further exploration into adaptive dimensionality techniques could be beneficial.

Summary updated

Abstract

Use of physics-based simulation as a planning model enables a planner to reason and generate plans that involve non-trivial interactions with the world. For example, grasping a milk container out of a cluttered refrigerator may involve moving a robot manipulator in between other objects, pushing away the ones that are movable and avoiding interactions with certain fragile containers. A physics-based simulator allows a planner to reason about the effects of interactions with these objects and to generate a plan that grasps the milk container successfully. The use of physics-based simulation for planning however is underutilized. One of the reasons for it being that physics-based simulations are typically way too slow for being used within a planning loop that typically requires tens of thousands of actions to be evaluated within a matter of a second or two. In this work, we develop a planning algorithm that tries to address this challenge. In particular, it builds on the observation that only a small number of actions actually need to be simulated using physics, and the remaining set of actions, such as moving an arm around obstacles, can be evaluated using a much simpler internal planning model, e.g., a simple collision-checking model. Motivated by this, we develop an algorithm called Planning with Selective Physics-based Simulation that automatically discovers what should be simulated with physics and what can utilize an internal planning model for pick-and-place tasks.
BibTeX
@inproceedings{saleem2020planning,
  author = {Muhammad Suhail Saleem and Maxim Likhachev},
  title = {{Planning with Selective Physics-based Simulation for Manipulation Among Movable Objects}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2020},
  doi = {10.1109/icra40945.2020.9197451},
}
Figure