A Popular Kind of Rule-Based Model: Production Systems

How One Works (Roughly)

• Components
  • A set of rules, representing general, long-term knowledge about some class of problems
    Each rule has
    • A set of conditions (the left-hand side of the rule) which characterize the situations under which the rule applies

      if (ABOVE ?X ?Y)

      if (MOVING)
      and (AHEAD ?X)
      and (SOLID ?X)

      if (GAVE ?GIVER ?GIVEN ?RECIPIENT)

      if (GOAL (PAST_TENSE ?V))

    • A set of inferences or actions (the right-hand side of the rule) which describe what to do when the rule applies

      then (BELOW ?Y ?X)

      then (TURN 90)

      then (HAVE ?RECIPIENT ?GIVEN)
      and *delete* (HAVE ?GIVER ?GIVEN)

      then *do* (SAY [?V + /ID/])

  • A working memory, representing the system's short-term knowledge, what it knows about the current situation
    • The system starts with a particular working memory as its input; this is the description of the current problem.
    • As rules apply, they may add things to working memory or delete things from working memory.
    • Examples
      
    (GAVE LUCINDA PEACH23 WILLARD)
    (ABOVE IMU_FLOOR1 IMU_MEZZANINE)
    (STRESSED (SYLL "MER"))
    (SEQUENCE E1 E2 E3 E4)
    (GROUPING (GROUPING E1 E2) (GROUPING E4 E5))
• An algorithm for running the production system
  • Repeatedly do the following
    • Pick a rule whose conditions match the patterns in working memory.
      (If more than one rule matches, use some conflict resolution strategy to pick one over the other.)
    • Execute the right-hand side of the rule (by adding the specified pattern to working memory, deleting the specified pattern from working memory, or carrying out the specified action in the "world")
  • Stop if no rule applies if the system goes past some pre-specified time limit.

Examples

• English stress
  • Rules
    1. if (node phrase ?x ?y)
       then (stress right ?x ?y)
       and *delete* (node phrase ?x ?y)
    2. if (node ?type ?x (foot ?y ?z))
       then (stress right ?x (foot ?y ?z))
       and *delete* (node ?type ?x (foot ?y ?z))
    3. if (node ?type ?x ?y)
       then (stress left ?x ?y)
       and *delete* (node ?type ?x ?y)
    4. if (node word ?x nil)
       then (stress left ?x nil)
       and *delete* (node word ?x nil)
  • Working memory
    1. (node foot mer i)
    2. (node foot (foot mer i) can)
    3. (node word a (foot (mer i) can))
    4. (node word dream nil)
    5. (node phrase (word a mer i can) (word dream))
  • Conflict resolution: pick the first rule which matches
  • What happens when we run it
    1. Rule 1 matches clause 5 in WM. There are two actions:
       add (stress right (word a mer i can) (word dream))
       delete (node phrase (word a mer i can) (word dream))
       Working memory
       1. (stress right (word a mer i can) (word dream))
       2. (node foot mer i)
       3. (node foot (foot mer i) can)
       4. (node word a (foot (mer i) can))
       5. (node word dream nil)
    2. Rule 2 matches clause 4.
       Working memory
       1. (stress right a (foot (mer i) can))
       2. (stress right (word a mer i can) (word dream))
       3. (node foot mer i)
       4. (node foot (foot mer i) can)
       5. (node word dream nil)
    3. Rule 3 matches clause 3.
       Working memory
       1. (stress left mer i)
       2. (stress right a (foot (mer i) can))
       3. (stress right (word a mer i can) (word dream))
       4. (node foot (foot mer i) can)
       5. (node word dream nil)
    4. Rule 3 matches clause 4.
       Working memory
       1. (stress left (foot mer i) can)
       2. (stress left mer i)
       3. (stress right a (foot (mer i) can))
       4. (stress right (word a mer i can) (word dream))
       5. (node word dream nil)
    5. Rule 4 matches clause 5.
       Working memory
       1. (stress left dream nil)
       2. (stress left (foot mer i) can)
       3. (stress left mer i)
       4. (stress right a (foor (mer i) can))
       5. (stress right (word a mer i can) (word dream))
    6. No more rules match
• A more complicated example involving inference
  • Rules

    if 	  (mushroom ?c) & (orange ?c)	   R1
    then 	  (edibility ?c delicious) 
    
    if	  (edibility ?d edible)            R2
    then	  (not (edibility ?d poisonous)) 
    
    if	  (edibility ?e poisonous)	   R3
    then	  (not (edibility ?e edible)) 
    
    if	  (edibility ?f delicious)	   R4 
    then	  (edibility ?f edible) 
    
    if	  (edibility ?g delicious)	   R5 
    then	  (nutrition ?g low) 
    
    if	  (higher-than ?i ?j) &            R6
                (edibility ?j edible)
    then	  (edibility ?i edible) 
    
    if	  (claim ?m (edibility ?n ?o)) &   R7
                 (reliable ?m)
    then 	  (edibility ?n ?o)
    

  • Working memory

    (mushroom m1)
    (reliable regis)
    (claim regis (edibility m1 delicious))
    (higher-than m2 m1)
    (higher-than m3 m2)
    

  • Conflict resolution
    • Don't allow a rule to match the same set of clauses more than once.
    • Pick the first rule that matches.
  • What happens when you run it
    1. Rule 7 matches with ?m = regis, ?n = m1, ?o = delicious
       Added to WM: (edibility m1 delicious)
    2. Rule 4 matches with ?f = m1
       Added to WM: (edibility m1 edible)
    3. Rule 2 matches with ?d = m1
       Added to WM: (not (edibility m1 poisonous))
    4. Rule 5 matches with ?g = m1
       Added to WM: (nutrition m1 low)
    5. Rule 6 matches with ?i = m2, ?j = m1
       Added to WM: (edibility m2 edible)
    6. Rule 2 matches with ?d = m2
       Added to WM: (not (edibility m2 poisonous))
    7. Rule 6 matches with ?i = m3, ?j = m2
       Added to WM: (edibility m3 edible)
    8. Rule 2 matches with ?d = m3
       Added to WM: (not (edibility m3 poisonout))
    9. No more rules match

Take me back to the Rhythm and Cognition Home Page.

Last updated: 14 November 1995
URL: http://www.indiana.edu/~gasser/rules2.html
Comments: gasser@salsa.indiana.edu
Copyright 1995, The Trustees of Indiana University