Movimentum - The solver algorithm needs more debug output

It seems that we now have a solver framework in place which we can fill with "intelligence"—i.e., rewriting rules. But which rules? Well, I do have a target: Animating machines. So the constraints to be solved should come from that domain. And so, a legitimate way of proceeding, at least for some time, is to solve examples. We already have two:

• The crank-and-piston mechanism from this old posting.
• The moving hockey stick from that posting.

Using these examples, we will now try to add sensible rewriting rules that create little films. We can start with the hockey stick, which seems very simple. However, the crank-and-piston mechanism is already quite large, with four parts (three moving, one fixed) and, hence, about eight variables. Therefore, I suggest two more examples in between:

• A simple rotating bar;
• and a rotating triangle, made from three bars. This leads to a lot of rigid-body-constraints that have to be solved.

Let us start with the hockey stick!

    [Test]
    public void TestMovingHockeyStick() {
        const string s =
            @".config (20, 200, 200);
            B : .bar P = [0,0] Q = [5,5] R = [5,30];

            @0  B.P = [60 + .t, 60 + .t];
                B.Q = [65 + .t, 65 + .t];
                B.R = [65 + .t, 90 + .t];
            @10";
        Script script = Program.Parse(s);

        string prefix = MkTestDir();
        Program.Interpret(script, prefix);
    }

MkTestDir() is a simple method that creates a test output directory. This is not standard for a unit test, but as I explained here, I want to (also) test the results visually, and so I need the frames in a directory to assemble them into a movie.

Let us run the test ... and ... it is ... red: It throws an exception that says "System.Exception : No solution found for frame 1." What happened?

Let us think a moment: In each step, the solver takes the first open node and tries to match all constraints against the rewriting rules. But if no rule matches, it closes the node without an expansion, which means it is "unsolvable," and continues with the next open node. Missing a solution, therefore, means that

• either a rule that should have matched did not match (because of a programming error);
• or there is not yet a rule for some situation—our two rules are certainly not enough to solve all constraint systems!

In order to find out what happens, we need more insight into what goes on in the solver. One method is to use a debugger—but this is very cumbersome in an algorithm that crates a lot of small data structures, and moreover does this in some unintuitive order (the reason for which is the worklist approach). What we'd rather want, is some sort of "snapshot" on the data structures at crucial points of time—especially, of course, when no solution is found. So we need more debugging output—much more!

We already have a readable representation of constraints, using our ToStringVisitor. With that code, we can output a single SolverNode:

    public override string ToString() {
        return "SolverNode"
                + _constraints.Aggregate("",
                    (s, c) => s + "\r\n  ! " + c)
                + _variableInRangeKnowledges.Aggregate("",
                    (s, k) => s + "\r\n  "
                      + k.Key.Name
                      + " = " + ((VariableValueRestriction)k.Value).Value);
    }

Which additional structures do we want to see?

• We want to see the "history" of a SolverNode: From which node it was crated ("expanded"), and how.
• In addition, we want to see all the nodes that did not result in a solution, i.e., that were expanded to an empty set: After all, one (or more) of them might contain constraints that should have been matched, but were somehow missed.

For the first item, we give each node a number:

    private static int _debugIdCount = 1000;
    public readonly int DebugId = _debugIdCount++;

In addition, we remember the creating node, add a string about the creation rule, and write the same information recursively for a few predecessor nodes. To get a feeling for the node graph, I also want to see whether a SolverNode is the sole descendent of its predecessor, or whether there is more than one expansion. Here is a code snippet that tries to do this:

    private readonly SolverNode _debugOrigin;
    private int _debugSuccessors;
    private string DebugCreationRule;
 
    private string DebugOriginChain(int depth) {
    return
        (_debugSuccessors == 0 ? "" : _debugSuccessors == 1 ? "-" : "*") +
        DebugId + "<" + DebugCreationRule +
        (depth > 10 ? "..."
         : _debugOrigin == null ? ""
         : _debugOrigin.DebugOriginChain(depth + 1));
    }

Now, when we call DebugOriginChain() inside ToString(), we now get output like the following:

{SolverNode 1020 < 0=C-1019 < 0=V+C-1018 < 0=C-1017 < 0=V+C-1016 < 0=C-1015 < 0=V+C...
  ! {EqualsZeroConstraint}0 = 60+-(65+root 25)
  ! {EqualsZeroConstraint}0 = 0+-(0+root 0)
  ! {EqualsZeroConstraint}0 = 60+-(90+root 900)
  ! {EqualsZeroConstraint}0 = 65+-(65+root 0)
  ! {EqualsZeroConstraint}0 = 65+-(90+root 625)
  B.P.X = 60
  B.P.Y = 60
  B.P.Z = 0
  B.Q.X = 65
  ...

The lines after the first one are, first, the constraints, and then the variable assignments. The first line can be read as follows:

• First, we are told that node id is 1020.
• Then, we see the predecessor nodes, and to the left of each, the name of the rule that created. For example, 1019 was created from 1018 by a 0=V+C rule rewrite, and the current node, 1020, was in turn created by a 0=C rewrite (I do not show the additional string we must pass into the rewrite rule, and a little bit of code that sets DebugCreationRule in Expand—it is very simple).

In order to see all the nodes that "went dead," we add a static list where we put a node if the expansion is empty:

    public static readonly List<SolverNode> DebugDeadNodes =
        new List<SolverNode>();

    public static IEnumerable<SolverNode> SolverStep(...) {
         ...
         SolverNode selected = ...;
         IEnumerable<SolverNode> expandedSets = selected.Expand(...);
         if (!expandedSets.Any()) {
             DebugDeadNodes.Add(selected);
         }
         ...
     }

When the solver algorithm runs out of nodes without finding a solution, it writes all these nodes to the debug output so that we can find out what went wrong:

    public static int Solve(...) {
         ...
         do {
             if (!open.Any()) {
                 Debug.WriteLine("---- " + DebugDeadNodes.Count
                                                   + " dead nodes ----");
                 foreach (var deadNode in DebugDeadNodes) {
                     Debug.WriteLine(deadNode);
                 }
                 throw new Exception("No solution found for frame " + ...);
             }
             ...
         } while (...);
         ...
     }

Using this machinery, we can again run the test. And here is the output of the dead nodes:

---- 1 dead nodes ----
SolverNode 1020 < 0=C-1019 < 0=V+C-1018 < 0=C-1017 < 0=V+C...
  ! {EqualsZeroConstraint}0 = 60+-(65+root 25)
  ! {EqualsZeroConstraint}0 = 0+-(0+root 0)
  ! {EqualsZeroConstraint}0 = 60+-(90+root 900)
  ! {EqualsZeroConstraint}0 = 65+-(65+root 0)
  ! {EqualsZeroConstraint}0 = 65+-(90+root 625)
  B.P.X = 60
  B.P.Y = 60
  B.P.Z = 0
  B.Q.X = 65
  B.Q.Y = 65
  B.Q.Z = 0
  B.R.X = 65
  B.R.Y = 90
  B.R.Z = 0
  ZERO = 0

Let us think about this result in the next posting.