Rule-based systems

• easy knowledge acquisition
• simple control

But

• as # of rules increase - inference
• loss of efficiency
  (check all rules for match)
  ... rules often applied in clusters
• p-s techniques and knowledge rep.
  not same for all problems

  Need Modularity -

  tasks/subtasks (generic tasks)

  problems: how can an agent know which task, and how to communicate between them, how are they 'connected' ?

  early work in AI used "agendas"

  Agendas

  (use of modules)

  Agenda: a list of tasks a system could perform

  - with each task is included:

  1. a list of reasons why the task is being proposed (justifications)
  2. a rating representing the overall weight of evidence suggesting that the task would be useful

  Operation...

  1. Choose the most promising task from the agenda (task rep ? ADT's... any rep.)
  2. Execute the task by devoting to it the number of resources determined by its importance.

  For each task generated from (2)

  • see if it is already on agenda...
    and for the same reason (insert if not)
  • compute task rating

  - How does one find the most promising task on each cycle?

  • maintain the agenda sorted by rating
    (when task has justif. changed- recompute)
  • when task proposed - compare only against top few
    (low level control methodology: Best-first search)

  Blackboards

  More recently, AIers have seen that the central issue of problem solving deals with the question:

  "What pieces of knowledge should be applied when and how?"

  A problem solving model provides a conceptual framework for organizing knowledge (form and content) and a strategy (control mechanism) for applying that knowledge.

  Blackboards encapsulate knowledge into manageable and relatively independent chunks

  Hume, James, Dennett (time out for philosophy)

  Master Homunculus Theory:

  The mind cannot be the sum of its parts because we need the mind to do the summing and to acknowledge the addition.

  But one and the same entity cannot be one of the elements being added and the adder...so need a "master". MH is like consciousness of the whole.

  But this leads to an infinite regress.

  Eg. Say MH is in area Omega. Ask, "Am I conscious of this fact?" But I cannot say I comprehend that area Omega is the seat of consciousness with area Omega because then there is no comprehender outside.

  The Blackboard model is usually described as having 3 major components:

  - The Knowledge Sources: separate&independent

  - The Blackboard data structure: global database

  - Control: KS's respond opportunistically (event-driven) to changes in the blackboard

  "It does no good to have great ideas if they cannot be communicated" - Anne Keuneke ;-)

  notice: different than subroutines - many tasks are computing simultaneously - demons trigger when useful info is available. Basically control is Scheduling all others (MH).

  HEARSAY - 1980 - Speech Understanding

  Entire system consists of a set of independent modules (knowledge sources KS's)

  that contain domain-specific knowledge and a blackboard - a shared data structure to which all the KS's have access. (like demons - triggers)

  Mechanisms that affect a message (speech):

  • psychology of the speaker
  • semantics
  • rules of discourse
  • syntax
  • lexicon (meaning of word)
  • prosodic system (science/art of versification)
  • phonemic system (distinguish utterances)
  • speaker's artculatory apparatus
  • ambient environmental noise
  eg. till Bob rings

  tell Bob rings

  till Bob brings

  tell Bob brings

  eg. script C/-\T

  Interpretations: higher level interpretations incorporate lower level ones

  Hypotheses on the blackboard are arranged along two diminsions:

  level - (from small, low-level hyp. about individual sounds to large, high-level hyp. about the meaning of the entire sentence)

  time - time periods of the utterance being analyzed

  Associated with each KS is a set of triggers for activation

  When a trigger fires, it creates an activation record describing

  1. the KS that should be activated and
  2. the specific event that fired the trigger.
  The determination of which KS should be activated next is done by a special KS called the Scheduler. (like Executive in Hayes-Roth)

  Main Points:

  Modularity with respect to task

  Communication

  HEARSAY III

  • - domain-independent blackboard shell

  • - time dimension removed (not appropriate for all domains)

  • - two blackboards:
    hypotheses about problem (units)
    scheduling (broken down into set of independent KS about scheduling)

  more later, but first other examples:

  Blackboards - Hayes-Roth (Stanford)

  BB1 blackboard control architecture

  Hierarchical family of tools used to modify the

  global data structure called the blackboard:

  Top level:

  Knowledge structures for representing all actions, states, events, and facts in a system.

  Wide range of problem classes, methods, and domains. This level is control of overall system.

  A system may have 3 classes of know. sources.

  1. domain knowledge sources

  2. control knowledge sources

  3. learning knowledge sources (modify KSs and facts in knowledge base)

  Next level:

  Knowledge structures for representing all actions, states, events, and facts involved in addressing a particular class of problems with a particular problem-solving method.

  (Generic Tasks)

  Lowest level:

  Individual applications for particular classes of problems with particular problem-solving methods in particular subject-matter domains

  (Domain knowledge)

  Boeing Blackboard System

  derived from BB1

  In problem-solving ... use of "domain-specific problem solving strategies". not well said

  significance of user-interface

  note term: event-driven system

  HEARSAY III

• domain
• independent

• scheduling is so complex a task that an approach is needed to build adequate schedulers

  Generalizations from Hearsay II to III:

• aggregate several interpretations at one level into composite interpretation at a higher level

  (abstraction capabilities...like HH rules in VPExpert. Notice all of these issues can arise at different levels

• within a problem or between problems)

• manipulating alternative interpretations

  (Interpretations conflict and there may be alternatives. Allocate resources among competing interpretations. Critics & evaluators

• criticizing proposed interpretations

  The complexity of scheduling introduced:

  a separate scheduling blackboard, thus

  • two blackboards:
    • hypotheses about problem (units)
      (competence knowledge)
    • scheduling (broken down into set of independent KS about scheduling)
      (performance knowledge)
    This blackboard has a data base consisting of dynamically created activation records of KSs

  • the ks that should be activated

  • the specific event that fired the trigger

  The organization of these activations (with agendas, priorities, etc) is left to the application writer.

  In Hearsay II, nodes on the blackboard, which represented partial interpretations, were called hypotheses.

  In Hearsay III, the more neutral term used -units. Hearsay III provides primitives for creating units and aggregating them

  Each unit is created (runtime) as an instances of some class

  Classes:

  Unit with subclasses of DomainUnit

  SchedulingUnit

  these subclasses serve to define the two blackboards.

  All other subclasses are declared by the application writer, appropriate to the domain