<- Architecture I  home  

 

T-877-AUTO-2010-2 Autonomous Robots

Architecture II

 

February 11, 2010

 

 

 

1
Outline of Topics
  Concepts and terms  
  Blackboards  
  Daemons, experts & parallel execution  
  Blackboard example (speech processing)  
     

 

 

 

 

 

 

 

 

 

 

 

2
Concepts and terms
  Expert, daemon, specialist, knowledge source An expert is a process that collaborates with other processes to find a solution to a problem. Often they use a Blackboard for this purpose.
  Blackboard Think "shared memory space" - a storage of information where experts can put and get information from
  Agent, module Generic term that can be applied to any free-running, semi-independent entity in an AI system
  Layer In an architecture, layers group agents/modules.
     

 

 

 

 

 

 

 

 

 

 

 

3
Blackboards
  What it is

"Imagine a group of human specialists seated next to a large blackboard. The specialists are working cooperatively to solve a problem, using the blackboard as the workplace for developing the solution.

Problem solving begins when the problem and initial data are written onto the blackboard. The specialists watch the blackboard, looking for an opportunity to apply their expertise to the developing solution. When a specialist finds sufficient information to make a contribution, she records the contribution on the blackboard, hopefully enabling other specialists to apply their expertise. This process of adding contributions to the blackboard continues until the problem has been solved." [REF]

  When was it first proposed? 1959, in a paper by Oliver Selfridge, MIT.
  What it is composed of
  • Experts: Processing entities with domain expertise
  • Blackboard: Common data storage through which knowledge sources communicate
  • Control system, for deciding:
    • which experts should get which information
    • when experts should return results (how long they run)
  How does it work

The key is how experts are triggered by information that appears on the BB. This can be done in the BB or in the expert, or in both places.

Method I ("Soviet model"): The BB has a list of which experts are relevant for any kind of content. When content X appears on the BB, the BB will match it with its list of experts and send X to those experts that seem to be able to process and respond to it.

Method II ("market model"): In this version the BB is a dumb information bus (infobus); the BB has a complete list of all experts that exist and will simply forward all information that comes in to every expert. The experts will then have to decide, each for themselves, which of the information they are capable of acting upon.

Variation: Most systems are hybrids - a combination of the two extremes above, as method I puts too much burden on the BB and method II too much burden on the experts.

     

 

 

 

 

 

 

 

 

 

 

4
Blackboard example: Determining Part-of-Speech for misspelled sentences
  Example scenario Imagine a system that is trying to identify the words in a collection of misspelled writings. (Alternatively, imagine a system that is supposed to correct in real-time misspellings in an instant messaging system.) The system uses experts to propose various interpretations of the tokens as they arrive - tokens such as dawg, aite, and tha - which may not map directly to a single word or concept. This example shows the operation of a set of experts that tries to figure out the part-of-speech* of the tokens, based on a mapping from the tokens to known words.
  Given PoS: Part-of-speech
H: hypothesis
E : patterns describing the expertise of experts
P: pattern that describes a problem
  Example patterns, intended to be processed by experts (P (PoS dawg ?))
(P (PoS aite ?))
  Experts announce their expertise to the BB, in the form of a pattern
(question mark means "any value")
(PoS-Verb-Expert-X (E (PoS x ?)))
  Patterns arrive on the BB (pattern set S) (P (PoS the ?))
(P (PoS dawg ?))
(P (PoS aite ?))
(P (PoS tha ?))
(P (PoS bown ?))
  BB has list of PoS experts, e.g. PoS-Noun-Expert-1

Upon receiving a problem pattern, the BB matches it against the patterns of each expert.
In this example the BB finds expert PoS-Verb-Expert-1 to be relevant for all the problems, as the last part, (PoS x ?), of

(PoS-Noun-Expert-1 (E (PoS x ?)))

matches all problems posted in S.

  Hypotheses Posted by experts to the BB
  Resulting BB contents after PoS-Noun-Expert-1 has processed the Ps in S (H (PoS dawg noun))
(H (PoS bown noun))
  Resulting BB contents after PoS-Adjective-Expert-1 has processed the Ps in S

(H (PoS dawg noun))
(H (PoS bown noun))
(H (PoS bown adjective))
*

  Sidenote

The experts would probably post the spelling of the words that they hyopthesize the tokens to stand for, e.g. (H (PoS bown brown adjective)) and (H (PoS bown bone noun)).

They might also include an estimated probability that their hypothesis is correct: (H 0.7(PoS bown brown adjective))

  When all PoS experts have finished processing

(H (PoS the det))
(H (PoS dawg noun))
(H (PoS aite verb))
(H (PoS the det))
(H (PoS bown verb))
(H (PoS bown adjective))

     

* part-of-speech = orðflokkur

* adjective = lýsingarorð