Structural Backtrack

There are many programs, used in planning and other areas, which "backtrack" - that is, make a decision, evaluate the consequences, observe the result, then undo the decision if the result is either not possible (a constraint is violated) or non-optimal (a better result can be found using a different decision). It is a necessary technique, as the effect of many constraints cannot be seen without exercising them.

The problem with these programs is that the problem must be essentially static. The usual approach is to create a new stack frame, put a copy of the set of variables on the stack, then alter their values while respecting constraints among them. If the result is acceptable, a new decision may be made, by making a copy of these variables, and so on. If the result is not acceptable, the stack frame and its set of variables are "popped" (thrown away).

The obvious limitation with this approach is that the set of variables must be known beforehand - no construction can occur, as this would introduce new variables.

An alternative approach, which ORION uses, is to represent the complete structure of the problem using variables, operators,  links, every part which changes state. When a change occurs in any of these components, an image of the old state is saved. This approach allows the structure to change - to grow new connections, to create new objects, to destroy parts of the structure so new structure can grow in its place, anything that is necessary to represent the dynamic aspects of the problem. It is easy to revert to the previous state, by simply overlaying the saved image of the structure over the current structure.

A simple example of structural backtrack is shown in a SelfModifying presentation. While this example looks trivial, it demonstrates how fundamental structural backtracking is to the effective representation of many problems that range from almost (but not quite) completely static, to wildly dynamic, as text understanding is in WordsToKnowledge.

Prepositional maps use backtracking to orient themselves as they crawl over a structure.

Tools that do not allow this structural backtracking either force or train the user to think statically, but a dynamic interplay of influences is typical of most problems.

Active Structure