💻 computer science

COAD: Constant-Time Planning for Continuous Goal Manipulation with Compressed Library and Online Adaptation

COAD is a framework that enables constant-time motion planning for continuous goal manipulation tasks by discretizing the task space into coverage regions, constructing a compressed library of representative root solutions, and adapting them online to new goals with sub-millisecond query times.

Original authors: Adil Shiyas, Zhuoyun Zhong, Constantinos Chamzas

Published 2026-03-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Adil Shiyas, Zhuoyun Zhong, Constantinos Chamzas

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a robot arm in a busy factory. Your job is to pick up a specific object (like a coffee mug) and move it to a shelf. The problem? The mug isn't always in the same spot. Sometimes it's on the left, sometimes on the right, sometimes tilted slightly. The rest of the room (the table, the walls, other boxes) stays exactly the same.

Every time the mug moves, a traditional robot has to stop and think: "Okay, where is the mug now? How do I move my arm to get there without hitting the table? Let me calculate a brand new path from scratch." This takes time. If the mug moves 1,000 times, the robot calculates 1,000 different paths. That's slow and uses a lot of memory.

COAD is a new "smart robot brain" that solves this problem by changing how the robot thinks. Here is how it works, using some simple analogies:

1. The "Neighborhood" Map (Task Coverage Regions)

Instead of thinking about every single possible spot the mug could be (which is infinite), COAD divides the workspace into neighborhoods.

Imagine the table is a giant city. Instead of memorizing a unique driving route for every single house number, COAD says: "If the mug is anywhere in 'Block A', I can use the same main highway to get there."

The Magic: If a path works for the mug in the center of Block A, it will likely still work if the mug moves slightly to the left or right within that same block.
The Result: COAD turns an infinite number of problems into a finite number of "blocks."

2. The "Master Recipe" vs. The "Quick Adjustments" (Compressed Library)

In the past, robots would store a unique, detailed recipe (a motion plan) for every single house in the city. That's like having a cookbook with 10,000 pages just for making toast.

COAD is smarter. It only cooks the Master Recipes (called "Root Motions") for a few representative spots in each neighborhood.

The Library: It stores these few Master Recipes.
The Compression: Instead of storing 10,000 paths, it might only store 100. That's a 97% reduction in memory!

3. The "Tailor" (Online Adaptation)

When the robot gets a new command ("Pick up the mug at this exact spot!"), it doesn't start from zero.

Lookup: It instantly checks the map to see which "neighborhood" the mug is in. (This takes almost no time).
Retrieve: It grabs the Master Recipe for that neighborhood.
Tailor: It uses a quick "tailoring" tool to slightly stretch or bend that Master Recipe so it fits the mug's exact new position.

Think of it like a suit. You don't need a custom-made suit for every single day of the year. You buy one great suit (the Master Recipe) and just roll up the sleeves or adjust the collar (the Adaptation) to fit the specific occasion.

The Three "Tailoring" Tools

The paper tests three different ways to do this "tailoring":

Linear Interpolation (The Quick Stretch): Like pulling a rubber band. It's the fastest but might look a bit jerky.
Dynamic Movement Primitives (The Smooth Curve): Like a dancer adjusting their steps. It's slightly slower but keeps the movement very smooth and natural.
Simple Trajectory Optimization (The Polish): Like a sculptor refining a statue. It takes a bit more time to make the path perfect but results in the highest quality movement.

Why This Matters

Speed: The robot can answer "How do I get there?" in less than a millisecond. That's faster than you can blink.
Memory: It doesn't need a massive hard drive. It fits on a tiny chip.
Reliability: Even in crowded, messy rooms (like a cage of boxes), it works almost 100% of the time, whereas older methods often get stuck or fail.

The Bottom Line

COAD is like giving a robot a GPS that doesn't need to recalculate the whole route every time you turn a corner. Instead, it knows the "neighborhoods," keeps a few "master routes" in its pocket, and just tweaks them on the fly. This allows robots to work faster, smarter, and with less computing power, making them ready for real-world jobs like packing boxes or assembling products.

1. Problem Statement

The paper addresses the challenge of goal-varying motion planning in robotic manipulation. In many industrial scenarios (e.g., pick-and-place, kitting), a robot must repeatedly solve motion planning problems where the environment and obstacles remain static, but the pose of the target object varies continuously within a bounded region of $SE(3)$.

The Challenge: Traditional sampling-based planners (like RRT) lack deterministic runtime guarantees and are too slow for high-frequency repeated queries. Existing experience-based methods (libraries) often require storing a massive number of solutions to cover a continuous task space, leading to high memory usage and no guarantee that every possible continuous goal is solvable.
The Goal: Develop a framework that provides constant-time ( $O(1)$ ) planning guarantees for a continuous goal space while maintaining high path quality and significantly compressing the storage requirements of the solution library.

2. Methodology: The COAD Framework

COAD (Constant-time planning for Continuous goal manipulation with compressed Library and Online Adaptation) operates in two phases: Offline Library Building and Online Querying.

A. Task Space Discretization via Task Coverage Regions (TCRs)

Instead of discretizing the goal space arbitrarily, COAD leverages the geometric property that a single valid motion path can cover a continuous subset of object poses.

Task Space Regions (TSRs): Defines valid end-effector poses relative to an object.
Task Coverage Regions (TCRs): Inverts the relationship. A TCR is defined as the set of all object poses for which a fixed end-effector pose remains a valid goal.
Theoretical Guarantee: The authors prove that if the displacement bounds of the TSR have a non-empty interior, the resulting TCR also contains an axis-aligned box. This allows the continuous task space to be discretized into a finite grid of boxes, where each box is fully covered by a single representative solution.
Indexing: Any query object pose is mapped to a grid index $(i_x, i_y, i_z, i_\psi)$ in $O(1)$ time.

B. Offline Library Building with Compression

Rather than planning a unique path for every grid cell (which is memory-intensive), COAD constructs a compressed library:

Root Path Selection: The algorithm samples an uncovered region, solves for a "root" motion (a full path from start to a representative goal) using a standard planner (e.g., RRT-Connect).
Adaptation & Verification: The algorithm attempts to cover neighboring regions by adapting the root path to the new goal poses.
- Crucially, collision checking is performed offline during this adaptation phase. If an adapted path is collision-free, the neighbor region is marked as "covered" by the root path.
- This creates a map linking every covered region to a specific root path index.
Compression: The final library stores only the root paths and the adaptation map. The number of stored paths is drastically reduced because one root path can serve many nearby goals.

C. Online Querying

When a new query arrives:

Retrieval: The object pose is mapped to a TCR grid index. The system retrieves the associated root path in constant time.
Adaptation: A lightweight adaptation module deforms the root path to the specific query goal.
Output: The final trajectory is generated without running a full planner.

Adaptation Strategies:
The paper evaluates three adaptation methods:

Linear Interpolation (LI): Connects the end of the root path to the new goal via a straight line in joint space. Fastest but lowest path quality.
Dynamic Movement Primitives (DMPs): Fits a dynamical system to the root path and retargets it. Offers a balance of speed and smoothness.
Simple Trajectory Optimization (STO): Uses the root path as a warm-start for a convex quadratic program (QP) to minimize velocity/acceleration while satisfying constraints. Highest quality but slightly slower.

3. Key Contributions

Continuous-to-Finite Partitioning: A novel framework that partitions an infinite family of continuous planning queries into a finite set of Task Coverage Regions (TCRs), each certified by a single path.
Compressed Library Construction: A method to build a library where the majority of the task space is covered by adapting a small set of "root" paths, achieving up to 97% compression of the full path library.
Constant-Time Guarantees: The first framework to provide deterministic constant-time planning guarantees for continuous goal-parameterized domains (previous works only guaranteed this for discrete spaces).
Real-World Validation: Successful deployment on physical robots (UR10, Panda, Fetch) demonstrating sub-millisecond query times and high success rates.

4. Experimental Results

The framework was evaluated on 7-DOF (Panda) and 8-DOF (Fetch) manipulators in three environments (Table, Shelf, Cage) and on a real UR10 robot.

Compression: COAD reduced the library size by 67% to 97% compared to a full uncompressed library, depending on the environment and adaptation method.
Query Time:
- COAD-LI: Achieved query times as low as 0.02 ms.
- COAD-DMP/STO: Achieved times in the 0.7 ms – 10 ms range.
- Comparison: COAD was 2 to 3 orders of magnitude faster than RRT-Connect (which had a 3s timeout) and significantly faster than baseline library methods.
Success Rate: COAD achieved a 100% success rate across all simulated and real-world tests, whereas RRT-Connect and baseline libraries failed frequently in constrained environments (e.g., Cage/Shelf).
Path Quality: While LI had slightly lower quality, COAD-DMP and STO produced path qualities comparable to or better than baseline libraries, with STO providing the smoothest trajectories.

5. Significance

COAD represents a significant advancement in robotic manipulation by bridging the gap between theoretical guarantees and practical efficiency.

Industrial Applicability: It enables robots to react instantly to continuous variations in object placement (e.g., on a conveyor belt) without re-planning from scratch, making it ideal for high-speed pick-and-place and assembly tasks.
Memory Efficiency: By proving that a small set of root paths can cover a continuous space, it solves the "memory bottleneck" of traditional experience-based planners.
Determinism: It moves motion planning from probabilistic success (common in sampling-based methods) to deterministic, constant-time execution, a critical requirement for safety-critical and high-throughput robotic systems.