Feedrate planning is one of the core features of OpenCN.
It is formulated as an LP (linear program) optimization problem, one of the simplest and best known optimization problems.
Currently we use the coin-or CLP solver.
We discovered some issues :
CLP is quite slow, the execution speed of OpenCN is dominated by CLP
Sometimes CLP fails to find a solution even if the problem is feasible and other solvers find the solution
Sometimes the acceleration profile of the solution shows undesirable oscillations
I’m working on finding a better solution.
In principle MPC (model predictive control) utilizes QP solvers that might perform better.
We sometimes experience “infeasibility” using CLP in the feedrate optimization.
My suspicion :
It is not related to a CLP issue. If CLP finds the problem infeasible, then it really is infeasible.
The reason might be that we enter with an initial speed v0 that is slightly higher than vmax. By “slightly” I mean caused by numerical roundoff errors. Also the initial tangential acceleration a0 might produce a slight violation of the acceleration constraints right at the beginning.
Hi Raoul, I noticed the latest version has add some slack variables. Is it intended to improve the LP solver stability? What is the underlying theory for doing this? Thanks!
I see. It adds the positive constraint of q(u) and the slack variable gives some flexibility to the constraints violation. I’m curious that if it does help to reduce the change of optimization failure. Is there some example to show that the original problem is unfeasible and becomes feasible after adding the slack variable?
Since the beginning of OpenCN we had experimented some issues related to the infeasibility of our LPs.
Here are the steps we implemented to tackle these infeasibilities :
We reduced the PrimalTolerance and DualTolerance of our solver coinor (~1e-6).
We added a small ramp to the acceleration and velocity constraints over the horizon to overcome some numerical errors when the solution of the previous optimization problem is passed to the next one.
( reduction about 0.1% of the desired value )
We imposed a zero speed and zero tangential acceleration at the end of the horizon window. The idea is to build a recursively feasible problem between a real zero-start (ZN) and zero-end (NZ). This mean if solve a first window the next one remain feasible, since imposing zero speed and acceleration as solution of the newly added curve is a valid solution.
Note : This is only true for the first call of the LP.
When an infeasibility arose from a ZN or NZ, we reduce the pseudo-jerk used to compute the hand-written profile until the problem gets feasible.
When we added the jerk constraints to the optimization problem, we lost the recursive feasibility. This might lead to an infeasibility in a non-zero-start / non-zero-stop (NN) window of curves to occur. In this situation, our only room of action is to relax the jerk constraints in order to obtain a feasible solution. We did so by using a slack variable ( only one for all the jerk constraints, it is a bit sub-optimal but it’s more trackable for RT application ). In theory, our formulation forced the slack variable to remain zero when a feasible solution is possible and to be only active if the problem really needs to be relaxed.
Note : That in any case both velocity and acceleration are remain valid.
As summary, our approach is empirical without real solid mathematical basis as justification. However we are now able to process all the different gcodes present in folder ngc_test/full and here is a summary of the results and the parameters used are the one on the master. In most senario the jerk maximum remains below the maximum specified. As comparison, the first release of openCN failed in about half of our scenario
