3.VL - CompInt

Start: Folie 80 Ende: Folie 97

Einführung und Orientierung

Willkommen zur Vorlesung über Intelligente Agenten und deren Zielsetzungen. Diese Vorlesung ist speziell für Informatikstudenten konzipiert und dient als Lernhilfe, ohne dabei übermäßig erschöpfend zu sein. Um den Überblick zu behalten, findet die Vorlesung auf drei parallelen Tracks statt:

1. Vorlesungstrack: Hier werden die theoretischen Konzepte anhand von Folien erläutert.
2. Übungstrack: Dieser ist weiter unterteilt in Übungsblätter, von denen nächste Woche das erste veröffentlicht wird.
3. Python-Tutorial: Bisher habt ihr Reading-Exercises durchgeführt, die euch mit praktischen Programmieraufgaben vertraut machen.

Alle relevanten Informationen, inklusive des Zeitplans und weiterer Details, sind auf der Vorlesungswebseite verfügbar.

Struktur der Vorlesung

Die Vorlesung konzentriert sich auf die Computation und National Intelligence. Wir starten direkt mit dem heutigen Thema und nutzen die Folien, auf denen wir zuletzt aufgehört haben, inklusive meiner Annotationen. Unser Fokus liegt darauf, die Möglichkeiten der Erstellung intelligenter Agenten zu erkunden und deren Zielsetzungen zu klassifizieren.

Intelligente Agenten und Ziele

Intelligente Agenten agieren innerhalb einer Umgebung und verfolgen bestimmte Ziele. Diese Ziele können unterschiedlich komplex sein und auf verschiedene Arten formuliert werden. Wir teilen die Agenten basierend auf ihren Zielsetzungen in verschiedene Klassen ein:

• Klasse Null: Agenten ohne spezifische Ziele oder mit allgemeinen Zielsetzungen.
• Klasse 1: Einführung der einfachsten Form von Zielen, dargestellt durch Prädikate.
• Klasse 1.5: Erweiterung um mehrere Ziele, die gleichzeitig erfüllt werden müssen.
• Weitere Klassen: Komplexere Zielsetzungen, die Gewichtungen und Prioritäten beinhalten.

Prädikate als Ziele

Ein Prädikat ist eine Funktion, die einen Wahrheitswert (True oder False) zurückgibt. Mathematisch ausgedrückt:

$$\Gamma :\text{Policy}\to \{\text{goal fulfilled, not fulfilled}\}$$

Dies ist die grundlegendste Form eines Ziels. Ein Prädikat kann beispielsweise bestimmen, ob eine bestimmte Bedingung erfüllt ist oder nicht. Komplexere Zieldefinitionen sind möglich, aber ein Prädikat bietet eine einfache Basis, um die Erfüllung von Zielen zu überprüfen.

Beispiele für Szenarien mit intelligenten Agenten

Um die Zielsetzungen intelligenter Agenten besser zu verstehen, betrachten wir vier Beispielszenarien:

1. Vacuum World
2. Grid World
3. Cutting Marble
4. Autonomous Driving

1. Vacuum World

Szenario

• Umgebung: Zwei Räume.
• Agent: Ein Roboter bewegt sich zwischen den Räumen.
• Zustände: In jedem Raum kann Staub vorhanden sein (dirty) oder nicht (clean).

Zielsetzung

Das intuitive Ziel ist, dass der Roboter möglichst viel Staub aufsammelt oder die Räume sauber hält. Mathematisch können wir ein einfaches Kriterium formulieren:

$$\Gamma (\pi )=\text{clean}$$

Eine mögliche Policy könnte beispielsweise jede zweite Zeiteinheit die Aktion clean ausführen. Eine sehr einfache Policy wäre, dass der Roboter immer die Aktion clean ausführt, unabhängig von der aktuellen Situation. Dies erfüllt das Ziel auf einem rudimentären Niveau, ist jedoch wenig effizient.

Erweiterte Zielsetzungen

Wir können komplexere Ziele definieren, z.B.:

• Effizienz: Der Roboter soll möglichst wenig Energie verbrauchen.
• Reichweite: Der Roboter soll alle Räume innerhalb einer bestimmten Zeit reinigen.
• Priorisierung: Räume mit mehr Staub sollen zuerst gereinigt werden.

2. Grid World

Szenario

• Umgebung: Ein Gitterfeld, ähnlich einem Schachbrett.
• Agent: Ein Agent, der sich innerhalb des Gitters bewegt.
• Aktionen: Go North, Go East, Go South, Go West.
• Sensoren: Der Agent kann die umliegenden Felder und seine aktuelle Position erkennen.

Zielsetzung

gamma holds if the agent never executes action "do_nothing" twiche in a row

$$\gamma (\pi )⟺\overline{\exists }t:a_t=a_{t+1}=\text{"do\_nothing"}$$

Ein häufiges Sicherheitskriterium ist, dass der Agent nicht gegen Wände läuft. Mathematisch ausgedrückt:

$$\forall t:{\text{Wenn Observation}}_t=\text{Blockt North},{\text{dann Aktion}}_t\ne \text{Go North}$$

Dies bedeutet, dass der Agent niemals die Aktion Go North ausführen darf, wenn sich dort eine Wand befindet. Solche Sicherheitskriterien sind essenziell, um Fehlverhalten des Agenten zu verhindern.

Erweiterte Zielsetzungen

• Pfadoptimierung: Der Agent soll den kürzesten Weg zu einem Zielpunkt finden.
• Exploration: Der Agent soll alle erreichbaren Felder innerhalb des Gitters erkunden.
• Interaktion: Der Agent soll mit Objekten innerhalb des Gitters interagieren (z.B. Objekte aufnehmen oder ablegen).

2.1 Resource / StockTrading

$$\begin{array}{rl}{o}^{\ast }& \in \mathcal{O}\\ o_x^{\ast }& =\text{"Reddit says buy"}+x\end{array}$$

$\gamma$ holds iff everytime Reddit says,everyone should buy $\alpha$ stock, we buy 10 of that stock

$$\gamma (\pi )⟺\forall o_t\in \mathcal{O}:\exists x:o_t=o_t^{\ast }⟹(\text{’buy’},x,10)={\alpha }_t$$

Possible Policy

Nur ein Beispiel nicht komplett korrekt

$$\Gamma (o)=\{\begin{array}{ll}(\text{’buy’,’Gamestop’},0),& \text{ if o = "Gamestop increase"}\\ & \\ (\text{’sell’,’Gamestop’},1),& \text{ otherwise}\end{array}$$

2.2 Personal Life Assistant

$\gamma$ holds iff PLA recommends drinking water atleast six times a day

$${\mathcal{A}}^{\ast }\in \mathcal{A}\text{so that }{a}^{\ast }\in {\mathcal{A}}^{\ast }\text{means "drinking water"}$$

• Assume: 50 recommandations (=action) per day

$$\gamma (\pi )⟺\forall t:\exists t^{{}^{\prime }}\in [t;t+50]:a_{t^{{}^{\prime }}}\in {\mathcal{A}}^{\ast }$$

3. Cutting Marble

Szenario

• Umgebung: Eine Werkstatt zur Bearbeitung von Marmorsteinen.
• Agent: Ein Roboter, der Marmorsteine bearbeitet.
• Ziel: Herstellung einer bestimmten Form oder Statue aus einem Marmorstein.

Zielsetzung

Das Ziel könnte sein, dass der Roboter eine bestimmte Statue herstellt. Mathematisch könnte dies wie folgt formuliert werden:

$$\Gamma (\pi )=\exists t:{\text{Observation}}_t=\text{Statue}$$

Dies bedeutet, dass es einen Zeitpunkt t geben muss, zu dem die Observation des Agenten eine fertige Statue zeigt. Diese Formulierung ist sehr allgemein und lässt viel Spielraum für die tatsächliche Umsetzung der Policy.

Herausforderungen

• Präzision: Die genaue Form und Größe der herzustellenden Statue muss spezifiziert werden.
• Feinsteuerung: Die Aktionen des Roboters müssen präzise koordiniert werden, um die gewünschte Form zu erreichen.
• Qualitätskontrolle: Sicherstellen, dass die hergestellte Statue den Qualitätsstandards entspricht.

4. Autonomous Driving

Szenario

• Umgebung: Straßenverkehr mit verschiedenen Verkehrsteilnehmern.
• Agent: Ein autonomes Fahrzeug mit Sensoren zur Erkennung von Fußgängern, anderen Fahrzeugen und Verkehrsschildern.
• Aktionen: Beschleunigen, Bremsen, Abbiegen, Spurwechseln.

Zielsetzung

Ein Beispielziel könnte sein, dass das Fahrzeug niemals beschleunigt, wenn ein Fußgänger vor dem Fahrzeug erkannt wird:

$$\Gamma (\pi )=\forall t:\text{Wenn Fußga¨nger vor mir},{\text{dann Aktion}}_t\ne \text{Accelerate Ahead}$$

Erweiterte Zielsetzungen

• Sicherheitsvorgaben: Vermeidung von Unfällen durch rechtzeitiges Bremsen oder Ausweichen.
• Effizienz: Optimierung des Kraftstoffverbrauchs und der Fahrzeit.
• Komfort: Gewährleistung eines ruhigen und komfortablen Fahrerlebnisses.
• Umweltfreundlichkeit: Reduktion von Emissionen durch optimierte Fahrweise.

Suchalgorithmen für Policies

Um eine Policy zu finden, die ein bestimmtes Ziel erfüllt, verwenden wir Suchalgorithmen. Zwei grundlegende Methoden sind:

1. Brute Force Search
2. Random Search

1. Brute Force Search

Ein einfacher Algorithmus, der systematisch alle möglichen Policies durchgeht, bis eine gefunden wird, die das Ziel erfüllt.

Funktionsweise

1. Policy Space: Eine abzählbare Menge aller möglichen Policies.
2. Iteration: Jede Policy wird nacheinander überprüft.
3. Überprüfung: Für jede Policy wird geprüft, ob sie das Ziel erfüllt ($\Gamma (\pi )$).
4. Rückgabe: Die erste Policy, die das Ziel erfüllt, wird zurückgegeben.

Beispielcode

def brute_force_search(gamma, policy_space):
    for pi in policy_space:
        if gamma(pi):
            return pi
    return None

Annahmen

• Der Policy-Space ist abzählbar und durchsuchbar.
• Jede Policy kann effizient überprüft werden, ob sie das Ziel erfüllt.

Herausforderungen

• Komplexität: Der Policy-Space ist oft extrem groß oder sogar unendlich, was die Durchsuchung ineffizient macht.
• Rechenzeit: Brute Force kann sehr lange dauern, insbesondere bei komplexen Zielen und großen Policy-Spaces.

2. Random Search

Anstatt systematisch alle Policies zu durchlaufen, wählt Random Search zufällig Policies aus dem Policy-Space aus und überprüft diese.

Funktionsweise

1. Sampling: Zufällige Auswahl einer Policy aus dem Policy-Space.
2. Überprüfung: Prüfen, ob die ausgewählte Policy das Ziel erfüllt ($\Gamma (\pi )$).
3. Wiederholung: Dieser Prozess wird für eine vorgegebene Anzahl von Versuchen (n) wiederholt.
4. **R

Rückgabe: Die erste Policy, die das Ziel erfüllt, wird zurückgegeben.

Beispielcode

import random
 
def random_search(gamma, policy_space, n):
    for _ in range(n):
        pi = random.choice(policy_space)
        if gamma(pi):
            return pi
    return None

Vorteile gegenüber Brute Force

• Effizienz: Kann schneller eine geeignete Policy finden, insbesondere in sehr großen Policy-Spaces.
• Flexibilität: Keine feste Reihenfolge der Durchsuchung, wodurch zufällige Policies möglicherweise schneller das Ziel erreichen.

Nachteile

• Keine Garantie: Es besteht keine Sicherheit, dass innerhalb der vorgegebenen Anzahl von Versuchen eine geeignete Policy gefunden wird.
• Wiederholungen: Möglichkeit, dieselben Policies mehrfach auszuwählen, was die Suche ineffizient macht.

Programmierung von Policies

Die Umsetzung von Policies in einer Programmiersprache wie Python bringt einige Herausforderungen mit sich. Wir betrachten ein Beispiel, um diese zu verdeutlichen.

Beispiel: Python-Policy für Vacuum World

while True:
    observation = receive_observation()
    if observation.is_clean:
        # Aktion: Nichts tun
        pass
    else:
        execute_action('clean')
 
    if robot_current_position == 0:
        execute_action('move_right')
    else:
        execute_action('move_left')

Probleme bei der Programmierung

1. Boilerplate-Code: Notwendigkeit von Bibliotheken und Frameworks, um grundlegende Funktionen wie receive_observation() und execute_action() zu implementieren.
2. Fehlende Struktur: Schwierigkeit, Policies systematisch zu durchsuchen, da der Code oft unübersichtlich und unstrukturiert ist.
3. Syntaxfehler: Gefahr von Fehlern bei der manuellen Codierung, die die Funktionalität der Policy beeinträchtigen können.
4. Eskalierende Komplexität: Bei komplexeren Policies wächst der Code schnell in Umfang und Komplexität, was die Wartung und Erweiterung erschwert.

Abstrakte Syntaxbäume

Eine verbesserte Methode zur Darstellung von Policies ist die Verwendung von abstrakten Syntaxbäumen (ASTs). Diese bieten eine strukturierte und hierarchische Darstellung des Codes, die einfacher zu manipulieren und zu analysieren ist.

Beispiel: Abstrakter Syntaxbaum für die Vacuum World Policy

Robot
├── while True
│   ├── observation = receive_observation()
│   ├── if observation.is_clean
│   │   └── pass
│   ├── else
│   │   └── execute_action('clean')
│   ├── if robot_current_position == 0
│   │   └── execute_action('move_right')
│   └── else
│       └── execute_action('move_left')

Vorteile von ASTs

• Strukturierte Darstellung: Klare Hierarchie und Modularität erleichtern die Analyse und Modifikation.
• Einfache Manipulation: Automatisierte Tools können ASTs effizient durchsuchen und verändern.
• Fehlerreduktion: Minimierung von Syntaxfehlern durch strukturierte Repräsentation.

Herausforderungen

• Komplexität der Baumstruktur: Für sehr komplexe Policies kann der AST schnell unübersichtlich werden.
• Integration mit Suchalgorithmen: Die Nutzung von ASTs in Suchalgorithmen erfordert spezielle Techniken zur Traversierung und Manipulation.

Behavior Trees

Behavior Trees sind eine Abstraktionsmethode, die es ermöglicht, komplexe Verhaltensweisen modular und übersichtlich zu gestalten. Sie sind besonders in der Spieleentwicklung und der Robotik verbreitet.

Konzept

• Knoten: Jedes Verhalten wird als Knoten im Baum dargestellt.
• Hierarchie: Verhaltensweisen werden hierarchisch angeordnet, um komplexe Aktionen aus einfachen zu kombinieren.
• Modularität: Einfache Verhaltensweisen können wiederverwendet und in verschiedenen Kontexten eingesetzt werden.

Beispiel: Behavior Tree aus der Unreal Engine

Abbildung: Beispiel eines Behavior Trees aus der Unreal Engine.

Vorteile

• Modularität: Einfache Kombination und Wiederverwendung von Verhaltensweisen.
• Lesbarkeit: Bessere Verständlichkeit für Designer und Entwickler.
• Flexibilität: Einfache Anpassung und Erweiterung von Verhaltensweisen ohne tiefgreifende Änderungen am gesamten System.

Anwendung in der Praxis

Behavior Trees werden häufig verwendet, um das Verhalten von Non-Player Characters (NPCs) in Videospielen zu steuern. Sie ermöglichen es, komplexe Verhaltensmuster zu erstellen, die auf verschiedene Situationen reagieren können, ohne dass der Code unübersichtlich wird.

Zielklassen

Wir erweitern die Zielklassen, um komplexere Zielsetzungen zu ermöglichen. Besonders wichtig ist die Möglichkeit, mehrere Ziele gleichzeitig zu definieren und zu überprüfen.

Klasse 1.5: Multiple Goals

In Klasse 1.5 können Ziele aus mehreren Prädikaten bestehen, die alle erfüllt sein müssen:

$$\Gamma (\pi )=P_1(\pi )\wedge P_2(\pi )\wedge \cdots \wedge P_n(\pi )$$

Vorteile

• Granularität: Besseres Verständnis der Erfüllung von Zielen durch einzelne Kriterien.
• Flexibilität: Möglichkeit, unterschiedliche Kriterien zu kombinieren und komplexere Zielsetzungen zu definieren.

Nachteile

• Keine Gewichtung: Alle Kriterien sind gleich wichtig, wodurch keine Prioritäten gesetzt werden können.
• Komplexität: Schwieriger zu bewerten, welche Kriterien bereits erfüllt sind und welche noch fehlen.

Beispiel

In der Grid World könnten mehrere Sicherheitskriterien definiert werden, z.B.:

$$\Gamma (\pi )=(\forall t:\text{Wenn Blockt North},{\text{dann Aktion}}_t\ne \text{Go North})\wedge (\forall t:\text{Wenn Blockt East},{\text{dann Aktion}}_t\ne \text{Go East})$$

Dies stellt sicher, dass der Agent niemals gegen eine Wand in eine beliebige Richtung läuft.

Model Checking

Model Checking ist ein Ansatz aus der formalen Verifikation, der es ermöglicht, Programme gegen logische Spezifikationen zu überprüfen. Dies bietet eine Möglichkeit, die Korrektheit von Programmen zu garantieren, ohne umfangreiche Tests durchführen zu müssen.

Konzept

1. Spezifikation: Formale Beschreibung der gewünschten Eigenschaften oder Ziele des Programms.
2. Modell: Abstrakte Darstellung des Programms, oft in Form eines Zustandsautomaten oder eines abstrakten Syntaxbaums.
3. Überprüfung: Automatisierte Tools durchsuchen das Modell, um zu überprüfen, ob die Spezifikationen erfüllt sind.

Vorteile

• Sicherheit: Garantierte Erfüllung der Spezifikation ohne die Notwendigkeit umfangreicher Tests.
• Automatisierung: Effiziente und systematische Überprüfung durch spezialisierte Tools.
• Fehlerreduktion: Frühe Erkennung von Fehlern und Inkonsistenzen in der Programmstruktur.

Nachteile

• Komplexität: Aufwändige Spezifikation und Modellierung, besonders bei großen und komplexen Programmen.
• Begrenzte Anwendbarkeit: Funktioniert am besten für Programme mit klar definierten und überschaubaren Zuständen.
• Rechenaufwand: Kann bei sehr großen Modellen sehr ressourcenintensiv sein.

Beispiel: Model Checking für die Vacuum World Policy

Process Robot
├── is_clean == false → execute_clean → Robot
├── is_clean == true & position == 0 → execute_move_right → Robot
└── is_clean == true & position == 1 → execute_move_left → Robot

In diesem Beispiel wird das Verhalten des Roboters als Prozess beschrieben. Der Model Checker würde überprüfen, ob dieser Prozess die Spezifikation $\Gamma (\pi )$ erfüllt, indem er alle möglichen Ausführungen des Prozesses durchgeht.

Anwendung

Model Checking wird häufig in sicherheitskritischen Bereichen eingesetzt, wie z.B. in der Luftfahrt, der Automobilindustrie oder bei der Entwicklung von Betriebssystemen. Es stellt sicher, dass Systeme unter allen möglichen Bedingungen korrekt funktionieren.

Zusammenfassung

In dieser Vorlesung haben wir die Grundlagen intelligenter Agenten und deren Zielsetzungen kennengelernt. Wir haben verschiedene Szenarien untersucht, um die Formulierung und Erfüllung von Zielen zu verstehen. Zudem haben wir grundlegende Suchalgorithmen zur Findung passender Policies betrachtet und die Herausforderungen bei der Programmierung von Policies diskutiert. Methoden wie abstrakte Syntaxbäume und Behavior Trees bieten strukturierte Ansätze zur Darstellung und Manipulation von Policies. Abschließend haben wir den Ansatz des Model Checkings kennengelernt, der eine formale Verifikation von Programmen ermöglicht.

Ausblick

In der nächsten Vorlesung werden wir tiefer in die Thematik eintauchen und komplexere Methoden zur Formulierung und Verifikation von Zielen und Policies kennenlernen. Außerdem werden wir praktische Übungen durchführen, um das Gelernte anzuwenden und zu vertiefen. Themen wie Reinforcement Learning, Neuronale Netzwerke zur Policy-Generierung und Fortgeschrittene Verifikationstechniken werden behandelt.

---