Nell/ProductionRules

From OLPC
Jump to: navigation, search

[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).

Related

JSON rules

There exists a JSON-based production rule system with a implementation of the rete algorithm: JSON rules. It is described in a paper from the CEUR Workshop. It is interesting and relevant work. I have two main objections to the implementation:

  1. It stores all working state in the DOM, and is tightly coupled to this choice. This is a pretty fundamental objection: I don't really want to embed the entire story (including all the independent story modules) in the page DOM. The story modules should be fetched and cached such that that the Story lives in a (client-side, datalog) database. One could imagine fetching the entire story from the database and inserting it into the DOM for every page, but this seems suboptimal.
  2. Actions and Conditions are specified as opaque strings in the JSON, to be eval'ed or otherwise parsed at rule load time, which feels wrong to me. See below for a solution leveraging quasiquotation.

AIML

AIML is a "stimulus response" pattern-matching language for creating chatbots. It's not strictly related to the production rule system, but it might be interesting to integrate AIML fragments with story specifications. A new story module could then also include new 'topics' for the AIML-based chatbot. Moving between pieces of a story could be accomplished by <script> elements embedded in the AIML rules for parts of a conversation; those <script> fragments would assert the appropriate properties and invoke the production rule system.

A simple example might be an AIML fragment which just defined "north", "south", "east" and "west" conversational patterns. When the related story module was entered, the AIML fragment would be activated. Story pieces corresponding to various rooms in the castle would contain preconditions related to the room connectivity -- for example, if 'entrance' is below the 'tower' then the precondition for the 'tower' description in the story might include 'At(entrance) && Event(Chatbot, "UP")' and the AIML fragment for the conversational pattern "up" (ie, "go up", "climb", etc) might include 'FireEvent(Chatbot, "UP")'. A globally-activated AIML fragment might enable the child to say "go to the castle" (or "return to the castle") at any time to jump into this story module.

More AIML links:

Quasiquote

Our story modules are currently specified in JSON. One issue with integrating the rule language is that the conditions and actions end up as opaque strings when embedded in JSON, rather than syntax-checked JavaScript expressions.

One alternative is to add a preprocessor implementing a quasiquote syntax to rewrite (and syntax check) the executable portions. For example, instead of: 

rule = { condition: "Foo(Bar)" }

...the preprocessor would take as input: 

rule = { condition: js`Foo(Bar)` }

...and output proper JSON: 

rule = { condition: { type:"apply", name:"Foo", args: [ { type: "literal", name: "Bar" } ] } }

This uses the Harmony proposals for Quasiquoting combined with a 'js' quasi-quote operator, which might be implemented in terms of the Mozilla Parser API (or, in the short-terms, implemented using Narcissus, which doesn't quite match the proposed Parser API but is very close in spirit).

Retrieved from "http://wiki.laptop.org/mediawiki/index.php?title=Nell/ProductionRules&oldid=269578"