Agenten in simulierten Umgebungen Landminensuche II Stefan Fleischer Stephan Kramer Alexander Simons...

Agenten in simulierten Agenten in simulierten UmgebungenUmgebungen

Landminensuche IILandminensuche II

Stefan Fleischer

Stephan Kramer

Alexander Simons

Agenten in simulierten Umgebungen -1-Agenten in simulierten Umgebungen -1-

Gliederung (I)Gliederung (I)

2. Ansätze2. Ansätze1. Systematische Suche2. Kommunikation3. Zentrale Informationsverwaltung

4. Befehlshabender Roboter

1. Wiederholung: Robbi1. Wiederholung: Robbi1. Was Robbi kann…2. „Warum bin ich so dumm?“3. Offensichtliche Verbesserungsmöglichkeiten

Gliederung (II)Gliederung (II)

3. Realisierung: Schritt für Schritt3. Realisierung: Schritt für Schritt 1. Rundumcheck 2. „Wo war ich schon, wo will ich hin?“

3. Wegfindung1. Einführung

2. Der Dijkstra-Algorithmus3. Best-First-Search4. Der A*-Algorithmus

4. Kommunikation1. Flooding vs. Verteiler

Gliederung (III)Gliederung (III)

5. Der „Commander“ 1. Verwaltung und Verteilung von

Informationen1. Roboter meldet sich an

2. Roboter meldet sich ab3. Roboter entdeckt unerforschtes Land4. Roboter ändert seine Position

2. Behandlung von Fehlinformationen3. Einzelne Einsatzgebiete

1. Ermittlung geeigneter Einsatzgebiete2. Zuweisung der Einsatzgebiete

Gliederung (IV)Gliederung (IV)

4. Effektivität der verwendeten Methoden4. Effektivität der verwendeten Methoden

5. Weitere - nicht realisierte - Möglichkeiten5. Weitere - nicht realisierte - Möglichkeiten

6. Beurteilung der Simulationsumgebung6. Beurteilung der Simulationsumgebung

7. Alternative Simulationsideen7. Alternative Simulationsideen

1.1. Wiederholung: RobbiWiederholung: Robbi

1.1 Was Robbi kann…• zu untersuchende Felder werden zunächst

mit dem Stoßsensor überprüft…

• …falls kein Hindernis identifiziert wird,

verwendet Robbi den Metalldetektor

• Karten, in denen ausschließlich Metallminen

hinterlegt sind, werden von Robbi vollständig

„aufgedeckt“ (Ausnahmen)

1. Wiederholung: Robbi1. Wiederholung: Robbi

1.1 Was Robbi kann…1.1 Was Robbi kann…

1. Wiederholung Robbi

1. Was Robbi kann…

2. „Warum bin ich so dumm?“

3. Offensichtliche Verbesserungs-

möglichkeiten

• trifft Robbi auf eine Mine, kontaktiert er

umgehend seinen Agentenkollegen, um ihm

die Position der gefundenen Mine mitzuteilen

• Beispiel: Metallkarte.map (Hans und Herse )

Start:

• gefundene Minen und Hindernisse werden rot

eingefärbt

1.2 „Warum bin ich so dumm?“1.2 „Warum bin ich so dumm?“

möglichkeiten

Was Robbi allerdings nicht kann…Was Robbi allerdings nicht kann…

• …Minen ohne Metallgehalt aufspüren

• …sich die Felder merken, die er bereits

überprüft hat

• …sich den Weg merken, den er zurückgelegt hat

• …sich den kürzesten Weg „überlegen“

• …die Karte untereinander „aufteilen“

1.3 Offensichtliche1.3 Offensichtliche VerbesserungsmöglichkeitenVerbesserungsmöglichkeiten

möglichkeiten

Verbesserung der Intelligenz der Roboter durch:

• effiziente Wegfindungsalgorithmen (Der

A*-Algorithmus, Kap. 3.3)

• effizientere Informationsverwaltung (bereits

kontrollierte Felder merken,… Kap. 3.2)

• verbesserte Kommunikation (Kap. 3.4)

• Arbeitsteilung (Der „Commander“, Kap. 3.5)

2. Ansätze2. Ansätze

2.1 Systematische Suche

• Roboter sollten zunächst die angrenzenden

Felder kontrollieren…

• …sofern sie noch nicht kontrolliert wurden

• hat der Roboter sämtliche (8) umliegenden

Felder überprüft, muss er sich zu einem

geeigneten neuen Feld bewegen

2.2 Kommunikation2.2 Kommunikation

2. Ansätze2. Ansätze 2. Ansätze

1. Systematische Suche

2. Kommunikation

3. Zentrale Informationsverwaltung

• Roboter müssen sich einander mitteilen und

ihre Karten abgleichen

• Welche Felder wurden kontrolliert?

• Welche Beschaffenheit besitzen die Felder?

• Minen?

• Hindernisse?

• Wasser?

2.3 Zentrale Informations-2.3 Zentrale Informations- verwaltungverwaltung

2. Kommunikation

• Roboter speichern ihre „Version“ der Karte

(lokale Datenverwaltung)…

• …jedoch wird eine fehlerfreie Version der

Karte an zentraler Stelle gespeichert

• z.B. Zusammenstoß von Robotern

2.4 Befehlshabender 2.4 Befehlshabender RoboterRoboter

2. Kommunikation

• verwaltet die gemeinsame Karte

• verantwortlich für die Aufteilung der Karte

zwischen den Robotern

3. Realisierung3. Realisierung

3.1 Rundumcheck

3. Realisierung

1. Rundumcheck

2. „Wo war ich schon,…“

3. Wegfindung

4. Kommunikation

5. Der „Commander“

3.2 „Wo war ich schon, ...“3.2 „Wo war ich schon, ...“

3. Realisierung3. Realisierung3. Realisierung

1. Rundumcheck

3. Wegfindung

4. Kommunikation

3.2 „…wo will ich hin?“3.2 „…wo will ich hin?“

• Alle benachbarten Felder gecheckt

Positionswechsel

• Als neue Position eignen sich Felder, die…

• …noch nicht betreten wurden

chooseFieldInVicinity

• …noch gar nicht erforscht wurden

chooseFieldInWorkingArea

3. Realisierung

1. Rundumcheck

3. Wegfindung

4. Kommunikation

1. Rundumcheck

3. Wegfindung

4. Kommunikation

1. Rundumcheck

3. Wegfindung

4. Kommunikation

3.3 Wegfindung3.3 Wegfindung

3. Wegfindung

1. Einführung

2. Dijkstra

3. Best-First-Search

4. A*-Algorithmus

3.3.1 Einführung: „Warum Wegfindung?“3.3.1 Einführung: „Warum Wegfindung?“

Problem:Problem:

Ineffiziente Wegfindungs-

algorithmen bleiben im

Hindernis „hängen“!

3.3 Wegfindung: Einführung3.3 Wegfindung: Einführung

„Sichtradius“

• Hindernis wird zu spät bemerkt• Weg ist ineffizient

• ein guter Wegfindungs-

algorithmus betritt das „U“-

Hindernis nur, wenn sich das

Ziel dort befindet

3. Realisierung

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

3.3 Wegfindung: Einführung3.3 Wegfindung: Einführung

Die Algorithmen:Die Algorithmen:

• ...basieren auf Graphen im

mathematischen Sinn (Knoten, Kanten,...)

• Karten können als Graphen angesehen

werden (Entfernungen zwischen den

einzelnen Feldern entsprechen den

Bewertungen der Kanten)

3. Realisierung

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

3.3.2 Der Dijkstra-Algorithmus3.3.2 Der Dijkstra-Algorithmus

3. Realisierung

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

3.3 Wegfindung: Dijkstra3.3 Wegfindung: Dijkstra

Beispiel!

• ausgehend von einem Startknoten wird der

jeweils kürzeste, erreichbare Knoten

ausgewählt...

Soll heißen:Soll heißen:

• ...bis der Zielknoten erreicht ist!

3. Realisierung

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

Fazit:Fazit:

• gieriger Algorithmus: Aus-

wahl des nächstgelegenen,

erreichbaren Knotens

• der Algorithmus ist optimal,

solange keine Kante nega-

tive Kosten besitzt

3. Realisierung

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

Fazit:Fazit:

• der Algorithmus ist jedoch

nicht optimal effizient: Es

werden zu viele Knoten

expandiert!

3. Realisierung

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

3.3.2 Best-First-Search3.3.2 Best-First-Search

• funktioniert ähnlich wie der Dijkstra-

Algorithmus...

• ...er verwendet jedoch eine Heuristik, aus

der hervorgeht, wie nah jeder Knoten vom

Zielknoten entfernt ist

3. Realisierung

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

3.3 Wegfindung: BF-Search3.3 Wegfindung: BF-Search

• nicht derjenige Knoten wird expandiert, der

die geringste Entfernung zum Startknoten

aufweist, sondern derjenige, der am

nächsten am Zielknoten liegt

Beispiel!

3. Realisierung

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

3.3 Wegfindung: BF-Search3.3 Wegfindung: BF-Search

Fazit:Fazit:

• die Lösung muss nicht

optimal sein

• der Algorithmus ist schneller

als der Dijkstra-Algorithmus:

Er expandiert weniger

Knoten

3. Realisierung

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

3.3.3 Der A*-Algorithmus3.3.3 Der A*-Algorithmus

• Kombination von Dijkstra und BFS:

Es werden Knoten expandiert, die sich...

• ...möglichst nahe am Startknoten und...

• Bewertungsfunktion: f(n) = g(n) + h(n)

• ...möglichst nahe am Zielknoten befinden

3. Realisierung

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

3.3 Wegfindung: A*-Algorithmus3.3 Wegfindung: A*-Algorithmus

• f(n): geschätzte Kosten für die optimale

Lösung durch n

• n: zu expandierender Knoten

• g(n): Pfadkosten (vom Startkosten zu n)

• h(n): geschätzte Kosten des optimalen

Pfades von n zu einem Zielknoten

3. Realisierung

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

• wobei h*(n) die tatsächlichen

(unbekannten) Kosten des optimalen

Pfades von n zum Zielknoten sind

(„zulässige Heuristik“)

Beispiel!

3. Realisierung

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

• für die Schätzung h(n) muss gelten:

h(n) h*(n)

Fazit:Fazit:

• mit dem A*-Algorithmus

werden wesentlich weniger

Knoten expandiert als mit

dem Dijkstra-Algorithmus

• A* nutzt die Vorteile der

Verwendung einer Heuristik

3. Realisierung

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

Fazit:Fazit:

• A* ist optimal effizient für

jede beliebige Heuristik-

funktion

• Algorithmen, die weniger

Knoten expandieren, gehen

das Risiko ein, die optimale

Lösung zu übersehen

3. Realisierung

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

Fazit:Fazit:

• im einfachsten Fall, werden

genau so viele Knoten

expandiert,

wie beim BFS-

Algorithmus

3. Realisierung

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

3. Wegfindung

1. Einführung

2. Dijkstra

4. A*-Algorithmus

4. Kommunikation

4.1 Flooding vs. Verteiler

• sendMessage und receiveMessage erwarten

bzw. liefern Nachrichten in Form von Strings

• Je nach Art der Nachricht müssen die einzelnen

Daten auf unterschiedliche Weise in dem String

abgelegt werden

• Overhead bezüglich Programmieraufwand

und Quellcode

Einheitliche Schnittstelle

4. Kommunikation

3.4.1 Flooding vs. Verteiler3.4.1 Flooding vs. Verteiler

3. Realisierung

4. Kommunikation

3.5 Der Commander3.5 Der Commander

1. Verwaltung und Verteilung…

2. Behandlung von Fehlinformationen

3. Einzelne Einsatzgebiete

• Sucht keine Minen, …

• …sondern dient als Verwalter und Verteiler

von Informationen, …

• …teilt die Karte in einzelne Einsatzgebiete auf…• …und weist jedem Roboter eines dieser

Gebiete zu

3.5.1 Verwaltung und Verteilung3.5.1 Verwaltung und Verteilung von Informationenvon Informationen

• Roboter meldet sich an

• Roboter entdeckt unerforschtes Land

• Roboter ändert seine Position

• Roboter meldet sich ab

• Der „Commander“ führt eine Liste aller Roboter

• Roboter entdeckt unerforschtes Land

• Der „Commander“ aktualisiert die Karte und

benachrichtigt alle anderen Roboter

• Roboter ändert seine Position

• Der „Commander“ aktualisiert die Karte und die Position

des Absenders und benachrichtigt alle anderen Roboter

• Roboter meldet sich an

• Der „Commander“ nimmt den Roboter in seine List auf

• Roboter meldet sich ab

• Der „Commander“ entfernt den

Roboter aus seiner Liste

3.5.1 Behandlung von3.5.1 Behandlung von FehlinformationenFehlinformationen

• Einzelne Roboter wissen nichts voneinander

• Trifft ein Roboter einen anderen, hält er

diesen für ein Hindernis und benachrichtigt

den „Commander“

• Der „Commander“ identifiziert diese

Fehlinformation und schickt die Nachricht

an den Absender zurück

• Wurde ein Roboter als Hindernis angesehen?

3.5.1 Einzelne3.5.1 Einzelne EinsatzgebieteEinsatzgebiete

• Einteilung der Karte in Einsatzgebiete

• „Flinsch-Einsatzgebiet-Zerlegungs-Algorithmus“

Gebiet in mindestens so viele Teile zerlegen,

wie es Roboter gibt

Anzahl an horizontalen Grenzen und

vertikalen Grenzen möglichst ausgewogen• Jedem Roboter ein Einsatzgebiet zuweisen

• A*-Algorithmus als am besten geeignetes

Verfahren zur Wegfindung

3. Realisierung

4. Effektivität der verwendeten…

5. Weitere - nicht realisierte - …

6. Beurteilung der Simulations…

7. Alternative Simulationsideen

4. Effektivität der4. Effektivität der verwendeten Methodenverwendeten Methoden

• Roboter verfügen über eigene

Einsatzgebiete, d.h. sie kommen sich nicht

in die Quere

• Nachrichtenaustausch über Verteiler

effizienter

• „Intelligentere“ Zuweisung der Einsatzgebiete

3. Realisierung

5. Weitere - nicht realisierte -5. Weitere - nicht realisierte - MöglichkeitenMöglichkeiten

• Einsatzgebiet komplett gecheckt

neue Einsatzgebiete ermitteln/zuweisen

• Verwendung des optischen

und des Infrarot-Sensors

• Noch nicht erforschte Felder werden in

optimierter Reihenfolge abgearbeitet

• ???

• PROs:

6. Beurteilung der6. Beurteilung der SimulationsumgebungSimulationsumgebung

• Realisiert FIPA-Standards

• Flexibel (erweiterbar)

• Sehr Einfache Bedienung

3. Realisierung

• Plattform unabhängig

• CONTRAs:

6. Beurteilung der6. Beurteilung der SimulationsumgebungSimulationsumgebung

• Allgemein sehr „buggy“

• Teilweise instabil

• Quellcode passt nicht zu vorkompilierten

Klassen Anpassung nicht möglich

3. Realisierung

• Sehr schöne „spielerische“ Simulation,

doch von der Realität weit entfernt

• Keine gekachelte Umgebung, …

7. Alternative7. Alternative SimulationsideenSimulationsideen

• …sondern eine auf Vektoren basierende Umgebung

• 3D-Landschaften

• Bekanntes, „verseuchtes“ Terrain

3. Realisierung

• Verschiedene Missionen/Einsätze

• Bewertung eines Einsatzes (Zeitbedarf,

Energieverbrauch, Materialverlust)

• Pause-Funktion, Replay-Funktion, …

• ???

Agenten in simulierten Agenten in simulierten UmgebungenUmgebungen

Stefan Fleischer

Stephan Kramer

Alexander Simons

Agenten in simulierten Umgebungen Landminensuche II Stefan Fleischer Stephan Kramer Alexander Simons...

Documents

Android in SIEM-Umgebungen

Virtuelle 3D-Umgebungen - Chancen und Möglichkeiten -

Puppet - Umgebungen, Daten & Code, Abhängigkeiten

Übung Teil 1 Prinzipal-Agenten Beziehungen. Grundlegende Annahmen Prinzipal beauftragt Agenten Vertrag wird geschlossen –Anknüpfungspunkt: kontrahierbare

Einführung in die Theorie der Multi-Agenten-Systeme

Logikbasierte Agenten. Überblick Wissensbasierte Agenten Bsp.: Wumpus-Welt Logik im Allgemeinen, Modelle und Logische Konsequenz Aussagenlogik Inferenzregelen

Prinzipal-Agenten- Theorie.............. 1 Prinzipal-Agenten-Theorie Präsentiert von Sven Hanus Partha Banerjee Hassan Amjahad

Suchen mit Agenten Seminar Softwareagenten Simon Fischer

Multi agenten-systeme

Robotfussball und Agenten

Veränderung des Befindlichkeitsniveaus unter moderatem Sauerstoffmangel bei Luftfahrzeugbesatzungen in simulierten Druckhöhen von 15.000 ft und 18.000

Auswirkung einer simulierten Flüssigkeitsbewegung in der ...hss.ulb.uni-bonn.de/2013/3384/3384.pdf · Auswirkung einer simulierten Flüssigkeitsbewegung in der Zahnpulpa auf die

Seminar: Agenten in simulierten Umgebungen 1 Implementierung einer RoboCup Soccer Server Fußball-Mannschaft Alexander Bernard Johannes Tuchscherer 17.01.2005

Entscheidungsunterstützungssysteme IWI Frankfurt 2004 Software-Agenten zur Entscheidungsunterstützung Warum Agenten? –Technologie- und Organisationstrends

4. Agentenorientierte Simulation & HLA · Simulation kann als Hilfsmittel eingesetzt werden, um • die reale Umwelt des Agenten nachzubilden und den Agenten per Simulation zu testen

Visual Analytics zur Unterstützung von Multi-Agenten ...ubicomp/... · Visual Analytics zur Unterstützung von Multi-Agenten-Simulationen JanusDybulla janus-dybulla@haw-hamburg.de

IT-Sicherheit in Terminalserver-Umgebungen ...2014.kes.info/archiv/material/bsikongress2007/poster-zamzow.pdf · IT-Sicherheit in Terminalserver-Umgebungen Bausteinentwicklung in

,,Navigation mobiler Systeme in Indoor-Umgebungen”ots.fh-brandenburg.de/downloads/abschlussarbeiten/da_joerg_dressler.pdf · Aufgabenstellung,,Navigation mobiler Systeme in Indoor-Umgebungen”

9 Ausgewählte Themen · 2000. 1. 25. · 9 Ausgewählte Themen 27. Vorlesung: Mensch-Maschine-Kommunikation – Von Agenten zu Interface-Agenten ! " und Standpunkt IW • Intelligenz

Dokument1 - Softshell · zusichern, und gaben diese anschließend an unsere Agenten weiter. Zum Schluss griffen Agenten verbunden Sind und 0b ihre Konfi- guration aktuell ist. Darüber