Source-linked AI summary
Integrated Task and Motion Planning
Caelan Reed Garrett, Rohan Chitnis, Rachel Holladay, Beomjoon Kim, Tom Silver, Leslie Pack Kaelbling, Tomás Lozano-Pérez
TL;DR
Robots operating in unstructured environments must coordinate high-level actions with continuous motions and object-state changes. This paper formalizes a class of task and motion planning problems, surveys solution algorithms, and organizes them by continuous-subproblem and search-integration strategies.
Problem
Task and motion planning requires coordinating interdependent task-level decisions with motion-level constraints, which approaches treating them independently cannot solve generally.
Method
The paper formalizes a broad TAMP class and surveys algorithms by how they solve continuous constraints and integrate discrete plan-structure search with continuous parameter search.
Results
Existing TAMP approaches are usefully categorized by their strategies for sequencing actions, selecting continuous parameters, and integrating these decisions.
Takeaways & Limitations
The framework clarifies modeling and algorithmic trade-offs across a broad range of TAMP solution methods.
Takeaways & Limitations
The surveyed problem class assumes deterministic actions, complete state knowledge, rigid known-shape bodies, a holonomic robot, and final-state goals.
Abstract
from arXiv · showhide
The problem of planning for a robot that operates in environments containing a large number of objects, taking actions to move itself through the world as well as to change the state of the objects, is known as task and motion planning (TAMP). TAMP problems contain elements of discrete task planning, discrete-continuous mathematical programming, and continuous motion planning, and thus cannot be effectively addressed by any of these fields directly. In this paper, we define a class of TAMP problems and survey algorithms for solving them, characterizing the solution methods in terms of their strategies for solving the continuous-space subproblems and their techniques for integrating the discrete and continuous components of the search.
1. INTRODUCTION
The introduction frames task and motion planning as the integration of discrete task planning, continuous motion planning, and intermediate mode-parameter selection for robots acting in unstructured environments. It motivates this integration by the interdependence of task and geometric constraints and states the survey’s restricted problem class and organizing framework.
- Motivation: Directly planning over entire world states fails algorithmically because the world is highly under-actuated and objects can be changed only through appropriate robot contact and motion.The relevant state includes grasped objects, grasps, and other object poses.
- Problem definition: Task and motion planning combines AI task-planning methods with robotic motion planning while also selecting real-valued mode parameters such as grasps and object placements.These parameters govern which continuous motions are legally feasible.
- Problem definition: Task-level and motion-level decisions are interdependent, so treating them independently cannot solve the general class of problems.A high-level action skeleton must be instantiated with configurations, grasps, placements, and paths that satisfy geometric constraints.
- Scope: The survey assumes deterministic actions, complete state knowledge, known rigid-body shapes, a holonomic robot, and goals specified over final configurations and object poses.These assumptions define the bounded class of TAMP problems considered in the main discussion.
- Survey framework: The paper formalizes TAMP by combining discrete plan-structure search with continuous constraint-satisfaction search, after reviewing motion, multimodal motion, and task planning.The framework is intended to organize a broad class of existing TAMP algorithms.
2. BACKGROUND
The background situates TAMP among robot motion planning, multi-modal motion planning, and AI task planning. It introduces multi-modal planning as whole-system constrained motion planning whose discrete mode changes capture manipulation actions such as picking up and placing objects.
- 2. BACKGROUND: TAMP rests on foundations in robot motion planning, multi-modal motion planning, and AI task planning.The section provides a compact overview of these three planning problem classes.
- Robot Motion Planning: Motion planning represents a robot trajectory as a path through a d-dimensional configuration space subject to feasibility constraints and goal conditions.The formal problem uses Q, F, q0, Q∗, and feasible space QF.
- Multi-Modal Motion Planning: Multi-modal motion planning extends motion planning to changing object states by modeling kinematic changes, broader constraints, and their integration.These extensions support planning actions that alter attachments and other world relationships.
- Multi-Modal Motion Planning: Kinematic trees derive the full world configuration from robot joint values through forward kinematics, while object attachments define the current mode.A kinematic switch changes the graph when the robot picks up an object, potentially carrying transitively attached objects.
- Multi-Modal Motion Planning: Multi-step manipulation requires discrete mode switches because making and breaking contact changes the kinematic graph and active motion constraints.A multi-modal state is represented as s = ⟨w, σ⟩, with mode-specific constraint functions and switches enabled when the new constraints are satisfied.
- Multi-Modal Motion Planning: In pick-and-place tasks, transit modes represent free motion, while transfer modes represent holding a grasped object.With one gripper, there is one transit mode family and a transfer mode family for each graspable object.
3. TASK AND MOTION PLANNING
This section presents a unified framework for describing task and motion planning problems and algorithms, clarifying modeling and algorithmic trade-offs across existing methods.
- 3. TASK AND MOTION PLANNING: The framework integrates motion planning, multi-modal motion planning, and task planning to describe a broad range of TAMP methods.It first formalizes TAMP problems, then characterizes solution methods.
3.1. TAMP problem description
TAMP extends task-planning representations to mixed-multimedia motion-planning problems with additional nongeometric state variables. Its structured action, constraint, and plan representations expose subproblem structure while requiring parameter assignments that satisfy all constraints.
- Problem formulation: TAMP extends MMMP with nongeometric state variables, such as whether lights are on or pizza is cooked.The formulation uses task-planning representations to describe and extend MMMP problems.
- Problem formulation: TAMP unpacks entities into simpler subparts, revealing problem substructure and enabling algorithmic insights in domains with many objects.Large-object domains require many mode families and high-dimensional configuration-space constraints.
- Action representation: moveF and moveH describe transit and transfer motion, while pick and place switch between transit and transfer modes.Pick switches from transit to transfer; place switches from transfer to transit.
- Constraint representation: Constraints can be decomposed into conjunctions of smaller-arity constraints, including kinematic relationships and trajectory-motion relationships.For example, Kin[obj](q, p, g) relates robot configuration, object pose, and grasp, while Motion(q, τ, q′) relates trajectories and configurations.
- Solutions: A solution is a finite action-instance sequence whose assigned parameters satisfy action constraints and induce a corresponding state sequence.The initial state precedes the induced states, and each action must satisfy its preconditions.
- Solutions: Any assignment satisfying all plan-skeleton constraints fills it into a complete legal plan guaranteed to achieve the goal.The plan skeleton represents state-variable values and motion parameters across the action sequence.
3.2. Hybrid constraint satisfaction
Hybrid constraint satisfaction assigns discrete and continuous plan parameters so their associated constraints hold. The surveyed strategies solve constraints jointly through mathematical programs, individually through samplers, or by integrating both approaches.
- Problem formulation: An h-csp assigns values to plan-skeleton parameters, which may have continuous or discrete domains, subject to a constraint network.Discrete parameters can represent choices such as a finite set of stable resting surfaces.
- Joint satisfaction: Mathematical programming solves for all free parameters simultaneously, but high dimensionality, discrete variables, and non-convex constraints make TAMP instances difficult.Local-descent methods may reach only a local optimum that violates constraints.
- Individual satisfaction: Samplers generate parameter assignments guaranteed to satisfy individual constraints or small constraint sets, then combine those assignments.Conditional samplers consume values satisfying existing constraints and produce compatible values for additional constraints; several can form a directed acyclic sampling network.
- Trade-offs and integration: Individual satisfaction enables special-purpose procedures and reuse, whereas joint satisfaction needs one complete solution; samplers must asymptotically cover all feasible solutions.The strategies can be integrated by sampling grasp, stability, and kinematics while jointly solving motion and collision constraints.
3.3. Combining action sequence and parameter search
Integrated TAMP algorithms combine action-sequence search with h-CSP parameter solving through different control-flow strategies, while using backtracking, pruning, interleaving, and reuse of prior results to manage infeasibility and search effort.
- Control-flow strategies: Three predominant control-flow strategies order action sequencing and h-CSP solving as sequence before satisfy, satisfy before sequence, or interleaved search.These strategies differ in whether they search plan skeletons first, generate satisfying assignments first, or alternate between the two processes.
- Efficiency and limitations: Sampling and optimization are typically semi-complete: failure to find a solution within available time does not certify infeasibility, particularly when feasible solutions occupy tiny volumes.Efficiency also depends on reusing previous subproblem assignments or failures to avoid repeatedly addressing related subproblems.
- Sequence before satisfy: Sequence-before-satisfy methods search plan skeletons and solve each associated h-CSP, backtracking to alternatives when lower-level constraints fail.Top-down decomposition remains effective when high-level plans are not guaranteed to refine downward, provided failed h-CSP attempts trigger backtracking.
- Satisfy before sequence: Satisfy-before-sequence methods precompute continuous values and their satisfied constraints, benefiting cases where sampling is efficient and repeated sequencing failures are costly.This strategy reduces the hybrid problem to discretized planning problems, especially when sampled values do not cause combinatorial explosion and sequencing has non-negligible overhead.
- Interleaved search: Interleaving can pre-sample state variables while deferring motion parameters, and can prune partial plan skeletons whose induced h-CSPs are infeasible.Because every subsequence of a satisfiable plan skeleton must also be satisfiable, infeasible partial skeletons can be removed, sometimes using relaxed h-CSPs.
3.4. Communication between subproblems
TAMP strategies can exploit shared substructure across h-CSP subproblems by communicating either satisfying constraint assignments or unsatisfiable counterexamples. Positive methods build reusable solution databases, while negative methods prune h-CSPs containing recorded failures, with smaller counterexamples offering broader pruning at additional diagnostic cost.
- Communication strategies: TAMP strategies exploit shared substructure across multiple h-CSP subproblems, reducing computation by sharing either satisfying constraints or unsatisfiable counterexamples.The primary algorithmic question is whether to communicate positive or negative information between subproblems.
- Positive methods: Positive methods add each solved constraint and its satisfying assignment to a database of known constraint elements.For methods that satisfy constraints before sequencing, this database instantiates action instances before sequencing.
- Negative methods: Negative methods record unsatisfiable counterexample h-CSPs, allowing any larger h-CSP containing one to be pruned.This can prevent action sequencing from exploring plan skeletons that share a previously observed failure case.
- Counterexample diagnosis: Smaller counterexamples prune more h-CSPs and plan skeletons, but identifying them may require decomposing and separately testing smaller h-CSPs.Several TAMP approaches use heuristic failure diagnosis and problem repair, while domain-independent strategies also exist.
3.5. Taxonomy
The taxonomy organizes representative MMMP and TAMP algorithms by their continuous-parameter-solving methods and by how they integrate searches over plan structure and continuous values.
- Algorithm taxonomy: Table 1 categorizes representative MMMP and TAMP algorithms by continuous parameter-solving strategy and search integration between plan structure and continuous values.The table is intended to provide broad coverage rather than an exhaustive survey.
- Integration strategies: Each table row identifies one of three strategies for integrating constraint satisfaction with action sequencing.The passage names satisfaction first and interleaved satisfaction and sequencing as examples of these strategies.
- Search dimensions: The taxonomy covers both mode-family or task-level plan structure and continuous values as coordinated search dimensions.These dimensions define how the listed algorithms combine discrete structure search with continuous search.
4. EXTENSIONS
Key extensions to task and motion planning address richer physical dynamics, uncertainty in future and present states, and learning-based model and search guidance. Future methods should also combine sampling with optimization and operate in more realistic environments.
- Uncertainty: Real-world TAMP must handle future-state uncertainty by preparing responses to multiple outcomes, including unlikely but disastrous ones.This requires planning actions that remain available across possible action outcomes.
- Uncertainty: Present-state uncertainty can be treated as belief-space planning, where actions both gather information and drive the world toward a desired belief state.The planner reasons explicitly about the agent’s state of information about the world.
- Learning: Learning can help acquire execution constraints and improve search guidance through domain-dependent heuristics, policies, value estimates, and action orderings.Generalization remains difficult because TAMP states involve object shapes and poses and goals must also be encoded.
- Realistic environments: TAMP should extend beyond quasi-static rigid-body settings to deformable objects, liquids, time, full dynamics, and other agents.Several approaches have already demonstrated planning for kinodynamic systems.
- Algorithmic extensions: Further investigation is needed into strategies that combine sampling and optimization approaches to TAMP.This is identified as a future research direction alongside extensions to more realistic environments and uncertainty-aware planning.
DISCLOSURE STATEMENT
The authors report no known affiliations, memberships, funding, or financial holdings that might be perceived as affecting the review’s objectivity.
- The authors report no affiliations, memberships, funding, or financial holdings known to affect the review’s objectivity.