Sep 27, 2019

methods of constraint solving.

first, what is a constraint solver? in my opinion, on the tiers of programming levels of abstraction, constraints specification is the highest level programming language. it’s declaring a set of variables, then declaring their relationship to each other, and what values they can’t have. then the computer has to pick some algorithm to find good values for those variables- amongst a potentially infinite set.

usually you find constraint solvers in CAD programs, or 3D modelling programs. it’s also used in Apple’s UI layout system, called Autolayout” but, you could potentially put it to solving optimisation problems like nurse scheduling, travelling salesman, anything where the only thing you really know for sure about a problem is what the solutions are not.

there’s a special kind of constraint called a “linear constraint”, and what that means in essense is that whatever the solution set is, you know it’s somewhere along some line. so the most common form of this is seen in cocoa autolayout, as equalities and inequalities. examples:

a = b + 10

b > c

c < 60

and the first step with these in any solver is to turn them into a system of linear equations.

0 < 60 - c

0 <= -c + b

0 = b + 10 - a

if all of your constraints are linear, then a technique called “linear programming” can be used. it’s called that if you do it with pen and paper, but if a computer algorithm is doing it, it is called a “simplex solver”. how this works is, the linear constraints form a flat faceted shape in N dimensional space, where N is the number of variables you are trying to solve. this kind of shape is called a “simplex”. it is then easy to find the edges of this shape and pathfind to the solution

“the solution” is in fact anywhere on the surface or possibly inside volume of the simplex. so you need some way of deciding what a “best” solution is. the minimum of all the variables? the maximum? or the nearest to some starting point, usually are what is used.

ok so what if the constraints aren’t “linear”? what does that look like? an example of a non linear constraint problem is Inverse Kinematics. The simplest example of this would be a robot arm. your system of constraints is the bone lengths, enforced by

len^2=((x_2-x_1)^2+(y_2-y_1)^2+(z_2-z_1)^2):

it’s the pythagoran theorum in 3d, and it’s a quadratic equation, not linear. finally, you want the end of one bone to be equal to some target point.

one way of approaching a problem like this is with a physics engine. you would, in essence, turn each bone into a spring, and simply use some integration algorithm like verlet to incrementally push the points around until the bones are all the right length. this can be a bit computationally intensive, and also it can make your robot seem kinda “squishy”.

a less computationally intense approach is detailed on this page with javascript demos:

Constraints - Sublucid Geometry the important thing to note here is that the constraints are all neatly linked together along a single line.

so Ivan Sutherland got this ball rolling in the early 1960s. it seems he singlehandedly invented guis, object oriented programming (prototype based), constraints solvers, light pens, touch screen interfaces, interactive computing, CAD, all in an era where most computing was done in “batch” mode with stacks of punch cards. when asked how he did all this he answered “nobody told me it was supposed to be hard”

Ivan Sutherland Demos Sketchpad (1963) - YouTube

you can look at his paper on the sketchpad system here:

sketchpad - a human machine interface PDF

in it he details two approaches he took to constraints solving. a “maze solving approach” and “relaxation”.

in “maze solving”, construct a graph where the nodes are the free variables, and the edges are a constraint that connects them. if the resulting graph is a tree, you can traverse from the root to the leaves by fixing the root variable and solving the leaf variables of each subtree.

so what’s the state of the art if constraints solvers in 2019? well I am not sure but I think it’s the Minizinc language from Monash University, in Melbourne.

the language is a concise way of specifying a system of constraints, which compiles to a smaller language which is usable on a set of modern solver engines you can plug into with minizinc’s IDE.

i tried this, and I have to admit I couldn’t get it to work very well!

the problem with a non interactive system, is that it kind of doesn’t have a user supplied starting point like in a CAD system, so it picks a random starting point each run. from there, the constraints can act in very counter intuitive ways. since these are problems with infinite solutions, the solver can end up with solutions that are degenerate, or, in some systems the solver can end up running an absurdly long time in the worst case of trying to do a brute force search.

a fascinating and incredibly obscure Constraints oriented language is from 1980, named “IDEAL”. some really novel things about the IDEAL language:

1: all variables in IDEAL are complex numbers, so rotations become a matter of multiplication by i

2: functions are expressed in the form of systems of equations with some free variables, and they are “called” by supplying concrete values for any of those free variables, until there’s a single solution to the equation.

3: IDEAL had a strategy for over constrained systems: that is, systems with no solution that satisfies all the constraints. each constraint is given a priority, assigned by the order in which it appears in the source text. the higher priority constraints are solved until a single solution is arrived at, and the remaining constraints distance to satisfaction is minimized as much as possible.

- the result of compiling and running an IDEAL program was a vector image, in DVI format intended to be used with UNIX’s troff utility.

I was able to find, with a great deal of google-fu, the manual and source code for IDEAL. i haven’t got it to compile yet- the source code I found expects to be running in Unix System V, which has a myriad of tiny differences from a modern system, mostly in the parser generator it uses: yacc

well, actually the problem isn’t even yacc. it’s with the C code it ends up generating! i got it to compile but it segfaults when I try to run any of the example programs! i might need help from a Real Programmer(tm)

did I miss anything ? i suppose another approach is to frame your constraints as something like signed distance field, and then use an optimiser, like gradient descent. it might end uo being a good approach since hardware is now optimising for gradient descent for deep learning algorithms.