Discretization scheme for feedrate planning

In the paper Linear programming feedrate optimization - Adaptive path sampling and feedrate override, it is mentioned that if we use the Greville abscissae as the evaluation sampling points, the optimization will be more stable since it results in a sparse band M matrix. Current code uses a sinewave function to discretize the path. Maybe it is worth having a try.

Some thoughts (without actually answering your question) :

The original feedrate planning is an optimization problem involving an unknown function q(u) and a bunch of constraints that must hold for every value of u in the interval [0, 1]. This original problem is also known as a “variational” problem, i.e. an optimization problem in infinite dimensions.

In order to convert it to a finite optimization proble, two things need to be done.

  1. Choose a finite basis for the unknown function. The coefficients become the decision variables. In the case of a B-spline basis, this amounts to choosing the degree and the number of knots as well as the knot distribution.

  2. In order to have a finite number of constraints, the constraints will only be formulated on a grid of u values between 0 and 1. The danger is that the constraints might be violated between the grid points if the grid is too coarse. One way to avoid this, is to use “spline relaxation”, refer to publications of KU Leuven, but it induces conservatism and we did not use it.

Now, the number of knots for the parametrization of q(u) and the number of grid points for the discretization of the constraints should be in a given ratio. Computation time becomes excessively high if the discretization scheme is not carefully chosen.
On the other hand, a “too coarse” discretization scheme has the risk of leading to a suboptimal cost function, maybe of violating constraints between the grid points, or of showing unwanted oscillations.

This is the big picture.

It is not clear for me if “Greville abscissae” for the choice of grid points would improve things.

Thanks Raoul!

In another thread Feedrate planning using CLP as LP solver. It was mentioned that sometimes CLP failed to find a solution. Maybe we could try with a different grid points like “Greville abscissae” to see if it has an improved result to get a solution. Or do you have a failed example, then I can try it :grinning:

I have a sneaking suspicion why CLP sometimes fails.
I will try to find the corresponding gitlab issue and will answer in the other thread.

1 Like