linuxcnc scurve motion planner

Hi,

For information.
Here is a patch manual. It's included in the repository now.
patch manual

Hi Grothus,

always impressive how fast you make progress here.
Did you have a closer look at the problem you called "overfitting"? It looks not like classical overfitting (this usually descibes if a fit follows the data much to closely and therefore follows statiscal fluctuations instead of the desired data trend).
In your case it just found a local minimum during fitting instead of the global minimum. Doing a 360 or creating this sort of step in the corner is a viable solution that is quite smooth etc. it is just not the solution we want.
One possibillity to avoid this would be to somehow create a better initial guess before the fitting starts. This could also reduce the iterations/time needed for fitting. Another possibillity might be to use a different solver.

Best regards,
Fabian

Hi Fabian.

In the mean time i experimented with clothoid used for motion. This includes 2 attached clothoids for example.
Now the problem is not the ceres solver, the iterations, or the initial guess value. All these are ok.
It takes about ~12 iterations to fit the clothoid.

There are certain gcode files that have very short segment attached to longer segments under 90 degree angle.
Then the trim algo trims both segments given the P value. But the very short segment is trimmed less then the longer segment.
The clothoid result is valid, however it path can be into the workpiece.

Soon i will show a picture how this looks like. I think the solution lies in even trimming to both segments in some cases, or in all cases.
The solution is therefore quite simple.



 

Fabian,
Yes, I agree that overfitting doesn't exactly describe what is happening.

I was meaning to post some additional info I found on this. It's one of Raph Levien's blog post on fitting cubic Bézier curves, (specifically in the section on the solutions for quartic polynominals):
raphlinus.github.io/curves/2021/03/11/bezier-fitting.html

My understanding is that in his case, the degree of the curve (in this example quartic) and the fact that there are two parameters (x-moment and signed area) leads to four minimal solutions that the solver could converge to (not infinite solutions, luckily!). I believe that in Raph's case, three of these will be local minima and only one will be the global minimum, so we cannot be certain of converging to the global minimum if we start at a random position in the parameter space, as you said.

Raph says that one of these solutions (when optimising for x-moment and signed area) may contain a loop. This is a valid solution to these parameters because the area inside the loop has the opposite sign to the outside, so the signed area is still minimised.

Raph says that you can generally reject this solution as the arm length is longer than the others. But my understanding is that you can only do this by calculating multiple solutions and rejecting the one with the extreme arm length. You can only do this if you obtain at least two solutions, and even then both may have issues.

What might be happening is that you're regularly converging to a non-global minimum, but normally it's so similar to the global minimum that it isn't evident in the result. It's only when you converge to the solution with the extreme arm length that you notice an issue.

Grotius,
I think your method of fixing this by applying a tiny offset worked because it meant that the the loop was no longer complete so its signed area was a lot larger. Although likewise, adding this offset could technically break a curve which would have worked without it? But that's most likely an edge case.

Also, slightly off-topic, but there might also be instances where this loop with the extreme arm length is the solution the user intended. For example, the intended path did have this loop, but under-sampling in the CAM software means that points are missing which should explicitly indicate the presence of the loop. But since this information is missing, it's probably better to treat this as a bug, and reaffirm that the trajectory planner may choose a solution which doesn't match the path you intended. The way to get around this is to increase your sampling frequency in your CAM software.

Back on topic, the way I see it is that the most rigorous way to solve this problem is to start from enough locations in the parameter space that you obtain all (or some) of the local minima, meaning you can be certain of having found the global minimum (or be sure enough of being close to it). But this is computationally expensive and harder to predict how long it will take to return its output.

So it's probably better to find shortcuts which make you more certain that if you converge to a single value, it's good enough even if not the global minimum. I think the idea you mentioned of initially fitting lower-order curves should help with this.
It also seems that using the gradient descent method along with the appropriate number of parameters will increase this probability of you finding the global minimum.
But I understand that some of these solutions are antagonistic to making the solver work fast, even if it is in a separate thread.

I also think that finding all solutions and picking the best might be quite complicated and also computationally expensive. I hope starting with a slightly better initial guess that's closer to the desired global minimum will get us there already.
@Grotius what are currently the starting values for the fit? I assume the boundary conditions from the two endpoints for curvature and torsion. Maybe we can find a good set of vlues for the other parameters. Maybe something that is close to a simple arc connecting the points or something similar.

@DauntlessA

I think your method of fixing this by applying a tiny offset worked because it meant that the the loop was no longer complete so its signed area was a lot larger. Although likewise, adding this offset could technically break a curve which would have worked without it?

The offset is not breaking the curve, and the curve is valid without this offset.
The 1e-12 offset was made to get the curve out off a singularity.
The 4-clothoid constrain formula has this result in rare cases where local clothoid plane alignes with global world plane.

We have input xy angle, input z angle for the clothoid fit.

The abstract could also use vector rotation as input, wich can be used to set the
torsion in and out rotations. Technically you can create clothoid helixes using this torsion turn value. But the abstract does not
use this oppertunity.

@Arciera,
Thanks for your contribution!