FFRob: Leveraging Symbolic Planning for Efficient Task and Motion Planning
arXiv:1608.01335 · doi:10.1177/0278364917739114
Abstract
Mobile manipulation problems involving many objects are challenging to solve due to the high dimensionality and multi-modality of their hybrid configuration spaces. Planners that perform a purely geometric search are prohibitively slow for solving these problems because they are unable to factor the configuration space. Symbolic task planners can efficiently construct plans involving many variables but cannot represent the geometric and kinematic constraints required in manipulation. We present the FFRob algorithm for solving task and motion planning problems. First, we introduce Extended Action Specification (EAS) as a general purpose planning representation that supports arbitrary predicates as conditions. We adapt existing heuristic search ideas for solving \proc{strips} planning problems, particularly delete-relaxations, to solve EAS problem instances. We then apply the EAS representation and planners to manipulation problems resulting in FFRob. FFRob iteratively discretizes task and motion planning problems using batch sampling of manipulation primitives and a multi-query roadmap structure that can be conditionalized to evaluate reachability under different placements of movable objects. This structure enables the EAS planner to efficiently compute heuristics that incorporate geometric and kinematic planning constraints to give a tight estimate of the distance to the goal. Additionally, we show FFRob is probabilistically complete and has finite expected runtime. Finally, we empirically demonstrate FFRob's effectiveness on complex and diverse task and motion planning tasks including rearrangement planning and navigation among movable objects.
References in corpus (3)
Cited by in corpus (33)
- A Review of Robot Learning for Manipulation: Challenges, Representations, and Algorithms
- Sampling-Based Methods for Factored Task and Motion Planning
- iGibson 1.0: a Simulation Environment for Interactive Tasks in Large Realistic Scenes
- From Machine Learning to Robotics: Challenges and Opportunities for Embodied Intelligence
- Optimal task and motion planning and execution for human-robot multi-agent systems in dynamic environments
- NM: Learning Navigation for Arbitrary Mobile Manipulation Motions in Unseen and Dynamic Environments
- Representation, learning, and planning algorithms for geometric task and motion planning
- MPTP: Motion-Planning-aware Task Planning for Navigation in Belief Space
- Task and Motion Informed Trees (TMIT*): Almost-Surely Asymptotically Optimal Integrated Task and Motion Planning
- Deliberative Acting, Online Planning and Learning with Hierarchical Operational Models
- Learning to Place Objects onto Flat Surfaces in Upright Orientations
- Automated sequence and motion planning for robotic spatial extrusion of 3D trusses
- Modeling Long-horizon Tasks as Sequential Interaction Landscapes
- Extended Tree Search for Robot Task and Motion Planning
- Multi-Object Rearrangement with Monte Carlo Tree Search:A Case Study on Planar Nonprehensile Sorting
- HRL4IN: Hierarchical Reinforcement Learning for Interactive Navigation with Mobile Manipulators
- Integrating Task-Motion Planning with Reinforcement Learning for Robust Decision Making in Mobile Robots
- Pushing the Boundaries of Asymptotic Optimality in Integrated Task and Motion Planning
- Learning Manipulation States and Actions for Efficient Non-prehensile Rearrangement Planning
- STRIPS Planning in Infinite Domains
- Synchronized Multi-Arm Rearrangement Guided by Mode Graphs with Capacity Constraints
- Fast and resilient manipulation planning for target retrieval in clutter
- Socially intelligent task and motion planning for human-robot interaction
- Task-assisted Motion Planning in Partially Observable Domains
- Conditional Task and Motion Planning through an Effort-based Approach
- Task-Motion Planning for Safe and Efficient Urban Driving
- A Constraint Programming Approach to Simultaneous Task Allocation and Motion Scheduling for Industrial Dual-Arm Manipulation Tasks
- Towards Multi-Robot Task-Motion Planning for Navigation in Belief Space
- Object Rearrangement with Nested Nonprehensile Manipulation Actions
- LLM-GROP: Visually Grounded Robot Task and Motion Planning with Large Language Models
- A Task-Motion Planning Framework Using Iteratively Deepened AND/OR Graph Networks
- Optimal Mixed Discrete-Continuous Planning for Linear Hybrid Systems
- Locally Optimal Solutions to Constraint Displacement Problems via Path-Obstacle Overlaps