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
3) Intention und Glauben
P2
5) Kooperation mit Kommunikation
6) Agentenorientiert: Systeme, Architekturen ...
P3
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:
* 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 Systeme1.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.
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.
