A* Algorithmus

Was ist der A* Algorithmus?

Der A* Algorithmus wird benutzt um die kürzeste Strecke zwischen zwei Punkten im Raum zuberechnen. In unserem Projekt verwenden wir eine Version, die auf einer festgelegte Karte aus gleichgrßen Quadraten arbeitet. Allerdings kann der Algorithmus auch bei "ungraden" Entfernungen benutzt werden.

Wann wird er benutzt?

Der A* Algorithmus wird verwendet sobald der Nutzer im Raum Widget ein Quadrat ausgewählt hat, zu dem der EV3 fahren soll.
Sobald der Nutzer dies getan hat, wird dem Algorithmus die aktuelle Position mit Orientierung und die Endposition übergeben. Wenn der Algorithmus den Pfad berechnet hat konvertiert dieser ihn in einzelne Befehle, die der EV3 ausführen kann.

Hindernisunterbrechung

Sollte der EV3 ein Hindernis erkennen, so berechnet der A* Algorithmus den Pfad (mit dem neu eingetragenen Hindernis) von der aktuellen Position aus bis zum gewählten Endpunkt.

Unmöglicher Pfad

Sollte der A* Algorithmus erkennen, dass der Pfad nicht ausführbar ist, weil das Ziel ein Hindernis ist oder von Hindernissen umgeben ist, so wird eine Warnung ausgegeben das der Pfad nicht möglich ist und die Ausführung angehalten/nicht gestartet.

Hindernis am Rand des erkannten Raumes

Sobald der EV3 ein Hindernis erkennt, dass für ihn am Rand des erkannten Raumes liegt, wird auf dem Widget eine Reihe/Spalte von leeren Quadraten an der Seite des Hindernis, das am Rande des erkannten Raumes ist, hinzugefügt.

def updateState(self, newState):
    """Update the square state"""
    self.state = newState

    if self.state:
        self.grid.getSquare(self.x()- 1, self.y())
        self.grid.getSquare(self.x(), self.y() - 1)
        self.grid.getSquare(self.x() + 1, self.y())
        self.grid.getSquare(self.x(), self.y() + 1)

Wenn der "Status" (Wand oder nicht) eines Quadrats aktualisiert wird, werden, wenn das Quadrat danach eine Wand ist, die umliegenden Quadrate abgefragt. Die getSquare() Funktion versucht das Quadrat zusuchen, das bei den angegebenen Koordinaten ist. Sollte dort keine Quadrat vorhanden sein, so wird eine Zeile/Spalte an leeren Quadraten hinzugefügt.

Speicherung/Laden des erkannten Raumes

Wenn das Programm geschlossen wird, speichert es den erkannten Raum, um sich beim nächsten Mal besser/schneller im Raum zurechtzufinden. Diese Speicherung kann überschrieben werden, falls ein neuer Raum benutzt wird oder der Nutzer bemerkt, dass die Hindernisse ungenau platziert wurden.
Beim starten des Programms wird der gespeichert Raum geladen:

def load(self, filename):
    """Load the old grid from a text file"""
    try:
        # Open the file...
        file = open(filename, "r")

        # Read each line...
        for line in file:
            coordinates = line.split(":")
            x = int(coordinates[0])
            y = int(coordinates[1])

            self.addSquare(x, y, True)
    except:
        debug("Cannot find file: %s" % filename)

Zuerst wird die Datei eingelesen. Sollte dabei ein Fehler passieren, so ist es wahrscheinlich, dass es keinen gespeicherten Raum gibt.
Danach wird Zeile für Zeile gelesen in einzelne Koordinaten aufgeteilt. Es wird ein Quadrat an entsprechender Stelle hinzugefügt.

Ablauf des Algorithmus

Der Algorithmus verwendet zwei Listen ("Sets") in denen er Quadrate speichern kann. Als erstes werden alle "alten" Algorithmus Daten zurück gesetzt. Danach wird der Startpunkt in das Openset gefügt. Dann beginnt eine while-Schleife:

Wenn die Anzahl der Quadrate im Openset 0 ist, wird die while-Schleife und der Algorithmus abgebrochen, weil es keinen Pfad zum Endpunkt gibt.
Danach wird im Openset nach einem Quadrat gesucht, dass einen kürzeren Weg zum Endpunkt hat als das Quadrat mit dem aktuell kürzesten Weg. Ist das Quadrat mit dem kürzesten Weg der Endpunkt, so hat der Algorithmus das Ziel erreicht.
Dann wird das aktuelle Quadrat aus dem Openset entfernt und in das Closedset hinzugefügt.
Nun wird mit jedem Nachbarquadrat des aktuellen Quadrats dies gemacht:

Wenn das Nachbarquadrat nicht im Closedset ist und keine Wand ist, wird der g-Wert des aktuellen Quadrats temporär um 1 erhöht.
Wenn das Nachbarquadrat dann auch noch im Openset ist und der temporäre g-Wert kleiner als der g-Wert des Nachbarquadrats ist, so wird der g-Wert des Nachbarn zum temporären g-Wert des aktuellen Quadrats.
Doch wenn das Nachbarquadrat nicht im Openset ist, so wird der g-Wert des Nachbarquadrats zum g-Wert des aktuellen Quadrats und das Nachbarquadrat wird zum Openset hinzugefügt.
Sollte der g-Wert des Nachbarquadrats erhöht worden sein, so wird der h-Wert des Nachbarquadrats mit der Heuristik berechnet, der f-Wert wird zum g-Wert + h-Wert und das Nachbarquadrat speichert das aktuelle Quadrat als vorheriges.

Wenn der Algorithmus das Ziel erreicht hat, wird der Pfad zusammengestellt, indem der Algorithmus rückwärts die gespeicherten Quadrate vom Endpunkt bis zum Startpunkt entlang geht und diese aufnimmt.

Heuristik

Die Heuristik berechnet die Strecke zwischen zwischen 2 Punkten, indem sie den Betrag der voneinander abgezogenen x-Koordinaten zu dem Betrag der voneinander abgezogenen y-Koordinaten addiert.

def heuristic(self, a, b):
    """Calculate the distance to the end square"""
    return abs(a.x() - b.x()) + abs(a.y() - b.y())

"a" und "b" sind hierbei die beiden erwähnten Punkte und "abs" ist eine Funktion die den absoluten Wert/Betrag der voneinander abgezogenen x-/y-Werte berechnet.
Bei der Heuristik ist es wichtig, dass der berechnete Wert niedriger oder gleich der tatsächlichen Distanz ist, denn der Algorithmus sucht immer den kürzesten Weg. Sonst könnte es dazu kommen, dass zwar ein funktionierender Pfad gefunden wurde, aber es trotzdem einen kurzeren gibt.

g, h, f

g

Der g-Wert speichert den vom Startpunkt aus zurückgelegten Weg in Quadraten. Dieser Wert ist immer genau. Der Weg wird in Quadraten passiert. Es gibt keine Diagonalen, da der EV3 offensichtlich nicht durch Wände oder Ecken fahren kann.

h

Der h-Wert speichert die Heuristik.

f

Der f-Wert ist der g-Wert und der h-Wert zusammengenommen. Anhand ihm wird die Strecke ausgerechnet, die der Pfad braucht. Je kleiner der f-Wert ist, desto besser scheint dieser Pfad für den Algorithmus zu sein.

Umsetzung des berechneten Pfades

Ein zweiter Algorithmus geht alle Quadrate entlang die der A* Algorithmus in den Pfad getan hat. Es wird die Richtung zwischen jedem Quadrat und dem nächsten andhand der Koordinaten berechnet.
Wenn die neue Orientierung die selbe wie die alte ist, so trägt der Algorithmus "Vorwärts" als nächsten Befehl ein.
Wenn die Orientierung eine andere ist als die vorherige, so wird nur eingetragen, dass der EV3 sich drehen soll und ihm wird übergeben in welche Richtung.

Nachdem der ganze Pfad abgehandelt wurde, werden die Befehle zum EV3 gesendet, der die Befehle umsetzt.

Demo

Hier findest du eine kleine Live-Demo, bei der die Karten zufällig generiert wurde. Sobald der Algorithmus merkt, dass es keine Lösung gibt, lädt er die Demo neu.