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

Nayesha Gandotra; Itamar Mishani; Lai Yuan; Oren Salzman; Maxim Likhachev

cs.RONov 30, 2025

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

Authors: Nayesha Gandotra, Itamar Mishani, Lai Yuan, Oren Salzman, Maxim Likhachev

Organizations: Robotics Institute, School of Computer Science Carnegie Mellon University, United States

Abstract

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.

Figures & tables

Fig. 1 : Shelf picking in industrial warehouse automation. Offline, B-CTMP caches a path from the robot’s home state to an attractor initiation state (red), from which a behavior policy is executed to reach the target (green). Each cached plan is certified to meet a user-specified success rate, and is retrieved online in constant time.

Fig. 2 : Overview of the preprocessing phase. Preprocessing computes a reduced set of initiation states $\widetilde{\mathcal{S}}$ , each reached from $s_{home}$ by a precomputed path, and each covering a neighborhood $n_{i}(s_{i})$ of object states within the region of interest $\mathcal{G}$ .

Panel of Figure 3 — Fig. 3 : Experimental results across the three manipulation tasks. Each table reports (i) the end-to-end success rate over feasible task instances ( $N{=}100$ grasping, $N{=}60$ insertion, and $N{=}200$ wheel replacement queries), scored under the $L\geq 0.9$ criterion of Section V-B , and (ii) the online planning time. Left panels show representative infeasible queries. For grasping (top), the object is placed where every candidate grasp pose collides with static obstacles. For insertion (middle), the port pose induces a joint singularity, causing loss of manipulability and failure to reach the target. For wheel replacement (bottom), the hub pose lies in a location where the policy results in a collision. Red bounding boxes indicate the affected joints.

Task	Goal Region	Preprocessing	Memory
Task	Vol. [cm 3 ]	Time [h]	Compression [%]
Shelf Grasping	$1260$	$0.28$	$99.6$
	$2500$	$5.90$	$94.0$
	$5600$	$14.5$	$92.7$
	Succ. [%]	Infeas. [%]	Plan. [ms]
	100	18	1.8 $\pm$ 0.007

TABLE I : Real-robot experiments. We report preprocessing statistics, showing the growth of preprocessing time with goal-region volume and the memory compression relative to a naive baseline storing every precomputed path. For each task we also report B-CTMP’s coverage, as the fraction of queries declined as infeasible, and the execution success rate on feasible queries (50, 50, and 20 trials, respectively).

Explore similar work

CABTO: Context-Aware Behavior Tree Grounding for Robot Manipulation
Mar 17, 2026Yishuai Cai, Xinglin Chen, Yunxin Mao +6Behavior Tree Robot Planning
National University of Defense Technology · PsiBot · PKU-Psibot Lab +1
Asymptotically Optimal Multi-Robot Task and Motion Planning
Sep 16, 2026Thi Thuy Ngan Duong, Cheuk Tung Shadow Yiu, Rahul Shome +1Multi-Robot Motion Planning Motion Planning
Nanyang Technological University · The Australian National University
Occluding the Solution Space: Planner-Agnostic Adversarial Attacks on Tolerance-Aware Manipulation
Jul 4, 2026Keke Tang, Tianyu Hao, Weilong Peng +5Motion Planning Obstacle Avoidance
Guangzhou University, Guangzhou 510006, China · University of Science and Technology of China, Hefei 230026, China · Northwestern Polytechnical University, Xi’an 710072, China

Mar 17, 2026, cs.ROJ/K move · Enter open · S save

CABTO: Context-Aware Behavior Tree Grounding for Robot Manipulation

Yishuai Cai, Xinglin Chen, Yunxin Mao, Kun Hu+5

National University of Defense Technology · PsiBot · PKU-Psibot Lab+1

Behavior Tree Robot Planning Robotic Manipulation Robot Systems

Open paper AskPDF arXiv

Behavior Trees (BTs) offer a powerful paradigm for designing modular and reactive robot controllers. BT planning, an emerging field, provides theoretical guarantees for the automated generation of reliable BTs. However, BT planning typically assumes that a well-designed BT system is already grounded -- comprising high-level action models and low-level control policies -- which often requires extensive expert knowledge and manual effort. In this paper, we formalize the BT Grounding problem: the automated construction of a complete and consistent BT system. We analyze its complexity and introduce CABTO (Context-Aware Behavior Tree grOunding), the first framework to efficiently solve this challenge. CABTO leverages pre-trained Large Models (LMs) to heuristically search the space of action models and control policies, guided by contextual feedback from BT planners and environmental observations. Experiments spanning seven task sets across three distinct robotic manipulation scenarios demonstrate CABTO's effectiveness and efficiency in generating complete and consistent behavior tree systems.

Abstract

Explore similar work

CABTO: Context-Aware Behavior Tree Grounding for Robot Manipulation

Asymptotically Optimal Multi-Robot Task and Motion Planning

Occluding the Solution Space: Planner-Agnostic Adversarial Attacks on Tolerance-Aware Manipulation