Implement a new algorithm in sketch solver

Here's the place for discussion related to coding in FreeCAD, C++ or Python. Design, interfaces and structures.
Forum rules
Be nice to others! Respect the FreeCAD code of conduct!
abdullah
Veteran
Posts: 4935
Joined: Sun May 04, 2014 3:16 pm
Contact:

Re: Implement a new algorithm in sketch solver

Post by abdullah »

_Nemo wrote: Thu Jun 01, 2023 1:48 am Could you please provide me with a few issues in the bug tracker related to diagnostic algorithms? Or could you advise me on how to find such issues myself? I need them as test cases.
"GCS" Label in issues is generally a good filter:
https://github.com/FreeCAD/FreeCAD/issu ... abel%3AGCS

Here you have all kind of issues with the solver. So no specific to diagnosis. You will have to do some classifying work. Also, bear in mind that they are generally drafted from the perspective of the user. The root cause may be very different from what it may appear from the description.

If you want to produce functional tests from sketches, there is a new tool to create macros:
https://github.com/FreeCAD/FreeCAD/issues/9683
https://github.com/FreeCAD/FreeCAD/pull/9684
_Nemo wrote: Thu Jun 01, 2023 1:48 am First, are there any constraint conflicts that current diagnostic algorithms cannot detect so that causes the convergence problems?
"Conflict" detection, which can ultimately be conflicting constraints or redundant, is IMO very well detected by the QR decomposition when constraints provide appropriate divergence values.

What happens is that in some corner cases one (or more) divergences of the Jacobian (that should not get zero) gets zero. This is because in the specific "position" of the geometry, due to the combination of constraints, and the way the constraint is written. This is being solved by modifying the constraint, either rewriting it in another form, or by not allowing it (the divergence) to become zero (but making it a minimum fixed value, 1e-13). This magnitude is believed to be high enough to be over the QR pivot threshold (minimum value not considered to be zero) and low enough not to interfere in DogLeg convergence. In practice it appears to behave as intended. This has been treated until now as "The constraint is the problem and should be rewritten".

When the Jacobian is not degenerate due to constraints, it is my impression that the QR decomposition does an awesome job of identifying the groups of "Conflicting constraints".

Then we have the weakest link in the chain, the identification of which constraints are the ones the user should remove (popularity contest).

After this, there are two possible outcomes: (a) there are conflicting/full redundant sketcher constraints, (b) there are partially redundant sketcher constraints.

Definition: Partially redundant sketcher constraint happens when a sketcher constraint corresponds to more than one solver constraint, wherein at least one solver constraint is redundant, but at least another solver constraint causes no problem at all. Thus, the cannot "just remove" the sketcher constraint, because part of it is necessary. This is being solved by the user changing the combination of constraints. Here, it should be possible to improve by identifying the substitution necessary and advising the user (or requesting permission for automatically substituting it).

In case (a) there are no convergence problems that may arise because there is no attempt to converge. DogLeg is not executed. The user is notified of the problem, together with the "advice" from the "weak link". From experience I can tell you that, when the issue is one of redundancy, if I by-pass the stopping mechanism and DogLeg is executed, DogLeg converges without any issue. However, allowing for redundant constraints ends up being a big problem (the weak chain algorithm becomes useless as they accumulate). Our decision here is notifying the user as earlier as possible so that the issue gets fixed.

In case (b) we allow convergence while ignoring the partial redundant. We mark it in the solver messages. This is the intermediate way we took between: (i) users thinking that all redundant constraints should be ignored and not bother the user, and (ii) those other users, more purist and mindful of what they are doing and wanting to be in control, who would advocate to stop convergence as in (a) and ask the user to fix it. So, at the end, there is an annoying solver message, but then it operates as if it there was not one. There has never been a convergence problem to my knowledge in these cases. But, accumulation of this partial redundant constraints do affect our "popularity contest" weakest link in the chain algorithm.

So answering the last part of your question: Unless two constraints are really conflicting, DogLeg generally converges. There are some cases where it does not (uncommon). Take a look in the issues. They need to be studied.
_Nemo wrote: Thu Jun 01, 2023 1:48 am Second, can intelligent optimization algorithms be helpful in solving multi-solution problems?
This question is not specific to FreeCAD or its solver.

One would need to agree what is to be understood by multi-solution in FreeCAD. Is it parallel convergence using different parameters (or different algorithms) from a same starting point (different ones is a little bit trickier in CAD, as we have a starting point from the previous operation) to try to discover a plurality of solutions (local minima)? Is it directed to find just one local minima in non-convex problems in which some algorithms or combinations of parameters will just not converge?

The problem with multiple solutions is knowing which one is the one the user wants. We have multiple solutions in sketches (flipping of geometry). I believe one could certainly implement algorithms to detect flipped solutions, with specialised algorithms or even by training a machine learning model. We have not explored that area.

I am under the impression that we do achieve convergence in the vast majority of the cases. But there are some tickets with convergence issues. Take a look at them. It is not common to have convergence issues. Where they happen it may be possible that such algorithms are helpful. I could not tell.
_Nemo wrote: Thu Jun 01, 2023 1:48 am Is the current solver architecture convenient to extend for providing multiple solutions?
It was not designed to provide multiple solutions in parallel. I does try solving sequentially with other algorithms if the default fails. Generally the sequence is DogLeg => LM => BGFS. SQP is also used sometimes (I do not have a clear memory). Between algorithm executions, the system needs to be reset to the original state.

That said, I do not think the architecture is inherently bad in the sense of impossible to adapt. But it would certainly need modifications. Because the Sketcher is totally separate from GCS (Sketch.cpp is a kind of Facade software barrier between the two), it should be possible to create copies of the initial state, run several algorithms in parallel, wait for all solutions (or time out some after one arrived), pick one and update the Sketcher with it.
_Nemo
Posts: 117
Joined: Sat Feb 06, 2021 8:25 am

Re: Implement a new algorithm in sketch solver

Post by _Nemo »

abdullah wrote: Thu Jun 01, 2023 9:11 pm
Then we have the weakest link in the chain, the identification of which constraints are the ones the user should remove (popularity contest).
Thank you very much for your response!
My question is, when you mentioned that the popularity contest is the weakest link, what specifically are its issues? Or, to put it another way, what problems currently exist that make it a source of many errors? Is it because the constraint deletion suggestions it provides are not accurate enough?

Also, regarding the multi-solution problem, my initial thought was that traditional optimization algorithms can only provide one solution, while intelligent optimization algorithms can provide all solutions to a given problem.
However, your statement is very accurate that the key to the problem lies in whether we can provide the solution that the user wants, which is the most crucial factor. Therefore, it seems that this is not an urgent issue at the moment.
abdullah
Veteran
Posts: 4935
Joined: Sun May 04, 2014 3:16 pm
Contact:

Re: Implement a new algorithm in sketch solver

Post by abdullah »

_Nemo wrote: Fri Jun 02, 2023 1:23 am My question is, when you mentioned that the popularity contest is the weakest link, what specifically are its issues? Or, to put it another way, what problems currently exist that make it a source of many errors? Is it because the constraint deletion suggestions it provides are not accurate enough?
The main issue is that sometimes the suggestion is not accurate (the constraint it says should be removed is not the one the user will want). There have been other issues, like for example detecting a partially redundant constraint as a fully redundant constraint. I have fixed one such case about a month ago. I am not sure if there would still be other such cases.

The algorithm is a heuristic. It is not an exhaustive search. I do not mean it needs be an exhaustive search. I mean that it is reasonable to think it is limited if we consider all possible input values and all output values.

When (a) a single constraint is causing the problem (the removal of a single constraint may solve the problem) and (b) we did not have any problem before adding the last constraint, the algorithm works well in possibly over 95% of the cases. We keep receiving bug reports from time to time and we keep improving it. We need to increase our coverage of functional tests, because being a heuristic it is easy to fix one case while introducing a regression for another case. I am not sure if we would arrive to a 100% compliance eventually.

However, sometimes assumption (a) and (b) is wrong, for example:
i. a power user introduced several constraints via a macro at once
ii. the user was warned about a partially redundant constraint, but continued adding constraints which are redundant or partially redundant.
iii. the popularity contest algorithm failed to detect a corner case, the user kept adding constraints.

Then, the algorithm's reliability drops, I could not produce a number based on statistics, but let's say it fails in 30% of the cases when two constraints are problematic, and 40% when three are problematic. These numbers are invented, they give an impression of my perception only, which is not scientific.

I am unsure if a different method could prove better.

The importance of the algorithm's outcome is possibly undervalued.

With a certain degree of knowledge, it is possible for a human to understand the suggestion is wrong. A wrong suggestion, after it is understood it is wrong, it may even help a skilled human to understand which constraint is the wrong one (i.e. which one would have been the right one). The important bit of that reasoning "skilled" and the fact that realising it will take a human time (more time if less skilled, less time is more skilled, yet time). We do not want our users to waste time as they need to be productive and efficient. While a user is always in the best position when he knows his tools, the goal of the user is to produce a part, not to dedicate his time to the joys of the intellectual challenge of proving the sketcher wrong (though some of us may feel it rewarding, it means less parts per unit of time, so less productivity).

If the algorithm's outcome were always accurate, it would pave the way to automation. Why tell the user a constraint should be removed instead of directly removing it and let him go on with the design?

This automation is currently implemented under the name "Auto remove redundants" (under the settings drop button in the constraints widget). There are two types of users: (i) they work with this automation always on, turning it off when problems arise, (ii) because problems arise, they have this automation turn off by default.

I belong to group (i). When the algorithm works fine it is a joy to work with this automation on. When the algorithm fails, it may become a nightmare. In particular, a user may not realise a constraint was actually removed. This is often the case when the user cannot expect a given constraint to be removed. When the algorithm fails, it is often the case that whatever the algorithm chose to remove is unexpected by the user. Often the user does not realise this removal directly, unless after several other constraining trials he may realise the DoFs are not decreasing as expected. Of course, realising appropriate decreasing of DoFs requires a certain skill. New users which may lack that skill may get annoyed by what they perceive as the software not obeying their constraining instructions.

An appropriately working popularity contest algorithm would enable systematic use of the automation, which would lead to a higher productivity.

In addition to this automation, there are other automations during autoconstraining that could benefit from a well working popularity contest algorithm. One approach during autoconstraining is to set a number of constraints and remove any redundant (reactive approach). The popularity contest failing does not allow this approach. The alternative approach is proactive, to check which parameters of geometric elements are unconstrained, and select the right constraint to only fulfill those parameters. This I have it implemented in a development branch, but requires many checks and iterations.
User avatar
onekk
Veteran
Posts: 6144
Joined: Sat Jan 17, 2015 7:48 am
Contact:

Re: Implement a new algorithm in sketch solver

Post by onekk »

I have experienced some of the weakness explained above when modelling some simple rectangle with rounded corners, and trying to give it some relative position in respect to the origin, ie centered with a side centered and the other aligned to one axis, round constraints (radius and relative position of arc starting and ending points to use a quarter of circle as corner).

Some of these constraints are redundant do I have found by hand redundant ones and put in if clauses related to the relative position I need in the model.

But for such "simple cases" a way to have them automatically removed would have speed up development a little.

But probably I'm missing some setting in when creating a sketch.

I know that my use case is a corner one, but it is not infrequent to see similar questions on help forum.

Regards

Carlo D.
GitHub page: https://github.com/onekk/freecad-doc.
- In deep articles on FreeCAD.
- Learning how to model with scripting.
- Various other stuffs.

Blog: https://okkmkblog.wordpress.com/
abdullah
Veteran
Posts: 4935
Joined: Sun May 04, 2014 3:16 pm
Contact:

Re: Implement a new algorithm in sketch solver

Post by abdullah »

onekk wrote: Fri Jun 02, 2023 9:45 pm I have experienced some of the weakness explained above when modelling some simple rectangle with rounded corners, ...
Some of these constraints are redundant do I have found by hand redundant ones and put in if clauses related to the relative position I need in the model.

But for such "simple cases" a way to have them automatically removed would have speed up development a little.
I am not sure from the description of the issue how we got there.

If the setting that is not checked here, is checked:
Screenshot_20230606_154123.png
Screenshot_20230606_154123.png (38.25 KiB) Viewed 3712 times
and you got into trouble, I would encourage you to create an issue. If this happened, at some point either the system got degenerated or the popularity contest failed.

That setting "only" fails to my knowledge when there was a degenerated system (at some point in the process) or the popularity contest failed. We want to report those issues to improve that algorithm.

If you do not have that option activated, it is expected that you as user leave the solver in a good state after each addition before continuing. Yes it is annoying. I know. The problem with having the option activated all the time is that sometimes, when the algorithm fails to identify the right constraint, constraints get removed that you do not want removed and you might not even realise it. It works well most of the time.

As an alternative to it, we have a separate system in the making, which checks for DoFs before adding autoconstraints. That will go in the next release cycle as part of the improvement of the geometry creation tools. This other system prevents introduction of redundants by only adding constraints that would limit existing DoFs. I added that concept to the tool widget branch.
User avatar
onekk
Veteran
Posts: 6144
Joined: Sat Jan 17, 2015 7:48 am
Contact:

Re: Implement a new algorithm in sketch solver

Post by onekk »

abdullah wrote: Tue Jun 06, 2023 1:54 pm ...
Thanks, for the answer.

I suspect however that I have not explained correctly my problem

Sorry for the inconvenience, I will try to explain it better this time.

When creating a Sketch with Python, what are the activated options?

In other words, I have to explicitly Issue a command to "autoremove redundant constraints" or set something around?

Maybe this information is already in Documentation, and I have not managed to find it.

Regards

Carlo D.
GitHub page: https://github.com/onekk/freecad-doc.
- In deep articles on FreeCAD.
- Learning how to model with scripting.
- Various other stuffs.

Blog: https://okkmkblog.wordpress.com/
_Nemo
Posts: 117
Joined: Sat Feb 06, 2021 8:25 am

Re: Implement a new algorithm in sketch solver

Post by _Nemo »

abdullah wrote: Wed May 31, 2023 8:34 am Let me know if you need more information.
Hello friend! I encountered a problem with my work in the solver.
As shown in the figure below, after I called setParams to set the value of pvals, how can I synchronize the value of pmap with it?
Because I found that the parameter values of the constraints seem to be set using pmap, and if pmap is not updated, the error remains unchanged.
X{U@GYERK(IX{~0YC]KMDN0.png
X{U@GYERK(IX{~0YC]KMDN0.png (25.88 KiB) Viewed 3564 times
_Nemo
Posts: 117
Joined: Sat Feb 06, 2021 8:25 am

Re: Implement a new algorithm in sketch solver

Post by _Nemo »

Recently, I tested several cases that were reported to have problems by everyone.
It seems that currently only the redundancy recognized by the solver in "Gourd" is incorrect, and when I tried to drag the sketch, the solver recalculated and gave the correct result.
Gourd_error.png
Gourd_error.png (70.69 KiB) Viewed 3482 times
Gourd_correct.png
Gourd_correct.png (78.66 KiB) Viewed 3482 times
This inspired me: if I am correct, we can try to add parameter perturbations to the constraint system and re-detect redundant constraints, and the final result may be similar to "Gourd".
Attachments
Symmetrical Rectangle.txt
(1.94 KiB) Downloaded 34 times
Sector.FCStd
(3.5 KiB) Downloaded 31 times
Gourd.txt
(2.43 KiB) Downloaded 36 times
_Nemo
Posts: 117
Joined: Sat Feb 06, 2021 8:25 am

Re: Implement a new algorithm in sketch solver

Post by _Nemo »

abdullah wrote: Wed May 31, 2023 8:34 am
(2) starts here:
https://github.com/FreeCAD/FreeCAD/blob ... .cpp#L5270
Also, I think the popularity contest may be sufficient in identifying conflicting constraints.
In the current situation where we are unable to obtain user design intentions, the only solution to resolve conflicts is to remove one constraint from the conflicting constraint group.
There is still room for optimization in identifying redundant constraints.
User avatar
onekk
Veteran
Posts: 6144
Joined: Sat Jan 17, 2015 7:48 am
Contact:

Re: Implement a new algorithm in sketch solver

Post by onekk »

abdullah wrote: Tue Jun 06, 2023 1:54 pm ...
Probably the point is that when scripting the action of auto removing redundant constraints is simply not triggered when doing the sketch.recompute()

See maybe, to not hijack further this topic:

viewtopic.php?t=78954

Regards

Carlo D.
GitHub page: https://github.com/onekk/freecad-doc.
- In deep articles on FreeCAD.
- Learning how to model with scripting.
- Various other stuffs.

Blog: https://okkmkblog.wordpress.com/
Post Reply