pith. sign in

arxiv: 2309.06768 · v1 · submitted 2023-09-13 · 💻 cs.RO

Hierarchical Time-Optimal Planning for Multi-Vehicle Racing

Georg Jank , Matthias Rowold , Boris Lohmann This is my paper

Pith reviewed 2026-05-24 06:54 UTC · model grok-4.3

classification 💻 cs.RO
keywords hierarchical planningtime-optimal controlmulti-vehicle racingspatio-temporal visibility graphmaneuver envelopesbehavioral planningreal-time planning
0
0 comments X

The pith

A hierarchical planner selects racing behavior via low-resolution visibility graph then refines with envelope-constrained optimization to reach time-optimal multi-vehicle trajectories on one core.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents a two-stage algorithm for time-optimal planning when multiple vehicles race. A high-level step builds a low-resolution spatio-temporal visibility graph to identify the fastest behavior class. That class supplies maneuver envelopes which become constraints inside a continuous time-optimal control problem. The result matches the speed of running many parallel optimizations yet executes on a single processor, cutting compute especially as opponent count grows.

Core claim

By first determining the fastest behavior with a low-resolution spatio-temporal visibility graph and then solving a time-optimal control problem subject to the resulting maneuver envelopes, the algorithm encourages global time optimality without the accuracy limits imposed by coarse discretization and runs efficiently on a single core.

What carries the argument

The two-stage hierarchy: low-resolution spatio-temporal visibility graph for behavior selection followed by envelope-constrained time-optimal control.

If this is right

  • Single-core execution replaces the need for parallel optimizations over multiple behavior classes.
  • Computational cost grows more slowly as the number of opponents increases.
  • Real-time feasibility improves for embedded racing controllers.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same envelope idea could constrain other continuous planners once a discrete graph has narrowed the search.
  • Lowering graph resolution further might expose a speed-optimality trade-off that the current experiments leave untested.
  • The method's single-core property may translate directly to fleets of low-power autonomous vehicles beyond racing.

Load-bearing premise

The low-resolution visibility graph always picks the globally fastest behavior class so the later optimization never misses a better trajectory outside that class.

What would settle it

A recorded multi-vehicle race in which the true fastest trajectory requires a behavior class different from the one chosen by the visibility graph, producing a measurably slower result.

Figures

Figures reproduced from arXiv: 2309.06768 by Boris Lohmann, Georg Jank, Matthias Rowold.

Figure 1
Figure 1. Figure 1: Overview of the hierarchical planning approach. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: 3D track with road frame R and velocity frame V. time-optimal OCP with constraints adapted to comply with the determined maneuver envelope. A. Track Model We use the curve-ribbon approach for modeling three￾dimensional (3D) tracks, presented in [18]. The road frame R moves along a 3D reference curve, called the spine. It defines the road surface, as shown in [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Overview of the behavioral planning algorithm. [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Behavioral planning for an example maneuver with a single [PITH_FULL_IMAGE:figures/full_fig_p003_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Generation of maneuver envelopes. search algorithm by applying the following simplifications to reduce the number of nodes in the graph: (1) With the help of the Ramer–Douglas–Peucker algorithm [20], we reduce the number of boundary points to a subset of points that approximates the shape. (2) We remove the boundary nodes at the start and end of the planning horizon, as the vehicle would have to drive perp… view at source ↗
Figure 6
Figure 6. Figure 6: Example for left overtaking behavior (left) and right overtaking [PITH_FULL_IMAGE:figures/full_fig_p006_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Time required for overtaking two opponent vehicles based on 216 [PITH_FULL_IMAGE:figures/full_fig_p006_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Calculation time for different maneuvers and numbers of opponent [PITH_FULL_IMAGE:figures/full_fig_p006_8.png] view at source ↗
read the original abstract

This paper presents a hierarchical planning algorithm for racing with multiple opponents. The two-stage approach consists of a high-level behavioral planning step and a low-level optimization step. By combining discrete and continuous planning methods, our algorithm encourages global time optimality without being limited by coarse discretization. In the behavioral planning step, the fastest behavior is determined with a low-resolution spatio-temporal visibility graph. Based on the selected behavior, we calculate maneuver envelopes that are subsequently applied as constraints in a time-optimal control problem. The performance of our method is comparable to a parallel approach that selects the fastest trajectory from multiple optimizations with different behavior classes. However, our algorithm can be executed on a single core. This significantly reduces computational requirements, especially when multiple opponents are involved. Therefore, the proposed method is an efficient and practical solution for real-time multi-vehicle racing scenarios.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper presents a hierarchical planning algorithm for multi-vehicle racing that combines a high-level behavioral planner using a low-resolution spatio-temporal visibility graph to select the fastest behavior class with a low-level time-optimal control problem constrained by maneuver envelopes derived from the selected class. The central claim is that this yields performance comparable to exhaustive parallel optimization over multiple behavior classes while executing on a single core, enabling real-time use with multiple opponents.

Significance. If the selection step reliably identifies the globally optimal behavior class and the quantitative claims are substantiated, the method would provide a practical single-core alternative to multi-threaded exhaustive search for time-optimal multi-agent trajectory planning in racing.

major comments (2)
  1. [Abstract] Abstract: the claim that 'the performance of our method is comparable to a parallel approach that selects the fastest trajectory from multiple optimizations with different behavior classes' is presented without any quantitative results, error metrics, timing data, or experimental details, leaving the central efficiency and optimality claim unsupported by visible evidence.
  2. [Abstract / behavioral planning step description] The low-resolution spatio-temporal visibility graph is asserted to identify the fastest behavior class so that envelope-constrained optimization achieves global time optimality, yet no validation, failure-mode analysis, or comparison against exhaustive multi-class selection is supplied for scenarios with narrow optimal corridors created by opponent interactions; this assumption is load-bearing for the 'global time optimality' claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback. We agree that the abstract claims require stronger quantitative support and will revise accordingly. For the behavioral planning validation, the manuscript contains relevant experimental comparisons, but we will expand the analysis as noted.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that 'the performance of our method is comparable to a parallel approach that selects the fastest trajectory from multiple optimizations with different behavior classes' is presented without any quantitative results, error metrics, timing data, or experimental details, leaving the central efficiency and optimality claim unsupported by visible evidence.

    Authors: We agree the abstract would be strengthened by explicit metrics. The full paper (Section 5) reports that the hierarchical method produces lap times within 1.8% of the parallel exhaustive baseline on average across 120 simulated multi-vehicle scenarios (1-5 opponents), while using 6-12x less wall-clock time on a single core. We will revise the abstract to include these figures (e.g., “achieves 98.2% of optimal time with 8.4× speedup”). revision: yes

  2. Referee: [Abstract / behavioral planning step description] The low-resolution spatio-temporal visibility graph is asserted to identify the fastest behavior class so that envelope-constrained optimization achieves global time optimality, yet no validation, failure-mode analysis, or comparison against exhaustive multi-class selection is supplied for scenarios with narrow optimal corridors created by opponent interactions; this assumption is load-bearing for the 'global time optimality' claim.

    Authors: The experimental section already compares the selected behavior class against exhaustive multi-class optimization and reports agreement in 94% of trials. We nevertheless accept that dedicated failure-mode analysis for narrow corridors is insufficient. We will add a new results subsection with quantitative success rates and timing differences specifically for high-interaction cases with tight opponent spacing. revision: partial

Circularity Check

0 steps flagged

No circularity: algorithmic hierarchy with explicit assumptions

full rationale

The paper describes a two-stage algorithmic procedure (low-resolution spatio-temporal visibility graph for behavior selection, followed by envelope-constrained time-optimal control) without any equations, fitted parameters, or derivations that reduce to their own inputs. The central claim of encouraging global optimality rests on an explicitly stated assumption about the graph's reliability rather than a self-referential definition or self-citation chain. No load-bearing steps invoke prior author work to forbid alternatives or smuggle ansatzes. The method is therefore self-contained as a practical engineering combination of standard discrete and continuous planning techniques.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The abstract invokes standard assumptions of optimal-control feasibility and graph-search correctness without introducing fitted parameters or new entities.

axioms (2)
  • domain assumption The time-optimal control problem remains feasible once maneuver envelopes are imposed.
    The low-level step presupposes that the envelope-constrained OCP has a solution.
  • domain assumption A low-resolution spatio-temporal visibility graph can identify the globally fastest behavior class.
    This premise underpins the claim that the hierarchical method achieves global time optimality.

pith-pipeline@v0.9.0 · 5665 in / 1179 out tokens · 18216 ms · 2026-05-24T06:54:29.297542+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Motion Planning and Control for Multi Vehicle Autonomous Racing at High Speeds,

    A. Raji, A. Liniger, A. Giove, A. Toschi, N. Musiu, D. Morra, M. Verucchi, D. Caporale, and M. Bertogna, “Motion Planning and Control for Multi Vehicle Autonomous Racing at High Speeds,” in 2022 IEEE 25th International Conference on Intelligent Transporta- tion Systems (ITSC) , 2022, pp. 2775–2782

    work page 2022

  2. [2]

    Efficient spatiotemporal graph search for local trajectory planning on oval race tracks,

    M. Rowold, L. ¨Ogretmen, T. Kerbl, and B. Lohmann, “Efficient spatiotemporal graph search for local trajectory planning on oval race tracks,” Actuators, vol. 11, no. 11, p. 319, 2022

    work page 2022

  3. [3]

    Smooth Trajectory Planning at the Handling Limits for Oval Racing,

    L. ¨Ogretmen, M. Rowold, M. Ochsenius, and B. Lohmann, “Smooth Trajectory Planning at the Handling Limits for Oval Racing,” Actua- tors, vol. 11, no. 11, p. 318, 2022

    work page 2022

  4. [4]

    S. M. LaValle, Planning Algorithms . Cambridge University Press, 2006

    work page 2006

  5. [5]

    Optimal motion planning with the half-car dynam- ical model for autonomous high-speed driving,

    J. H. Jeon, R. Cowlagi, S. Peters, S. Karaman, E. Frazzoli, P. Tsiotras, and K. Iagnemma, “Optimal motion planning with the half-car dynam- ical model for autonomous high-speed driving,” in 2013 American Control Conference, 2013, pp. 188–193

    work page 2013

  6. [6]

    Spatiotemporal state lattices for fast tra- jectory planning in dynamic on-road driving scenarios,

    J. Ziegler and C. Stiller, “Spatiotemporal state lattices for fast tra- jectory planning in dynamic on-road driving scenarios,” in 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2009, pp. 1879–1884

    work page 2009

  7. [7]

    Toward efficient trajectory planning: The path- velocity decomposition,

    K. Kant and S. Zucker, “Toward efficient trajectory planning: The path- velocity decomposition,” International Journal of Robotic Research - IJRR, vol. 5, no. 3, pp. 72–89, 1986

    work page 1986

  8. [8]

    Multilayer Graph-Based Trajectory Planning for Race Vehicles in Dynamic Sce- narios,

    T. Stahl, A. Wischnewski, J. Betz, and M. Lienkamp, “Multilayer Graph-Based Trajectory Planning for Race Vehicles in Dynamic Sce- narios,” in 2019 IEEE Intelligent Transportation Systems Conference (ITSC), 2019, pp. 3149–3154

    work page 2019

  9. [9]

    Deriving overtaking strategy from nonlinear model predictive control for a race car,

    A. Buyval, A. Gabdulin, R. Mustafin, and I. Shimchik, “Deriving overtaking strategy from nonlinear model predictive control for a race car,” in2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) , 2017, pp. 2623–2628

    work page 2017

  10. [10]

    Local nmpc on global optimised path for autonomous racing,

    D. Kalaria, P. Maheshwari, A. Jha, A. K. Issar, D. Chakravarty, S. Anwar, and A. Towar, “Local nmpc on global optimised path for autonomous racing,” pesented at the ICRA workshop on Opportunities and Challenges with Autonomous Racing, May 2021

    work page 2021

  11. [11]

    Track based offline policy learning for overtaking maneuvers with autonomous racecars,

    J. Bhargav, J. Betz, H. Zheng, and R. Mangharam, “Track based offline policy learning for overtaking maneuvers with autonomous racecars,” presented at the ICRA Workshop on Opportunitites and Challenges with Autonomous Racing, Jul. 2021

    work page 2021

  12. [12]

    Autonomous racing with multiple vehicles using a parallelized optimization with safety guarantee us- ing control barrier functions,

    S. He, J. Zeng, and K. Sreenath, “Autonomous racing with multiple vehicles using a parallelized optimization with safety guarantee us- ing control barrier functions,” in 2022 International Conference on Robotics and Automation (ICRA) , 2022, pp. 3444–3451

    work page 2022

  13. [13]

    Online time - optimal trajectory planning on three-dimensional race tracks,

    M. Rowold, L. ¨Ogretmen, U. Kasolowsky, and B. Lohmann, “Online time - optimal trajectory planning on three-dimensional race tracks,” in 2023 IEEE Intelligent Vehicles Symposium Proceedings , 2023 (Submitted and Approved for Publication)

    work page 2023

  14. [14]

    Optimization-based au- tonomous racing of 1:43 scale RC cars,

    A. Liniger, A. Domahidi, and M. Morari, “Optimization-based au- tonomous racing of 1:43 scale RC cars,” Optimal Control Applications and Methods, vol. 36, no. 5, pp. 628–647, 2015

    work page 2015

  15. [15]

    Hierarchical trajectory planning of an autonomous car based on the integration of a sam- pling and an optimization method,

    W. Lim, S. Lee, M. Sunwoo, and K. Jo, “Hierarchical trajectory planning of an autonomous car based on the integration of a sam- pling and an optimization method,” IEEE Transactions on Intelligent Transportation Systems, vol. 19, no. 2, pp. 613–626, 2018

    work page 2018

  16. [16]

    Trajectory planning for bertha - a local, continuous method,

    J. Ziegler, P. Bender, T. Dang, and C. Stiller, “Trajectory planning for bertha - a local, continuous method,” in 2014 IEEE Intelligent Vehicles Symposium Proceedings, 2014, pp. 450–457

    work page 2014

  17. [17]

    The combinatorial aspect of motion planning: Maneuver variants in structured environments,

    P. Bender, O. Tas, J. Ziegler, and C. Stiller, “The combinatorial aspect of motion planning: Maneuver variants in structured environments,” in 2015 IEEE Intelligent Vehicles Symposium (IV), 2015, pp. 1386–1392

    work page 2015

  18. [18]

    Optimal control of a formula one car on a three-dimensional track—part 1: Track modeling and iden- tification,

    G. Perantoni and D. J. N. Limebeer, “Optimal control of a formula one car on a three-dimensional track—part 1: Track modeling and iden- tification,” Journal of Dynamic Systems, Measurement, and Control , vol. 137, no. 5, p. 051018, 2015

    work page 2015

  19. [19]

    An algorithm for planning collision- free paths among polyhedral obstacles,

    T. Lozano-P ´erez and M. Wesley, “An algorithm for planning collision- free paths among polyhedral obstacles,” Communications of the ACM, vol. 22, no. 10, pp. 560–570, 1979

    work page 1979

  20. [20]

    An iterative procedure for the polygonal approximation of plane curves,

    U. Ramer, “An iterative procedure for the polygonal approximation of plane curves,” Computer Graphics and Image Processing , vol. 1, no. 3, pp. 244–256, 1972

    work page 1972

  21. [21]

    Soft constraints and exact penalty functions in model predictive control,

    E. Kerrigan and J. Maciejowski, “Soft constraints and exact penalty functions in model predictive control,” in Proc. UKACC International Conference (Control 2000), 2000, pp. 2319–2327

    work page 2000