PaperlayerView exact revision on arXiv

Source-linked AI summary

Jerk-limited Real-time Trajectory Generation with Arbitrary Target States

Lars Berscheid, Torsten Kröger

arXiv:2105.04830v2cs.RO

TL;DR

Robots need online trajectories that respond to new inputs while respecting jerk and other kinematic limits. Ruckig generates time-optimal, synchronized multi-DoF trajectories to complete target states, including nonzero target acceleration; its trajectories matched Reflexxes Type IV within the reported test-suite tolerance and it supports real-time cycles as low as 1 ms.

  • Problem

    Online trajectory generation commonly uses velocity and acceleration constraints, while jerk constraints are desirable to reduce mechanical stress, wear, and lifetime cost.

    Source: §I · p. 1

  • Method

    Ruckig computes time-optimal trajectories to complete target states under velocity, acceleration, and jerk limits, synchronizing profiles across DoFs.

    Source: §I · p. 1, §IV · pp. 2–3

  • Results

    For the tested inputs with af = 0, Ruckig and Reflexxes Type IV trajectory durations differed by |∆t| < 10−6, and Ruckig supports control cycles as low as 1 ms.

    Source: A. Robustness · p. 6, §VI · p. 8

  • Takeaways & Limitations

    Nonzero target accelerations can better approximate curves, circles, or splines and result in smoother motions than zero-velocity waypoints.

    Source: §VI · p. 8

Abstract

from arXiv · show

We present Ruckig, an algorithm for Online Trajectory Generation (OTG) respecting third-order constraints and complete kinematic target states. Given any initial state of a system with multiple Degrees of Freedom (DoFs), Ruckig calculates a time-optimal trajectory to an arbitrary target state defined by its position, velocity, and acceleration limited by velocity, acceleration, and jerk constraints. The proposed algorithm and implementation allows three contributions: (1) To the best of our knowledge, we derive the first time-optimal OTG algorithm for arbitrary, multi-dimensional target states, in particular including non-zero target acceleration. (2) This is the first open-source prototype of time-optimal OTG with limited jerk and complete time synchronization for multiple DoFs. (3) Ruckig allows for directional velocity and acceleration limits, enabling robots to better use their dynamical resources. We evaluate the robustness and real-time capability of the proposed algorithm on a test suite with over 1,000,000,000 random trajectories as well as in real-world applications.

I. INTRODUCTION

Robots need online trajectories that can respond to new sensor input while respecting dynamic limits; jerk constraints are especially relevant because acceleration discontinuities can trigger robot-controller termination. Ruckig targets this setting with complete kinematic waypoints, jerk limits, and directional velocity and acceleration limits.

I. INTRODUCTION

  • Jerk limits matter because acceleration discontinuities can cause industrial robot controllers to terminate motion.The introduction notes that modern robots, including Franka Emika systems, monitor jerk internally.Source: §I · p. 1
  • Ruckig supports complete target kinematic states, including acceleration, and directional velocity and acceleration limits for multi-DoF OTG.The paper presents these capabilities as improving practical usability in dynamic tasks and helping exploit robot dynamics.Source: §I · p. 1

II. RELATED WORK

  • Prior jerk-constrained OTG included single-DoF methods and multi-DoF methods with zero initial acceleration, while other work handled arbitrary initial states for position targets.Ruckig is presented as the first Type V and first open-source Type IV implementation.Source: §II · p. 2
  • Related approaches include complete third-order-state planning without direct velocity, acceleration, or jerk limits, and jerk-constrained OTG without complete time synchronization for arbitrary states.Source: §II · p. 2

III. PROBLEM DEFINITION

The problem is to find a time-optimal trajectory for a multi-DoF kinematic system between complete initial and target states. The trajectory must obey velocity, acceleration, and jerk constraints, with directional velocity and acceleration limits and symmetric jerk limits.

III. PROBLEM DEFINITION

  • Each DoF state comprises position and its derivatives through velocity, acceleration, and jerk; the objective is a time-optimal trajectory from initial to target state.Source: §III · p. 2
  • The trajectory must satisfy velocity, acceleration, and jerk constraints throughout its duration for every DoF.Source: §III · p. 2
  • Initial and target states may have nonzero derivatives; jerk limits are symmetric, while velocity and acceleration limits may be directional.Not every kinematic target state is physically possible: constrained jerk requires a minimum velocity interval to reach a target acceleration.Source: §III · p. 2

IV. ALGORITHM

Ruckig constructs time-optimal, time-synchronized trajectories by finding valid extremal profiles for each DoF and selecting the fastest duration not blocked by any DoF. An optional braking pre-trajectory first handles initial states that exceed or will inevitably exceed kinematic limits.

A. Brake Pre-trajectory

  • An optional brake pre-trajectory is calculated when the initial state exceeds or will inevitably exceed velocity or acceleration limits.This step prioritizes recovery to a safe kinematic state before the remaining trajectory is generated.Source: §IV · p. 2

IV. ALGORITHM

  • For each DoF, the algorithm finds valid extremal profiles, then selects the fastest duration that is not blocked by any DoF and synchronizes every profile to it.The fastest valid profile for a DoF defines its minimum duration; longer durations may be unavailable because of blocked intervals.Source: §IV · pp. 2–3
  • A time-optimal trajectory has a limiting DoF that uses its full dynamical resources, with jerk switching among −jmax, 0, and jmax.The algorithm represents profiles as constant-jerk steps with nonnegative durations.Source: §IV · p. 3

A. Brake Pre-trajectory

  • The braking step works in the velocity domain and finds the fastest profile to return below the relevant limits.Its decision tree depends on initial velocity and acceleration, plus the directional velocity and acceleration limits.Source: A. Brake Pre-trajectory · p. 3

B. Step 1: Extremal Times

The algorithm constructs and tests extremal jerk profiles to find each DoF’s fastest feasible trajectory. These profiles have a restricted sequence of limit contacts and constant-jerk steps.

B. Step 1: Extremal Times

  • An extremal profile reaches at most ACC0, VEL, and ACC1, with no more than two acceleration limits or one velocity limit.ACC0 and ACC1 are acceleration limits, while VEL is a velocity limit.Source: B. Step 1: Extremal Times · p. 3
  • The profile uses up to seven constant-jerk steps; symmetry reduces the four unique patterns to ↑↓↓↑ and ↑↓↑↓.Redundant steps have zero duration.Source: B. Step 1: Extremal Times · pp. 3–4
  • Profile types map the initial and target states and kinematic limits to step times, with some cases requiring roots of polynomials up to sixth order.A safe Newton method with bisection fallback bounds iterations to support real-time capability.Source: B. Step 1: Extremal Times · p. 4
  • The algorithm calculates times for 24 possible profile types, then rejects profiles with negative steps or violations of acceleration or velocity limits.Acceleration limits are checked at the acceleration peaks; velocity limits are checked when acceleration is zero.Source: B. Step 1: Extremal Times · p. 4
  • Among valid profiles, the shortest duration determines the fastest profile for each DoF.The duration of that profile is denoted Ti,min.Source: B. Step 1: Extremal Times · p. 4

C. Blocked Duration Intervals

Durations above a DoF’s fastest profile are not always feasible: blocked intervals lie between neighboring extremal profiles, with up to two such intervals for a third-order target state.

C. Blocked Duration Intervals

  • A DoF can have up to two blocked duration intervals, each bounded by neighboring extremal profiles.Each valid extremal profile corresponds to an interval boundary.Source: C. Blocked Duration Intervals · pp. 4–5
  • For the example with p0 = −0.75, pf = 0.75, and v0 = vf = 1.0, no trajectory is possible below tmin = 1.35 or for t ∈ (2.0, 2.6).Source: Figure 3 · p. 5
  • The possible maximum number of blocked intervals depends on whether the target velocity and acceleration are non-zero, as in Kröger et al..Source: C. Blocked Duration Intervals · pp. 4–5
  • The number of extremal profiles determines the gaps: one profile gives no blocked interval, three give one, and five give two.The intervals lie between the second and third profiles, and, when there are two, between the fourth and fifth.Source: C. Blocked Duration Intervals · p. 5

D. Minimum Duration

The minimum shared duration is the earliest candidate that is unblocked for every DoF, with any braking pre-trajectory duration included.

D. Minimum Duration

  • The final duration Tf is the first candidate duration that is not blocked in any DoF.Candidates include each DoF’s time-optimal duration and the right boundaries of its blocked intervals.Source: D. Minimum Duration · p. 5
  • The algorithm adds any braking pre-trajectory duration, then sorts and evaluates up to 3N candidate durations in ascending order.Source: D. Minimum Duration · p. 5
  • The DoF associated with the resulting minimum duration is called the limiting DoF.The figure distinguishes blocked intervals, candidate minima, possible braking pre-trajectories, and the final minimum by color.Source: D. Minimum Duration · p. 5, Figure 4 · p. 5

E. Step 2: Time Synchronization

Given the shared duration, Step 2 finds a feasible trajectory for each DoF, reusing the limiting DoF’s profile where possible. It adjusts profile duration through a velocity plateau or reduced jerk.

E. Step 2: Time Synchronization

F. New State

Ruckig computes the state at any time by integrating from the last completed step, applying the same approach to any brake pre-trajectory. After initial calculation, the state is typically updated each control cycle; the full trajectory is recalculated only when input parameters change.

F. New State

  • At time t, Ruckig integrates from the last step boundary to compute the state, applying the same procedure to any brake pre-trajectory.The final profile is integrated from its stored position, velocity, and acceleration at the selected step.Source: F. New State · p. 6
  • The full trajectory is recalculated if and only if input parameters change; otherwise, only the new state is integrated each control cycle.Source: F. New State · p. 6

V. EXPERIMENTAL RESULTS

The experiments assess Ruckig’s robustness and calculation performance, including comparison with Reflexxes Type IV for zero target acceleration. They test more than one billion random trajectories and identify a numerical duration boundary for the reported robustness.

V. EXPERIMENTAL RESULTS

  • Ruckig is implemented as a C++17 library without further dependencies, with generated equations and a Python wrapper for offline trajectory generation.The paper focuses on the complete position-control interface.Source: §V · p. 6

A. Robustness

  • Over 1,000,000,000 random trajectories with up to 7 DoFs were generated to evaluate robustness and numerical stability.Cases violating the target acceleration requirement are skipped, and inputs are drawn from normal and gamma distributions with a minimum limit of 5 × 10−2.Source: A. Robustness · p. 6
  • Integration error propagates as ∆p = T^2∆a, making Ruckig sensitive to long trajectory durations.The duration bound follows from double precision for acceleration and the required position accuracy.Source: A. Robustness · p. 6
  • Ruckig achieves 100% robustness when trajectories above the numerical duration limit are ignored; in SI units, that limit is around 16 minutes.The input parameters can be scaled across distance units without loss of generality.Source: A. Robustness · p. 6
  • |∆t| < 10−6 for every tested trajectory with af = 0 separates Ruckig and Reflexxes Type IV trajectory durations.The authors present this agreement as supporting time-optimality.Source: A. Robustness · p. 6

B. Calculation Duration

Ruckig’s calculation performance scales near-linearly with the number of DoFs and supports short robotic control cycles. The paper also demonstrates online reaction to a safety violation using directional velocity limits.

B. Calculation Duration

  • Ruckig is tested on an Intel i7-8700K using one thread, against a benchmark distribution reused from the robustness tests.Typical robotic control cycles range from 0.5 ms to 5 ms.Source: B. Calculation Duration · p. 6
  • Average calculation performance scales near-linearly with DoF count; on the tested hardware, N = 82 is the smallest DoF count that misses a 1 ms cycle in the worst case.Fig. 5 shows calculation performance depending on DoF count; Table III reports mean and worst performance for 7 DoFs.Source: Figure 5 · p. 6, B. Calculation Duration · pp. 6–7, Table III · p. 6

C. Real-world Experiments

  • Ruckig is integrated into the 7-DoF Franka Emika Panda controller, where constrained jerk is required and the control cycle is 1 ms.Source: C. Real-world Experiments · p. 7

1) Online Reaction to Sensor Input:

2) Offline Trajectory Planning:

The offline planning example uses non-zero target acceleration to coordinate a jerk-limited robot with an object, while the discussion connects such waypoints to smoother path approximations. Ruckig also reports a simpler implementation and support for complete target states and multiple DoFs.

2) Offline Trajectory Planning:

  • The offline task accelerates an object as quickly as possible without impact, using maximum robot acceleration at contact before the robot decelerates and returns to its origin.The robot has a jerk constraint, while the object does not; the illustrated phases include contact at T1 and target velocity at Tv.Source: 2) Offline Trajectory Planning · p. 7, Figure 7 · p. 8

VI. DISCUSSION AND OUTLOOK

  • Ruckig handles non-zero target accelerations under velocity, acceleration, and jerk constraints, and the implementation is an open-source C++ library.The conclusion describes it as real-time capable for control cycles as low as 1 ms.Source: §VI · p. 8
  • Ruckig’s relevant code base has around 2,800 lines versus 23,000 for Reflexxes Type IV, and it avoids decision trees for matching profiles and blocked intervals [7, 8].The paper reports that Ruckig calculates valid extremal profiles first, then derives matching profiles and blocked intervals.Source: §VI · p. 8
  • Non-zero target-acceleration waypoints can better approximate curves, circles, or splines, whereas zero-velocity waypoints produce constant-velocity plateaus.The authors identify bridging OTG and path-following time-parametrization as future work.Source: §VI · p. 8

Related papers

Loading 2105.04830v2…