# Constant-Time Planning for Chaining Collision-free Motion to Manipulation Behaviors

arXiv: https://arxiv.org/abs/2512.00939 · HTML: https://mlsanity.com/paper/2512.00939/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 30 references that are in the map.
- First posted on arXiv 30 Nov 2025.

## Builds on (most cited first, 18 of 18)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Learning Fine-Grained Bimanual Manipulation with Low-Cost Hardware](https://mlsanity.com/paper/2304.13705/) (2023)
- [Planning with Diffusion for Flexible Behavior Synthesis](https://mlsanity.com/paper/2205.09991/) (2022)
- [Integrated Task and Motion Planning](https://mlsanity.com/paper/2010.01083/) (2020)
- [ManiSkill3: GPU Parallelized Robotics Simulation and Rendering for Generalizable Embodied AI](https://mlsanity.com/paper/2410.00425/) (2024)
- [A Review of Robot Learning for Manipulation: Challenges, Representations, and Algorithms](https://mlsanity.com/paper/1907.03146/) (2019)
- [cuRobo: Parallelized Collision-Free Minimum-Jerk Robot Motion Generation](https://mlsanity.com/paper/2310.17274/) (2023)
- [Analysis and Observations from the First Amazon Picking Challenge](https://mlsanity.com/paper/1601.05484/) (2016)
- [Adaptive Online Replanning with Diffusion Models](https://mlsanity.com/paper/2310.09629/) (2023)
- [Motion Planning around Obstacles with Convex Optimization](https://mlsanity.com/paper/2205.04422/) (2022)
- [Shortest Paths in Graphs of Convex Sets](https://mlsanity.com/paper/2101.11565/) (2021)
- [Motions in Microseconds via Vectorized Sampling-Based Planning](https://mlsanity.com/paper/2309.14545/) (2023)
- [Provably Constant-time Planning and Replanning for Real-time Grasping Objects off a Conveyor Belt](https://mlsanity.com/paper/2101.07148/) (2021)
- [Certified Polyhedral Decompositions of Collision-Free Configuration Space](https://mlsanity.com/paper/2302.12219/) (2023)
- [Alternative Paths Planner (APP) for Provably Fixed-time Manipulation Planning in Semi-structured Environments](https://mlsanity.com/paper/2012.14970/) (2020)
- [Growing Convex Collision-Free Regions in Configuration Space using Nonlinear Programming](https://mlsanity.com/paper/2303.14737/) (2023)
- [Constant-time Motion Planning with Anytime Refinement for Manipulation](https://mlsanity.com/paper/2311.00837/) (2023)
- [COVER:COverage-VErified Roadmaps for Fixed-time Motion Planning in Continuous Semi-Static Environments](https://mlsanity.com/paper/2510.03875/) (2025)

## Abstract (arXiv)

Recent progress in contact-rich robotic manipulation has been striking, yet most deployed systems remain confined to simple, scripted routines. One of the barriers is the lack of motion planning algorithms that can provide verifiable guarantees for safety, efficiency and reliability. Constant-Time Motion Planning (CTMP) is a recent step toward such guarantees for collision-free motion in a priori known environments:: a preprocessing phase enables queries to be answered within a fixed, user-specified time budget (e.g., 10 milliseconds). However, CTMP certifies only reachability---a binary predicate---and ignores the manipulation behavior that completes the task, which is increasingly stochastic (e.g., a learned skill) and whose success no single offline rollout can establish, let alone certify. We introduce the Behavioral Constant-Time Motion Planner (B-CTMP), which extends CTMP to two-step manipulation tasks in semi-structured environments: a collision-free motion to a behavior initiation state, followed by execution of a behavior such as grasping or insertion. B-CTMP departs from prior CTMP in two ways: neighborhoods are constructed in object-pose space rather than robot configuration space, and coverage is established by statistical certification rather than a reachability check. A plan is cached only if repeated rollouts lower-bound its success rate above a user-specified threshold, and we prove these bounds hold simultaneously across the entire cache at a prescribed confidence level. For deterministic behaviors a single rollout suffices, recovering the binary check of prior CTMP as a special case. We evaluate B-CTMP on three manipulation tasks---shelf picking, plug insertion, and wheel replacement---in simulation and on real robots. B-CTMP's certified plans succeed consistently where baselines fail during behavior execution, and it rejects infeasible object poses in constant time.