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 S , each reached from shome by a precomputed path, and each covering a neighborhood ni(si) of object states within the region of interest G .
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≥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
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 ± 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).
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.
Yishuai Cai, Xinglin Chen, Yunxin Mao +6
National University of Defense Technology · PsiBot · PKU-Psibot Lab +1
Multi-robot task and motion planning (MR-TAMP) requires jointly reasoning about discrete task decisions and continuous collision-free motions of multiple interacting robots. Although asymptotically optimal algorithms have been developed for task and motion planning, extending these guarantees to the multi-robot setting introduces an important challenge: different task transitions may involve different subsets of robots and therefore impose constraints of different dimensions on the composite configuration space. Consequently, an asymptotically optimal planner must not only optimize motion within each task mode, but also ensure sufficient exploration of the different types of transitions connecting them. We characterize this transition structure and establish sufficient conditions for global asymptotic optimality in MR-TAMP, requiring persistent coverage of relevant transitions and asymptotically improving motion planning within connected feasible regions. Based on these conditions, we develop an efficient asymptotically optimal MR-TAMP algorithm that combines evolving individual-robot roadmaps with implicit tensor-product search, avoiding explicit construction of the composite roadmap. The planner further employs conditional transition sampling, lazy collision checking, and mode- and solution-level guidance to improve finite-time planning efficiency while retaining persistent exploration. The resulting framework provides asymptotic optimality guarantees for multi-robot manipulation while efficiently exploiting the structure of individual-robot motion planning.
Adversarial attacks on motion planning are crucial for evaluating and quantifying the intrinsic robustness of robotic manipulation. However, existing approaches are typically limited by restrictive exact-pose objectives and their reliance on planner-in-the-loop queries. To address these limitations, we propose a planner-agnostic attack framework for tolerance-aware manipulation. Our approach shifts the evaluation paradigm to task-level feasibility over goal regions, efficiently inserting adversarial obstacles without requiring oracle access to the victim system. Offline, we characterize the robot's intrinsic workspace capabilities via a kinematic occupancy heatmap, which encodes the density of feasible trajectories and robustness priors without invoking a specific planner. Online, we formulate the attack as a budgeted maximum-coverage optimization, strategically deploying obstacles subject to explicit geometric constraints to occlude the solution space. Extensive experiments across simulation and real-world scenarios demonstrate that our method reliably induces planning failures, significantly outperforming planner-in-the-loop baselines in both computational efficiency and attack efficacy.
Keke Tang, Tianyu Hao, Weilong Peng +5
Guangzhou University, Guangzhou 510006, China · University of Science and Technology of China, Hefei 230026, China · Northwestern Polytechnical University, Xi’an 710072, China