Einführung in die Berufsmaturitätsarbeit

Was sind Pathfinder Algorithmen? #

Um diese Berufsmaturitätsarbeit adäquat verstehen zu können, benötigt man einen gewissen Wissensstand. Darum werden die Pathfinder als nächstes verständlich erklärt und im Anschluss das Ziel dieser Arbeit aufgelistet. Diese Seite sollte gelesen und verstanden werden, bevor man sich mit den weiteren Seiten auseinandersetzt. Da sich unsere Arbeit tief im Teilgebiet Informatik bewegt, steht ausserdem ein Glossar zum Nachschlagen von Fachbegriffen zur Verfügung.

Ein Pathfinder ist ein Programm, welches in einem zweidimensionalen Raum mit Start- und Endpunkt den Weg findet.


Nutzen

Wozu kann man sie gebrauchen? #

Pathfinder findet man zum Beispiel bei Roboterstaubsaugern, die selbstständig Zimmer reinigen können.

Beispiele

  1. Im Beispielbild hat ein Programmierer dem Roboter zwei Pathfinder ins Hirn gepflanzt und anschliessend ein Ziel im Raum gegeben. Nennen wir sie bzw. deren gefundene Wege A und B. Der mit Grün markierte Weg A ist scheinbar kürzer (schneller) und der mit Gelb markierte Weg B länger (längsämer).

  2. Ein weiteres typisches Anwendungsbeispiel wären Videospiele. Hat man einen computergesteuerten Begleiter, dem man folgen muss, wird dieser einen Weg folgen, der von einem Pathfinder berechnet wurde, um "intelligent" zu wirken.

  3. Als drittes Beispiel stellen wir uns zwei Personen vor, die möglichst schnell vom Zürich HB nach Oerlikon gelangen müssen. Person A ist ein Einheimischer. Person B ist ein Tourist. Der Einheimische nimmt die S-Bahn und ist unter zehn Minuten in Oerlikon angekommen. Der Tourist hingegen befargt zuerst Leute und entscheidet sich mit dem Tram zu fahren. Beide Wege führen zum Ziel, jedoch hat die Person A den schnellsten Weg gefunden. Anders gesagt hat der Pathfinder der Person A einen kürzeren Weg erarbeitet.

    Wie die beiden Vorgegangen sind hängt davon ab, wie sie denken (wie ihr Pathfinder "programmiert" ist).

Bildlegende: Ein Roboterstaubsauger (orange) überlegt sich auf zwei Arten den Weg zum Ziel (blau).


Arten

Welche Pathfinder gibt es? #

Es gibt viele verschiedene Pathfinder. In unserer Arbeit konzentrieren wir uns aber nur auf die folgenden:

  • A* (sprich "a star")
  • BestFirstFinder
  • BreadthFirstFinder

Algorithmen

Was sind Algorithmen? #

Ein Algorithmus ist einfach gesagt ein Programm, welches Daten in einer nützlichen Weise in Schritten verwandelt. Pathfinder sind auch eine Art von Algorithmus. Man gibt den Pathfindern als Parameter den Raum und den Start- und Endpunkt. Dieser liefert einem als Resultat einen passenden Weg.

A*(Raum, Startpunkt, Endpunkt) Weg

Ein weiteres Beispiel, mit dem wir alle vertraut sind, wäre online Shopping. Möchte man sich zuerst die günstigsten Produktvarianten anschauen, so wählt man bei der Sortierung "günstigste zuerst" oder "Preise aufsteigend". Im Hintergrund ordnet dann ein Sortieralgoritmus alle Produkte nach ihrem Preis.


Ziel

Was möchten wir herausfinden? #

Wir haben nun gelernt was Pathfinder Algorithmen sind und tun und dazu echte Beispiele entdeckt, damit man sich auch im echten Leben dazu etwas vorstellen kann. Aber was ist nun das Ziel unserer Berufsmaturitätsarbeit? Wie wir gesehen haben, kann es sein dass verschiedene Pathfinding Algorithmen andere Wege liefern können.

Im Zusammenhang dazu liefert unsere Arbeit Antworten auf die Folgenden Fragestellungen:

  • Ziel 1: In welchen Umständen entstehen mit den genannten Pathfindern (siehe Arten) Abweichungen vom Pfad?
  • Ziel 2: Welche technischen Gründe gibt es dafür?
  • Ziel 3: Daraus abgeleitet und gemessen kann auch erkannt werden, welcher Pathfinder in gewissen Situationen der schnellste bzw. langsamste ist.

Nächste Schritte

Demonstration der Pathfinder #

Im nächsten Schritt visualisiert die Webapplikation die einzelnen Pathfinder und beschreibt ihre Grundgedanken und Funktionsweisen (Navigationspunkt 2).

Danach vergleicht die Webapplikation die Pathfinder interaktiv (Navigationspunkt 3).


Ziele im Detail (optional)

Ausführliche Erörterung der Ziele #

Dieses optionale Panel dient dazu die Ziele genauer in der technischen Umsetzung zu erklären. Die Methodik zum Erreichen der Ziele sieht folgend aus.

Ziel 1

Es ist bekannt, dass Pathfinder unter Umständen verschiedene Wege in einem gleichen gegebenen Raum berechnen. Nun geht es darum herauszufinden, in welchen Arten von Räumen solche Abweichungen zwischen zwei oder mehr Pathfinder vorkommen. Unter "Arten von Räumen" verstehen wir die Anordnung der Wände, welche Pathfinder dazu bewegen verschiedene Wege zu finden.

Unsere Webapplikation generiert in Serie dazu zufällige Räume und lässt zwei oder mehr Pathfinder den Weg vom Start zum Ziel berechnen. Sollte ein Unterschied in der Form vom Weg vorkommen, wird dieser zur Auswertung vom Nutzer zwischengespeichert und angezeigt.

Ziel 2

Durch die generierten Resultate im Ziel 1 und allfälligen eigenen Erkenntnissen analysieren wir anhand des Quellcodes der Pathfinder von PathFinding.js die algorithmischen Gründe für die Abweichungen.

Ziel 3

Schlussendlich folgern wir aus den Erkenntnissen der Ziele 1 und 2 die Stärken der Pathfinder. Wir versuchen somit Regeln zu finden, in denen ein Pathfinder am optimalsten seinen Weg findet und umgekehrt in welchen Situationen er weniger geeignet ist.