ScheduleStream: Temporal Planning with Samplers for GPU-Accelerated Multi-Arm Task and Motion Planning & Scheduling

AI summary

Overview

Research area: Robotics — task and motion planning (TAMP), temporal planning and scheduling, multi-arm (bimanual/humanoid) manipulation, GPU-accelerated sampling.

Technical level: Advanced. The paper assumes familiarity with classical planning, hybrid discrete-continuous planning, and robot motion planning, though the high-level ideas are describable in plain language.

Scope: The paper introduces ScheduleStream, a domain-independent temporal planning-and-scheduling framework built in Python, together with algorithms that alternate between scheduling and sampling, applied to multi-arm Task and Motion Planning & Scheduling (TAMPAS) with GPU-accelerated samplers.

What This Paper Is About

Most Task and Motion Planning systems produce plans — serial sequences of actions where only one arm moves at a time — so a bimanual robot never exploits its two arms simultaneously, wasting execution time. The goal is to instead produce schedules: sets of timed durative actions that can start asynchronously and overlap in time, so that robots can move arms in parallel and minimize the schedule makespan (total duration). The authors tackle full Task and Motion Planning & Scheduling (TAMPAS), where solutions are schedules of timed hybrid actions, and they aim to do so with a general framework rather than application-specific mechanisms.

Key Contributions

1. ScheduleStream, described as the first domain-independent temporal planning language with support for procedural functions and samplers (called streams), enabling planning and scheduling for mixed discrete-continuous systems. It is implemented in Python so that declarative and procedural aspects interface directly, allowing external procedures such as GPU-accelerated collision checkers and inverse kinematics solvers to be invoked by the algorithms.
2. Novel ScheduleStream algorithms that lazily solve problems while minimizing schedule makespan: eager-stream (Algorithm 1), a schedule subroutine (Algorithm 2) that reduces scheduling to sequential planning over action start and end events, and lazy-stream (Algorithm 3).
3. An application of ScheduleStream to TAMPAS, which leverages GPU acceleration for parallelized sampling (building on cuRobo custom CUDA kernels), extending GPU use beyond single-arm TAMP as in cuTAMP.
4. Simulated and real-world experiments and demonstrations across multiple multi-arm platforms, including a real-world bimanual robot.

Main Findings

• Parallelism shortens schedules. In Table II, the authors report that "Ours (+GPU) produces schedules on average half as long as Sequential." The average makespans reported are: Sequential 3.4 (first) and 3.1 (final); Hierarchical 1.7* and 1.5*; Ours 1.9* and 1.6*; Ours+GPU 2.0 and 1.5. Asterisk markers appear on the Table II averages for Hierarchical and Ours; the provided text does not explain them.
• Hierarchical planning fails often. Table I reports average success rate and first solution time: Sequential 99% at 6.5, Hierarchical 64% at 28.3, Ours 91% at 31.4, and Ours+GPU 99% at 1.9. The caption states Hierarchical fails to solve several tasks because it does not backtrack.
• GPU acceleration matters for runtime. The Table I caption notes that Ours has a lower success rate and higher runtime than its GPU-accelerated counterpart Ours + GPU. For example, SO100 Any 3: Sequential 99% / 5.9, Hierarchical 24% / 58.1, Ours 58% / 115.4, Ours+GPU 100% / 2.3. SO100 Any 4: Sequential 100% / 9.1, Hierarchical 9% / 101.4, Ours 18% / 244.2, Ours+GPU 99% / 4.4.
• Scaling behavior varies by task type. On Franka Any 4, success/time was Sequential 100 / 22.1, Hierarchical 5 / 57.9, Ours 99 / 31.6, Ours+GPU 100 / 6.8. On Franka Pack 4: Sequential 90 / 12.4, Hierarchical 41 / 40.2, Ours 96 / 18.2, Ours+GPU 99 / 2.3.
• Sequential planning has full success but poor makespan. Sequential achieved 100% success on most tasks with relatively short first-solution times (e.g., Franka Assigned 4 at 8.2), yet its makespans were highest (e.g., Franka Assigned 4: 2.8 first / 2.4 final; SO100 Any 4: 7.8 / 7.6).
• Collision structure dictates achievable parallelism. In the illustrative bimanual examples, Problem 1 admits full parallelism because trajectories "@t1" and "@t2" never collide; Problem 2 requires serial motion because those trajectories collide, although "@t1" does not collide with q2 and "@t2" does not collide with "@q1"; Problem 3 requires an extra move action to retreat arm1 out of the way because the pick configurations "@q1" and "@q2" collide.
• Real-world demonstration. A bimanual robot uses ScheduleStream to sort an apple into the red bin and a lime into the green bin, with algorithms automatically selecting which arm handles which object based on kinematics and executing actions asynchronously in parallel. Demonstrations are available at the project site, https://schedulestream.github.io.

Methodology in Plain English

The authors define a new language in Python where the world state is described by functions (relations between input values and an output value) rather than only Boolean predicates, subsuming predicate-based languages like STRIPS and PDDL. Some functions are static (fixed over time) and some are fluent (change as actions are applied). Actions come in two flavors: instantaneous actions with preconditions and effects (like pick and place), and durative actions with start conditions, start effects, ongoing conditions, end conditions, end effects, and a duration (the key example being move, whose duration is computed procedurally from the trajectory).

Continuous values (arm configurations, object placements, grasp poses, trajectories) are produced by streams — procedural conditional generators that consume known constants and emit new ones, extending the PDDLStream idea. To solve a problem, the algorithms alternate between a scheduling phase and a stream-sampling phase. eager-stream repeatedly tries to solve a finite scheduling problem with the constants available and, when that fails, calls streams to generate new constants that augment the initial state. The schedule subroutine compiles each durative action into a start and an end instantaneous action and runs a sequential search (lazy weighted A* with a modified Fast-Forward heuristic that ignores procedural and nested conditions), then extracts start and end times from the resulting plan, adding elapsed time where needed, and locally re-optimizes the plan with weight w = 1.

Because calling all streams is wasteful — robotics streams involve expensive operations like inverse kinematics — lazy-stream first substitutes streams with generators that emit unique placeholder constants (prefixed "@") and plans with those cheap values, then retraces which placeholders matter, calls only the necessary streams, and attempts to bind real values; failure triggers another round. On the robotics side, the authors use GPU batching for collision checking, forward and inverse kinematics, and motion planning, representing each robot as a union of inflated inscribed spheres (greedily sampled for a computation budget). Moving-object collisions use asymmetric sphere-mesh checks, and moving-arm collisions are cast as batched sphere-sphere self-collision checks for a two-arm composite robot. Experiments compare four algorithms consuming the same problem formulation: Sequential (a traditional TAMP-style ablation), Hierarchical (schedule-then-motion-plan without backtracking), Ours (lazy-stream), and Ours + GPU.

Why This Matters

Impact on research: The work claims the first domain-independent temporal planning language with procedural samplers, and the first general-purpose framework for planning and scheduling with sampling operations. It shows that the long-standing "one arm at a time" limitation of TAMP can be removed without giving up generality, and that the strict schedule-then-motion-plan hierarchy loses much of its success rate (64% average vs 99% for the GPU variant) while still producing longer makespans than parallel methods.

Real-world applications:

• Industrial assembly, where multiple arms work on the same workpiece; the paper notes prior multi-arm assembly work often assumes fixed task allocations, monotonicity, and single-object goals.
• Home and service robotics, where bimanual or humanoid robots must sort and place objects (demonstrated with the apple/lime bin-sorting task).
• Multi-robot pick-and-place on separate platforms, as in the Franka Hold Assigned/Any and SO100 Hold Any task families, where robots must be matched to objects based on reachability.
• Automated generation of training data for imitation learning, which the paper lists as a way planning supports learning systems.

Industry relevance: The framework is implemented in Python, allowing direct reuse of industrial and research tooling such as GPU collision checkers and kinematics solvers; the authors are at NVIDIA Research Seattle Robotics Lab (with an affiliation at the University of Sydney), and the GPU acceleration builds on cuRobo custom CUDA kernels. Reported first-solution times as low as an average of 1.9 for Ours+GPU versus 6.5 for Sequential, and 2.3 versus 115.4 on SO100 Any 3, speak to practical deployment on multi-arm hardware.

Future Directions

The provided content does not report an explicit future-work section; the following are logical next steps raised by the work.

• Extending beyond the two-arm composite robot used for batched sphere-sphere self-collision checks, to see how the "quadratic number of collision checks" for moving-arm pairs scales for larger arm counts and how GPU batching holds up.
• Broadening the evaluated task families beyond holding, packing, and stacking with the studied Franka and SO100 platforms, and closing the remaining gap where Ours and Ours+GPU do not reach 100% success on every task (for example Franka Any 4 at 99% for Ours, SO100 Any 2 at 95%, SO100 Any 4 at 99%).
• Improving the non-GPU lazy-stream path, since Ours averaged 91% success at 31.4 versus 99% at 1.9 for Ours+GPU, and investigating why first-solution time is sometimes higher than Hierarchy's on tasks the hierarchy can still solve.
• Clarifying whether the makespan advantage reported in Table II can be combined with the full success rate of the Sequential ablation, given that Sequential achieves 99% average success but the longest average makespans.

Target Audience

This paper is most valuable to robotics researchers and graduate students working on task and motion planning, temporal planning, and multi-arm manipulation; to engineers building bimanual or humanoid robot systems who need parallel arm scheduling; and to practitioners interested in GPU-accelerated sampling pipelines for robotics, particularly those already familiar with PDDLStream, cuTAMP, or cuRobo. Readers without a background in classical or hybrid planning will find the algorithmic sections (Sections IV-A through IV-C) demanding, though the problem framing and results tables are accessible.

Authors’ abstract

Bimanual and humanoid robots are appealing because of their human-like ability to leverage multiple arms to efficiently complete tasks. However, controlling multiple arms at once is computationally challenging due to the growth in the hybrid discrete-continuous action space. Task and Motion Planning (TAMP) algorithms can efficiently plan in hybrid spaces but generally produce plans, where only one arm is moving at a time, rather than schedules that allow for parallel arm motion. In order to extend TAMP to produce schedules, we present ScheduleStream, the first general-purpose framework for planning & scheduling with sampling operations. ScheduleStream models temporal dynamics using hybrid durative actions, which can be started asynchronously and persist for a duration that's a function of their parameters. We propose domain-independent algorithms that solve ScheduleStream problems without any application-specific mechanisms. We apply ScheduleStream to Task and Motion Planning & Scheduling (TAMPAS), where we use GPU acceleration within samplers to expedite planning. We compare ScheduleStream algorithms to several ablations in simulation and find that they produce more efficient solutions. We demonstrate ScheduleStream on several real-world bimanual robot tasks at https://schedulestream.github.io.