Nell/ProductionRules

[CSA] I did some research (and AI archaeology) to try to determine the "proper" way to implement story module preconditions. The original goal was twofold: first, to find the next story module to run more efficiently than by scanning every story module and evaluating its preconditions (which wouldn't scale as we accumulated story modules); and second, to attempt to integrate a full programming language for the condition expressions in such a way that we could leverage the story module evaluation semantics more generally to implement other Avatar Services functionality (ie, do as much as possible with a single abstraction).

Summary: the rete algorithm achieves the first goal, and the second goal was misguided. We can strengthen the 'Action' clauses, but the 'Precondition' clauses should stay relatively simple (Horn clauses, roughly) to enable the use of the rete algorithm.

Planners

A long detour took me through Nell/Prolog, before eventually coming to the realization that Backward Chaining (the core of Prolog) was *not* actually what we needed for story evaluation. (Although Prolog is very cool.)

The second detour took me through various planner implementations. The language used in expressing plans for STRIPS has proven to be very popular and durable over the past 30 years. (Although slight extensions such as ADL or one of the PDDLs might be necessary.) A STRIPS implementation in Python is not too complicated; a simple implementation in PROLOG is only 11 lines or so. More sophisticated planner implementations (mostly in Lisp) are available from the CMU AI repository.

Planners of this sort seem to be useful in story generation (cf "Story Telling as Planning and Learning", an early UNIVERSE paper, and Mark Riedl's Story Analogues paper). So we might resurrect this for the "Story Generation" activity... but that's not part of the Story execution engine.

Production rule systems

Forward chaining is the inference mechanism needed for story execution -- whenever some new fact is asserted, we want to eagerly search forward for ("infer") all the new facts which become true. The specific case of "executing some code when some conditions become true" is called a Production Rule System. There's a slippery slope here -- many production rule systems slide into becoming Business Rule Management Systems, which means they've grown "pointy-hair--friendly" UIs so that "non-technical" users can modify the rules via Excel or some bespoke GUI, usually to workaround officious corporate IT departments which prevent deploying updates to software more directly. We don't have to implement a BRMS!

Production Rule Systems can be efficiently evaluated using the Rete algorithm. This keeps track of the dependencies of each action so that when new facts are asserted, only a subset of the preconditions must be re-evaluated. Doorenbos' thesis describes the algorithm in depth. An actual implementation might want to follow Drools' implementation ("ReteOO") closely. Drools implementation adds some object-oriented features to rule specifications, as well as adding backward-chaining capabilities. JavaScript is not strongly typed, like Java is, so some of Drools syntax and implementation might not be applicable, but the basic object-to-field-selector mechanisms should still be applicable.

Production rule systems are Turing-complete, but expressing typical conditional logic and loops using production rules can be awkward. Strengthening the expressive power of production rule conditions increases the difficulty of the rete algorithm implementation. As a result, we probably don't want to attempt to hoist other parts of the Avatar Services code into the production rule system. Production rules are strong enough for story execution; we will use external planners or OO languages for other functionality.

On the other hand, arbitrary JavaScript code might be easily embedded in the "action" portion of the rule, so long as those portions of the action which affect rule preconditions are distinguished. (For example, all rule conditions might be constrained to name only fields in the AvatarServices object, and the only way to alter fields in AvatarServices is via some API which properly hooks into the production rule system.)

Conflict Resolution Strategy

In a production rule system, it will often be the case that several different rules become executable at the same time (a "conflict set"). One of them has to be chosen for execution first. In production rule systems, this choice is made by a "conflict resolution strategy".

Many of the standard conflict resolution strategies from the literature are appropriate for our story execution application; explicit rule priorities, for instance. Story-specific resolution strategies might include:

• Specificity: prefer executing "the next module in the current story" over introductory modules in other stories. (This could also be implemented by bumping the priority of introductory modules down below the default.
• Explicit random choice: if there are various options that should be chosen randomly to add a bit of variety of the story, they might be explicitly annotated so that the conflict resolver will select between them at random.
• "Most recent"/"least recent": if we went back to replay part of a story, we might want to make the same random choices as we did in the previous execution; choosing the execute the "most recently executed rules" would have this effect. Choosing the "least recently executed rule" is nice for a "choose-your-own-adventure" type story where the child might want to see how all the paths play out.
• Error: modules might be tagged such that if multiple modules with the same priority are detected the system will register an error. This would be helpful for detecting and debugging unintentional ambiguities during story creation.
• Prompt: ambiguous rules will result in a user prompt asking for a choice. This might be accomplished by adding a special "ambiguous rule" condition of high priority which would be triggered in this case. That rule would display the choices and prompt the user in some story-friendly manner -- for example, the rule might transport the protagonist to the controls of their magical balloon, from which they can "fly" to the various story locations. There can be multiple story steps taken by the child before a choice is made. Making a choice adds a special "priority rule" property which would then disambiguate the situation which originally resulted in the prompt, if/when the child returned to that situation. (There might be additional story steps -- describing the balloon flight, for example -- before the original situation resulting in the prompt was again reached.)

As a concrete proposal, I recommend adding a "rule group" to every rule. The default rule group implies a default priority and an "error" semantics for detected ambiguities. An "story intro" rule group provides a lower priority and a "prompt" semantics. A "random choice" rule switches from an "error" semantics to an "explicit random choice" semantics, allowing for controlled ambiguity. Within "explicit random choice" there might be "most recent" or "least recent" overrides, for use during story replay or in certain story situations. It is always an error if there are multiple rules with the same priority but differing resolution hints in the conflict set.

In addition to these default rule groups, the user can define their own rule groups with user-specified priorities and javascript hooks for resolution. The hook would take as an argument the full conflict set, and would manipulate the state such that re-evaluation would yield a different (presumably smaller) conflict set. For example, the priority of the desired rule might be temporarily increased, removing the other members from the conflict set.

It might be possible to define the conflict resolution strategy as "just another rule". For example, the high priority "resolve-story-intro" rule might become active iff a conflict set of rules in the story-intro group became active. The "action" portion of the "resolve-story-intro" rule might execute arbitrary javascript code to resolve the conflict (for example, by temporarily bumping the priority of one member of the conflict set).