Such-Probleme

Modellierung

Unser Ziel ist nicht in einem Schritt offensichtlich erreichbar.

Wir brauchen einen Plan mit mehreren Schritten.

Wir finden den Plan durch Suchen.

https://www.google.com/maps

Mögliche Aktionen

  • Geradeaus fahren
  • Nach Links fahren
  • Nach Rechts fahren

Ziele

  • Kürzeste Route
  • Schnellste Route
  • Billigste Route
  • Szenischste Route

https://commons.wikimedia.org/wiki/File:Robotic_ROV_Manipulator_Arm_2.png

Mögliche Aktionen

  • Gelenk drehen
  • Gelenk aus-/einfahren
  • Endeffektor einsetzen

Ziele

  • Schnellster Pfad
  • Möglichst Energieeffizient
  • Möglichst Sicher

https://commons.wikimedia.org/wiki/File:Rubiks_cube_by_keqs.jpg

Mögliche Aktionen

  • Links / rechts / oben / unten / vorne / hinten
    im / gegen den Uhrzeigersinn drehen.

Ziele

  • Zielkonfiguration erreichen
  • Minimale Anzahl Züge

https://commons.wikimedia.org/wiki/File:VLSI_VL82C389A_die.jpg

Mögliche Aktionen

  • Geradeaus
  • Links
  • Rechts
  • Ebene wechseln

Ziele

  • Kürzester Weg
  • Minimale Anzahl Ebenenwechsel
  • Andere Wege möglichst wenig stören
Such Probleme
Regression Markov Decision Processes Constraint Satisfaction Problems
Classifier Kompetitive Spiele Bayesian networks
Reflex Zustände Variablen Logik
"Niedrige Intelligenz" "Höhere Intelligenz"

Classifier (Reflex basiertes Modell):
$x \Rightarrow f \Rightarrow$ Aktion $y\in \{-1, +1\}$

Such Problem (State basiertes Modell):
$x \Rightarrow f \Rightarrow$ Folge von Aktionen $(a_1, a_2, a_3, \ldots )$

Warum können wir nicht einfach ein Reflex Modell nehmen und uns eine Aktion nach der anderen generieren?

Unsere Aktionen können weitreichende Konsequenzen haben.

Ein Suchproblem besteht aus:

  • Einer Menge an möglichen Zuständen $S$
  • Einem initialen Zustand $s_{start}$
  • Einer Menge von Zielzuständen $S_{target}$, bzw. Funktion $IsEnd(s)$
  • Aktionen die in einem bestimmten Zustand gemacht werden können $Actions(s)$
  • Zu jeder Aktion der resultierende Zustand $Succ(s,a)$
  • Zu jeder Aktion die Kosten $Cost(s,a)$

Beispiel: Navigation

Modellierung

Einteilung in mögliche Zustände

$S = \{A\uparrow, A\downarrow, B\uparrow, B\downarrow, C\uparrow, C\downarrow, D\rightarrow, D\leftarrow, E\rightarrow, E\leftarrow\}$

$s_{start} = A\uparrow$
$S_{target} = \{ E\rightarrow \}$

Aktionen

  • $Actions(A\uparrow) = \{GoRight, GoStraight\}$
  • $Actions(D\rightarrow) = \{TurnAround\}$
  • $Actions(B\downarrow) = \{GoLeft, GoStraight\}$

Ergebnisse von Aktionen

  • $Succ(A\uparrow, GoRight) = D\rightarrow$
  • $Succ(D\rightarrow, TurnAround) = D\leftarrow$
  • $Succ(B\downarrow, GoStraight) = A\downarrow$

Kosten

  • $Cost(A\uparrow, GoRight) = 1$
  • $Cost(D\leftarrow, TurnArround) = 1$
  • $Cost(B\downarrow, GoStraight) = 1$

Modellierung als Graph

Jeder Zustand wird zu einem Knoten.

Jede Aktion und ihr Ergebnis werden zu einer Kante.

An die Kanten schreiben wir die Kosten (und ggf. den Namen der Aktion)

Kann man jedes Suchproblem als Graph aufmalen?

Jein

Die Menge $S$ kann extrem groß sein.

Ein Rubik's Cube hat 43 252 003 274 489 856 000 mögliche Konfigurationen

Beispiel: Spielautomat

Wir starten mit $1$ Punkt und wollen $n$ Punkte erreichen.

Wir können den linken Hebel ziehen, was uns $1$ Euro kostet um $1$ Punkt zu bekommen.

Wir können den rechten Hebel ziehen, was $2$ Euro kostet und unsere Punkte verdoppelt.

Wie erreichen wir am günstigsten $n$ Punkte?

Jupyter


          class Slotmachine:
          def __init__(self, n):
              self.n = n

          def start_state(self):
              return 1

          def is_end(self, state):
              return state == self.n

          def succ_and_cost(self, state):
              # Return list of (action, newState, cost) triples
              result = []
              if state + 1 <= self.n:
                  result.append(('linker Hebel', state + 1, 1))
              if state * 2 <= self.n:
                  result.append(('rechter Hebel', state * 2, 2))
              return result

Ansatz: Wir bauen einen Such-Baum mit allen möglichen Entscheidungen auf.

Wurzelknoten sind Start-Zustände.

Blätter sind Ziel-Zustände (oder Sackgassen / verbotene Zustände).

Beispiel: Wolf, Ziege und Kohlkopf

Ein Bauer möchte einen Kohlkopf, eine Ziege und einen Wolf über einen Fluss bringen. Der Farmer kann im Boot nur einen Gegenstand oder Tier mitnehmen. Der Wolf kann nicht allein mit der Ziege und die Ziege nicht allein mit dem Kohlkopf bleiben.

Wie gelingt die Überquerung mit möglichst wenig Überfahrten?

https://xkcd.com/1134/

Start Zustand: $BKZW ||$

Ziel Zustand: $|| BKZW$

Erlaubte Aktionen

  • $B\rightarrow$, $B\leftarrow$
  • $BK\rightarrow$, $BK\leftarrow$
  • $BZ\rightarrow$, $BZ\leftarrow$
  • $BW\rightarrow$, $BW\leftarrow$

Jupyter


class RiverCrossingProblem:
def __init__(self):
    pass
def start_state(self):
    return (set(["B", "K", "Z", "W"]), set())
def is_end(self, state):
    return state == (set(), set(["B", "K", "Z", "W"]))
def succ_and_cost(self, state):
    # Return list of (action, newState, cost) triples

    bad_combinations = [set(["K", "Z"]), set(["Z", "W"])]
    if state[0] in bad_combinations or state[1] in bad_combinations:
        return []

    if "B" in state[0]:
        direction = "→"
        potential_passengers = []
        for passenger in state[0]:
            potential_passengers.append(set(["B"]) | set([passenger]))
    else:
        direction = "←"
        potential_passengers = []
        for passenger in state[1]:
            potential_passengers.append(set(["B"]) | set([passenger]))

    result = []
    for passengers in potential_passengers:
        action = "".join(passengers) + direction
        if direction == "→":
            new_state = (state[0] - passengers, state[1] | passengers)
        else:
            new_state = (state[0] | passengers, state[1] - passengers)

        result.append( (action, new_state, 1) )

    return result

Such-Probleme

Einfache Such-Algorithmen

Backtracking Search

Baue ganzen Suchbaum rekursiv auf.

Wie groß kann ein Suchbaum werden?

$D$: Tiefe des Baums

$b$: Branching Faktor (wie viele Kinder hat ein Knoten)

Größenordnung $b^D$ Knoten

Jupyter


def backtracking_search(problem):
    def recurse(state, history, total_cost):
        if problem.is_end(state):
            return total_cost, history

        best_cost = float("+inf")
        best_history = None

        for action, new_state, cost in problem.succ_and_cost(state):
            if new_state == problem.start_state() or new_state in [state for _, state, _ in history]:
                # Do not visit a state again
                continue

            candidate_cost, candidate_history = recurse(new_state, history + [(action, new_state, cost)], total_cost + cost)

            if candidate_cost < best_cost:
                best_cost = candidate_cost
                best_history = candidate_history

        return best_cost, best_history

    return recurse(problem.start_state(), [], 0)
AlgorithmusKostenZeitSpeicher
Backtracking SearchAlle$O(b^D)$$O(D)$

Depth-first search (DFS)

Annahme: Kosten sind $0$

Idee: Backtracking Search, aber stoppe an erstem end State

Komplexität?

Speicher: $O(D)$

Zeit: $O(b^D)$

Aber: Wir haben die Chance schneller zu sein, falls eine Lösung leicht zu finden ist.

AlgorithmusKostenZeitSpeicher
Backtracking SearchAlle$O(b^D)$$O(D)$
DFS0$O(b^D)$$O(D)$

Breadth-first search (BFS)

Annahme: Kosten sind konstant $c \geq 0$

Idee: Erkunde den Such-Baum Ebene für Ebene.

Komplexität?

Zeit: $O(b^d)$, $d$ ist die Anzahl an Aktionen der Lösung

Speicher: $O(b^d)$

AlgorithmusKostenZeitSpeicher
Backtracking SearchAlle$O(b^D)$$O(D)$
DFS$0$$O(b^D)$$O(D)$
BFS$c \geq 0$$O(b^d)$$O(b^d)$

DFS with iterative deepening (DFS-ID)

Annahme: Kosten sind konstant $c \geq 0$

Idee: Lasse DFS nur bis zu einer maximalen Tiefe $d$ laufen. Das machen wir für $d = 1, 2, 3, \ldots$ bis wir eine Lösung haben.

Komplexität?

Speicher: $O(d)$

Zeit: $O(b^d)$ (wie in BFS)

Wir besuchen viele Knoten mehrfach; jede Ebene hat aber mehr Knoten, wie der ganze Baum vorher, daher fällt das nicht so ins Gewicht.

AlgorithmusKostenZeitSpeicher
Backtracking SearchAlle$O(b^D)$$O(D)$
DFS$0$$O(b^D)$$O(D)$
BFS$c \geq 0$$O(b^d)$$O(b^d)$
DFS-ID$c \geq 0$$O(b^d)$$O(d)$

Mit unseren Algorithmen kommen wir nicht um exponentiellen Zeitverbrauch herum.

Wir können aber exponentiellen Speicherverbrauch vermeiden. Und Speicher ist meistens wertvoller als Zeit.

Such-Probleme

Dynamic Programming

Wie kommen wir mit weniger als exponentieller Zeit zum Ziel?

$FutureCost(s) = \begin{cases} 0 && if\ IsEnd(s) \\ min_a [Cost(s,a) + FutureCost(Succ(s, a))] && else \end{cases}$

"Bellman equation"

Kern-Idee: $FutureCost(s)$ hängt nur von $s$ ab, nicht von der Historie.

Rekursion in unserem Backtracking Search Algorithmus basiert auf: Aktueller Zustand + Historie

Suchbaum hat viele Dopplungen

Kontrahieren gleicher Knoten => Suchgraph

Dynamic Programming = Backtracking Search + Cache

Keine Historie in Rekursion bedeuted: Suchbaum darf keine Zyklen haben!

Jupyter


          def dynamic_programming(problem):
          cache = {} # remember state -> future_cost(state)
          def future_cost(state):
              if problem.is_end(state):
                  return 0
              if state in cache:
                  return cache[state]

              result = min(cost + future_cost(new_state) for action, new_state, cost in problem.succ_and_cost(state))

              cache[state] = result
              return result
          return future_cost(problem.start_state())

Wir besuchen jeden Zustand nur noch einmal: Exponentielle Reduktion der Laufzeit

Laufzeit: $O(2N)$ (für den Spielautomat),
$O(|S|^2)$ allgemein.

Speicher: $O(|S|)$

Durch eine gute Modellierung der Zustände können wir die Vergangenheit ignorieren.

Modifikation vom Spielautomat: Wir dürfen den rechten Hebel nicht zweimal in Folge ziehen.

Wir können im Zustand speichern, welchen Hebel wir zuletzt gezogen haben.

Zustand: (Punktezahl, letzter Hebel war rechts)

$N$ mögliche Zustände $\Rightarrow$ $2N$ mögliche Zustände.

Neue Modifikation: Erreiche $N$ möglichst günstig, aber zwischendurch muss die Punktezahl mindestens 3 mal gerade gewesen sein.

Zustand: (Punktezahl, Anzahl gerader Punktzahlen bisher)

Pro Variante: (Punktezahl, min(3, Anzahl gerader Punktzahlen bisher))

Such-Probleme

Uniform cost search (UCS)

Was machen wir, wenn wir Zyklen haben?

Beobachtung: Prefix eines optimalen Pfades ist optimal.

Analog zu FutureCost

Graph ist azyklisch => Dynamic Programming berechnet PastCost(s) vor PastCost(s').

Wenn wir Zyklen haben, dann müssen wir das anders sicherstellen.

Kernidee von UCS: Bearbeite zuerst die Zustände mit den günstigsten PastCost - also mit den geringsten Kosten seit dem Start

Voraussetzung: Kosten sind nicht negativ; $Cost(s,a) \geq 0$

Anderer Name für UCS: Dijkstras Algorithmus.

  • Erkundet: Zustände wo wir optimale PastCost kennen.
  • Offen: Nicht erkundete Nachfolger von erkundeten Zuständen.
  • Unbekannt: Zustände, zu denen wir noch keinen Weg kennen.
  • Starte mit $s_{start}$ im "Offen" Set. $Priority(s) = 0$
  • Solange kein Ziel Zustand erkundet ist:
    • Wähle Zustand $s$ mit geringsten $Priority(s)$ aus den offenen Zuständen.
    • $s$ ist nun erkundet.
    • Alle Nachfolger $s'$ von $s$ sind jetzt offen. $Priority(s') = min(Priority(s'), Priority(s) + Cost(s, a))$

https://commons.wikimedia.org/wiki/File:Dijkstras_progress_animation.gif

Jupyter

Priority Queue


          import heapq

          class PriorityQueue:
              def __init__(self):
                  self.heap = []
                  self.priorities = {}

              def update(self, state, priority):
                  # Set new priority for a state or add it to queue
                  old_prio = self.priorities.get(state)
                  if old_prio is None or priority < old_prio:
                      self.priorities[state] = priority
                      heapq.heappush(self.heap, (priority, state))
                      return True
                  else:
                      return False

              def pop(self):
                  # Return state with minimum priority as tuple (state, priority)

                  while len(self.heap) > 0:
                      priority, state = heapq.heappop(self.heap)
                      if self.priorities[state] < priority:
                          # This is an old version which we already updated
                          continue
                      return (state, priority)

                  return (None, None)

UCS


          def uniform_cost_search(problem):
              open_set = PriorityQueue()
              open_set.update(problem.start_state(), 0)

              while True:
                  state, past_cost = open_set.pop()

                  if problem.is_end(state):
                      return (past_cost, [])

                  for action, new_state, cost in problem.succ_and_cost(state):
                      open_set.update(new_state, past_cost + cost)

Warum ist das Ergebnis von UCS optimal?

Theorem: Wenn Zustand $s$ erkundet wird, ist $Priority(s) = PastCost(s)$

Sei $s$ der erste erkundete Zustand für den es einen besseren Weg $p'$ zu $s$ gibt.

$p'$ muss irgendwo die erkundete Region verlassen. Sei $u$ ist der erste offene Zustand in $p'$, $t$ sein Vorgänger und $a$ die Aktion von $t$ nach $u$.

$\Rightarrow Priority(t) + Cost(t,a) < Priority(s)$

$\Rightarrow Priority(u) < Priority(s)$ - Widerspruch!

DP vs UCS

Alg. Zyklen Kosten Zeit Speicher
DP nein alle $O(N)$ $O(N)$
UCS ja $\geq 0$ $O(n \log(n))$ $O(n)$

$N$ Anzahl Zustände; $n$ Anzahl Zustände, die näher am Start als ein Ziel sind.

Annahme: Anzahl Nachfolger je Zustand ist konstant.

UCS erkundet potentiell weniger, hat aber Overhead für die Priority Queue.
Anzahl Kanten pro Zustand ist meistens eine kleine Konstante

Such-Probleme

A*

Erkunden wir Knoten in der falschen Richtung unnötig?

UCS: Erkunde Knoten in der Reihenfolge $PastCost(s)$

Ideal: Erkunde Knoten in der Reihenfolge $PastCost(s) + FutureCost(s) = OptimalCost(s)$

A*: Erkunde Knoten in der Reihenfolge $PastCost(s) + h(s)$

$h(s)$ ist eine Heuristik, welche $FutureCost(s)$ abschätzt.

https://commons.wikimedia.org/wiki/File:Dijkstras_progress_animation.gif
https://commons.wikimedia.org/wiki/File:Weighted_A_star_with_eps_5.gif

Algorithmus: UCS, aber mit einer kleinen Modifikation:
$Priority(s') = min(Priority(s'), PastCost(s) + Cost(s,a) + h(s'))$

Geht jede Heuristik?

$h$ ist zulässig (admissible), wenn sie $FutureCost$ nie überschätzt.

$h(s) \leq FutureCost(s)$

Eine zulässige Heuristik kann dazu führen, dass wir Zustände mehrfach besuchen müssen.
Das muss bei der Implementierung der Suche berücksichtigt werden!

$h$ ist monoton (consistent) wenn folgende Dreiecksungleichung für $s$ und Nachfolger $s'$ mit Aktion $a$ gilt:

$h(s) \leq cost(s,a) + h(s')$

Mit einer monotonen Heuristik liefert A* eine optimale Lösung und kein Zustand muss doppelt besucht werden.

Eine monotone Heuristik ist immer auch zulässig.

Eine Heuristik ist idealerweise monoton und so nah wie möglich an $FutureCost$ (also so groß wie möglich).

Wie kommen wir an gute Heuristiken?

Idee: Wir relaxieren Nebenbedingungen, so dass unser Problem einfacher wird.

Beispiel: Routensuche

Suchen den kürzesten / schnellsten Weg von A nach B

  • Distanz Luftlinie
  • Distanz Luftlinie geteilt durch maximale Geschwindigkeit

Beispiel: Schiebepuzzle

https://commons.wikimedia.org/wiki/File:15-puzzle_magical.svg

Relaxiere Nebenbedingung: Felder dürfen sich nicht überlappen.

Heuristik: Manhatten Distanz zum Ziel je Feld.

Tradeoff

Effiziente Berechnung von h

vs

Qualität von h (wie nah ist h an FutureCost)

Kombinieren von Heuristiken

Wenn $h_1$ und $h_2$ monotone Heuristiken sind, dann ist
$h(s) = max\{h_1(s), h_2(s)\}$
auch eine monotone Heuristik.

Ist A* grundsätzlich besser als Uniform cost search / Dijkstra?

It depends!

  • Wie aufwändig ist es einen Knoten zu expandieren?
  • Wie viel spart uns die Heuristik?
  • Wie aufwändig ist die Berechnung der Heuristik?
  • Wollen wir mehr als nur die beste Lösung?

Beispiel: Navigation / Routensuche

Routensuche hat oft wenig nutzen aus der A* Suche. Warum?

  • Knoten expandieren ist günstig, da wir den Suchgraphen explizit speichern können.
  • Einfache Heuristiken (Distanz / max Geschwindigkeit) helfen auf Innenstadtstrassen praktisch nicht.
  • Alternative Routen sind oft auch interessant.

Such-Probleme

Structured Perceptron

Spielautomat
Start: 1
Linker Hebel: s → s + 1; Kosten: 1 ?
Rechter Hebel: s → 2s; Kosten: 2 ?
Ziel: N

Was, wenn wir die Kosten nicht kennen?

Daten: Beispiel Pfade ("Linker Hebel", "Linker Hebel", "Rechter Hebel")

Das wir unsere Kosten / Zielfunktion nicht (genau) kennen ist ein häufiges Problem in der Praxis!

Kunden können einfacher Beispiele liefern als abstrakte Zahlen.

Forward Problem (Suche)
$Cost(s,a)$ → $(a_1, a_2, \ldots)$

Inverse Problem (Lernen)
$(a_1, a_2, \ldots)$ → $Cost(s,a)$

Input $x$: Such Problem ohne Kosten

Output $y$: Lösungspfad
["Linker Hebel", "Linker Hebel", "Linker Hebel"]

Wir modellieren Kosten abhängig von der Aktion:
$Cost(s,a) = w(a)$

Algorithmus: Structured Perceptron (einfach)

  • Initialisiere Gewichte $w$ zufällig
  • Wiederhole (bis keine Verbesserung oder Iterationslimit erreicht):
    • Pro Beispiel $(x,y) \in D_{train}$
      • Berechne Pfad $y'$ basierend auf $w$
      • Für Aktion $a \in y$: $w(a) \leftarrow w(a) - 1$
      • Für Aktion $a \in y'$: $w(a) \leftarrow w(a) + 1$

Jupyter

Ausblick: Kosten basierend auf Featuren

Kosten sind abhängig von Features $\phi$ aus Aktion und Zustand:
$Cost(s,a) = w \cdot \phi(s,a)$

Algorithmus: Structured Perceptron [Collins, 2002]

  • Initialisiere Gewichte $w$ zufällig
  • Wiederhole (bis keine Verbesserung oder Iterationslimit erreicht):
    • Pro Beispiel $(x,y) \in D_{train}$
      • Berechne Pfad $y'$ basierend auf $w$
      • $w \leftarrow w - \phi(y) + \phi(y')$