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: be more efficient than scanning every story module and evaluating its conditions (which wouldn't scale as we accumulated story modules), and secondly 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).

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 -- more 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.