2.1 Pfadplanung & Navigation

Worum geht’s#

„Komm von A nach B” klingt nach einer trivialen Aufgabe — bis man sich klarmacht, wie unterschiedlich das Problem ist, je nachdem was der Agent über die Welt weiß. Ein Lieferroboter, der einen vollständigen Lageplan im Speicher hat, löst ein Graphensuchproblem: Orte sind Knoten, befahrbare Verbindungen sind Kanten, gesucht ist der kostengünstigste Pfad. Ein Roboter, der blind in eine unbekannte Höhle gesetzt wird, hat diesen Graphen nicht — er muss ihn sich ertasten, während er fährt.

Mich reizt an diesem Kapitel, dass diese beiden Welten ganz verschiedene Antworten erzwingen und trotzdem dieselbe Frage stellen: Wie navigiere ich zielgerichtet, ohne Sackgassen blind durchzuprobieren? Mit Karte ist die eleganteste Antwort A*, das die garantierte Optimalität von Dijkstra mit dem Tempo der gierigen Bestensuche verbindet. Ohne Karte sind es die verblüffend sparsamen Bug-Algorithmen, die mit nichts als „fahr aufs Ziel zu und taste dich an Hindernissen entlang” auskommen — und beweisbar terminieren. Ich finde es lehrreich, beide Extreme nebeneinanderzulegen: Sie markieren die Endpunkte einer Achse, auf der jedes reale Navigationssystem irgendwo dazwischenliegt.

Kernkonzepte#

Zwei Regime: mit Karte und ohne Karte#

Eine Karte ist eine explizite Repräsentation des Suchraums — meist ein Graph aus Orten und Verbindungen. Liegt sie vor, kann man vor der Fahrt rechnen: den gesamten Pfad bestimmen und dann abfahren. Liegt sie nicht vor, verzahnen sich Planen und Handeln; der Agent entscheidet lokal mit dem, was seine Sensoren gerade hergeben. Diese Unterscheidung zieht sich durch das ganze Thema und bestimmt, welche Gütekriterien überhaupt erreichbar sind.

Ohne Karte: Bug-Algorithmen#

Die Bug-Algorithmen lösen das Navigationsproblem mit minimalem Wissen: Der Roboter kennt nur seine Position, die Zielkoordinate und spürt Hindernisse erst, wenn er sie berührt (bzw. mit einem Sensor knapp davor). Die Vorlesung führt das am Bild eines Roboters ein, der in einer unbekannten Höhle/einem Labyrinth eine Schatztruhe sucht, und stellt zwei Bug-Varianten plus den Tangent-Bug gegenüber: Variante 1 umfährt Hindernisse nach fester Regel (z.B. im Uhrzeigersinn) und scannt nach jedem Schritt neu; Variante 2 ergänzt das um Gedächtnis und Wechsel der Vorzugsrichtung, um „im Kreis laufen” zu verhindern. Die klassische, beweisbar terminierende Ausprägung (Lumelsky & Stepanov) formuliert das über eine M-Linie — die gedachte Gerade von Start zu Ziel — kombiniert mit Wandverfolgung:

• Bug1 umfährt jedes getroffene Hindernis vollständig, merkt sich dabei den Randpunkt mit minimaler Zieldistanz, kehrt zu diesem zurück und fährt dort weiter Richtung Ziel. Sicher, aber teuer: einmal komplett herum.
• Bug2 ist gieriger: Es folgt dem Rand nur so lange, bis es die M-Linie an einem Punkt näher am Ziel als der Trefferpunkt wieder kreuzt — und löst sich dort. Meist deutlich kürzer, in manipulierten Spiral-Hindernissen aber auch einmal länger als Bug1.

Der Bug-Reflex braucht keinen Speicher für eine Karte — genau das macht ihn für einen Lagerroboter mit „temporär abgestellten Kisten” (Aufgabe 1) attraktiv. Die Praxis unten enthält eine lauffähige Bug2-Implementierung.

Mit Karte: Gitter, Graphen, Suche#

Liegt der Raum nicht schon als Wegenetz vor, rastert man ihn: Der befahrbare Bereich wird in Zellen geteilt (rechteckig mit 4 oder 8 Nachbarn, hexagonal mit 6, dreieckig …). Die Zellen werden zu Knoten, Nachbarschaft zu Kanten — fertig ist der Suchgraph. Darauf laufen die klassischen Verfahren:

• Breitensuche (BFS) expandiert schalenweise vom Start. Vollständig und — bei Einheitskosten — optimal, aber sie wächst „blind” kreisförmig.
• Dijkstra / Uniform-Cost verallgemeinert BFS auf beliebige positive Kantenkosten und bleibt optimal, expandiert aber ähnlich viele Knoten.
• Gierige Bestensuche expandiert immer den Knoten mit kleinster geschätzter Restdistanz $h(n)$ zum Ziel. Schnell, aber weder vollständig noch optimal — sie läuft „direkt aufs Ziel” und kann an Wänden teure Umwege nehmen.

Auf dem Gitter ist die Manhattan-Distanz $h = |x_n - x_z| + |y_n - y_z|$ die naheliegende zulässige Heuristik (bei 4-Nachbarschaft), weil man mindestens so viele Schritte braucht und sie billiger zu rechnen ist als die euklidische. Genau das Zusammenspiel von $g$, $h$ und der Expansionsreihenfolge macht die folgende Insel sichtbar.

Optimale Effizienz von A*#

A* ist nicht nur optimal in der Lösung, sondern unter allen Algorithmen mit derselben Heuristik auch optimal effizient: Es expandiert alle Knoten mit $f(n) < C^{*}$ (den optimalen Kosten), keinen mit $f(n) > C^{*}$ — jeder Algorithmus, der weniger expandiert, riskiert, das Optimum zu verpassen. Die Folien führen den Optimalitätsbeweis per Widerspruch: Hätte A* ein suboptimales Ziel $Z'$ geliefert, gäbe es auf dem optimalen Pfad einen Knoten $n$ mit $f(n) \le C^{*} < g(Z') = f(Z')$, der vor $Z'$ hätte expandiert werden müssen — ein Widerspruch.

Praxis#

Ich löse die fachlichen Aufgaben von Blatt 3 und untermauere zwei davon mit ausführbarem Code: eine lauffähige Bug2-Simulation (Aufgabe 1) und eine Nachrechnung der Wahr/Falsch-Behauptungen aus Aufgabe 3.

(a) Algorithmus. Ich wähle Bug2, weil er ohne Karte auskommt und in der Praxis kürzere Wege als Bug1 liefert. Die Regel:

1. Berechne die M-Linie $\overline{AB}$ und fahre auf ihr geradeaus Richtung $B$.
2. Bei Kollision: merke den Trefferpunkt und seine Distanz $d_{\text{hit}}$ zum Ziel. Folge dem Hindernisrand (feste Hand, z.B. linke).
3. Erreichst du die M-Linie an einem Punkt mit Distanz $< d_{\text{hit}}$ wieder, verlasse das Hindernis und fahre wieder geradeaus (zurück zu 1).
4. Ende, sobald $B$ erreicht ist (oder Unerreichbarkeit erkannt: man kehrt zum Trefferpunkt zurück, ohne je näher heranzukommen).

(b) Güte. Bug2 ist vollständig für erreichbare Ziele und terminiert nach endlicher Strecke; er braucht $O(1)$ Speicher (nur Trefferpunkt-Distanz), also keine Karte. Pathologisch wird es, wenn die M-Linie ein Hindernis oft schneidet: Ein spiralförmiges oder kammartiges Hindernis zwingt Bug2, denselben Rand mehrfach abzufahren — hier ist Bug1 (einmal komplett herum, dann zum besten Punkt) günstiger. Sackgassen, deren Öffnung von der M-Linie weg­zeigt, kosten ebenfalls überflüssige Randfahrt. Versagen kann der reine Tast-Bug nicht beim Finden, wohl aber bei der Effizienz.

(c) Sensor-Variante. Der Ultraschallsensor (Reichweite 1 m, $\pm 45°$ schwenkbar) erlaubt es, Kollisionen vorausschauend zu vermeiden, statt sie abzuwarten. Drei Verbesserungen:

• Frühes Ausweichen statt Berührung: Meldet der nach vorn gerichtete Sensor ein Hindernis im 1-m-Korridor, wechsle bereits dort in den Wandfolge-Modus, ohne die Wand wirklich zu berühren — schont Mechanik und glättet den Pfad.
• Tangentiale Randverfolgung: Durch Schwenken um $\pm 45°$ lässt sich die Wandrichtung schätzen; der Roboter folgt der Kontur berührungslos in konstantem Abstand (Contour-Tracing, vgl. Folie 52), statt am Rand „entlangzuschrubben”.
• Frühes Loslösen (kürzerer Pfad): Statt die M-Linie abzuwarten, kann der Roboter den Sensor periodisch aufs Ziel richten; ist die Linie zum Ziel frei und liegt der aktuelle Punkt näher als $d_{\text{hit}}$, löst er sofort ab. Das verkürzt den Umweg gegenüber dem reinen Bug2 spürbar.

Mit diesen Erweiterungen wird aus dem Tast-Reflex eine „Tangent-Bug”-artige Variante — der Sensor ersetzt fehlendes Wissen durch lokale Vorausschau.

Bug2 — lauffähig simuliert#

Der Kern der Implementierung ist die Zweiphasen-Logik: Geradeausfahrt auf der M-Linie, bis ein Schritt blockiert wäre; dann Wandverfolgung, bis die M-Linie näher am Ziel wieder gekreuzt wird.

def bug2(start, goal, obstacles, max_steps=100_000):
    pos = start.astype(float).copy()
    path = [pos.copy()]
    while steps < max_steps:
        # Phase 1: geradeaus auf der M-Linie
        if np.linalg.norm(goal - pos) < goal_tol:
            reached = True; break
        nxt = pos + STEP * to_goal()
        if not _blocked(nxt, obstacles):
            pos = nxt; path.append(pos.copy()); continue
        # Phase 2: Hindernis getroffen -> Rand umfahren
        hit = pos.copy()
        d_hit = np.linalg.norm(goal - hit)
        while ...:                         # Wandverfolgung (linke Hand)
            ...                            # drehe, bis frei UND Wand rechts liegt
            crosses = _seg_intersect(prev, pos, start, goal)
            if crosses and np.linalg.norm(goal - pos) < d_hit - 2*STEP:
                break                      # leave point: naeher am Ziel -> ab

Die Szene hat zwei polygonale Hindernisse (ein Rechteck, ein Dreieck), beide auf der M-Linie $y = 0{,}5$. Der Roboter „fühlt” nur lokal (Punkt-in-Polygon in seiner Nachbarschaft) — er hat keine Karte. Die echte Ausgabe:

=== Bug2 — kartenlose Navigation auf der M-Linie ===
Start  = (0.10, 0.50)
Ziel   = (2.90, 0.50)
Hindernisse: 1 Rechteck, 1 Dreieck (beide auf der M-Linie)
Ziel erreicht: ja
Abgefahrene Pfadlänge : 4.280
Direkte M-Linie       : 2.800
Umweg-Faktor          : 1.53x
Simulationsschritte   : 107

Anders als Bug2 geht es hier nicht um Wegfindung (A nach B), sondern um Flächendeckung (coverage): Jede Bodenzelle soll mindestens einmal befahren werden. Ohne Karte stehen zwei Grundstrategien zur Wahl, die ich beide in einem Gitter-Modell simuliert habe (Roboter „fühlt” nur Wände/Möbel in seiner Nachbarschaft):

• (a) Leerer Raum — Mäander schlägt Zufall. Ein Boustrophedon-Mäander (Reihe abfahren, am Rand eine Reihe tiefer, Richtung umkehren) deckt den konvexen Leerraum vollständig und effizient. Der Zufallsreflex (geradeaus, an Wänden und gelegentlich zufällig neu ausrichten — das klassische Roomba-Prinzip) deckt zwar auch alles ab, braucht dafür aber deutlich länger.
• (b) Möblierter Raum — Zufall wird robuster. Hier kippt das Bild: Der kartenlose Mäander läuft an Möbeln auf und springt zu früh in die nächste Reihe — hinter und neben Möbeln bleiben Lücken, er erreicht nur einen Teil der Fläche. Der Zufallsreflex hat keine feste Sweep-Struktur, die Möbel zerstören könnten, und ist probabilistisch vollständig: Gegeben genug Zeit erreicht er jede zugängliche Zelle. Genau deshalb fahren reale Billig-Roombas zufällig.

=== Aufgabe 2 — kartenlose Flächendeckung (Staubsaugerroboter) ===
  Zufallsreflex  im leer      Raum: 100.0% Deckung  (2490 Schritte bis 90%)
  Mäander        im leer      Raum: 100.0% Deckung  ( 633 Schritte bis 90%)
  Zufallsreflex  im möbliert  Raum: 100.0% Deckung  (2360 Schritte bis 90%)
  Mäander        im möbliert  Raum:  77.0% Deckung  (90% nie erreicht)

Fazit. Im Leerraum gewinnt der systematische Mäander (schnell, vollständig); mit Möblierung kauft man sich die Vollständigkeit des Zufalls mit Langsamkeit. Reale Geräte kombinieren beides — Wandfolgen für die Ränder, einen Sweep für die Fläche, Zufall als Lückenfüller — und moderne Modelle bauen sich per SLAM (vgl. Querbezüge) doch eine Karte, womit aus der kartenlosen A2 effektiv das kartenbasierte Regime wird.

(a) falsch. Der Suchbaum entsteht durch wiederholtes Expandieren; bei Zyklen oder unendlich tiefen Pfaden wächst er ohne Zyklencheck unbeschränkt. Ein Zustandsraum mit auch nur einem Zyklus erzeugt einen unendlichen Suchbaum.

(b) falsch. Selbst ein endlicher Zustandsraum reicht nicht. Schon ein 3-Zustands-Zyklus $0 \to 1 \to 2 \to 0$ liefert unendlich lange zyklische Pfade, also einen unendlichen naiven Suchbaum. (Erst mit Mehrfachbesuchs-Erkennung wird er endlich — das ist genau die „Generelle Strategie” der Folien: Mehrfachbesuche vermeiden.)

(c) falsch. Rückkehr zu einem Zustand verlangt keine inversen Aktionen, sondern nur einen gerichteten Zyklus. Im Beispiel $0 \to 1 \to 2 \to 0$ gibt es keine Aktion $1 \to 0$, trotzdem kehrt man über $1 \to 2 \to 0$ zu $0$ zurück.

Ich lasse den Code diese drei Begründungen nachrechnen: Er baut den 3-Zustands-Zyklus, misst die Größe des naiven Suchbaums je Tiefe und zählt Wiederbesuche bei reiner BFS über gerichtete Kanten.

=== Aufgabe 3 — Zustandsraum vs. Suchbaum (nachgerechnet) ===
Zustandsraum: 3 Zustände, Zyklus 0->1->2->0
(a/b) naiver Suchbaum (ohne Zyklencheck) je Tiefe:
      Tiefe  2:   3 Knoten
      Tiefe  5:   6 Knoten
      Tiefe 10:  11 Knoten
      Tiefe 20:  21 Knoten
      -> waechst unbeschraenkt: endlicher Zustandsraum, UNENDLICHER Suchbaum => (a) falsch, (b) falsch.
(c) Besuchsreihenfolge BFS: [0, 1, 2, 0, 1, 2, 0]
      Wiederbesuche trotz rein gerichteter Kanten: 4
      -> Rueckkehr ohne inverse Aktion moeglich => (c) falsch.

Der linear mit der Tiefe wachsende Suchbaum bei nur drei Zuständen belegt (a) und (b); die Besuchsreihenfolge $0,1,2,0,\dots$ über ausschließlich gerichtete Kanten belegt (c).

(a) Ohne Karte: reaktive, kartenlose Verfahren — Bug1/Bug2 und Tangent-Bug für die Zielnavigation, Boustrophedon-Streifen oder der Roomba-Zufallsreflex für flächendeckendes Abfahren. Randomisierte Planer wie RRT/RRT* und PRM gehören in die Nähe dieses Falls, weil sie den freien Raum erst durch Sampling erschließen; sie brauchen aber Kollisionsprüfungen und bauen dabei nach und nach einen Baum bzw. eine Roadmap auf.

(b) Mit Karte: Graphensuche auf dem Wegenetz/Gitter — BFS und Dijkstra (blind/uniform), gierige Bestensuche und vor allem A* für den kostenoptimalen Pfad; in Spielen ergänzt durch Navigation-Meshes und Pfadglättung.

(c) Mit GPS: Die Selbstortung liefert die aktuelle Pose in einem globalen Koordinatensystem. Damit lassen sich kartenbasierte Verfahren überhaupt erst robust ausführen (man weiß, wo auf der Karte man ist) und mit Outdoor-Routing (z.B. geodätische Wege, Vektorfeld-Planung auf 3D-Meshes) verbinden. GPS ersetzt keine Hindernisplanung, sondern liefert die Lokalisierung dafür.

(d) Kombination (a)+(b): Reale Umgebungen sind nur teilweise kartiert — „Karten mit weißen Flecken”. Man plant global mit A* auf der bekannten Karte und schaltet lokal auf einen Bug-/Sensor-Reflex um, sobald ein nicht kartiertes Hindernis (die abgestellte Kiste aus Aufgabe 1, ein Fußgänger) auftaucht. Beispiel: Ein Lagerroboter routet mit A* zum Regal, weicht aber einer querstehenden Palette reaktiv aus und kehrt danach auf den geplanten Pfad zurück. So bekommt man einen global optimalen Plan auf der bekannten Karte und lokale Robustheit gegenüber Änderungen — der tatsächlich gefahrene Weg ist nach reaktivem Ausweichen nicht mehr garantiert global optimal.

(a) Gütekriterien (aus den Folien): Korrektheit (gelieferte Lösung ist eine echte Lösung), Vollständigkeit (existiert eine Lösung, wird sie gefunden), Optimalität (die kostengünstigste Lösung wird gefunden), Zeitkomplexität und Speicherkomplexität (jeweils worst-/average-case).

(b) Vergleich entlang der Kriterien aus (a):

• Vollständigkeit: beide vollständig — A*/Dijkstra bei endlichem Graph, Bug2 für jedes erreichbare Ziel.
• Optimalität: A* (mit zulässigem $h$) findet den kürzesten Weg; Bug2 erreicht das Ziel nur, garantiert aber keinen kürzesten Weg.
• Zeit: A* liegt im worst case bei $O(b^d)$, die Heuristik senkt vor allem die Konstante; Bug2 ist linear in der abgefahrenen Wegstrecke und lokal billig.
• Speicher: A* hält die ganze Frontier (und faktisch die Karte) im RAM — speicherintensiv; Bug2 braucht nur $O(1)$, im Wesentlichen die Trefferpunkt-Distanz.
• Vorwissen: A* setzt eine vollständige Karte voraus; Bug2 kommt mit Start, Ziel und einem Berührungs-/Nahsensor aus.

Die Pointe: Mit Karte kauft man Optimalität mit Speicher und Vorwissen. Ohne Karte zahlt man mit suboptimalen Wegen, bekommt dafür einen Planer, der sofort losfährt und in unbekanntem Terrain überhaupt funktioniert. Genau deshalb kombiniert man beide (Aufgabe 4d).

Ich modelliere das als klassisches Zustandsraum-Problem für meine Wohnung (ein Zimmer mit offener Küchenzeile, ein Flur, ein Bad — Türschwellen dazwischen).

Zustandsbeschreibung. Der Zustand $s$ fasst alles, was der Roboter zur Entscheidung braucht:

• Pose $(x, y, \theta)$ — Position und Orientierung (bei kartenlosen Geräten nur grob aus Odometrie, bei SLAM-Geräten in einer aufgebauten Karte);
• Belegungs-/Deckungsraster — je Zelle: frei / Hindernis / unbekannt und gereinigt / ungereinigt (das ist der Coverage-Zustand aus A2);
• Akkustand und Position der Ladestation (Dock);
• Modus (systematischer Sweep, Wandfolgen, Spot-Clean, Rückkehr zum Dock);
• Sondersensorik: Absturzsensoren (Treppe), Schmutzsensor, Stoß-/Bumper- und Einklemm-Status.

Operatoren (Aktionen, die den Zustand überführen): vorwärts fahren, um Winkel drehen, Wand folgen (links/rechts), Spot-Clean (enger Spiralreinigung bei erkanntem Schmutz), zum Dock zurückkehren (wenn Akku niedrig oder Fläche fertig) und andocken/laden. Jede Aktion ist nur ausführbar, wenn die Bumper-/Cliff-Sensoren das zulassen (Vorbedingungen), und markiert die überfahrenen Zellen als gereinigt (Effekt) — formal exakt die Operator-Semantik (Vorbedingung → Effekt) aus dem General Problem Solver in 1.1.

Besondere Hindernisse in meiner Wohnung und was schiefgehen kann:

• Lose Kabel (Schreibtisch, TV) — der Klassiker: Sie wickeln sich um die Bürste und legen den Roboter lahm. Gegenmaßnahme: Kabel hochlegen oder No-Go-Zone.
• Türschwellen zwischen Zimmer/Flur/Bad — zu hohe Kanten blockieren die Fahrt; ohne Übersteigen bleiben ganze Räume ungereinigt (genau die „Lücken” aus A2, hier auf Raumebene).
• Teppich mit Fransen — die Fransen werden eingesogen und verheddern die Bürste; der Roboter interpretiert den Teppich evtl. als Hindernis.
• Dunkle Möbel / Stuhlbeine — IR-Absturzsensoren deuten sehr dunkle Böden fälschlich als Abgrund (Stopp), und im Wald aus Stuhlbeinen verkeilt er sich.
• Treppe / Niveausprung — ohne funktionierende Cliff-Sensoren der Sturz; das ist der gefährlichste Fehlerfall.
• Geschlossene Türen — dahinterliegende Räume sind schlicht unerreichbar; der Coverage-Zustand bleibt dort „unbekannt”.
• Flüssigkeiten (umgekippter Napf) — werden verschmiert statt aufgenommen.

Der Bezug zu A2 ist direkt: Der Deckungs-Zustand und die Wandfolge-Operatoren sind genau die kartenlose Coverage-Maschinerie; die Türschwellen und Möbel sind die Möblierung, an der der reine Mäander scheitert — weshalb mein realer Roboter zusätzlich eine SLAM-Karte führt und No-Go-Zonen kennt.

Querbezüge#

• 2.2 (Informierte Suche): A* ist der direkte Anschlusspunkt. Dort wird die Zulässigkeit und Konsistenz von Heuristiken vertieft und A* gegen IDA*, SMA* und gierige Bestensuche abgegrenzt — die Insel oben liefert dafür die visuelle Intuition (Greedy schnell aber suboptimal, Dijkstra optimal aber teuer, A* dazwischen).
• 2.4 / Robotik: Die kartenlose Navigation ist der Brückenkopf zur Roboternavigation insgesamt — SLAM (gleichzeitiges Lokalisieren und Kartieren) ist im Grunde der Versuch, sich die Karte zu erarbeiten, die A* voraussetzt; RRT/PRM aus den Folien sind die Standardplaner im hochdimensionalen Konfigurationsraum echter Roboterarme.
• Algorithmen & Datenstrukturen: BFS, Dijkstra und A* sind reine Graphalgorithmen. Die Effizienz von A* steht und fällt mit dem Priority-Heap (Folie 22) für die offene Menge; die „gedachte” vs. explizite Graphdarstellung ist exakt die Frage Adjazenzmatrix vs. on-the-fly-Expansion aus der Datenstruktur-Vorlesung.
• Lineare Algebra / Geometrie: Die Bug2-Implementierung lebt von Punkt-in- Polygon-Tests, Segment-Schnitten und Rotationsmatrizen für die Wandverfolgung — elementare analytische Geometrie. Die Manhattan- vs. euklidische Heuristik ist die Wahl der $\ell_1$- gegen die $\ell_2$-Norm.
• Theoretische Informatik: Der Unterschied Zustandsraum vs. Suchbaum (Aufgabe 3) ist die Frage nach Endlichkeit und Erreichbarkeit in gerichteten Graphen — und die „Generelle Strategie”, Mehrfachbesuche zu vermeiden, ist nichts anderes als die visited-Menge, die einen Graph-Durchlauf terminieren lässt.

Quellen#

• Foliensatz _210_AI_Wayfinding.pdf — Hauptquelle für die Systematik (ohne/ mit Karte), die Bug-Varianten, die A*-Definition und den Optimalitätsbeweis. Stark ist der breite Anwendungsbogen (Spiele, Outdoor-Roboter, Navi-Meshes); bei den Bug-Algorithmen bleibt die Folie eher anschaulich, weshalb ich Terminierung und Loslöse-Bedingung aus der Primärliteratur ergänzt habe.
• Übungsblatt 3 ki_ueb210_Path.pdf — Vorlage für die in der Praxis gelösten Aufgaben 1, 2 (kartenlose Flächendeckung), 3, 4, 5 und 7 (Roomba-Operatoren).
• Lumelsky & Stepanov, Path-Planning Strategies for a Point Mobile Automaton (Algorithmica, 1987) — Originalquelle der Bug-Algorithmen; daran habe ich die exakte Loslöse-Bedingung von Bug2 und die Längenschranke von Bug1 abgeglichen.
• Russell & Norvig, AIMA, Kap. 3 — für die saubere Trennung von Zustandsraum und Suchbaum (Aufgabe 3) und die Gütekriterien konsultiert.
• PathFinding.js — die in Blatt 3, Aufgabe 6 empfohlene Web-Demo; ich habe Wände gezogen und die Zahl besuchter Zellen für BFS/Dijkstra/A* verglichen — das motiviert direkt die obige Insel, die denselben Effekt offline und mit Tönung nach Expansionsreihenfolge zeigt.