Source-linked AI summary
FFRob: Leveraging Symbolic Planning for Efficient Task and Motion Planning
Caelan Reed Garrett, Tomas Lozano-Perez, Leslie Pack Kaelbling
TL;DR
Mobile manipulation planning is difficult because symbolic planners omit geometric and kinematic constraints while geometric search scales poorly in cluttered, multi-object settings. The paper introduces EAS and FFRob, combining complex-condition symbolic planning with sampled manipulation primitives, roadmap-based reachability, and relaxed heuristics. FFRob is shown to be probabilistically complete with finite expected runtime and to solve diverse rearrangement and navigation tasks involving movable objects.
Problem
Mobile manipulation with cluttered environments and multiple objects is difficult because geometric and kinematic constraints interact in a high-dimensional configuration space that symbolic planners cannot naturally represent.
Method
FFRob uses Extended Action Specification with complex conditions, sampled manipulation actions, roadmap-based reachability evaluation, and relaxed-planning heuristics that incorporate geometric constraints.
Results
FFRob is probabilistically complete with finite expected runtime and solves a broad class of feasible task and motion planning problems involving rearrangement and navigation among movable objects.
Takeaways & Limitations
The approach demonstrates that symbolic planning heuristics can guide integrated task and motion planning while accounting for geometric and kinematic constraints.
Takeaways & Limitations
Related computed-predicate approaches can require expensive motion-planner calls, while ignoring such predicates during heuristic computation may produce uninformed heuristics and plateaus.
Abstract
from arXiv · showhide
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.
1 Introduction
Mobile manipulation with cluttered environments and multiple objects remains difficult because geometric and kinematic constraints interact across a high-dimensional configuration space. FFRob addresses this by combining symbolic planning, complex-condition actions, sampling-based discretization, and geometric heuristics.
- Challenge: Traditional symbolic planners represent long discrete action sequences efficiently but do not naturally encode manipulation geometry and kinematics.Realistic manipulation domains make compact symbolic encodings of geometric and kinematic success conditions difficult.
- Challenge: Cluttered mobile manipulation requires planning across many intertwined object, grasp, placement, and robot-motion decisions.The relevant configuration space combines the robot with all movable objects and grows exponentially with their number.
- Approach: FFRob integrates task and motion planning by using symbolic actions whose conditions include geometric and kinematic constraints.Its central computational benefit is incorporating those constraints into heuristic search to guide planning.
- Approach: Extended Action Specification represents complex action conditions and supports efficient custom predicate evaluation, including reachability testing for sampled manipulation problems.The paper extends relaxed-planning and FastForward-style heuristics to EAS representations.
- Approach: FFRob repeatedly samples poses, grasps, and configurations, then constructs a roadmap to discretize the task and motion problem for symbolic search.The roadmap supports efficient evaluation of reachability predicates during planning.
- Results: FFRob is presented as probabilistically complete with finite expected runtime and is evaluated on rearrangement and navigation among movable objects.The experiments target challenging manipulation problems involving moving among and rearranging movable objects.
2 Related Work
Prior work spans manipulation graphs, probabilistic roadmaps, hybrid planning, symbolic heuristic search, and task–motion integration. FFRob builds on these directions while targeting compact complex conditions and heuristics that retain geometric information.
- Manipulation Planning: Manipulation planning extends motion planning by requiring the robot to operate on objects through grasps, placements, and transit or transfer motions.Manipulation graphs decompose such problems into connected configuration-space components associated with grasps.
- Manipulation Planning: NAMO and rearrangement planners address movable obstacles or explicit object goals, but some approaches require characterizing configuration-space components that becomes computationally prohibitive beyond two dimensions.This limitation is stated for a probabilistically complete NAMO algorithm.
- Manipulation Planning: Hybrid-planning methods search systems with multiple modes, while HBF samples action primitives during state-space search rather than in FFRob’s batch-sampling scheme.Modes can encode grasps and movable-object placements.
- Symbolic Planning: Delete-relaxation heuristics estimate planning cost by removing negative action effects, with hff extracting a relaxed plan and using it to guide search.Relaxed plans can reduce the branching factor by suggesting useful actions.
- Symbolic Planning: Planning Modulo Theories supports complex conditions, but FFRob additionally allows custom evaluation of such conditions and heuristics more effective than hmax.The comparison is framed as similar in representation while differing in predicate evaluation and heuristic support.
- Task and Motion Planning: Earlier task–motion approaches use computed predicates for geometric checks, but expensive motion-planner calls and geometry-free heuristics can cause branching or heuristic plateaus.Considering sparse placements can also limit planner generality.
3 Problem Formulation
The paper formalizes pick-place-move problems for a mobile manipulator operating around movable rigid objects. A problem consists of a structured state, legal configurations, and an initial state with variable-based goals.
- Domain: A PPM domain specifies the robot configuration space plus placement-surface and grasp spaces for each movable object.Placement spaces contain legally supported poses, while grasp spaces may be discrete or continuous.
- Domain: PPM problems cover pick-and-place, rearrangement, and navigation among movable objects, while excluding stacking in the basic formulation.Stacking can be handled by sampling structurally sound object poses.
- State: A system state assigns values to robot configuration, robot holding status, and each movable object’s pose.The robot configuration includes base pose and manipulator joint angles; the holding variable records either no object or a grasped object.
- State: When the robot holds an object, its pose is determined from the robot configuration and grasp transform rather than stored independently.Legal states exclude collisions among the robot, held object, and placed objects.
- Problem: A PPM problem is defined by an initial state and a set of goal states, with the paper restricting experimental goals to conjunctions of variable-specific goal sets.An unspecified variable goal defaults to the full variable domain.
4 The FFRob Algorithm Overview
FFRob alternates between sampling and discrete planning until a solution is found. Each failed search triggers a larger discretization, allowing the planner to refine the finite symbolic approximation.
- Sampling: FFRob’s sampling phase creates symbolic actions from finite samples of poses, grasps, and robot configurations.The sampling parameters determine how many configurations, poses, and grasps are generated.
- Planning: The planning phase performs discrete search over the sampled representation to determine whether a solution exists.If search fails, FFRob repeats the process with a larger sample set.
- Architecture: The algorithm’s two central subroutines are SAMPLE-DISCRETIZATION and SEARCH.The paper develops the discretization and the efficient search algorithms as the main implementation components.
5 Symbolic Planning Representation
The paper represents sampled task-and-motion problems with EAS, extending SAS+ so action conditions can express geometric and kinematic predicates. It defines relaxed-state evaluation and action schemas for manipulation and broader tasks.
- Representation: Continuous configurations, poses, and grasps are sampled beforehand, yielding a finite set of actions for symbolic planning.The sampled variables parameterize robot configurations, object poses, and grasp transforms.
- Extended Action Specification: EAS extends SAS+ by allowing logical formulas over variable values, including predicates that evaluate collision-free reachability.This supports conditions such as whether a path between configurations avoids placed objects.
- Conditions: Conditions are predicates over state-variable values, with parameterized forms such as INREG and REACHABLE representing placement and motion constraints.REACHABLE evaluates roadmap paths while accounting for fixed objects, movable objects, and a grasped object.
- Action Schemas: Parameterized PICK, PLACE, and MOVE schemas encode manipulation actions through typed pose, object, grasp, configuration, and roadmap parameters.The schemas use preconditions and effects to update robot configuration, held-object, and object-pose variables.
- General Task Actions: EAS also supports additional task actions, including CLEAN and COOK, while an EAS problem consists of an initial state, goal partial state, and action set.Partial states are sets of conditions defining the states that satisfy them.
- Relaxed Evaluation: Relaxed states retain sets of possible values because relaxed actions add effects without removing existing values, enabling delete-relaxation heuristics.Condition satisfaction in a relaxed state requires an assignment of retained values that makes the condition true.
- Condition Tests: Condition tests must evaluate relaxed states and return true conditions with their achievers, allowing geometric tests to guide heuristic search.The same test implementation is sufficient for standard states when it is correct for relaxed states.
6 Search Algorithms
The paper uses a generic heuristic search procedure for EAS planning, separating search control, heuristic evaluation, and successor generation. Different extraction and processing choices recover standard search strategies.
- Generic Search: SEARCH takes an EAS problem, control procedures, a heuristic, and an action-successor procedure.EXTRACT and PROCESS alter search control, while H and ACTIONS estimate cost and generate successors.
- Search Strategies: Depending on EXTRACT and PROCESS, SEARCH can implement depth-first, breadth-first, uniform-cost, A*, greedy best-first, and hill-climbing search.The heuristic maps a state to an estimated cost to reach a goal state.
7 Search Heuristics
The section adapts delete-relaxation heuristics to EAS planning, using COMPUTE-COSTS to estimate goal distance despite complex Boolean conditions. The hff heuristic provides the strongest guidance in PPM experiments by reusing actions and accounting for alternative manipulation approaches.
- Heuristic Comparison: UNSATISFIED-GOALS is fast but gives an exceptionally poor cost estimate because satisfying one goal may require many actions.More involved approximate-planning heuristics trade computation per search node for fewer explored states.
- Relaxed Planning: Delete-relaxation searches over effects rather than complete states, with COMPUTE-COSTS propagating costs through an action hyper-graph.The COMB parameter determines how costs for sets of conditions are combined.
- Relaxed Planning: COMPUTE-COSTS records effect, condition, and action nodes while incrementally testing which unsatisfied conditions become achievable.It initializes a relaxed state and priority queue, then stores achievers and costs for reachable effects and conditions.
- Relaxed Planning: EAS heuristics adapt domain-independent planning methods to problems with complex Boolean conditions.The framework applies to any EAS planning problem, with physical interpretation demonstrated for discretized PPM problems.
- Practical Performance: Cached collision checks make COMPUTE-COSTS fast enough in practice to substantially reduce the number of explored search states.Although collision checks typically dominate PPM runtime, caching limits the heuristic’s computational overhead.
- The FF Heuristic: The EAS relaxed-plan extractor replaces complex conditions with their satisfying effects after achievers have been computed.This extends the original FF extraction procedure while using a different easiest-action metric.
- The FF Heuristic: hff has the best performance in the PPM experiments because greedy relaxed-plan extraction often selects approaches requiring fewer additional object movements.Its backwards pass reuses goals and therefore usually gives a better estimate of optimal goal cost.
8 Discretization
Discretization converts continuous manipulation planning into finite EAS problems by sampling placements, grasps, configurations, and actions. A conditional reachability graph then supports efficient, cached reachability evaluation across related object placements and grasps.
- Discretized Domains: A discretized PPM domain contains a robot configuration roadmap plus finite sampled placements and grasps for each movable object.The roadmap is represented by vertices and edges in configuration space.
- Sampling and EAS Construction: SAMPLE-DISCRETIZATION converts goals into predicates, samples PICK and PLACE actions, and builds MOVE actions from a roadmap connecting relevant configurations.The sampling parameters determine the number of configurations, poses, and grasps produced.
- Sampling and EAS Construction: Figure 9’s discretization procedure alternates sampled finite action construction with EAS specification generation for the current PPM instance.The procedure is the bridge between continuous PPM inputs and symbolic planning.
- Roadmap Construction: MOVE actions represent discretized motion plans within transit and transfer modes induced by sampled poses and grasps.The sampled PICK and PLACE configurations serve as roadmap targets, and MOVE actions are created from configuration pairs.
- Iterative Discretization: FFRob increases sampling parameters and repeats discretization when the current finite problem cannot yield a solution.The starting-state heuristic can identify when the sampled actions cannot possibly contain a plan.
- Sampling and EAS Construction: PICK and PLACE sampling produces poses and grasps, then uses inverse reachability and collision-free analytical IK to obtain valid robot configurations.Sampled pose–grasp–configuration tuples become manipulation action instances.
- Conditional Reachability Graph: The CRG supports reachability queries by storing configurations as vertices and manipulation-dependent traversability conditions on roadmap edges.It is initialized while sampling MOVE actions and includes approach trajectories near PICK and PLACE configurations.
- Conditional Reachability Graph: The conditional reachability graph conditions roadmap connectivity on movable-object placements and the object held by the robot.Its edge validity conditions are evaluated lazily and cached to maximize reuse across related queries.
9 Review of sPRM Theoretical Analysis
The sPRM analysis establishes probabilistic completeness and exponential convergence for robustly feasible motion-planning problems by reducing solution discovery to sampling a finite sequence of clearance-preserving spheres.
- Robustly feasible problems: Robust feasibility requires a solution trajectory with nonzero clearance and suitable start and goal neighborhoods that admit linear connections.This combines clearance with endpoint visibility, allowing problems whose start or goal lies on the boundary of the free configuration space.
- Sampling reduction: For every robustly feasible problem, k + 1 spheres of radius δ/2 can be placed along a solution trajectory so that samples covering them yield a collision-free interpolated path.The sequence has k = ⌈2L/δ⌉ intermediate intervals and includes the fixed start and goal configurations.
- sPRM procedure: The sPRM begins with the start and goal and repeatedly samples the configuration space, connecting samples whenever their linear interpolation is collision-free.This roadmap construction provides the sampling mechanism analyzed by the completeness proof.
- Theoretical guarantees: The sPRM is probabilistically complete and exponentially convergent over robustly feasible motion-planning problems.Because the probability of failure decreases exponentially with the number of samples, it tends to zero in the limit.
- Convergence analysis: If σ is the probability that a sample falls within any particular sphere, the probability of missing that sphere after n samples is bounded above by e^-σn.The proof uses σ as the ratio between a sphere's measure and the measure of the free configuration space, then applies a union bound across spheres.
10 FFROB Theoretical Analysis
FFROB’s theoretical analysis establishes convergence properties for robustly feasible pick-and-place manipulation problems, extending sampling-based motion-planning arguments across modes, placements, grasps, and inverse-kinematic solutions. The results show exponential decrease in failure probability, probabilistic completeness, finite expected runtime, and convergence toward minimum-length robust mode sequences.
- Robust feasibility: The analysis defines robustly feasible PPM problems through nonzero-volume solution sets spanning trajectories, placements, grasps, and inverse-kinematic solutions.The proof must account for multiple sampling domains and alternating transit and transfer modes.
- Mode-constrained planning: Mode-constrained motion planning restricts robot motion to an operable configuration space determined by the current transit or transfer mode.Transit modes constrain collision-free motion around placed objects, while transfer modes additionally account for the held object and grasp.
- Convergence in iterations: FFROB’s failure probability decreases exponentially with the number of sampling iterations for any robustly feasible PPM problem.This establishes exponential convergence in iterations for the algorithm’s sampling process.
- Theoretical guarantees: FFROB is probabilistically complete and exponentially convergent under the stated robust-feasibility assumptions.The result builds on simplified PRM arguments and applies across the integrated task-and-motion setting.
- Runtime: FFROB has finite expected runtime and finite runtime variance, while its discrete search on the nth sampling iteration has runtime O(m4n^(m+9)).The polynomial search bound is separate from the exponential convergence result in sampling iterations.
- Plan-length optimality: Continuing to sample after finding a solution makes FFROB converge exponentially to the minimal-length robust set of mode sequences.Within this set, the resulting plan uses the fewest PICK and PLACE mode switches.
11 Experiments
The experiments evaluate seven FFROB configurations across eight diverse manipulation problems, showing that reachability-aware heuristics and helpful actions provide the strongest overall performance. FFROB solves rearrangement, NAMO, nonmonotonic, and long-horizon task-and-motion problems, while sampling restarts can improve practical performance.
- Seven FFROB configurations were evaluated on eight problems spanning rearrangement planning, NAMO, nonmonotonic planning, and task and motion planning.
- HF F Rob, HA achieved the best success rate and runtime, while helpful actions improved performance over HF F Rob and reachability-aware heuristics outperformed HF F.
- All but one algorithm solved problem 1-2 with above 95 percent success in less than 40 seconds, although HGoals used more expansions with lower per-expansion overhead.
- Problems 2-1 and 2-2 show that one FFROB algorithm can solve both NAMO and traditional pick-and-place tasks.
- Problems 3-1 and 3-2 were the most difficult because their solutions require undoing several goal conditions through nonmonotonic actions.
- Restarting after a finite search timeout with newly generated samples can improve performance, even when the original sample set might have sufficed.
12 Conclusion
The conclusion presents FFROB as a probabilistically complete task-and-motion planner that combines EAS representations, heuristic guidance, and iterative sampling. It also identifies unnecessary independent sampling and solution-quality analysis as areas for future work.
- FFROB is probabilistically complete because repeated discretization eventually generates, with probability approaching one, samples containing a solution.
- FFROB uses EAS to represent discretized planning problems with complex conditions and adapts the FF heuristic to provide guidance for them.
- Including geometric information in the heuristic is critical for efficiently solving manipulation problems with substantial geometric constraints.
- FFROB can efficiently solve a diverse set of task-and-motion-planning problems with one algorithm.
- Future work includes studying solution quality, robustly optimal problem classes, and whether sampling-based algorithms are asymptotically optimal.
- FFROB often generates unnecessary samples because continuous sampling is independent of search, which can slow the search process.
A.1 Best-First Search
Best-first search extracts the lowest-cost queue element, while deferred best-first search delays successor heuristic evaluation and temporarily reuses the parent heuristic to reduce computation.
- A.1 Best-First Search: Best-first search selects the queue element minimizing a cost function such as path cost, A∗ cost, weighted A∗ cost, or heuristic cost.
- A.1 Best-First Search: Figure 27 presents the extract and process procedures used by best-first search.
- A.2 Deferred Best-First Search: Deferred best-first search delays successor-state heuristic evaluation until extraction, reducing the number of heuristic evaluations.
- A.2 Deferred Best-First Search: Deferred search temporarily assigns successors their parent’s heuristic cost so states believed closer to the goal are processed first.
- A.2 Deferred Best-First Search: Figure 28 specifies the deferred best-first search process procedure.
B.1 Proof of Theorem 1
The theorem constructs neighboring configuration-space balls around a robustly feasible trajectory and shows that sampled points connected by linear interpolation form a collision-free solution.
- For any robustly feasible motion-planning problem, there exists a sequence of k + 1 d-spheres centered along a trajectory, each with radius δ/2.
- Choosing configurations within these spheres and linearly interpolating them yields a collision-free solution trajectory.
- Each successive sampled configuration lies within a δ-ball around the trajectory, enabling the collision-free interpolation argument.
- The proof relies on the trajectory’s δ clearance from obstacles and the convexity of the d-spheres.