Library for generating cubic spline trajectories (not interpolation)?

13
votes

A little background. I have a simulation that uses cubic splines for 1D trajectories. In this context, a cubic spline specifies an object's position, velocity, acceleration, and jerk as a function of time.

If you have:

  • initial and final values for position, velocity, acceleration, and time
  • constant-value constraints on the maximum and minimum velocity, acceleration, and jerk

then there is a unique spline. If you don't specify the final time, but instead want the minimum-time trajectory, then there is also a unique spline.

Actually finding these splines can be a royal pain, though. In the case where time is specified, a spline will consist of up to 7 polynomials, and the knots (transition points between polynomials) aren't known ahead of time.

This is not the usual case of fitting a spline to a set of data, it's creating splines from the boundary conditions and some additional constraints. I've read papers where people have used similar arrangements and have had similar needs, but I've never found any libraries (or even source code) that tackles generating splines of this sort. I've written some code that handles most cases, but it isn't terribly robust or fast. I'm not very worried about it being fast, but more robust would be great.

Are there any libraries that can do this available? Open source code, even if not built as a library? C, C++, Java, or Python preferred, but if it's open source other languages would still be useful as a reference.

3
algorithmgeometryspline
I'm afraid you'll have to do it yourself, using some constrained minimization algorithm, or some multi dimensional root finding (depending on the two cases you describe). This is not especially hard to do, but you may greatly benefit from stranger's eyes if you want something robust. Could you tell us more precisely what you implemented ? – Alexandre C.
Can you comment how your approach is different to the usual CAM one? For example in homepages.laas.fr/xbroquer/publications/ICRA10.pdf – Dr. belisarius
Are you still interested in this one? Could you answer the questions and comment on the answers to refine the approach? – Dr. belisarius

3 Answers

1
votes

There is a boost library for C++ that is open source and might get you half-way there.

It has all the basic building blocks you need I think (Legrendre/Laguerre/Hermite polynomials, root finding, etc...), though it comes short of actually calculating splines.

The library documentation is here so you can check for yourself: http://www.boost.org/doc/libs/1_45_0/libs/math/doc/html/index.html

1
votes

The problem with splines is that you have to solve simultaneous linear equations to solve the conditions. If your situation has any more information about some of those derivatives, you may be able to use Piecewise Cubic Hermite Interpolation (PCHIP).

For example, instead of defining that jerk must be zero, you could come up with a different constraint, use PCHIP, and solve your problem greedily. Anyway, it's something to remember even if you can't use it this time.

http://www.mathworks.com/moler/interp.pdf

0
votes

SciPy's interpolation functions might help... Plus you can get the derivatives or integrals of those splines easily... I'm not sure why you say "not interpolation"... It seems to me like that is what you are trying to accomplish.