A-Star Wegoptimierung für besseren (schöneren) Fahrweg ..

[Ritchie]

Hallo Zusammen,

ich habe jetzt eine ganze Zeit an der Optimierung der Wegberechnung gearbeitet.

Hierbei habe ich z.B. jetzt die Hindernisse größer gemacht, anstatt ständig das Umfeld des Roboters zu prüfen. Dies hat die Verarbeitung deutlich vereinfacht. Ebenso habe ich hierbei die entsprechenden Objekt "rund" erweitert, was zu einem möglicheren besseren Weg führen kann.

Zeitweise habe ich für die Heuristik und Kostenfunktionen mit "double" Werte berechnet. Aber auch hier hat sich gezeigt, das Integer deutlich schneller ist.

Ich verwende hierbei 10 für gerade Strecken und 14 für diagnonale Strecken. Für die Wegberechnung ist das scheinbar genau genug.

A-Star findet jetzt relativ schnell den optimalen Weg. Nur ist dieser Weg nicht wirklich schön und vom eigentlichen Fahrweg eher ungünstig, da jede zusätzliche Drehung ein weiteres Problem der Positinierung für mich ergeben wird.

Den Vorschlag von :Two-Tiered A* Pathfinding, von der aktuellen Position so lange auf die folgenden Punkt zu prüft, ob dieser Weg frei ist, hat den Nachteil, das mir hierbei die Nodes zwischen den neu gefunden Punkte verloren gehen.


Ich habe daher mal in einem Beispiel eine mögliche Optimierung, wie ich sie mir vorstellen könnte in rot eingezeichnet.
Derzeit habe ich jedoch noch einen Ahnung, wie ich diese Art der Optimierung angehe, so das sie logischerweise auch für andere Fahrstrecken
einen "fahrtechnisch" günstigeren Weg findet. Das dieser Weg länger ist, kann ich hierbei gerne in kauf nehmen.

Hat jemand eine Idee, wie ich das ganze jetzt weiter angehen kann ?

Gruss R.

[markusj]

Du kannst an deiner Kostenfunktion feilen. Wenn du einfach jede Richtungsänderung mit einem gewissen Strafwert belegst, wird der Algorithmus dazu übergehen, optimale Wege bezüglich dieser Metrik zu suchen und zwangsläufig weniger Lenkmanöver einplanen. Wenn du es damit aber zu sehr übertreibst, könnten die Ergebnisse sehr weit von der Idealline abweichen, du musst an diesem Strafwert etwas justieren. (Ich könnte mir aber vorstellen, dass das Routing selbst bei irrsinnig großen Lenkkosten im Bereich von 100 oder mehr noch vernünftige Routen erzeugt, allerdings könnte das Routing unter Umständen länger dauern weil mehr schlechte Felder überprüft werden.)

mfG
Markus