UNIVERSITY
OF
PADERBORN
Projektgruppe KIMAS
MultiAgenten-Systeme
07.05.2003
Andreas Goebels
Projektgruppe KIMAS
1/25
Übersicht

Begriff

Entwurf eines MAS

Kommunikation in MAS

Planung in MAS

Swarm-Intelligence
Projektgruppe KIMAS
UNIVERSITY
OF
PADERBORN
2/25
Übersicht

Begriff

Entwurf eines MAS

Kommunikation in MAS

Planung in MAS

Swarm-Intelligence
Projektgruppe KIMAS
UNIVERSITY
OF
PADERBORN
3/25
Begriff

UNIVERSITY
OF
PADERBORN
Multiagentensysteme (MAS):
• Menge von autonomen Agenten
• Koordination von Zielen, Fähigkeiten und
Plänen (gemeinsames Agieren)
Agent
Agent
Plan
Agent
Agent
Agent
Projektgruppe KIMAS
4/25
Begriff

UNIVERSITY
OF
PADERBORN
Definiton (Ferber):
MAS ist ein System aus folgenden Elementen:
• Umwelt E (i.A. ein Raum mit Volumen)
• Menge von Objekten O
• Menge von Agenten A (A Teilmenge von O)
• Menge von Beziehungen R, die Objekte
verbinden
• Menge von Operatoren Op (Modifikation von
Objekten)
• Operatoren zur Darstellung
Projektgruppe KIMAS
5/25
Übersicht

Begriff

Entwurf eines MAS

Kommunikation in MAS

Planung in MAS

Swarm-Intelligence
Projektgruppe KIMAS
UNIVERSITY
OF
PADERBORN
6/25
Entwurf eines MAS I
UNIVERSITY
OF
PADERBORN
Entwurfsbereiche

Architektur der einzelnen Agenten

Regelung der Koordination
Projektgruppe KIMAS
7/25
Entwurf eines MAS II

UNIVERSITY
OF
PADERBORN
Architektur
• Simple Reflex Agent
• Goal Based Reflex Agent
•…

Homogene / Heterogene Gruppen
Projektgruppe KIMAS
8/25
Entwurf eines MAS III
UNIVERSITY
OF
PADERBORN
Koordination durch Kooperation
• Zusammenarbeit
• Gemeinsames Verfolgen von Zielen
• Phasen:
• Problemzerlegung (zentral / dezentral)
• Lösung der Teilprobleme
• Synthese der Gesamtlösung (zentral / dezentral)
 Hilfsmittel: Kommunikation
Projektgruppe KIMAS
9/25
Entwurf eines MAS IV
UNIVERSITY
OF
PADERBORN
Koordination durch Konkurrenz
• Verfolgung unterschiedlicher, teilweise
widersprüchlicher Ziele
 Hilfsmittel: Kommunikation
Projektgruppe KIMAS
10/25
Übersicht

Begriff

Entwurf eines MAS

Kommunikation in MAS

Planung in MAS

Swarm-Intelligence
Projektgruppe KIMAS
UNIVERSITY
OF
PADERBORN
11/25
Kommunikation in MAS I

UNIVERSITY
OF
PADERBORN
Unterschiedliche Reichweite
• Globale Kommunikation
• Broadcast
• Direktes Adressieren
• Lokale Kommunikation
• Lokaler Broadcast
• Next k neighbours
Projektgruppe KIMAS
12/25
Kommunikation in MAS II

UNIVERSITY
OF
PADERBORN
Unterschiedliche Kommunikationsart
• Direkte Kommunikation (Protokolle)
• Indirekte Kommunikation (Stigmergy)
 Vorlesung 14.05.2003
Projektgruppe KIMAS
13/25
Übersicht

Begriff

Entwurf eines MAS

Kommunikation in MAS

Planung in MAS

Swarm-Intelligence
Projektgruppe KIMAS
UNIVERSITY
OF
PADERBORN
14/25
Planung in MAS I
UNIVERSITY
OF
PADERBORN
„Planen ist das Entwerfen einer Aktionsfolge, mit der eine
Startsituation in eine gewünschte Zielsituation überführt
werden kann“ (B. Neumann)
 Existenz mehrerer autonomer Agenten
 Individuell unterschiedliche Pläne
 Kommunikation notwendig
 kein sequentieller Aktionsablauf (Nebenläufiger Plan)
 Gebiet / Bereich: Verteilte künstliche Intelligenz
Projektgruppe KIMAS
15/25
Planung in MAS II

UNIVERSITY
OF
PADERBORN
Arten der Planung
• Zentrales Planen
• Dezentrales Planen
• Blackboard-Planen
Projektgruppe KIMAS
16/25
Planung: Zentrales Planen I


UNIVERSITY
OF
PADERBORN
Planung an einer einzelnen Stelle (Master)
Befehlskette unidirektional
Master
Servant
Servant
Projektgruppe KIMAS
Servant
Servant
Servant
17/25
Planung: Zentrales Planen II

UNIVERSITY
OF
PADERBORN
Vorteile
• Geringe Kommunikation
• Keine Zielkonflikte der Agenten

Nachteile
• Fehleranfällig (Master fällt aus)
• Sehr komplex (Alle Agenten betrachten)
• Geringe Autonomie (neue Probleme)
Projektgruppe KIMAS
18/25
Planung: Dezentrales Planen I


UNIVERSITY
OF
PADERBORN
Jeder Agent besitzt Planungseinheit
Abstimmung durch Kommunikation
Agent
Agent
Agent
Agent
Agent
Projektgruppe KIMAS
19/25
Planung: Dezentrales Planen II

UNIVERSITY
OF
PADERBORN
Vorteile
• Geringer Planungsaufwand
(lokale Informationen, nur ein Agent)
• Sehr Fehlertolerant
(gegenseitige Überprüfung)

Nachteile
• Viel Kommunikation
• Konfliktpotential
Projektgruppe KIMAS
20/25
Planung: Blackboard-Planen I
UNIVERSITY
OF
PADERBORN
 Kompromiss zwischen verteilter und

zentraler Planung
Gemeinsames Kommunikationsmedium
(Speicherbereich,
Simulationsumgebung etc.)
Agent
Blackboard
Agent
Agent
Projektgruppe KIMAS
Agent
21/25
Planung: Blackboard-Planen II

UNIVERSITY
OF
PADERBORN
Vorteile
• Planungsaufwand gering
• Fehlertolerant (Redundanz)
• Geringe Kommunikation

Nachteile
• Mittleres Konfliktpotential
Fehlertolerant  Konfliktpotential
Projektgruppe KIMAS
22/25
Übersicht

Begriff

Entwurf eines MAS

Kommunikation in MAS

Planung in MAS

Swarm-Intelligence
Projektgruppe KIMAS
UNIVERSITY
OF
PADERBORN
23/25
Swarm Intelligence I




UNIVERSITY
OF
PADERBORN
an natürliche Populationen angelehnt
große Anzahl autonomer Agenten
mehr-dimensionale Umwelt
Selbstorganisation durch Interaktion
 spezielle Form von MAS
Projektgruppe KIMAS
24/25
Swarm Intelligence II

UNIVERSITY
OF
PADERBORN
Eigenschaften von Swarm-Intelligence
Algorithmen:
• Robustheit: einzelne Individuen können
ausfallen
• Flexibilität: Änderungen in der Umwelt /
fehlgeschlagene Aktionen werden kompensiert
• Emergenz: Gruppenfähigkeit ist größer als die
Summe der Einzelfähigkeiten
Projektgruppe KIMAS
25/25

PPT