Technical Summary: Waypoints Matter: A Systematic Study for Sampling-Based Trajectory Planning

Problem Statement

Real-time autonomous driving relies heavily on sampling-based trajectory planners that generate candidate paths by linking the vehicle's current state to a set of target waypoints sampled along the road centerline. While the selection of trajectory primitives (the mathematical representation of the path) and the computational budget are well-studied, the placement of these target waypoints is often treated as a secondary implementation detail or a fixed heuristic.

The core problem addressed is that the spatial distribution of waypoints directly dictates the existence and quality of feasible trajectories. Despite the critical nature of this step, its impact on planner performance remains largely unexplored in isolation. Existing literature often varies placement strategies alongside other planner components (e.g., optimizers or primitives), making it difficult to attribute performance gains specifically to waypoint placement. This paper posits that waypoint placement should be treated as a "first-class design variable" and seeks to systematically quantify its effect on planning outcomes.

Methodology

The authors propose a controlled evaluation framework designed to isolate the impact of waypoint placement strategies while holding all other variables constant.

Experimental Setup

• Fixed Constraints: The trajectory primitive is fixed as a degree-5 Bézier curve with $G^2$-continuous boundary conditions. The candidate budget is fixed at 4,000 candidates distributed uniformly across the selected waypoints.
• Environment: The study utilizes five CommonRoad maps ($M_1$ to $M_5$) representing increasing geometric complexity, from straight highways to demanding urban corridors.
• Test Scenarios: For each map, a 60-meter planning corridor is defined. The system generates 9,000+ "launch states" (ego vehicle poses) by sampling positions within elliptical regions along the centerline, with perturbed headings and curvatures to simulate real-world variance.
• Metrics: Four scalar metrics are evaluated for each configuration:
  1. Reliability ($f_1$): Success rate (percentage of queries yielding at least one valid trajectory).
  2. Candidate Yield ($f_2$): Fraction of the 4,000 budget that results in valid candidates.
  3. Trajectory Length ($f_3$): Mean length of valid trajectories, normalized by the horizon.
  4. Diversity ($f_4$): Shannon entropy of trajectory lengths, measuring the spread of the candidate set.
  • These are aggregated into a weighted score $J$, with a primary "balanced" weighting of 70% reliability, 20% yield, 8% length, and 2% diversity.

Strategies Evaluated

Three placement strategies were systematically swept across 449 configurations:

1. Uniform Sampling: Waypoints placed at fixed arc-length intervals ($d_s$).
2. RDP (Augmented Ramer–Douglas–Peucker):* A two-step process where the classical RDP algorithm simplifies the centerline, followed by a "gap-filling" step to ensure no segment exceeds the nominal distance $d_s$.
3. Curvature-Adaptive Sampling: A novel method where the local spacing $d_{local}$ is a function of the road curvature $\kappa(s)$: $d_{local}(s) = d_s / (1 + \alpha |\kappa(s)|)$. This was tested with both a centered window (densifying at the turn's midpoint) and a forward window (densifying just before the turn).

Key Contributions

1. Controlled Evaluation Framework: The paper establishes a rigorous method for isolating waypoint placement effects by fixing the trajectory primitive and candidate budget, sweeping three distinct strategies across a dense parameter grid (449 configurations) and five diverse maps.
2. Novel Curvature-Conditioned Allocation: The authors introduce a continuous, geometry-aware density control method that adjusts waypoint spacing explicitly based on local curvature, offering a mechanism to pre-densify the search space before high-curvature segments.
3. Empirical Evidence on Dominance of Spacing: The study provides data-driven evidence that the nominal inter-waypoint distance ($d_s$) is the dominant performance driver, outweighing the choice of placement strategy in most scenarios.

Results

The systematic sweep yielded several critical findings regarding planner performance:

• Dominance of Nominal Spacing ($d_s$): The inter-waypoint distance is the primary factor influencing reliability and candidate yield. Large differences in planner failure rates (ranging from 331 to over 400 failures across maps) were attributed to placement alone.
• Uniform Sampling Performance: Uniform sampling, when tuned to an optimal spacing (approximately $d_s \approx 8$ m), matches or surpasses the performance of more complex strategies. It offers a robust baseline that requires no geometric analysis.
• Curvature-Adaptive Advantage: The forward-window curvature-adaptive variant ($\gamma=0$) provides a small but consistent advantage over uniform sampling, particularly under reliability-first and balanced weightings. By placing extra waypoints before a curve, it compensates for the higher kinematic rejection rate inherent in curved paths. The centered-window variant was less effective, as it densified the path at the turn's midpoint rather than its entry.
• RDP Limitations:* The augmented RDP* strategy never outperformed uniform sampling. At high simplification tolerances, it converged to uniform sampling due to gap-filling; at low tolerances, it fragmented the candidate budget similarly to small uniform spacings.
• Trade-offs: Reliability and candidate yield improve with larger $d_s$ (assigning more candidates per target), while diversity and trajectory length favor smaller $d_s$. The "best" configuration depends on the weighting priority, but large $d_s$ consistently dominates the top ranks.

Significance and Claims

The paper claims that waypoint placement is not merely an implementation detail but a critical design variable that significantly impacts the feasibility of autonomous driving trajectories.

• Design Guidance: The authors conclude that $d_s$ should be treated as the dominant tuning parameter. Geometry-aware strategies (like curvature-adaptive sampling) are only necessary for geometrically complex corridors where feasibility is the limiting factor and offer only marginal gains over well-tuned uniform sampling.
• Re-evaluation of Heuristics: The study challenges the assumption that complex simplification heuristics (like RDP) inherently improve planning. In isolation, they do not offer advantages over simple uniform spacing when the candidate budget is fixed.
• Modest Scope: The authors acknowledge limitations, noting that the study assumes static maps without dynamic obstacles and uses a single trajectory primitive. They suggest that future work should explore the interaction between waypoint placement and dynamic obstacle avoidance, as well as the transferability of these findings to other primitives (e.g., clothoids).

In summary, the paper argues that for sampling-based planners, "Waypoints Matter," but the spacing matters more than the strategy, with a simple, well-tuned uniform grid often being the most effective solution.