User Tools

Site Tools

Trace: printer_controller_trajectory_planning

This is an old revision of the document!

Printer Controller Trajectory Planning

There have been numerous attempts to understand and implement trajectory planning. Obviously, solutions were found, else we hadn't printers moving.

What's missing is a more general, mathematically savy approach. Quite some research exists on this topic. Often found only with a high price tag or in university libraries. Also rarely coming with code usable on an embedded system (AVR ATmega, ARM Cortex-M0..M7). Let's collect the nuggets here and show implementations.

Order Types

Not surprising, several orders exist and first to fourth order are in practical use.

First Order Trajectory Planning

That's the most simple case. Turn motors on at the desired velocity and stop them when the target is reached. That's the variant most easy to implement and was in use on very early RepRap printers (Darwin, Sell's Mendel).

Usable speeds were up to about 200 mm/min or 3 mm/s. That's not much, but certainly better than a printer not moving at all. It's still plenty for low speed applications, like e.g. Electrostatic Discharge Machining (EDM).

Second Order Trajectory Planning

Second order means (constant) acceleration. Velocity is increased up to the commanded speed, then kept for a while, then decelerated just to arrive at the target position when also having velocity zero again.

Several approaches are known:

Non-linear acceleration

Moving stepper motors at a certain velocity means to send out pulses after certain delays. A computationally very cheap approach is to simply subtract some value from the previous delay to achieve higher speeds. However, this means non-constant acceleration. Still it's a lot better than no acceleration at all.

AFAIK, GRBL firmware uses such an approach and doing so allows GRBL to achieve rather high step rates. Like some 30'000 steps per second on an 16 MHz ATmega.

Constant Acceleration Calculation Step by Step

At every stepper motor step the delay for the next step is calculated. This is very accurate. There's an article on Embedded and Atmel Application Note AVR446 which describe the required math.

This math requires some computations, especially a division. Divisions are expensive on limited hardware like an ATmega, so achievable step rate is limited, too. Such an approach was used by earlier versions of Teacup Firmware and is still used by Marlin firmware. Ignoring quirks like quadstepping, achievable step rate on an 16 MHz ATmega is some 10'000 to 12'000 steps per second.

Step Based Acceleration Updates at Discrete Time Intervals

Instead of doing this computationally intensive acceleration calculation after every step, it's done every other millisecond (or at some other time interval), only. The calculation is still done based on motor steps, so it's positionally still perfectly accurate. Velocities obviously suffer in precision somewhat, but at 500 velocity updates per second that's not noticeable.

This is what Teacup firmware uses when compiled with ACCELERATION_REPRAP. Achievable step rate on an 16 MHz ATmega is some 40'000 steps per second. Faster hardware, like an ARM Cortex-M4 has been demonstrated to exceed 500'000 steps per second.

Velocity Calculation at Discrete Time Intervals

This is the strategy typically used on servo driven robots. After each time interval, the requested position and/or velocity is calculated and fed into the servo control loop. A well known implementation is LinuxCNC. LinuxCNC works even with stepper motors, they implemented kind of a fake feedback, closing the control loop.

Doing this with stepper motors and without feedback loop is a bit more tricky. There is no error correction, so steps have to be reliably accurate before they're sent. This is topic of current investigation:

There is a great research paper by Paul Lambrechts which gives valuable hints. The paper is about fourth order trajectory planning. On how to translate this into second order planning is described in the above Github Issue:

Integrator chain pictured on page 26.

Integrator chain pictured on page 26.

To the left is a “generator”, which outputs 1, 0 or -1. This “signal” is stuffed into the first integrator at discrete time steps, e.g. every 2 milliseconds. The output of that integrator is the integral of the original signal, which happens to be jerk.

This jerk signal (now any value in the range {-1, 1}) is put into another integrator, which integrates up again.This gives acceleration. Yet another integrator in the chain gives velocity. The last integrator gives position, and that integrator happens to be not some mathematical formula, but our stepper motor.

The non-trivial part here is to calculate the original signal. There's a matlab script at the end of the paper to calculate the signal in multiples of an adjustable time step. This script even takes error correction into account. But that's not my point here.

My point is, if two of these integrators get chopped off, we have second order acceleration, which is what Teacup currently does. Then there's a simple acceleration signal: 1 = acceleration, 0 = keep speed, -1 = decelerate. When to give which signal is easy to calculate.

Now, “forward Euler discrete time integrators” sounds impressive, doesn't it? Impressive name, simple math :-) It's as simple as velocity = velocity + signal, done at each time step. “At each time step” = once in dda_clock().

The magnitude of the signal is simple, too: it's the speed change happening from one time step to another: signal = dv = acceleration * 2ms. A constant value.

To sum up: instead of doing complex math calculations, one can simply add up velocities at each time step. Only for the adventurer: third order acceleration (constant jerk) would mean two such additions at runtime, fourth order acceleration three such additions. In any case: all the complex math is done at preparation time.

Third Order Trajectory Planning

Third order means, acceleration isn't on/off, but gently built up, too. This means the required acceleration force also builds up instead of appearing instantly, matching actual physics much closer.

There is a research paper from Bath University briefly describing the most important aspects. This paper also describes how one can overlap movements to avoid full stops between adjectant movements.

Third order is also described well in the Paul Lambrechts paper.

Fourth Order Trajectory Planning

See previous paragraph, just one additional integration. Preparation math becomes quite challenging already. Probably too much to be done on an ATmega in reasonable time. Still noticeable improvements in movement smoothness.

Plans for this Wiki Page

  • One dedicated page for each order of planning.
  • Graphs showing what these orders mean.
  • Each page describing preparation math, per-time-step math and per-motor-step math.
  • Code examples in C, ideally copied from Teacup firmware (or ready for putting it into there).
printer_controller_trajectory_planning.1470340779.txt.gz · Last modified: 2018/05/27 16:10 (external edit)