Multiagent Systems

Einführung

Zusammenfassung der ersten 18 Seiten des Survey-Papers von Peter Stone

Über diesen VortragUNTERLAGEN Präsentation „Mitschrift“ Zettel Begriffe

Survey-Papervon Peter Stone

Pdf-DateienKube

Über diesen VortragINHALT WAS sind MAS,

WOZU denn MAS,KATEGORIEN von MAS

Non-Communicating homogeneous MASPursuit-DomainCooperative Insects

Ausblicke Beispiel (cooperative

Transport) Diskussion Peter Stone

Über diesen VortragZiele Überblick Multiagents Systems

(Begriffe, Einteilung)

Motivation(Wozu, warum, Möglichkeiten)

Homogeneous Non-Comm. MAS(Aktualität, Einsatzgebiete, konkrete Vorstellung anhand von Beispielen)

1) WAS sind MAS

C A Icen trlized AI

D P Sd is tr ibuted P rob lem S o lv ing

M A SM u ltiagen t S ystem s

D A Id is tr ibuted AI

A IA rtific ia l Inte lligence

1.1) AGENT für sich

Goals(Ziel, Intention)

Actions(Handlung)

Domain Knowledge(Wissen)

goal

knowledge

action

1.2) AGENT „Behaviour“ Agent

(Goals, Action, Domain Knowledge)

BehaviourFlucht,Angriff, . . .

Bach umgehen!

1.3) Single-Agent System Ein Single-Agent

steuert eine (oder mehrere) Entities

Mehrere Single-Agents:Nehmen sich gegenseitig nicht als Agents wahr

1.4) Multi-Agent System Ein Agent

steuert eine Entity

Mehrere Agents nehmen sich als solche wahr(müssen nicht zwangs-weise miteinander kommunizieren)

Highlights zu Kapitel 1: „WAS sind MAS“ AI DAI MAS

Agent: Goals, Actions, Knowledge

Behaviour: Verhalten (nicht Action!)

Single-Agent versus Multi-Agent

F R A G E N ???

2. WOZU MAS ? Zwingende Gründe Allgemeine DAI – Aspekte Wissenschaftliche Gründe Wirtschaftliche Faktoren

2.1) Zwingende Gründe

„Roboter“ trifft Roboter in realer Welt(Auto)

Firmenübergreifende Programme(Datenschutz)

...

2.2) Allgemeine DAI Aspekte

Komplexität verringernTeilproblemreduktion

Robustheit erhöhenAusfallsicherheit

GeschwindigkeitParallelprocessing

ScalabilityErweiterbarkeit

2.3) Wissenschaftliche Gründe

Soziale Intelligenz

Weiß:

„Intelligence is deeply and inevitably coupled with interaction.“

2.4) Wirtschaftliche Faktoren

Massenproduktion „simpler“ Roboter

anstatt

Einzelfertigung hochspezialisierter Roboter

Highlights zu Kapitel 2:WOZU Multiagent - Systems

Zwingende Gründe Allgemeine DAI – Aspekte Wissenschaftliche Gründe Wirtschaftliche Faktoren

F R A G E N ???

3) Kategorien von MAS Taxonomie:

verschiedene Einteilungsmöglichkeiten existieren

Stone:

Heterogeneity Communication

Communication

Heterogeneity

0

4) Homogeneous Non-Communicating MAS

Alle Entities sind gleich(goals, actions, domain knowledge)

Keine (direkte) Kommunikation

4.0) Programm

Die Pursuit-Domain (PD) Verschiedene Strategien in der PD Reactive vs. Deliberative Agents Local vs. Global Perspective „indirekte“ Kommunikation –

Stigmergy Cooperative Insects

4.1) Pursuit Domain

Auch „Predator / Prey Domain“(seit 1985 benchmark proplem in der KI)

Klassische Spielart:4 Predators (agents),1 Prey (random)

Spielziel:Prey fangen (oder umstellen)

4.2) Strategien (1)

Stephens & Merx [1990]

Capture Positions Ignoriere andere

Predators

Gegenseitige Blockaden !

4.2) Strategien (2)

Korf [1992]

Greedy-Strategie

Prey zieht an,Predator stößt ab

Korf: „Explicit Cooperation is rearly necessary or useful!“

4.2) Strategien (3)

Vidal & Durfee [1995]

„predict“ Aktionen anderer Agents RMM

Aufwendigglobal / local scope ?

4.3) Reactive vs. Deliberative

Reactive:eher „reflexartig“,keine großen Interpolationen ...

Beispiel: Greedy

Deliberativeüberlegt, planend

Beispiel: RMM

4.4) Local vs. Global Perspective

Wie viel Sensor-Information sollte mein Agent überhaupt bekommen?

Limitierung oft effektiver!

gute Strategie besser als komplexe Auswertungen!

4.5) Indirekte Kommunikation: STIGMERGY

Active Stigmergy:

Passive Stigmergy:

4.6) Cooperative Insects

Piling dead Antsverstreute tote Ameisen werden auf einen großen Haufen zusammengetragen

Cooperative TransportAmeisen tragen eine Beute gemeinsam (die für eine oder zwei Ameisen zu schwer ist)

Owen Holland

University of Essex

C. Ronald Kube

Edmonton Research

Center

5) Ausblicke Goal over others:

indirektes, zeitverzögertes Feedback (Agent Y hat gemeinsames Ziel erreicht Agent X hat somit auch sein Ziel erreicht)

Modelling Agents:Lernalgorithmen basierend auf Umgebungs- und Behaviour-Beobachtungen

Cooperative Transport - ANTS

Eine Ameise findet eine Beute Versuch die Beute zu bewegen „TimeOut“ Signal an andere

(direkt od. chemisch) Andere Ameisen kommen und formieren sich Jede für sich: „TimeOut“ Repositionieren

Führt im allgemeinen zur Lösung

Diagramm „ANT-Transport“

Experiment Van Damme / De Neubourg

Cooperative Transport - ROBOTS

Erleuchtete Box soll ins Licht geschoben werden Gewicht der Box erfordert mindestens zwei

Roboter Roboter sucht Box Roboter schiebt „TimeOut“ Winkel ändern „TimeOut“ Repositionieren

Führt zur Lösung!

Diskussion / Fragen Vorteile

der MAS-Lösung von KUBE

Nachteile(Wäre ein zentralisiertes System besser? ...)

. . .

ANT PILING

Tote Ameisen werden um einen Ameisenhaufen verstreut.

Die lebenden Ameisen häufen diese zusammen, ohne (nachweisbar) zu kommunizieren.