Wie können Pfadfindungsalgorithmen an Bewegungseinschränkungen angepasst werden?

Stellen Sie sich eine autoähnliche Bewegung vor, bei der Entitäten keinen Cent einschalten können. Nehmen wir zur Diskussion an, dass sie sich bei hoher Geschwindigkeit um 90 Grad pro Sekunde drehen können. Dies würde in vielen Fällen den optimalen Pfad und damit die Pfadfindung ändern. Es kann sogar dazu führen, dass "übliche" Pfade nicht mehr zu überqueren sind.

Gibt es Pfadfindungsalgorithmen oder Bewegungsplanungsalgorithmen, die dies berücksichtigen können, oder gibt es einfache Möglichkeiten, die gängigen anzupassen?

Willkommen in der wundervollen Welt der nicht-holonomen Bewegungsplanung. Ich empfehle dies mit einem Gittergitterpfadplaner . Andere Alternativen umfassen die kinodynamische RRT und die Trajektorienoptimierung . Zu den nicht holonomen Systemen gehören Autos, Boote, Einräder oder alles, wo das Fahrzeug nicht in die gewünschte Richtung fahren kann. Die Planung für diese Systeme ist viel schwieriger als für holonome Systeme und befand sich bis 2000 am Rande der akademischen Forschung. Heutzutage gibt es viele Algorithmen zur Auswahl, die anständig funktionieren.

So funktioniert das.

Zustand

Die Konfiguration q Ihres Autos ist tatsächlich ein 3D-Zustand, der die x-, y-Position und die Ausrichtung t des Autos enthält . Die Knoten in Ihrem A * -Algorithmus sind tatsächlich 3D-Vektoren.

class Node
{
    // The position and orientation of the car.
    float x, y, theta;
}

Aktionen

Was ist also mit den Kanten?

Das ist etwas schwieriger, weil Ihr Auto tatsächlich unendlich viele Möglichkeiten wählen kann, das Rad zu drehen. Wir können dies also einem Gittergitterplaner zugänglich machen, indem wir die Anzahl der Aktionen, die das Auto ausführen kann, auf einen diskreten Satz A beschränken . Nehmen wir der Einfachheit halber an, dass das Auto nicht beschleunigt, sondern seine Geschwindigkeit sofort ändern kann. In unserem Fall kann A wie folgt sein:

class Action
{
    // The direction of the steering wheel.
    float wheelDirection;

    // The speed to go at in m/s.
    float speed;

    // The time that it takes to complete an action in seconds.
    float dt;
}

Jetzt können wir eine diskrete Reihe von Aktionen erstellen, die das Auto jederzeit ausführen kann. Zum Beispiel würde ein hartes Recht, während das Gas 0,5 Sekunden lang voll gedrückt wird, so aussehen:

Action turnRight;
turnRight.speed = 1;
turnRight.wheelDirection = 1;
turnRight.dt = 0.5;

Das Rückwärtsfahren und Rückwärtsfahren des Autos würde folgendermaßen aussehen:

Action reverse;
reverse.speed = -1;
reverse.wheelDirection = 0;
reverse.dt = 0.5;

Und Ihre Liste der Aktionen würde so aussehen:

List<Action> actions = { turnRight, turnLeft, goStraight, reverse ...}

Sie müssen auch definieren, wie eine an einem Knoten ausgeführte Aktion zu einem neuen Knoten führt. Dies wird als Vorwärtsdynamik des Systems bezeichnet.

// These forward dynamics are for a dubin's car that can change its
// course instantaneously.
Node forwardIntegrate(Node start, Action action) 
{
    // the speed of the car in theta, x and y.
    float thetaDot = action.wheelDirection * TURNING_RADIUS;

    // the discrete timestep in seconds that we integrate at.
    float timestep = 0.001;

    float x = start.x;
    float y = start.y;
    float theta = start.theta;

    // Discrete Euler integration over the length of the action.
    for (float t = 0; t < action.dt; t += timestep)
    {
       theta += timestep * thetaDot;
       float xDot = action.speed * cos(theta);
       float yDot = action.speed * sin(theta);
       x += timestep * xDot;
       y += timestep * yDot;
    }

    return Node(x, y, theta);
}

Diskrete Gitterzellen

Nun, das Gitternetz zu bauen, alles , was wir tun müssen , um Hash die Zustände des Fahrzeugs in einzelne Rasterzellen. Dies macht sie zu diskreten Knoten, denen A * folgen kann. Dies ist sehr wichtig, da A * sonst nicht wissen könnte, ob zwei Fahrzeugzustände tatsächlich gleich sind, um sie zu vergleichen. Durch Hashing auf ganzzahlige Gitterzellenwerte wird dies trivial.

GridCell hashNode(Node node)
{
    GridCell cell;
    cell.x = round(node.x / X_RESOLUTION);
    cell.y = round(node.y / Y_RESOLUTION);
    cell.theta = round(node.theta / THETA_RESOLUTION);
    return cell; 
}

Jetzt können wir einen A * -Plan erstellen, in dem GridCells die Knoten sind, Aktionen die Kanten zwischen Knoten sind und Start und Ziel in GridCells ausgedrückt werden. Die Heuristik zwischen zwei GridCells ist der Abstand in x und y plus der Winkelabstand in Theta.

Dem Pfad folgen

Jetzt, da wir einen Pfad in Bezug auf GridCells und Aktionen zwischen ihnen haben, können wir einen Pfadfolger für das Auto schreiben. Da die Gitterzellen diskret sind, würde das Auto zwischen die Zellen springen. Wir müssen also die Bewegung des Autos auf dem Weg glätten. Wenn Ihr Spiel eine Physik-Engine verwendet, können Sie dies erreichen, indem Sie einen Lenkungsregler schreiben, der versucht, das Auto so nah wie möglich am Pfad zu halten. Andernfalls können Sie den Pfad mithilfe von Bezierkurven oder einfach durch Mitteln der nächsten Punkte im Pfad animieren.

Die meisten Pfadfindungsalgorithmen arbeiten mit einem beliebigen Graphen ohne Einschränkung der Geometrie.

Sie müssen also jedem erkundeten Knoten die Ausrichtung des Fahrzeugs hinzufügen und einschränken, welche Knoten tatsächlich verbunden sind.

Meine Gedanken haben sie nicht getestet!

1. Führen Sie A * vom Start bis zum Ziel aus und geben Sie den Pfad zurück.
2. Wenn Sie eine Kurve erkennen, verwenden Sie einen Bezier- Algorithmus (oder einen ähnlichen Algorithmus), der die aktuelle Geschwindigkeit des Suchers verwendet, um die Knoten vorherzusagen, die eine glatte Kurve erzeugen. Stellen Sie sicher, dass versucht wird, zum nächsten Pfadknoten zurückzukehren.
3. Wenn die Drehung durchgeführt werden kann, großartig, wenn nicht, wiederholen Sie dies mit langsamerer Geschwindigkeit, um eine schärfere Drehung zu erzielen.
4. Sobald der richtige Pfad erstellt wurde, gehen Sie zurück durch den Pfad und passen Sie die Geschwindigkeit des Suchers an, bevor die Abbiegung durchgeführt wird, damit er auf die richtige Geschwindigkeit verlangsamt wird, bevor er die Abbiegung einleitet.
5. Wenn die Wende überhaupt nicht möglich ist, führen Sie das Ganze erneut aus. Stellen Sie einfach sicher, dass alle behandelten Knoten der Runde, die nicht gemacht werden können, in der geschlossenen Liste sind, damit sie ignoriert werden. Sie können mit dem Punkt beginnen, an dem die Abbiegung eingeleitet wird, sodass Sie den erfolgreichen Teil des Pfads überspringen können. In einigen Fällen kann dies jedoch möglicherweise zu einem nicht optimalen Pfad führen.

Sie sollten dies auch tun können, ohne zuerst den Pfad abschließen zu müssen, ergo: Handhabung von Kurven während A *, was wahrscheinlich viel besser optimiert wird, aber es könnte sich auch als problematisch und fehlerhaft erweisen, ich würde es wirklich nicht wissen und leider i Ich habe nicht die Zeit, es selbst zu testen.

Wenn Ihr Agent die volle Kontrolle über das Auto hat, machen Sie es umgekehrt. Verbinden Sie zuerst eine Linie von Anfang bis Ende und finden Sie dann heraus, mit welcher Geschwindigkeit Sie in jeder Runde navigieren können, ähnlich wie bei Dennis 'Antwort.

Zeichnen Sie jedoch keine Bezier-Kurven von festen Punkten. Um den Geschwindigkeitsverlust zu minimieren, müssen Sie die gesamte Linie verschieben. Fügen Sie zunächst zusätzliche Knoten in mehr oder weniger gleichmäßiger Entfernung ein und bewegen Sie sich dann zur Energieminimierung oder ähnlichen Strategien. Für Details müssen Sie sich mit der Erzeugung von KI-Linien in (vorzugsweise Sim- oder Semi-Sim-) Rennspielen befassen.

Sobald Sie das AI-Liniensystem ausgeführt haben, führen Sie Ihre A * -Suche aus und gehen Sie für jeden Pfad mindestens eine Ecke vorwärts. Berechnen Sie dann die AI-Linie, die Ihnen eine Zeitschätzung gibt. Dies wäre Ihre Kostenfunktion.