STITCHER: Constrained Trajectory Planning in Complex Environments with Real-Time Motion Primitive Search

summary

The gist

Autonomous high-speed navigation through large, complex environments requires real-time generation of agile trajectories that are dynamically feasible, collision-free…

In short

STITCHER is an optimization-free planning framework that generates long-range, near-optimal trajectories in real-time for autonomous navigation. It achieves this by stitching short motion primitives together using a three-stage graph search architecture. This method allows for fast, safe trajectory generation within milliseconds, outperforming state-of-the-art optimization planners while guaranteeing constraint satisfaction.

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 used across episodes

This episode discusses

The paper

STITCHER: Constrained Trajectory Planning in Complex Environments with Real-Time Motion Primitive Search · Read on arXiv

Helene J. Levy, Brett T. Lopez

University of California, Los Angeles

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.

More episodes

← Home