Verteilte KI

Verteilte Künstliche Intelligenz - Uni Ulm WS95/96

9 Blackboardsysteme

Metaphorically we can think of a set of workers all looking at the same blackboard: each is able to read everything that is on it and to judge when he has something whorthwhile to add to it. This conception is just that of Selfidge's Pandemonium: a set of demons each independently looking at the total situation and shrieking in proportion to what they see that fits their natures.

Newell 1962

Literatur: Durfee E.H., 1988: Coordination of Distributed Problem Solvers, Kluwer Academic Publshers, Boston. V. Jagannathan et al., 1993: Blackboard Architectures and Applications. Academic Press, London.

9.1 Geschichtliche Entwicklung von Blackboardsystemen

Im Gegensatz zu vielen anderen methodischen Bereichen, stand eine Anwendung am Anfang der Entwicklung von Blackboardsystemen

* HEARSAY II -
Erman L.D., Hayes-Roth F., Lesser V.R., Reddy D.R.
Aufgabenstellung: Sprachverstehen (um 1980)
insuläres Wachstum von Blackboardsystemen

* GBB Generic Blackboard Development System (um 1985)
Corkill D.D. Gallagher K.Q., Murray K.E., Lesser V.R.
(University of Massachusetts, Armherst)

GBB - Fokus auf einem effizienteren Zugriff auf das Blackboardsystem, musterbasiertes Retrieval, Aufteilung in hochstrukturierte Ebenen

* BB1
Hayes-Roth B., um 1985, University of California
Generalisierung der Blackboardarchitektur unabhängig vom Sprachverstehen, das erste Blackboardsystem, das explizit das Kontrollwissen repräsentierte und ähnlich dem Domainenwissen als Ausgangs- und Zielpunkt des Schließens darstellte

9.2 Aufbau von Blackboardsystemen

* Wissensquellen: Das Problemlösungswissen wird auf mehrere Wissensquellen aufgeteilt, die unabhängig von einander arbeiten.

* Blackboard-Datenstruktur: Die Daten, die den Zustand der Problemlösung beschreiben, werden in einer globalen Datenstruktur, dem Blackboard gehalten

* Kontrolle: Die Wissensquellen reagieren auf Änderungen des Blackboards durch eigene Änderungen.

Blackboardsysteme bieten nicht direkt eine Lösung für eine spezielle Problemklasse, z.B. Produktionensysteme für die Diagnose, sondern "a general framework for couching solutions". (Erman) , d.h. allgemeine Organisationsprinzipien werden angeboten, konzeptionelle Hinführung zu Lösungen und kein Berechnungsmodell

Blackboard als:

* Kommunikationsmodell (vs. Direktes Messagepassing zwischen Agenten, z.B. RATMAN)

* Problemlösungsmodell (z.B. vs. "Produktionensysteme" )

* als abstrakte Rahmenstruktur, um Probleme zu beschreiben, bezgl. der Domaine als auch bezgl. der Kontrollstrukturen

9.2.1 Wissensquellen

* Wissensquellen entsprechen Wissensbasen, d.h. domänenabhängiges, problemspezifisches Wissen, das zur Gesamtlösung des Problems geeignet ist.

* Repräsentation von Wissensquellen in Form von Prozeduren, Regelmengen oder logischen Aussagen

* Wissensquellen verändern ausschließlich das Blackboard oder Kontrollstrukturen (die auch als Blackboard repräsentiert sein können)

* Jede Wissensquelle verfügt über das Wissen, wann sie aktiv werden muß.

opportunistische Auswertung des Blackboards, Intention: mögliche Parallelisierung

9.2.2 Blackboard-Datenstruktur

* Aufnahme von Daten für den Problemlösungs- und den Berechnungszustand

* die Objekte und ihre Eigenschaften definieren das Vokabular des Lösungsraumes

* Aufnahme der Kontrollinformation

* Hierarchische Struktur des Blackboards, wobei die Objekte häufig genau einer Ebene des Problemlösungsprozesses zugeordnet sind.

BB-Objekte werden entsprechend ihrer Nähe zu der Ausgangsproblemstellung angeordnet

Spezielles Problem: Zugriffsgeschwindigkeit bei großen Blackboards, d.h. Effizienz im Ablegen und Auffinden von Objekten auf dem Blackboard, geeignete Strukturierung und Indezierung der Objekte, vgl. dazu GBB

9.2.3 Kontrolle

* eine datengetriebene Aufruf von Wissensquellen führt typischerweise zu mehreren ausführbaren Handlungen der Wissenquellen; die Auswahl der Handlung, die ausgeführt werden soll, ist Aufgabe der Kontrolle.

* aufgrund unterschiedlichem Kosten/Nutzen von Aktionen, ist die Kontrolle wesentlich für die Güte eines Blackboardsystems (vgl. z.B. bei Guardian, anytime Algorithmen)

* Überwachung des Blackboards durch Kontrolleinheiten, Selektion der nächsten auszuführenden Aktion (bei nebenläufigem Zugriff)

* Es werden Foki bestimmt (bezgl. Wissensquelle oder Blackboardebene)

* Unterscheidung in bzw. Integration von Daten- und Zielgerichtete Kontrolle

* Schrittweise Problemlösung

9.3 Problemlösungszyklus (vereinfacht)

1) Eine Wissensquelle verändert das Blackboard.

2) Speicherung in der globalen Datenstruktur

3) Jede Wissensquelle gibt an, welchen Beitrag sie zu dem neuen Stand der Problemlösung beitragen kann.

4) Diese Information werden von einem Kontrollmodul genutzt den Fokus einzustellen.

i) Falls der Fokus auf eine Wissensquelle gerichtet ist, dann wird eine Menge von Blackboardobjekten ausgewählt, die als Kontext für die Ausführung der Wissensquelle dienen (Wissensgetriebener Ansatz: knowledge-scheduling approach)

ii) Wenn der Fokus auf ein Blackboardobjekt gerichtet ist, wird diejenige Wissensquelle ausgesucht, die das Objekt verarbeiten kann.

iii) Falls Wissensquelle und BB-Objekt im Fokus stehen, wird die Wissensquelle im Kontext des BB-Objektes ausgeführt.

9.4 Problemlösungsverhalten

* Kontrollmodule prägen das Problemlösungsverhalten

* Eine Wissensquelle transformiert Inputs in Outputs, i.A. liegen die Objekte des Inputs und Outputs in einem hierarchisch angeordneten Blackboard auf unterschiedlichen Ebenen

* weg von den Rohdaten hin zu höheren Ebenen, bottom up oder vorwärts (datengetrieben)

* höherer Ebene der Inputs, top down oder rückwärts (zielgetrieben)

Definition von Blackboard-Systemen beschreibt allgemeine Organisationsprinzipien, d.h. sie bildet eher ein konzeptionelles Rezept zur Erstellung von BB-Systemen als ein ausführbares Berechnungsmodell.

vor der Entwicklung von Generischen BB-Systemen (allgemeineren Berechnungsmodellen) stand daher die Konzeption und Implementation von BB-Systemen, die an konkreten Problemstellungen ausgerichtet waren, z.B. Hearsay III .

9.5 Black Board Systeme

Eine Auswahl von Anwendungen

Hearsay-II Sprachverstehen

HASP Interpretation von Ultraschalldaten

CRYSALIS Bestimmung der 3-D Struktur eines Proteinmoleküls anhand der Elektronendichtekarte, die durch Berechnung von Röntgenstrahlen am krstallisierten Protein bestimmt wird.

OPM Planung von Botengängen

DVMT Erkennung von Fahrzeugbewegungen

eine Auswahl von generischen Systemen

HEARSAY-II war der Ausgangspunkt für die Entwicklung von GBB.

* AGE

* CAGE and POLIGON

* BB1

* GBB

9.5.1 AGE

* Implementation eines seriellen Blackboard Systems mit

Wissensquellen, die eine strukturierten Problemlösungsraum angeben

Blackboard, wo die Wissensquellen eigene Ergebnisse ablegen und die von anderen Wissensquellen lesen können, strukturierung in Ebenen

Änderungen des Blackboards werden als Ereignisse aufgefaßt

* der Scheduling Mechanismus (Controller) aktiviert eine Wissenquelle zu einem Zeitpunkt getriggert durch die vorangegangenen Ereignisse

9.5.2 HEARSAY-II

Domänenabhängige Umgebung für die Erstellung von Blackboardsystemen, führte eine Agendaorientierte Architektur für die Kontrolle ein. In jedem Zyklus wurden die anzuwendenden Wissensquellen auf eine Agenda gelegt um danach entsprechend spezieller Heuristiken eine Auswahl vorzunehmen. Integration verschiedener Heuristiken in den Schedulingprozess,

Aufgabe: Einen gesprochenen Satz verstehen und ihn als Anfrage an eine Datenbasis zu interpretieren. Die Datenbasis enthält eine Sammlung von KI-Artikeln.

Blackboard-Datenstrukturen:

* 7 Analyseebenen

* Jedes Element entspricht einer Hypothese, die durch ihren Wert, ihre Gültigkeit und ihre Abstraktionsebene charakterisiert ist.

* wg. der Unsicherheit des Problemlösungsprozesses ist es notwendig, viele Alternativen zu speichern

Wissensquellen:

* besitzen Bedingungs- und Aktionsteil, generieren Hypothesen

Kontrolle:

* Kontrolle prozedural, Monitor und Scheduler

* Aufgabe des Monitors: Suche der Wissensquelle, deren Bedingungsteil von der jüngsten Änderung des Blackboards betroffen ist, Speicherung von Verweisen auf diesen Bedingungsteil in einer Scheduling Warteschlange, Speicherung von Verweisen auf die für die Ausführung bereiten Aktionsteile, beide Informationen werden als Aktivitäten bezeichnet

* Aufgabe des Schedulers: Benutzt Heuristiken, die aufgrund von Experimenten entwickelt wurden, um Prioritäten zu berechnen und die Aktivität mit der höchsten Priorität auszuwählen. Der Bedingungsteil besteht aus einem Stimulus-Frame - eine Menge von Hypothesen, die den Bedingungsteil erfüllen, und ein Antwort Frame, eine abstrakte Beschreibung von Änderungen des Blackboards, die die Ausführung des Aktionsteils der Wissensquelle bewirken würde.

Problemlösungszyklus:

* Der Scheduler wählt eine Aktivität aus

* Falls die ausgewählte Aktivität ein Bedingungsteil ist, dann wird er ausgewertet, und falls er erfüllt ist, wird eine Menge Stimulus/Antwort Frames zusammen mit einem Verweis auf die entsprechende Wissensquelle in die Scheduling Warteschlange eingetragen

* Falls die ausgewählte Aktivität ein Aktionsteil ist, werden die Änderungen auf dem Blackboard vorgenommen, ausserdem wird dem Monitor Verweise auf Wissensquellen bekanntgegeben, die als nächstes ausgeführt werden können.

9.6 Parallele Blackboardsysteme

z.B. CAGE und POLIGON

Beides Erweiterungen von AGE (An Attempt to Generalize), die eine Parallelverarbeitung erlauben

CAGE Die Zielmaschine ist eine Multiprozessormaschine mit gemeinsamen Hauptspeicher (shared Memory)

POLIGON Die Zielmaschine ist ein verteiltes System ohne gemeinsamen Hauptspeicher (message passing).

Parallelisierung:

* Einzelne Wissensquellen können parallel ausgeführt werden und mehrere Wissensquellen können zueinander parallel ausgeführt werden.

* Pipeline - Folgen von Wissensquellen als Pipelining

* Datenparallelität - An einzelnen Lösungskomponenten kann parallel gearbeitet werden (z.B. kann das BB in mehrere Ebenen unterteilt werden, die parallel bearbeitet werden können)

* Kontrollparallelität

Probleme der Parallelisierung

* Konkurrenz um Ressourcen, bei shared memory, um Speicherzugriff, bei verteilten Systemen z.B. Kommunikationsmittel

* Prozeßerzeugung - um Teilprobleme parallel ablaufen zu lassen müssen sie durch einen eigenen Prozess ausgeführt werden.

Wichtige Konzepte für die Parallelisierung

* Definition von Atomaren Operationen

* kritische Bereiche ununterbrechbar ablaufende, komplexere Programmteile

* Definition von Synchronisationsprimitiven

* Sperrmechanismen

* Pipeline - eine Menge von Operationen, die parallel ausgeführt werden können aber sequentiell voneinander abhängen (vgl. Montagestrasse)

9.6.1 Alternatives Design für Parallele und Verteilte BB Systeme
"Shared Memory Blackboard Approach"

+---------------+ | KSI Queue | ---------------> +---------------+ <-------------- || /\ || \/ || \/ Processor Processor Processor /\ || /\ || \/ || || +-------------------------+ || -----------> | | <-------- | Blackboards | | | +-------------------------+

* direkte Abbildung des Paradigmas kooperierender Wissensquellen (Experten) auf der Basis eines Blackboards.

* Zwei Zuordnungen von Wissensquellen auf Prozessoren

Funktional: Jede Wissensquelle ist einem Prozessor zugeordnet, ein Prozessor ist verantwortlich für die Ausführung aller Instanzen einer Wissensquelle, falls mehr als eine Instanz ausführbar ist, werden diese in Schlangen verwaltet, Ideal falls die Ausführung von unterschiedlichen Wissensquellen unterschiedliche Anforderungen an die Hardware stellt, Problem falls die Wissenquellen nicht einheitlich ausgelastet sind,

Computational Server - Jeder Process kann alle Wissensquellen ausführen, Spezialisierungen der Rechnerresourcen ist ebenfalls möglich (preferential scheduling)

9.6.2 Alternatives Design für Parallele und Verteilte BB Systeme
"Distributed Blackboard Approach"

* Jeder Prozessor hat ein separates, lokales Blackboard, welches Objekte enthält die lokal kreiiert wurden und Kopien von Objekten, die der Knoten von anderen Knoten erhalten hat,

* falls die Kommunikation zwischen Prozessoren durch Übertragungs- und Verzögerungsrate zu aufwendig wird, ist die Idee eines zentralen Blackboards nicht aufrecht zu halten, d.h. jeder Prozessor erhält ein eigenes Blackboard, für seine privaten Problemlösungen, wichtige Ergebnisse werden zu den anderen hin kommuniziert.

* Zentrale Designentscheidung bei DBB: Welche Überschneidung der Blackboards ist notwendig ?

(vollständige impliziert, daß alle anderen Knoten über Änderungen ständig informiert werden, disjunkte Gestaltung bedeutet, sobald ein Knoten ein Objekt außerhalb seiner eigenen Domaine benötig, muß eine Kopie von einem Nachbarn angefordert werden, Kopien können über REQUEST oder INFORM ausgetauscht werden),

Antizipation von Bedürfnissen,

Bewertung von Information nach ihrer Sicherheit und Wichtigkeit

* Zentral: Wissen über die Bedürfnisse und Fähigkeiten anderer Knoten

Bsp. für ein DBB: DVMT

9.6.3 Alternatives Design für Parallele und Verteilte BB Systeme
"Blackboard Server Approach"

* im Gegensatz zum SMBB erlaubt der BBS keine mehrfach Zugriffe auf das Blackboard, eine einzige Version jedes Blackboardobjektes, keine Kopien,

* Aufteilung des Blackboards in nicht-überlappende Bereiche, für jeden dieser Bereiche ist ein Server zuständig

* Falls ein Objekt außerhalb der eigenen Zuständigkeit eines Servers werden indirekt über den geeigneten Serverknoten angesprochen

* Entscheidung: Wie wird das Blackboard aufgeteilt?
(Ein Server für das ganze Blackboard (s.o.) <-> jeder Knoten ist auch zugleich Server für einen bestimmten Teil des Blackboards)

* ebenso wie bei DBB ist die Antizipation von Bedürfnissen wichtig, um unnötige Verzögerungen zu vermeiden.

9.6.4 Überblick Alternativen (Schematisch)

	SMBB	DBB*	BBS
Adressraum anforderung	shared heap	keine	keine
BB Zugriffspfad	multiple	einfach	einfach
Kopien	nein	ja	nein
BB Objektzugriff	direkt	direkt	oft indirekt (internode)
BB Objekt Kreiierung	direkt	direkt, gefolgt durch internode	oft indirekt (internode)
BB Objekt Modifikation	direkt	direkt, gefolgt duch internode	oft indirekt (internode)
BB Bereichsüberlappung	-	yes	no

*DBB mit vollständigem Blackboard an jedem Knoten

9.6.5 CAGE Architektur

Shared Memory Multi-Processing Model - SMBB

* die Komponenten von CAGE entsprechen denen von AGE + Definition der parallel auszuführenden Komponenten und der Synchronisationspunkte

* Parallelausführbar sind Wissensquellen, die Regeln in den Wissensquellen, und die Aktionsteile der Regeln

* Synchronisationspunkte können definiert werden, im Kontrollzyklus zwischen der parallelen Ausführung von Wissensquellen, innerhalb einer Wissensquelle nachdem alle möglichen Konklusionen evaluiert wurden,

Wissensquellenparallelität

* entweder arbeiten Wissensquellen an unterschiedlichen Teilen des Blackboards oder in einer Art Pipeline, z.b. auf unterschiedlichen Ebenen des Blackboards

Dateninkonsistenz wird durch die Definition von atomaren Operationen, welche liest und schreibt, eine Blockread Operation liest alle zu einem Objekt vorhandene Information und sperrt das Objekt für andere

Datenkoheränz alle Slots, die in einer Wissensquelle referenziert werden, werden auf einmal gesperrt, d.h. alle Regeln einer Wissensquelle beziehen sich auf Daten zu einem Zeitpunkt gelesen.

9.6.6 POLIGON Architektur

* Spezielle DBB, Struktur. Ein Blackboardknoten ist ein Prozeß auf einem Prozessor umgeben von Prozessoren, die hinzugezogen werden können, um Regeln auszuführen, (fine-grained Parallelism), d.h. pro Knoten könen mehrere Regeln gleichzeitig bearbeitet werden, bzw. einzelne Regeln können von mehreren Prozessoren bearbeitet werden (-> verteiltes Objektorientiertes System)

Idee und Motivation:

* Eliminierung des Schedulingmechanismus und Unterstützung paraller Regelaktivierung

* Optimierung des Designs für distributed Memory, Message Passing Hardware für viele Prozessoren

Spezielle Probleme und Lösungen

* um die Wahrscheinlichkeit, daß ein Knoten zulange gesperrt ist (locked), zu vermeiden, werden Regeln ausgeführt im Kontext eines Snapshot, der den Lösungsraum zum Zeitpunkt des Aufrufes der Regel wiedergibt.

* Um Abwägungen zwischen Kosten einer eigenen Nachfrage, einer Beantwortung von Problemen usw. zu erlauben, werden die einzelnen Knoten als Agenten interpretiert.

9.6.7 DVMT - A Distributed Vehicle Monitoring Testbed
Lesser, Corkill, Durfee

Armherst 1981-
Ziel:

* Untersuchung der Interaktion zwischen mehreren Problemlösern sowie die Untersuchung von koordination und Kohärenz bei der Lösung von verteilten Problemen.

konkret:

* Ein globales Bild von Fahrzeugaktivitäten innerhalb einer Region auf der Basis von Daten, die von räumlich verteilten Sensoren gemessen werden.

Methode

* Basiert auf Menge von identischen Blackboardbasierten Systemen (HEARSAY II) - DBB

Sensoren sind mit Blackboardsystemen gekoppelt, dabei ist jeder Prozessor mit mehreren Sensoren verbunden, wie auch die Sensoren ihre Daten i.a. an mehrere Prozessoren weiterleiten.

* Monitoring und Interpretation von Daten durch Prozessoren, die eine Anzahl von Sensoren interpretieren

Es handelt sich bei den Daten um akustische Daten.

* Kommunikation und Verhandlung bei Inkonsistenzen und Unsicherheiten

Durch die Überschneidungen der Kontrol- und Abhörbereiche, können lokale Unsicherheiten durch Kommunikation zwischen den Prozessoren ausgeglichen werden.

DVMT - Knoten

Die Architektur der Problemlösungskomponenten der Prozessoren sieht folgendermassen aus:

* Die Wissensquellen (Knowledge Sources) sind verantwortlich für die Erweiterung und Verfeinerung von Hypothesen.

* Eine Hypothese besteht aus einer Zeit-Lokalisation, einer Ereignis Klasse, einem Belief-Measure, und dem Blackboardlevel (4 Ebenen - signal, gorup, vehicle, und pattern - werden unterschieden je nach Art der ausgeführten Datenanalysen).

* Die Knowledge Source Instantiations sind potential anwendbare Wissensquellen, die entsprechend ihrer Wichtigkeit angeordnet werden.

* Wenn eine Hypothese formuliert ist, werden Ziele definiert, die es erlauben, diese Hypothese zu verfeinern (zielgetriebene Auswertung)

* Der Goal Prozessor wählt auf der Basis der neuen Ziele, möglicherweise Anwendbare Knowledgesources aus und kreiert daraus, die Knoweldgesourceinstances.

* Zusätzlich wählt er subgoals aus und schreibt sie auf das Goalblackboard.

9.7 Nach(t)gedanken

Charakteristisches für Blackboardsysteme (nach Lee D. Erman):

* "the blackboard world has been predominantly applications-oriented and many prototype papplications have been built"

* "contributing to this insular growth was that all these early practitioners were so caught up in their applications that they presented the ideas and results intimately in the context of those applications; people with without similar problems were not motivated to read and understand the complex (and often turgid) reports"

* "general frameworks instead of solutions to some class of problems"

* "frameworks with considerable overheads, both cognitive and unless carefully implemented, computational"

* "for certain ambitious, complex applications, these overheads are justified and indeed perhaps required, however, this also means that the approach does not scale down meaningfully to simple, "toy" problems" (z.B. kryptoarithmetische Rätzel!)

* "difficult to describe and experiment with it other than in real world applciations."

* "the conceptualizing of the most simple adequate testbed application (DVMT) has consumed many men years and is more complex and has more content than many fielded expert systems"

Nicht ganz so Charakteristisches:

Anwendungen waren zwar stark bestimmend für die Entwicklung von Blackboardarchitekturen, trotztdem findet man/frau nur prototypische Anwendungen der Blackboardarchitektur in der Literatur;

Versuch einer Klärung

* da Blackboardarchitekturen sich nur für komplexe Aufgabengebiete lohnen, ist die Zeit seit Ihrer Entwicklung vielleicht zu kurz, spätere Jahre werden komplexe Realanwendungen bringen

* vielleicht lohnt sich der Blackboardansatz nur eine exemplarische Entwicklung von Anwendungen, ein Rapidprototyping, in dem Moment, in dem die Problemstellung hinreichend verstanden ist, kann die Lösung, effizienter und direkter reimplementiert werden (z.B.) in C oder auch Lisp.

Viele Systeme und Methoden der KI dienen dazu gedankliche Prozesse, die Modellierung und exakte Beschreibung von Problemen zu unterstützen und ihre Problemlösung damit voranzutreiben, sie sind oft weniger geeignet die Problemlösung zu realisieren.