From: dnk@OMIT.cs.mu.OZ.AU   
      
   In <4423343b$1@news.unimelb.edu.au> "g_chime@yahoo.com" writes:   
      
   > I'm new to AI and trying to understand forward chaining.   
      
   > I don't understand why we need conflict resolution.   
      
   > Why is it so important to fire only one rule per cycle?   
   > Why can't we fire 2 or 3 rules from the conflict set per cycle?   
   > Or even all of them?   
      
   > Is this only an efficiency issue or (most likely) am I missing   
   > something?   
      
   Whether to fire one or many of the set of enabled rules on a cycle   
   is a design choice. I suspect the usual choice of just one is more   
   for conceptual and implementation simplicity than for efficiency.   
   In firing just one rule, some form of conflict resolution is   
   needed but this can be a very simple scheme relying on explicit   
   rule priorities and/or implicit rule preference orderings (e.g. as   
   in Prolog), with any ties broken arbitrarily.   
      
   By contrast if you permit multiple rule firings on one cycle then   
   the need for conflict resolution doesn't really go away and   
   several new complexities are introduced.  A fundamental issue is   
   whether the execution semantics of these multiple firings should   
   be parallel or sequential execution.  Parallel execution is   
   conceptually simpler but there are problems with both.  Another   
   potential complexity that you suggest above would be how exactly   
   to choose the rules that are executed on a cycle if you don't   
   choose all of them, i.e. which 2 or 3 to choose.   
      
   To spell it out a bit, if your semantic model of multiple firings   
   is parallel, then all rules are evaluated in the intial state,   
   and the actions of those chosen for execution are applied to this   
   same state and "combined" to generate a single final state.   
   Conceptually, there are no intermediate states during the cycle.   
      
   If your model is sequential, then all rules are evaluated in the   
   initial state, some enabled subset to be executed is chosen, some   
   execution order is chosen, and they are executed one by one, with   
   the action of each applied to the state that results from the   
   actions of all those that preceded it.  This means that only the   
   first of the many is actually executed in the state in which it   
   was evaluated, the rest are executed in "microstates" in which   
   they may not even be enabled.  Overall, it's rather similar to   
   one per cycle execution except that the set of enabled rules is   
   not recomputed until all those chosen have been executed.   
      
   Most of this complexity matters only because of rules whose   
   actions don't commute, i.e. whose nett effect on working memory   
   depends on the order they are executed.  How this can occur   
   depends on what sort of working memory structures we are using,   
   but consider for example two distinct assignments to the same   
   variable such as X:=1 and X:=2, or one rule that inserts a new   
   tuple into a set A and another rule that updates the tuples in B   
   for each one existing in A.   
      
   Now if all the rules that are enabled on a given cycle do commute   
   there is no problem; the parallel and sequential models are almost   
   indistinguishable, and it makes no difference what execution order   
   is chosen.  But as soon as two enabled rules don't commute, the   
   parallel model breaks down completely (it must reject at least one   
   of the conflicting rules) and in the sequential model we are faced   
   with a choice of which order to execute them that matters because   
   it has observable effects on the system state at cycle end. If the   
   choice is arbitrary but consistent when repeated, rule execution   
   semantics may become merely obscure, but if it is inconsistent,   
   then rule (and hence system) behaviour becomes effectively   
   non-deterministic.  And the alternative to arbitrary choice is   
   going to be something at least as complex as conflict resolution,   
   except that now it chooses what order to execute rules within a   
   cycle rather than which one rule to execute.   
      
   But wait, why can't we save the parallel semantics (or simplify   
   the sequential semantics) by just executing a subset of the   
   enabled rules that is free of conflicting non-commutative rules?   
   First, there is an efficiency issue: to detect non-commutativity   
   in the general case may require comparing the results of different   
   execution orders, but more importantly, choosing a commutative   
   subset of the enabled rules solves nothing, as it just replaces   
   the problem of which order to execute non-commutative rules with   
   the equivalent problem of which of many such subsets to choose.   
      
   Finally it's not just non-commutative actions that reveal   
   differences between the parallel and sequential semantics.   
   Consider two rules whose identical actions "increment a counter",   
   doing something like X := X+1.  If both are enabled and executed   
   under the parallel semantics, the counter is only incremented   
   once, since X+1 is evaluated in the same initial state, but under   
   the sequential semantics, it's incremented twice, since X+1 is   
   evaluated twice but in different states.   
      
   I hope this gives you some initial sense of the complexity and   
   subtlety of executing multiple rules per cycle.  There are many   
   design decisions to be made, hence many ways to do it, most of   
   which suffer from semantic problems of one sort or another.   
   It's a problem area that still doesn't seem to be well explored   
   in the literature.   
      
   David   
      
   [ comp.ai is moderated.  To submit, just post and be patient, or if ]   
   [ that fails mail your article to , and ]   
   [ ask your news administrator to fix the problems with your system. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)