Architectural Patterns: Blackboard

Intention

This pattern comes from the Artificial Intelligence community

(The idea behind it worths a wider context)

It is useful in poorly-structured, or simply new and immature domains

We often have only patchy knowledge to arrive at solutions, even if they are sub-optimal or not guaranteed

When the application domain matures with time, designers often abandon the Blackboard architecture and develop architectures that support closed solution approaches

But, some domains are "never" well defined in general (such as voice and image recognization ... different ways of saying english, different essent in english, etc)

Introduction

The Blackboard architectural pattern is useful for problems for which no deterministic solution strategies are known

In this pattern, several specialized subsystems assemble their knowledge to build a possibly partial or approximate solution

Example

Building a software system for speech recognition

Input is speech recorded in waveform in single words as well as whole sentences

Restricted to syntax and vocabulary need for a specific application such as database query

Output is machine representation of English phrases (often used tuples)

The transformations involved linguistic, acoustic-phonetic and statistical expertise

We assume (which is true today) that there is no consistent algorithm that combines all the necessary procedures for recognizing speech

The problem is worse when it is affected by ambiguities of spoken language, noisy data, the individual peculiarities of speakers such as vocabulary, pronunciation and syntax

Context

An immature domain in which no closed approach to a solution is known or feasible

Problem

Besides voice, vision, image recognition, speech recognition and surveillance are examples of immature domain. Some people will group "mining" as one of them as well

So, we might have to work with uncertain or approximate knowledge

Each "transformation" step can also generate several alternative solutions ... then we will have to find the optimal solution

We have to balance the following forces:

A complete search of the solution space is not feasible

Need to experiment with different algorithms for the same subtask

Different algorithms might only solve partial problems

Input, as well as intermediate and final results have different representations, and the algorithms are implemented according to different paradigms

An algorithm usually works on the results of othe algorithms

Uncertain data and approximate solutions are involved, so we have to pick and choose

Using disjoint algorithms induces potential parallelism

Solution

The idea is to use a collection of independent programs that work cooperatively on a common data structure

Each program is specialized for solving a particular part of the overall task, and all programs work together on the solution

Specialized programs are independent of each other (they might still use the output from each other)

They do not call each other, nor is there a predetermined sequence for their activation

The direction taken by the system is mainly determined by the current state of progress

A central control component evaluates the current state of processing and coordinates the specialized programs

This data-directed control regime is referred to as opportunistic problem solving. It allows experimenting different algorithms possible and allows experimentally-derived heuristics to control processing

During the problem-solving process, the system works with partial solutions that are combined, changed or rejected

Each of these solutions represents a partial problem and a certain stage of its solution

The set of all possible solutions is called solution space and is organized into levels of abstraction

Lowest level is the internal representation of the input and

Highest level is the potential solutions

Blackboard is used to describe the situation where a group of human experts sit in front of a real blackboard and work together to solve a problem

So, partial solutions are "posted" to the blackboard for further processing

And, if there is a solution, the final solution will be posted on the blackboard

Structure

Divide your system into 1. Blackboard, 2. A collection of knowledge sources, 3. Control Component

Blackboard is the central data store for solution space and control data (we called that vocabulary)

Blackboard provides interface that enables all knowledge sources to read from and write to it

We use the term hypothesis or blackboard entry for solutions that are constructed during the problem solving process

Hypotheses has level of abstraction (how far we are from the input), estimated degree of truth, and/or time interval covered as attributes

Note that the blackboard can be viewed as a three-dimensional problem space with the time line for the subject (such as speech) on the X-axis, increasing levels of abstraction on the Y-axis and alternative solutions on hte Z-axis

Knowledge sources are separate, independent subsystems that solve specific aspects of the overall problem. Sometimes they are called "World Knowledge".

Together, knowledge sources model the overall problem domain

A solution can only be built by integrating the results of several knowledge sources

They do not communicate directly - they read and write to the blackboard. So, they have to understand the vocabulary of the blackboard

Knowledge source often do transformation with forward reasoning (from lower level solution to higher level solution)

Knowledge source sometimes does backward transformation which searches at a lower level for support for a solution and may refer it back to a lower level if the reasoning did not give support for the solution

Each knowledge source is responsible for knowing the conditions under which it can contribute to a solution, so it often splits into condition-part and an action-part

Condition-part (inspects) looks at the blackboard for current state and if there is anything can be done

Action-part (updates) takes the necessary action to the current blackboard contents

The control components runs a loop to monitor the changes on the blackboard

It will pick a knowledge source and decide what action to take next according to a knowledge application strategy

The basis for this strategy is the data on the blackboard

There is a sub-component called control knowledge source which does not contribute directly to solutions, but perform calculations on which control decisions are made (they do estimation of potential for progress, computational cost for execution of knowledge sources, etc)

Two problems:

• There might be two many hypotheses / alternative to consider (so we have to limit the choices)
• There might not be an answer (so we have to tell the users)

So, the control component should halt the system if there is an acceptable hypothesis is found, or when the space or time resources of the system are exhausted

Blackboard ---------- operates on -------- Knowledge Source 
     |                                           |
     |                                        activates
     |                                            |
     ----------------------------------------- Control

Dynamics

Scenario using the speech recognition example

The main loop of Control started

Control calls nextSource() to select the next knowledge source

nextSource() looks at the blackboard and determines which knowledge sources to call

For example, nextSource() determine that Segmentation, Syllable Creation and Word Creation are candidate

nextsource() invokes the condition-part of each candidate knowledge source

The condition-parts of canndidate knowledge source inspect the blackboard to determine if and how they can contribute to the current state of the solution

The Control chooses a knowledge source to invoke and a set of hypotheses to be worked on (according to the result of the condition parts and/or control data)

Apply the action-part of the knowledge source to the hypothesis

New contents are updated in the blackboard

 

Implementation

Define the problem: Specify the domain, input to the system, output to the system, interface, etc

Define the solution space for the problem (intermediate vs top-level, partial vs complete)

Specify exactly what constitutes a top-level solution

List the different abstraction levels of solutions

Organize solutions into one or more abstraction hierachies

Find subdivisions of complete solutions that can be worked on independently, for example, words of a phrase or regions of a picture or area

Divide the solution process into steps

How solutions transformed from one level to another higher level

How to predict hypotheses (rule base ?)

How to verify hypotheses (searching in a db ?)

Specify what world knowledge / konwledge sources can be used

Divide the knowledge into specialized knowledge sources with certain subtasks

Define the vocabulary of the blackborad (tuples, rules, math symbol ?)

Specify the control of the system (classified into categories to work on, creating a queue, etc)

Implement the knowledge sources (database of tuples, rules ?)

 

Variants

Production System from AI for solving problems with conflict resolution module

Repository

Repository vs blackboard

Action not determined mainly by internal states, can be determined by user input, etc

 

 

Known uses

HEARSAY-II, HASP/SIAP, CRYSALIS, TRICERO, Generalizations, SUS, Some data mining packages

 

 

Consequences

Advantages

Support for experimentation

Changeability and maintainability ?

Reusable knowledge sources

Fault tolerance and robustness

Disadvantages

Difficulty of testing

No good solution is guaranteed

Good Control is hard to build

Low efficiency

High development effort

Low support for parallelism (because of communication mainly using blackboard)