STITCHER: Constrained Trajectory Planning in Complex Environments with Real-Time Motion Primitive Search
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.
Rosa: We're looking at the paper: "STITCHER: Constrained Trajectory Planning in Complex Environments with Real-Time Motion Primitive Search".
Dev: Here's the gist of the paper. Autonomous high-speed navigation through large, complex environments requires real-time generation of agile trajectories that are dynamically feasible, collision-free, and satisfy state or actuator constraints <ref:2510.14893#pg2>.
Rosa: STITCHER presents an optimizationfree planning framework called STITCHER that stitches short trajectory segments together with graph search to compute longrange, expressive, and near-optimal trajectories in real-time <ref:2510.14893#pg2>.
Dev: Planning Architecture STITCHER utilizes an innovative three-stage planning architecture to generate smooth and expressive trajectories by stitching motion primitives together through graph search <ref:2510.14893#pg3>.
Rosa: The first two stages are designed to expedite the motion primitive search in the final stage by constructing a compact but expressive search graph and search heuristic <ref:2510.14893#pg3>.
Title and authors: Rosa: So we're looking at this paper today, "STITCHER: Constrained Trajectory Planning in Complex Environments with Real-Time Motion Primitive Search," and the authors are Helene Levy and Brett Lopez. It’s about finding a way to generate these high-speed trajectories that are safe, collision-free, and respect all the physical limits of the vehicle.
Dev: I think what's important is that they tackle this problem without relying on numerical optimization, which is usually how you get those high-quality, expressive paths today one. That’s a big deal because optimization can be slow and sometimes unstable when you need real-time performance in safety-critical situations.
Taro: I'm curious about the title itself. "Constrained Trajectory Planning in Complex Environments with Real-Time Motion Primitive Search." It sounds like they are promising something very specific, something that handles the complexity of a large area while keeping the calculation fast enough to actually be useful on a moving robot or plane.
Rosa: Exactly. They’re replacing optimization with this new planning framework called STITCHER, which stitches together small trajectory pieces using graph search instead of solving one massive optimization problem from scratch every time you need a path one.
Dev: The implication there is that we can get long-range, expressive paths in real time without the major computation bottlenecks that plague current methods. It moves the planning process into a much faster operational space.
Taro: So, if I'm driving or flying through something complex, this paper suggests we can get a good path quickly and safely using this stitching method instead of waiting for an optimizer to finish its work one.
The paper's summary: Rosa: In the summary, they explain that STITCHER uses a three-stage planning architecture to generate smooth and expressive trajectories by connecting motion primitives together through graph search two. They spend the first two stages building a compact but expressive search graph and a specific search heuristic to speed up the final stage.
Dev: That heuristic is used to guide the final stage, which is where they stitch everything together, using dynamic programming with the Bellman equation to figure out the cost-to-go for every point in that graph two. It’s a clever way to plan long distances by breaking it down into manageable steps.
Taro: I see how that structure works. They are not just throwing random motion primitives together; they are building a structured search space first, which is key because the number of possible paths grows exponentially if you just sample things blindly three.
Rosa: Right. And they also use a greedy graph pre-processing step to make the final graph smaller, which really helps speed things up in that last stage and makes the whole thing more efficient two.
Dev: The crucial technical result they highlight is that they prove all of these graphs are finite and that their heuristic is admissible, which gives them guarantees on a priori time and memory complexity bounds for the entire process two.
Taro: That guarantee about complexity sounds important because it means we know how much time and memory this will take before we even run the simulation or deployment, which is something we always need to know for real-time systems two.
The paper's improvements: Rosa: They point out several improvements over older methods. First, they use a novel three-stage architecture to achieve what used to require generating a huge number of motion primitives just to get enough density for a good path three.
Dev: And they improve on the search space reduction by using geometric paths as priors and constraining the motion primitives to pass through waypoints already computed in an earlier stage three. That helps narrow down what the final search has to look at.
Taro: I'm interested in how they handle the feasibility issue. Some prior work showed that using minimum-time input-constrained trajectories just for a set of waypoints results in a bang-bang acceleration profile, which isn't actually physically possible for things like quadrotors, leading to poor tracking three.
Rosa: So STITCHER seems to address that by adding an additional smoothing step, like model predictive contouring control, to get the trajectory smoothness we need three. It’s about ensuring the path is not just mathematically optimal but also something a real vehicle can actually follow smoothly.
Dev: And they handle constraints in a specific way. They prune motion primitives from the final search that violate any safety constraints or are in collision with obstacles two. That's how they guarantee safety by filtering out the bad options before committing to them.
Taro: So, it sounds like their improvement isn't just about finding *a* path, but about finding a path that is smooth and provably safe across all those physical limits, which is what makes it useful in the real world two.
Conclusion: Rosa: To wrap up the STITCHER paper, they show that this planning framework can generate high-quality trajectories over long distances—over fifty meters—with computation times measured in milliseconds three. They found it generates trajectories faster than three state-of-the-art optimization-based planners while maintaining constraint satisfaction three.
Dev: The main implication is that we can now achieve high quality and safety without the huge computational cost of traditional optimization methods, which opens up real-time planning for complex navigation in challenging environments one.
Taro: For me, what stands out is that they prove the search graph is finite and their heuristic is admissible, meaning they have those a priori bounds on time and memory complexity two. That’s a solid mathematical foundation for trusting the planner when it's running live.
Rosa: And hardware testing with flight speeds up to sixty-three kilometers per hour showed that this planner works well for position and attitude tracking control while staying within physical limits one. It seems like they've successfully bridged the gap between theory and actual flight performance.
Dev: So, the STITCHER paper gives us a way to plan for long distances in complex environments using a novel three-stage architecture that prioritizes real-time speed while keeping track of all the necessary constraints one.
Helene J. Levy, Brett T. Lopez
University of California, Los Angeles
cs.RO
Submitted: 2025-10-16
Updated: 2026-11-13
Code: https://github.com/vectr-ucla/stitcher
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 77/100
The gist: Autonomous high-speed navigation through large, complex environments requires real-time generation of agile trajectories that are dynamically feasible, collision-free…
Key concepts
- Motion Primitive Search
- This is the core idea where short, basic movements (like quick turns or straight paths) are pre-calculated. These primitives are then connected using a graph search to build a complete, long trajectory. This approach avoids complex optimization calculations during the actual pathfinding phase.
- Three-Stage Planning Architecture
- STITCHER uses three distinct steps: first, creating a compact search graph based on waypoints; second, using dynamic programming to find the best path cost; and third, using an admissible heuristic to guide the final motion primitive search. This structure speeds up the process significantly.
- Admissible Heuristic
- An admissible heuristic is a smart guess used during the search that never overestimates the true cost to reach a goal. In STITCHER, this estimate relies only on estimated minimum-time costs between states, making it fast and environment-agnostic because it ignores complex obstacle data during the initial guidance.
Terminology
Summary
Autonomous high-speed navigation through large, complex environments requires real-time generation of agile trajectories that are dynamically feasible, collision-free, and satisfy state or actuator constraints <ref:2510. p. 014893#pg2>. STITCHER presents an optimizationfree planning framework called STITCHER that stitches short trajectory segments together with graph search to compute longrange, expressive, and near-optimal trajectories in real-time <ref:2510. p. 014893#pg2>.
Planning Architecture
STITCHER utilizes an innovative three-stage planning architecture to generate smooth and expressive trajectories by stitching motion primitives together through graph search <ref:2510.14893#pg3>. The first two stages are designed to expedite the motion primitive search in the final stage by constructing a compact but expressive search graph and search heuristic <ref:2510. p. 114893#pg3>. Specifically, given a set of waypoints computed in the first stage, we create a velocity graph by representing nodes as sampled velocities at each waypoint, and edges as quick-to-generate minimum-time trajectories <ref:2510. p. 114893#pg3>. Dynamic programming on this graph is used to compute the cost-to-go for each node using the Bellman equation <ref:2510. p. 114893#pg3>.
Search Heuristics and Complexity
The first two stages are designed to expedite the motion primitive search in the final stage by constructing a compact but expressive search graph and search heuristic <ref:2510.14893#pg3>. The cost-to-go is then used as an admissible heuristic to efficiently guide the motion primitive search in the third stage <ref:2510. p. 114893#pg3>. STITCHER guarantees i) a priori time and memory complexity bounds and ii) trajectory optimality with respect to the graph discretization <ref:2510. p. 114893#pg3>. The size of the velocity graph G is finite and solely depends on the number of waypoints and sampled velocities <ref:2510. p. 614893#pg8>.
Real-Time Performance Gains
STITCHER was extensively tested in two simulation environments to evaluate algorithmic innovations and assess its performance against three state-of-the-art optimization-based planners <ref:2510.14893#pg3>. STITCHER is shown to generate highquality, dynamically feasible trajectories over long distances (over 50 m) with computation times in the milliseconds, and consistently generates trajectories faster than the state-of-the-art with comparable execution times <ref:2510. p. 114893#pg3>. The greedy motion primitive graph pre-processing step results in a negligible increase in solution cost but a substantial improvement in computation time <ref:2510. p. 914893#pg11>.
Constraint Handling and Hardware Verification
STITCHER guarantees safety by pruning motion primitives from the final search that violate constraints or are in collision <ref:2510.14893#pg7>. Hardware experiments with flight speeds up to 63 km/h further proved that our planner is effective in generating trajectories suitable for position and attitude tracking control while remaining within set physical limits <ref:2510. p. 014893#pg17>. STITCHER was shown to consistently generate trajectories faster than three state-of-the-art optimization-based planners while never violating constraints <ref:2510. p. 1 p. 114893#pg17>.
Comparison with State-of-the-Art
STITCHER’s computation times are faster than those measured for FASTER, GCOPTER, and MIGHTY for every test, and are up to 7x faster than MIGHTY, 8x faster than GCOPTER and 700x faster than FASTER <ref:2510.14893#pg14>. In some cases the baseline planners achieved lower execution times <ref:2510. p. 914893#pg14>. STITCHER is the only planner to achieve both zero state violations and collisions across all test cases <ref:2510.14893#pg15>.
Conclusion
In this work, we presented STITCHER, a motion primitive search planning algorithm that utilizes a novel three-stage planning architecture to design constrained trajectories in realtime over long distances <ref:2510.14893#pg9>. We proved the search graph is finite, and the proposed search heuristic is admissible, so STITCHER is guaranteed to i) have a priori bounded time and memory complexity and ii) generate optimal trajectories with respect to the sampled set of states <ref:2510. p. 114893#pg9>. Real-time search speeds were achieved through our novel heuristic crafting technique, greedy graph pre-processing method, and non-conservative constraint and collision checking procedure <ref:2510. p. 314893#pg9>. STITCHER was shown to consistently generate trajectories faster than three state-of-the-art optimization-based planners while never violating constraints <ref:2510.14893#pg9>. The hardware experiments with flight speeds up to 63 km/h further proved that our planner is effective in generating trajectories suitable for position and attitude tracking control while remaining within set physical limits <ref:2510. p. 014893#pg9>.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved trajectory planning speed through an optimizationfree planning framework called STITCHER which stitches short trajectory segments together with graph search to compute longrange, expressive, and near-optimal trajectories in real-time.
-
Enables autonomous high-speed navigation through large, complex environments by generating safe trajectories within a few milliseconds for paths spanning 50 m by 50 m environments.
-
Allows hardware testing with a custom quadrotor to produce trackable paths in real-time while respecting nonconvex constraints, such as limits on tilt angle and motor forces, with flight speeds up to 63 km/h.
-
Provides guarantees on path quality and algorithm complexity by proving all graphs are finite and that the proposed heuristic is admissible, which yields
a priori time and memory complexity bounds.
-
Enhances search efficiency by leveraging a greedy graph pre-processing step to form a compact motion primitive graph, which
is identical in size to the velocity graph G
while maintaining more connections than exhaustive search. -
Improves computation time by showing that the greedy motion primitive graph pre-processing step has a
negligible effect on solution cost compared to the observed computation speed up owing to the reduced graph size,
achieving an average of 82% speed-up over an exhaustive exponentially-growing graph. -
Increases search effort reduction by developing an admissible heuristic, which is
environment agnostic because it only relies on the estimated minimum-time cost between states and does not take into account obstacle or perception data.
-
Allows for flexible constraint handling by using a
samplingbased collision checking approach
that stores and reuses nearest neighbor queries to avoid repeated calculations, allowing for the inclusion of complex constraints like individual motor thrust limits. -
Enables robust performance across different environments by demonstrating that STITCHER
never violates constraints (state, control, or obstacles) because all constraints are strictly enforced,
unlike optimization-based methods that rely on relaxations.
Sources
- HEPP: Hyper-efficient Perception and Planning for High-speed Obstacle Avoidance of UAVs
- A Contracting Hierarchical Observer for Pose-Inertial Fusion
Related papers
- Rethinking Actions: Continuity-Aware Priors for World-Model Planning
- MOSAIC: Modular Obstacle and Spatial-Aware Framework for Manipulation In Cluttered Scenes
- SAGAS: Semantic-Aware Graph-Assisted Stitching for Offline Temporal Logic Planning
- DexSeed: Expanding Human Hand-Object Interactions into Robot Demonstrations for Dexterous Policy Learning
- LaST0.5: A Generalist World Action Model with Interaction-Centric Latent Reasoning
- CIALLO: Learning Shared Intent Representations for Cross-Embodiment Manipulation