PaperlayerView exact revision on arXiv

Source-linked AI summary

DynoFluxBench: Benchmarking Kinodynamic Space-Time Planners in Dynamic Environments

Franz Queißner, Andreas Orthey, Wolfgang Hönig

arXiv:2609.18549v1cs.RO

TL;DR

Kinodynamic feasibility and moving-obstacle avoidance have largely been addressed separately, leaving a gap for general systems with unknown, unbounded arrival time. DynoFluxBench and three planners combine these aspects for evaluation. ST-Db-RRT solves every dynamic instance and reaches a first solution up to 90× faster than optimization-free planners, while the other planners remain valuable where optimization struggles.

  • Problem

    Existing planners do not combine general kinodynamic planning with dynamic obstacles, no steering function, and unknown, unbounded arrival time.

    Source: §I · p. 1, C. Kinodynamic Planning in Dynamic… · p. 3

  • Method

    DynoFluxBench evaluates three planners that combine kinodynamic and space-time methods: ST-Db-RRT, ST-GBRRT, and KIST.

    Source: §I · pp. 1–2

  • Results

    ST-Db-RRT solves every dynamic instance and reaches a first solution up to 90× faster than optimization-free planners, while ST-GBRRT and KIST have cost advantages in some settings.

    Source: §VIII · pp. 7–8

  • Takeaways & Limitations

    Optimization-free planning remains valuable on higher-dimensional systems and where narrow feasible arrival windows make trajectory optimization struggle.

    Source: §VIII · p. 8

Abstract

from arXiv · show

Robots that leave structured, static environments must plan motions that are kinodynamically feasible and safe among moving obstacles. However, there are no dedicated benchmark frameworks that combine both aspects. To overcome this, we present DynoFluxBench, a framework to compare kinodynamic planners in known, dynamic environments with unbounded arrival time. To demonstrate its utility and establish strong baselines, we develop three dedicated planners, named ST-Db-RRT, ST-GBRRT, and KIST, that fuse kinodynamic and space-time methods, covering different kinodynamic search paradigms: ST-Db-RRT expands with randomly selected discontinuity-bounded motion primitives using trajectory optimization, whereas KIST and ST-GBRRT maintain a kinodynamically feasible tree with different heuristic guidance. We analyze the probabilistic completeness guarantees of those new planners in dynamic environments. Finally, we evaluate ST-Db-RRT, ST-GBRRT, and KIST using DynoFluxBench, showing that ST-Db-RRT reaches a first solution up to 32 times faster, while KIST and ST-GBRRT remain valuable where trajectory optimization is fragile. Videos and further analysis can be found at https://dynofluxbench.github.io/dynofluxbench/.

I. INTRODUCTION

Kinodynamic planning and planning around known moving obstacles have largely been studied separately, leaving a gap for general dynamical systems with unbounded arrival time. The paper introduces DynoFluxBench and three planners to evaluate this combined problem.

I. INTRODUCTION

  • The planners target dynamic environments without requiring a steering function or known arrival time.Source: §I · p. 1
  • The analysis finds GBRRT probabilistic completeness is preserved, whereas Db-RRT resolution completeness is preserved only with bounded time.Source: §I · pp. 1–2
  • The benchmark evaluates kinodynamic space-time planners on 25 scenarios involving four dynamical systems.Source: §I · pp. 1–2
  • ST-Db-RRT and ST-GBRRT extend iDb-RRT and GBRRT to space-time, while KIST combines aspects of both planners.Source: §I · p. 2

II. RELATED WORK

Prior work treats dynamic obstacles and kinodynamic constraints largely in separate planner families. Their intersection remains limited by system-specific assumptions or state-space discretization.

A. Planning in Dynamic Environments

B. Kinodynamic Motion Planning

  • Kinodynamic sampling methods handle differential constraints, but exact rewiring can require an expensive or unsolvable boundary-value problem for general systems.Source: B. Kinodynamic Motion Planning · p. 2
  • Trajectory optimization handles complex constraints but depends on its initial guess and can suffer local minima; iDb-RRT instead uses bounded-discontinuity primitives repaired by optimization, [29],,.Source: B. Kinodynamic Motion Planning · p. 2

C. Kinodynamic Planning in Dynamic Environments

Existing work at the intersection of kinodynamic planning and dynamic environments is restricted to particular system classes or state-space discretizations. The paper frames planning as finding a collision-free, controlled path through space-time to a goal region.

C. Kinodynamic Planning in Dynamic Environments

III. PROBLEM STATEMENT

  • A solution is a state and control sequence from the start to the goal region that remains collision-free at every time step, with cost K·Δt.Source: §III · p. 3

IV. KINODYNAMIC SPACE-TIME PRIMITIVES

The planner combines space-time search with kinodynamic motion primitives. Conditional sampling and progressive goal expansion address unbounded time, while a time-consistent pseudometric and selectable primitive policies guide search.

IV. KINODYNAMIC SPACE-TIME PRIMITIVES

  • The space-time extension combines goal-region expansion and distance computation with discontinuity-bounded motion primitives for kinodynamic systems.Source: §IV · p. 3

A. Goal Region Expansion

  • Conditional sampling restricts sampled times to those reachable from the start, while progressive goal expansion extends time bounds until a first solution is found.Source: A. Goal Region Expansion · p. 3

B. Distance Computation

  • The space-time pseudometric combines configuration distance and weighted time difference, assigning infinite distance when time order or velocity limits make a transition infeasible.Source: B. Distance Computation · p. 3

C. Kinodynamic Expansion Modes

  • Motion primitives are feasible state-action sequences whose start-state mismatch is bounded by δ; selection policies can apply bounded jumps or forward-propagate actions without discontinuity.Source: C. Kinodynamic Expansion Modes · p. 3

V. KINODYNAMIC SPACE-TIME PLANNERS

The section introduces three planners that generalize Db-RRT and GBRRT for kinodynamic planning in dynamic environments.

V. KINODYNAMIC SPACE-TIME PLANNERS

  • The section motivates three novel planners by generalizing Db-RRT and GBRRT.The passage introduces the planners but does not describe their individual mechanisms.Source: §V · p. 4

A. Naive Db-RRT for Dynamic Environments

Naive Db-RRT adds time-dependent collision checks while tracking node time as cost, but is not probabilistically complete. ST-Db-RRT plans in space-time and repairs its discontinuity-bounded solution with trajectory optimization.

A. Naive Db-RRT for Dynamic Environments

  • Naive Db-RRT tracks node time through time cost and uses it for dynamic collision checks, but is not probabilistically complete.Motion-primitive discontinuity durations are accounted for by the lower time-bound function t(q1, q2).Source: A. Naive Db-RRT for Dynamic Environments · p. 4

B. Planner 1: ST-Db-RRT

  • ST-Db-RRT samples in space-time with adaptive goal expansion and expands both trees using Db-RRT’s fast randomized mechanism.It connects the trees in BEST mode and extracts a discontinuity-bounded solution once connected.Source: B. Planner 1: ST-Db-RRT · p. 4
  • ST-Db-RRT repairs its discontinuity-bounded solution with DDP trajectory optimization, enforcing constraints such as collision avoidance through an iterative cost term.Time is passed to the cost function for collision checks, not treated as a decision variable; the state dynamics follow qk+1 = step(qk, uk).Source: B. Planner 1: ST-Db-RRT · p. 4

C. Planner 2: ST-GBRRT

This section describes ST-GBRRT and KIST and analyzes completeness guarantees for the planners in dynamic environments.

C. Planner 2: ST-GBRRT

  • ST-GBRRT guides a feasible forward tree with a reverse-tree cost-to-go heuristic, avoiding tree connection and a boundary value problem.Its reverse tree uses fast δ-discontinuity-bounded primitives, while the forward tree uses feasible action rollouts and needs no completion policy or trajectory optimization.Source: C. Planner 2: ST-GBRRT · p. 4

D. Planner 3: KIST

  • KIST combines space-time sampling and Db-RRT expansion with feasible forward action rollouts, using the reverse tree as a heuristic rather than connecting the trees.After approximate connection, a greedy A*-like policy guides forward expansion toward the goal; KIST also performs random action rollouts.Source: D. Planner 3: KIST · p. 4

VI. THEORETICAL ANALYSIS

  • Naive Db-RRT is not probabilistically complete because duplicate pruning can suppress a later visit to a state needed at a specific time.Space-time distinguishes (q, t0) from (q, t1), allowing the planner to represent arriving at the same configuration later.Source: §VI · p. 5
  • ST-Db-RRT’s resolution-completeness argument requires primitive generation to assign positive measure to time-suboptimal motions of varied duration.Random forward propagation with randomized duration satisfies this condition, yielding resolution completeness with respect to the generated primitives.Source: §VI · p. 5
  • ST-Db-RRT is not complete in unbounded time because it keeps searching and cannot report that no solution exists.A known or estimated upper bound on time could fix this limitation.Source: §VI · p. 5
  • ST-GBRRT retains probabilistic completeness through random action rollouts and positive-probability sampling of a feasible goal arrival time.KIST restores probabilistic completeness with random forward action rollouts and progressive goal-region expansion, including for unbounded goal time.Source: §VI · p. 5

VII. BENCHMARK RESULTS

The benchmark section describes the evaluation setup for Naive Db-RRT and the three space-time planners across environments and dynamical systems.

VII. BENCHMARK RESULTS

  • Each planner run is limited to 180 seconds on one CPU core, and reported metrics are solution cost, time to first solution, and success rate.Results are averages over 20 runs per algorithm.Source: §VII · p. 5
  • The benchmark suite contains 25 instances across 15 environments and four dynamical systems.The environments include 10 newly designed layouts and four dynamic adaptations of static Dynobench environments.Source: §VII · p. 5
  • The four systems are first- and second-order unicycles, a car with trailer, and a planar rotor.The car-with-trailer represents a driving system, and the planar rotor an underactuated flying system.Source: §VII · p. 5

A. Planner Parameter Study

The study tunes planner hyperparameters, comparing motion-primitive choices and selecting values for primitive density, discontinuity, sampling, and time weighting.

A. Planner Parameter Study

B. Planner Comparisons

Across the planner comparisons, ST-Db-RRT finds first solutions fastest on most instances, while success and solution-cost results vary by planner and environment.

1) Naive Db-RRT vs ST-Db-RRT:

  • Db-RRT solves 19 of 25 instances and reaches a first solution within t1 = 0.6 s on 17 of 18 solved unicycle and car instances.In Bugtrap, its t1 = 0.6 s versus ST-Db-RRT's t1 = 32.3 s.Source: 1) Naive Db-RRT vs ST-Db-RRT · p. 7
  • In Wait, Db-RRT fails while ST-Db-RRT reaches sr = 1.0 for the 1st Order Unicycle and sr = 0.7 for the 2nd Order Unicycle.Outside Wait, success rates are close, and Db-RRT matches or exceeds ST-Db-RRT on all five Planar Rotor instances.Source: 1) Naive Db-RRT vs ST-Db-RRT · p. 7
  • ST-Db-RRT has lower cost on only 9 of 23 jointly solved instances, all unicycle cases; Db-RRT has lower cost on all nine trailer and rotor cases.On the rotor, Db-RRT's cost advantage ranges from 26% to 107%.Source: 1) Naive Db-RRT vs ST-Db-RRT · p. 7

2) Space-Time Planner Comparison:

  • ST-Db-RRT succeeds on 21 of 25 instances and alone solves every instance at least once; KIST succeeds on 20 of 25, while ST-GBRRT fails 11 of 25.Source: 2) Space-Time Planner Comparison · p. 7
  • ST-Db-RRT is fastest on 19 of 25 instances and stays below t1 = 4 s on 17 of 20 unicycle and car instances.On the 1st Order Unicycle Wait, KIST takes t1 = 32.2 s against ST-Db-RRT's t1 = 2.0 s.Source: 2) Space-Time Planner Comparison · p. 7
  • ST-GBRRT reaches the lowest cost on all 14 instances it solves; KIST is cheapest on four of five Planar Rotor instances.ST-Db-RRT's cost is within 10% of the best on all but one unicycle instance, but is 29% to 123% above best on the Planar Rotor.Source: 2) Space-Time Planner Comparison · p. 7

VIII. CONCLUSION

DynoFluxBench evaluates kinodynamic space-time planners across dynamic scenarios and four dynamical systems. ST-Db-RRT leads on coverage and first-solution speed, while planner advantages vary by cost and scenario; several extensions remain open.

VIII. CONCLUSION

  • ST-Db-RRT is resolution-complete, solves every dynamic instance, and reaches its first solution up to 90× faster than optimization-free planners.The evaluation attributes its coverage and runtime under a fixed time budget to deferring feasibility to a single repair step.Source: §VIII · pp. 7–8
  • ST-GBRRT converges to the lowest cost on every instance its slower search can cover.Its cost advantage does not extend to instances it cannot cover.Source: §VIII · p. 8
  • KIST is both the most reliable and cheapest planner on the Planar Rotor.Source: §VIII · p. 8
  • The results invert on higher-dimensional systems and narrow feasible arrival windows, where optimization-free planning remains valuable when optimization struggles.The Elevator and moving-ceiling instances illustrate the narrow-window cases.Source: §VIII · p. 8
  • Proposed extensions include better arrival-time estimates, space-time kinodynamic rewiring, and variable-time trajectory optimization.These could improve late-window reliability, recover ST-RRT*'s asymptotic optimality, and improve solution quality, respectively.Source: §VIII · p. 8

Related papers

Loading 2609.18549v1…