Verteilte Künstliche Intelligenz - Uni Ulm WS95/96

1 Verteilte Künstliche Intelligenz
Eine Einführung

 

* Überblick über den Inhalt der Vorlesung

* Verteilte Künstliche Intelligenz: Begriffsbestimmung und Motivation

* Problemstellungen

* Zwei Herangehensweisen

* Geschichtlicher Überblick

* VKI Literatur


1.1 Überblick Vorlesung

 

1) Überblick, Motivation und Geschichte

2) Entscheidungstheorie - Kooperation ohne Kommunikation

3) Intention und Glauben: Theorie Deliberativer Agenten

4) Theories of Agencies - Von reaktiv bis deliberativ

5) Kooperation mit Kommunikation

6) Agentenorientiert: Systeme, Architekturen und Sprachen

7) Blackboardsysteme

8) Verteiltes Planen

9) Anwendungen

 

 


1.2 Begleitendes Praktikum

 

1) Überblick, Motivation und Geschichte

P1

2) Entscheidungstheorie

3) Intention und Glauben

P2

4) Theories of Agencies - Von reaktiv bis deliberativ

5) Kooperation mit Kommunikation

6) Agentenorientiert: Systeme, Architekturen ...

P3

7) Blackboardsysteme

8) Verteiltes Planen

9) Anwendungen

 

Zur Organisation:

* 2 bis max.4 Personen Gruppen

* Die Lösung jeder Aufgabe umfaßt:

Kurze (4-5 Seiten) Beschreibung der Problemstellung, Charakterisierung des eingesetzten Systems, Dokumentation von Experimenten und Implementation

Vorführung des Programms


1.3 Motivation und Begriffsbestimmung

 

Distributed planning and problem solving systems handle tasks that cannot be dealt with effectively and efficiently by one single processor.

Findler 1991

 

Typische Probleme bisheriger Methoden im Bereich
der "Single" KI:

* Scaleability: Von Spielproblemstellungen hin zu realen Anwendungen nicht nur ein quantitativer Sprung

* Versatility: Eine Problemlösungsstrategie oft ungenügend zur Bewältigung komplexer Probleme

* Reusability: Verschiedene Anwendungen benötigen ähnliche Expertisen

* Brittleness: Eine scharfe Grenze zwischen Kompetenz und Wissen einerseits und Inkompetenz und Ignoranz andererseits.

 

Die Lösung: Verteilte KI?

 

* Intelligenz ensteht erst durch das Zusammenwirken von verschiedenen Entitäten.

It was never supposed that cogitation is inherent in matter, or that every particle is a thinking being.

Samuel Johnson

 

* Zur Lösung komplexer Problemstellungen arbeiten mehrere Experten, Agenten, zusammen.

 


1.4 Begriffsbestimmung

Eine Annäherung von zwei Seiten

 

In der verteilten Künstlichen Intelligenz werden im allgemeinen zwischen zwei Ansätzen unterschieden:

Ausgehend von dem Problem (Blackboardsysteme)

* Wie kann die Lösung eines bestimmten Problems auf unterschiedliche Module verteilt werden, die miteinander auf der Basis des Informationssharings kooperieren und die Problemlösung gemeinsam entwickeln.

 

+ Kap. 7

Ausgehend von den Agenten (Multiagentensysteme)

• Wie sehen autonome, intelligente Agenten aus, die ihr Wissen, ihre Ziele, ihre Fähigkeiten und Pläne miteinander koordinieren, um Probleme zu lösen.

 

+ Kap. 3 und folgende


1.5 Bezug zu anderen Gebieten

 

 

 

 

1.5.1 Objekt-orientierte Programmierung

Designprinzipien

Die zu erstellende Software wird durch eine Menge nebenläufig ausführbare Module repräsentiert (nebenläufige Objekte). Die Interaktion geschieht ausschließlich mit Hilfe von Nachrichtenübermittlung zwischen solchen Objekten.

Beispielsprachen:

* ACTORS (Carl Hewitt)

* ABCL/1 (An Object-Based Concurrent Language)Akinoro Yonezywa

* Concurrent Smalltalk (Yasuhikko Yokote, Mario Tokoro).

 

 

Beispielprogramm (ABCL)

Definieren eines Objektes durch

* lokale Daten des Objektes

* Bedingungen für die Akzeptanz von Nachrichten

* Aktionenfolge, die nach dem Empfangen einer Nachricht ausgeführt werden soll, Aktionen: Versenden von Nachrichten, Erzeugen von Objekten, Modifikation von lokalen Daten...

[object objectname
       (state representation of local memory ...)
       (script (=> message pattern where constraint ... action ....)
		(=> message pattern where constraint ... action ...))] 

* Nachrichtentypen send and continue, send and wait usw.

 

Gemeinsamkeiten:

* Einheiten (Programme und Datenstrukturen) mit einer klaren Grenze nach Außen

* Kommunikation zwischen den Einheiten basiert auf Versenden von Nachrichten

* Teilweiser Gebrauch von Vererbungsstrategien (vgl. Concurrent)

 

Unterschiede:

Agenten sind gekennzeichnet i.a. durch:

* Explizite interne Modelle über ihre Umgebung und sich selbst, mentale Zustände, die Glauben, Wünsche und Intentionen ausdrücken (BDI Architekturen)

* Nachrichtensenden ist typisiert (High-level Communication) und strukturiert durch spezielle Protokolle und/oder linguistische Elemente , z.B. Sprechakttheorie und Dialoge.

* Größere Autonomie, zwar können Master-Slave Beziehungen modelliert werden, die Reaktion auf eine bestimmte Nachricht bleibt jedoch dem Agenten überlassen, Freiheit der Entscheidung

 

1.5.2 Verteilte Systeme

Das Ziel von Verteilten Systemen ist:

".. system that combines the accessibility, coherence, and manageability advantages of centralized systems with the sharing, growth, cost, and autonomy advantages of networked systems."

Schroeder 1993
In: Distributed Systems, Addison Wesley

Verteilte Systeme

* Athena (MIT), AMOEBA (Vrije Universität Amsterdam) ...

Spezielle Sprachen

* ORCA (in AMOEBA)

Gemeinsamkeiten:

* Fragen der parallelen und asynchronen Kommunikation ein wichtiger Aspekt

* Kommunikation von Agenten erfordert zuverlässige Kommunikationsmechanismen usw.

Unterschiede:

* spezielle Probleme ergeben sich für verteilte Systeme durch heterogene Umgebungen in Form von Hardware und Kommunikationsprotokollen.

* das "Wie" der parallelen Abarbeitung ist in der VKI weniger wichtig als das "Was", "Wann", "zu Wem" und "Warum".

+ Vorlesung: Verteilte Systeme


1.5.3 Künstliche Intelligenz

In der KI geht es um die Lösung von Problemen mit dem Rechner, deren Lösung als Indiz für Intelligenz gewertet werden kann.

* Wie können Probleme so aufbereitet werden, daß ein Rechner eine Lösung finden kann, d.h. computergeeignete Modellierung des menschlichen Wissens und menschlicher Problemlösungsstrategien

 

Gemeinsamkeiten:

Logik und Inferenzsysteme u.a.,

* epistemische Logiken

* temporale Logiken

 

+ Vorlesung: nicht Standard Logiken

 

* Planung

* Lernen

* Programmiersprachen und Programmiermethoden für Problemlösungsverfahren

 

+ Vorlesung: Grundlagen der KI,

 

Unterschiede:

 

* Kommunikation und Koordination von autonomen Einheiten stehen in der VKI im Vordergrund

* single agent systems vs. multi agent systems

 

 

1.5.4 Entscheidungstheorien

Von ihrer normativen Seite aus befaßt sich Entscheidungstheorie mit Problemen der Orientierung. Es geht darum Aktionsverläufe zu finden, die zu Ergebnissen führen, die akzeptabler sind als andere.

* Menge der möglichen Aktionen

* Bewertungskriterien zur Beurteilung der relativen Werte der Ergebnisse von Aktionen

 

Aktoren:

"Ein Aktor wird durch die spezifische Menge seiner Interessen beschrieben. Er kann ein Individuum, eine Gruppe von Individuen, eine Institution oder ein Staat sein - also etwas, dem erkennbare Aktionen zugeordnet werden können, und von dem angenommen werden kann, daß es von Zielvorstellungen, Wünschen, Präferenzen u.ä. geleitet wird. "

Rationale Aktoren:

"Ein rationaler Aktor ist jemand, der die ihm zur Verfügung stehende Information benutzt, um seine Aktionen auf die resultierenden Ergebnisse zu beziehen, d.h. jemand, der seine Aktionen von den erwarteten Konsequenzen leiten läßt."

(Rapoport 1980)

Gemeinsam:

* u.a. Kooperation zwischen mehreren Akteuren

* Theorien über Wünsche, Präferenzen, Entscheidungen

* Spiel- und Markttheorien usw.

 

Unterschiede:

* mathematische Darstellung

* einfache Struktur der Akteure

 

Beispiel Prisoners Dilemma

Joe und Jack Dalton haben zusammen eine Bank ausgeraubt. Gesteht Joe wird er freigelassen und Jack muß 5 Jahre ins Gefängnis et vice versa. Gestehen beide, sitzen sie jeweils für 3 Jahre, ansonsten sind sie nach einem Jahr wieder in Freiheit.

 

 

 


Weitere Bezüge:

Agenten und Organisations Theorie

Mit der Organisationstheorie verbindet die VKI z.B. relativ stabile Strukturen, u.a. Kommunikationsstrukturen, das Vorhandensein von allgemeinen Verhaltensregeln und Rollen in der Gemeinschaft. Aufbau von Hierarchien und Netzwerken zur kooperativen Lösung von Problemlösungen (Bezug zur Ökonomie).

 

Agenten und Individualistische Sozialtheorie

Da Agenten nicht singulär sondern als Gesellschaft modelliert werden, ist ihre Rolle in der Gesellschaft wechselnd, hierzu werden Ansätze aus den Sozialwissenschaften adaptiert. Ansätze des symbolischen Interaktionismus (Mead) und der Sozialen Theorie (Coleman) und erklärenden Soziologie (Alexander).

 

Zwischen Homo Sociologicus - Ein Mensch folgt nur den gesellschaftlichen Normen und Symbolen - und Homo Oeconomicus - Perfekte Information und für alle Situationen geordnete Präferenzen -

das RREEMM Modell (Lindenberg):

Der Mensch sei ein "resourceful, restricted, expecting, evaluating, maximizing man".

 

 


1.6 Wurzeln der VKI

 

* Hewitt, 1971: "Actors: A Model of Concurrent Computation in Distributed Systems."

What should be the communication mechanisms and conventions of civilized discourse for effective problem solving by a society of experts?

 

* Smith R.G., & Davis R., 1981: "Contract Net Protocoll"

 

* Minsky, 1986: "The society of mind."

 

How can intelligence emerge from nonintelligence?

 

 

Geschichte der VKI in den USA

1980 Erster DAI Workshop in Boston

1981 Erste umfangreiche Veröffentlichung: Sonderheft der IEEE Transactions on Systems, Man and Cybernetics.

1987 Erster DAI Band hrsg. von Norbert Huhns

1988 Readings in DAI hrsg. von Allen Bond und Les Gasser

Geschichte in Europa

1989 Erster Workshop on Modelling Autonomous Agents in a Multi-Agent World (MAAMAW)

Geschichte in Deutschland

1990 Erstes Treffen auf der GWAI - Gründung eines Arbeitskreises

1993 Gründungsworkshop der Fachgruppe VKI der Gesellschaft für Informatik (GI)

International

1995 Erste Internationale Konferenz on Multi-Agent Systems

E-Mail Listen:

vki-request@dfki.uni-sb.de vki-list@dfki.uni-sb.de
DAI-List-request@mcc.com DAI-List@mcc.com
demazeau@lifia.imag.fr maamaw@lifia.imag.fr
ckbs@cs.keele.ac.uk ckbs-int@cs.keele.ac.uk


1.7 VKI Sammelbände

Huhns N., (Hrsg.), 1987: Distributed Artificial Intelligence. Pitman, London.

Bond A. and Gasser L. (Hrsg.), 1988: Readings in Distributed Artificial Intelligence. Morgan Kaufmann, Los Angeles, CA, 1988.

Gasser L. and Huhns N. (Hrsg.), 1989: Distributed Artificial Intelligence. Pitman, London.

Demazeau Y. and Müller J.P. (Hrsg.), 1990: Decentralized Artificial Intelligence. Proc. of the 1. European Workshop on Modelling Autonomous Agents in a Multi-Agent World (MAAMAW). North Holland.

Demazeau Y. and Müller J.P. (Hrsg.), 1991: Decentralized Artificial Intelligence. Proc. of the 2. European Workshop on Modelling Autonomous Agents in a Multi-Agent World (MAAMAW). North Holland.

Demazeau Y. and Müller J.P. (Hrsg.), 1992: Decentralized Artificial Intelligence. Proc. of the 3. European Workshop on Modelling Autonomous Agents in a Multi-Agent World (MAAMAW). North Holland.

KI 1/92, 1992: Themenheft Einführung in die Verteilte KI, FBO Verlag.

Avouris N.M., Gasser L. (Hrsg.), 1992: Distributed Artificial Intelligence. Theory and Practice. Kluwer Press, New York.

Müller J. (Hrsg), 1993: Verteilte Künstliche Intelligenz. Wissenschaftsverlag, Mannheim.

Castelfranchi C., Werner E. (Hrsg.), 1994: Artificial Social Systems. Proc. of the 4. European Workshop on Modelling Autonomous Agents in a Multi-Agent World (MAAMAW). Springer.

Wooldridge M., Jennings N.R. (Hrsg.), 1995: Intelligent Agents. Proc. of the 5. European Workshop on Modelling Autonomous Agents in a Multi-Agent World (MAAMAW). Springer.

Lesser V. (Hrsg.), 1995: Proceedings of the first International Conference on Multi-Agent Systems (ICMAS). AAAI Press.


UP