Movimentum - The Solver: Yet Another Constraint Model

We want to write an algorithm that assigns, for each frame, a well-defined location to each anchor of each object in our model. To find this solution, we will have to juggle the constraints in some way—essentially, we must do what we all learned in school: Solving linear and quadratic equations, substituting variables, simplifying expressions.

You might remember from those times that it sometimes necessary to search for a solution—i.e., it is possible that one has to research more than one path, because some paths might lead to dead ends (unsolvable constraint combinations). This happens, for example, if there are square roots. Here is a simple example:

x = √ 100
x < 0

In order to solve for x, one must first find out that there are two solutions to the equation: x ∈ { -10, +10 }. With both possible values, one now evaluates the inequality and finds that only the solution x = –10 survives.

Here is a more realistic example, from our domain of mechanical linkages: We have two black bars linked at a joint and already have fixed the free end of each bar at the points marked in orange.

Moreover, we know that the link must be on the blue line. We get three constraints:

• One for the possible locations of the free end of the left bar (the left green circle);
• One for the locations of the free end of the right bar (the other circle);
• And one placing the joint on the blue line.

Any algorithm that first selects any two of these constraints, and then limits the solutions by using the remaining constraint, will get two possible solutions from the first step.
For example, the first two constraints will yield two possible positions by intersecting the two dashed green circles. Only checking both positions against the blue line constraint will reduce the solutions to the single position shown by the dashed lines.

This shows that we need some sort of search algorithm for solving the constraints. But I will postpone the design of that algorithm for some time, because we need another model!

The solver constraint model

Our constraints are complex. They are too complex: There are vector expressions and scalar expressions and mixtures of both types. Solving these constraints would need many different mechanism which is too much work.
Let me therefore introduce a new constraint model that is not derived from the user's perspective (as is the "input constraint model" in the previous postings),  but one that is as simple as possible so that solution algorithms can work with it. The idea is that this "solver constraint model" (as I'll call it from now on) deals only with scalar variables and expressions so that we do not need solution formulas for vector and mixed scalar-vector expression. Of course, we will have to transform the input constraints to the solver constraints, and we will have to write back the results. But the hope is that a simpler solver model saves work overall.

Here is an overview of the model:

The following code is a little boring to read, but if you want to follow the next postings, you should go through it:

    #region Solver constraints

    public abstract class AbstractConstraint {
    }

    public abstract class ScalarConstraint : AbstractConstraint {
        private readonly AbstractExpr _expr;

        protected ScalarConstraint(AbstractExpr expr) {
            _expr = expr;
        }

        public AbstractExpr Expr { get { return _expr; } }
    }

    public class EqualsZeroConstraint : ScalarConstraint {
        public EqualsZeroConstraint(AbstractExpr expr) : base(expr) { }
    }

    public class MoreThanZeroConstraint : ScalarConstraint {
        public MoreThanZeroConstraint(AbstractExpr expr) : base(expr) { }
    }

    public class AtLeastZeroConstraint : ScalarConstraint {
        public AtLeastZeroConstraint(AbstractExpr expr) : base(expr) { }
    }

    #endregion Solver constraints

    #region Solver expressions

    public abstract class AbstractExpr { }

    public abstract class AbstractOperator { }

    public class Constant : AbstractExpr {
        private readonly double _value;
        public Constant(double value) {
            _value = value;
        }
        public double Value { get { return _value; } }
    }

    public abstract class Variable : AbstractExpr {
        private readonly string _name;
        protected Variable(string name) {
            _name = name;
        }
        public string Name { get { return _name; } }
    }

    public class NamedVariable : Variable {
        public NamedVariable(string name) : base(name) { }
    }

    public class AnchorVariable : Variable {
        private readonly Anchor _anchor;
        private readonly Anchor.Coordinate _coordinate;

        public AnchorVariable(Anchor anchor, Anchor.Coordinate coordinate)
            : base(VariableName(anchor, coordinate)) {
            _anchor = anchor;
            _coordinate = coordinate;
        }

        public Anchor.Coordinate Coordinate { get { return _coordinate; } }
        public Anchor Anchor { get { return _anchor; } }

        public static string VariableName(Anchor anchor, Anchor.Coordinate coordinate) {
            return anchor.Thing + "." + anchor.Name + "." + coordinate;
        }
    }

    public class UnaryExpression : AbstractExpr {
        private readonly AbstractExpr _inner;
        private readonly UnaryOperator _op;
        public UnaryExpression(AbstractExpr inner, UnaryOperator op) {
            _inner = inner;
            _op = op;
        }

        public AbstractExpr Inner { get { return _inner; } }
        public UnaryOperator Op { get { return _op; } }
    }

    public abstract class UnaryOperator : AbstractOperator { }

    public class UnaryMinus : UnaryOperator { }
    public class Square : UnaryOperator { }
    public class FormalSquareroot : UnaryOperator { }
    public class PositiveSquareroot : UnaryOperator { }
    //public class Integral : UnaryOperator { }
    //public class Differential : UnaryOperator { }
    public class Sin : UnaryOperator { }
    public class Cos : UnaryOperator { }

    public class BinaryExpression : AbstractExpr {
        private readonly AbstractExpr _lhs;
        private readonly BinaryOperator _op;
        private readonly AbstractExpr _rhs;
        public BinaryExpression(AbstractExpr lhs, BinaryOperator op, AbstractExpr rhs) {
            _lhs = lhs;
            _op = op;
            _rhs = rhs;
        }

        public AbstractExpr Lhs { get { return _lhs; } }
        public BinaryOperator Op { get { return _op; } }
        public AbstractExpr Rhs { get { return _rhs; } }
    }

    public abstract class BinaryOperator : AbstractOperator { }

    public class Plus : BinaryOperator { }
    public class Times : BinaryOperator { }
    public class Divide : BinaryOperator { }

    public class RangeExpr : AbstractExpr {
        // ... Internals missing ...
        public RangeExpr() {
            throw new NotImplementedException("We do RangeExprs later ...");
        }
    }

    #endregion Solver expressions

Here are a few notes on the model:

• On the whole, it is quite obvious—there are three constraint types, constants, variables, binary and unary expressions, and a host of binary and unary operators—this time as classes, not as objects.
• The AnchorVariable class is our "return ticket" to the input model: When the solver has assigned values to all such variables, it is possible to place the objects.
• The only decision that is not obvious is the distinction of formal and positive square roots. It took me some playing around with expressions until I realized that this is necessary. The reasoning goes about as follows: We will have to evaluate expressions at some time; but for this, we need unique function results. On the other hand, as we saw in the examples above, the "square roots" we get from the input model constraints are "formal square roots": Their result for a concrete solution may be the positive or the negative root value.
  Of course, our solver machine will, at some point, have to rewrite formal square roots to non-formal square roots—we will deal with this later.

An alternative design possibility is the following: Expression evaluation does not return a single value, but a set of values. However, this designs deviates quite a lot from our usual, manual way of working with equations. It might make a nice research project (which probably has already been done many times), but is not the way I want to follow in this "blog project" that should be easy to understand.

• I skipped code for calculus operators (integral, differential) and for those complex range expressions. If the whole solver is more or less in place, we'll find out whether we still want them (i.e., we can solve them), and whether we need them ...

In the next postings, let me add some machinery that will be required for the solver:

• A visitor facility for constraints and expressions.
• ToString() output for debugging.
• Equality.
• Numerical evaluation of constraints.

And of course we will have to rewrite the input constraints to solver constraints!