Probleme mit A Star, wenn Objekt größer ist als eine Nodepunkt

[Ritchie]

Hallo Zusammen,

ich habe folgendes Problem mit meinem A-Star Verfahren.

Ich habe eine Matrix angelegt, welche deutlich keiner ist, als mein eigentlicher Roboter.
Die einfache Suche ohne Hindernis arbeitet ohne Probleme.

Nur wenn ich Hindernisse einfüge, so werden die Hindernisse nicht korrekt umfahren, da die Größe des Roboters nicht korrekt
vorgesehen wird.

Ich habe hierbei auch die Routine, welche für die Funktion "Feld Frei" dahingehend erweitert, das in einem Radius
in der Größe des Roboters die Felder (in Fahrtrichtung) geprüft werden. Nur rechnet sich hierbei mein Roby zu tode.

Hat hier jemand eine Idee, wie ich das weiter angehe sollte.

Die beigefügte Grafik zeigt ein Beispiel einer meiner letzten Versuche. Hierbei sind die gelben Punkte, die untersuchten Punkte.
Die grünen Punkte sind Stützpunkte welche angefahren werden sollen. Diese sind auch noch suboptimal.
Rot ist der Startpunkt und Blau der Zielpunkt.

Wäre der Roby nur so gross wie eine Karteneinheit, würde das ganze korrekt arbeiten. Die Karte ist aus dem Grund kleiner, da ich Objekte in einer entsprechenden Auflösung darstellen und umfahren kann.

Gruss R.

[markusj]

Üblicher Trick, um den Algorithmus einfach zu halten: Man erweitert alle Hindernisse um den Radius des Roboters. Das macht natürlich nur so lange Sinn, wie der Roboter sich halbwegs sinnvoll in einen Kreis einbetten lässt. Gegenbeispiel: Ein Auto wäre tendenziell eher ungeeignet ...

mfG
Markus

[Ritchie]

Hallo Markus,

nun ja, das ist bei mir leider der Fall. Ich habe keinen runden "Robby".

Was könnte man den noch machen ?

Gruss R.

[ijjiij]

Die einfachste Möglichkeit wäre wohl die größte Ausdehnung (halbiert), also in deinem Fall die halbe Diagonale aufzuschlagen.
Du kannst ja jedes beliebige Rechteck mit einem Umkreis versehen, der Radius wäre dann die halbe Diagonale.

Dann hast du zwar im Fall das du gerade drauf zu fährst links und rechts ein gewisses Spiel seitlich von deinem Roboter, andererseits sollte der Platz dann auch für eine Drehung in der nähe eines Objekts ausreichen.

[damfino]

Hi,
man kann in der Feldbewertung Felder die nahe einem Hinderniss sind, höher bewerten, damit wird dann ein Abstand eingehalten.
LG!

[Ritchie]

Hi,

ich arbeite derzeit an der Lösung, das ich ein größeres Quadrat um den Roboter spanne. In diesem Bereich darf dann kein Objekt sein. Wie ijjiij bereits sagte, ist der Bereich dann zwar etwas größer, aber wer will schon Schrammen in den Schränken haben :-).

Mir macht derzeit nur die Rechenzeit sorgen. Auf dem PC (iCore) geht das ruck zuck. Die kleine Linux CPU, derzeit noch 200MHz hat da echt zu kämpfen.
Wenn das Verfahren stimmt, gehe ich die Geschwindigkeit an.

@Damfino: Ich werde wohl eine Kombination aus beiden Vorschlägen machen müssen.

Gruss R.

[Ritchie]

Hi,

so, die Route wird jetzt schon besser berechnet.

Die Zeit hierfür ist derzeit noch nicht die nächste Aufgabenstellung, sondern immer noch der Weg der gefahren wird.

Wir bekomme ich die Hacken aus der Routine raus ?
Warum will er nicht direkt nach unten fahren und fährt anstelle dessen weiter in Richtung Ziel?

Hilft mir hier eine bessere/andere Heuristik ?

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Hier meine derzeitige Formel:


newnode->h = (Position.Low_x()-m_iDestination.Low_x())*(Position.Low_x()-m_iDestination.Low_x()) +
(Position.Low_y()-m_iDestination.Low_y())*(Position.Low_y()-m_iDestination.Low_y());


Gruss R.

[damfino]

Vielleicht passt die Kostenrechnung für diagonale Wege nicht?
Ich hab dieses Konzept übernommen:
http://pille.iwr.uni-heidelberg.de/~astar01/

Hab ein Feld mit 1000 Zellen, der Atmega berechnet den Weg ohne merkbare Verzögerung.

LG!

[markusj]

Das sieht weniger wie ein Fehler der Heuristik und mehr wie ein Problem deiner A*-Implementierung aus. A* findet optimale Wege, wenn die Heuristik (wie die von dir verwendete) bestimmte Bedingungen erfüllt (sie darf die Kosten nie überschätzen).

Den Fehler zu finden wird aber deine Aufgabe sein, eine Black-Box zu debuggen ist quasi unmöglich ...

mfG
Markus

[Ritchie]

Hi,

dann habe ich ja was zu suchen. Deine Aussage, das A* immer den optimalen Weg bei korrekter Parametierung findet, kann ich nur unterstreichen.

Von hier habe ich meinen Ursprung:
http://www.generation5.org/content/2000/cpathfinder.asp

Und mein PC Programm zu testen und lernen des A* stimmt mit diesem Code sehr gut noch überein. Aber auch hier ist dieses seltsame Verhalten.

@damfino: Meine Karte hat 90000 Felder.

Gruss R.

[markusj]

Interessant wäre fürs Debugging eine Darstellung der untersuchten Felder (ähnlich der Animation im A*-Artikel in der deutschen Wikipedia)

mfG
Markus

[Ritchie]

Hi,
das werde ich dann wohl heute abend mal eo erweitern.

Interessant ist aber, das diese besagte Ecke eigentlich der kürzstes Weg ist,
wenn ich den Weg nur in einer Breite von einem Kästchen sehen.

Also ohne mein zusätzliches Quadrat um den Robotermittelpunkt,
was ich als nicht begehbar ansehe um den Roboter
nicht gegen Wände fahren zu lassen.

Gruss R.

[markusj]

Ohne es auszurechnen: Das kann nicht sein (oder anders formuliert: Ich kann es nicht glauben ...).
Nach meinem Verständnis geht der kürzeste Weg diagonal zum ersten Tor. Ich hätte übrigens auch eine diagonale Verbindung vom Wegpunkt nach dem ersten Tor zum Wegpunkt vor dem zweiten Tor erwartet.

mfG
Markus

[Ritchie]

Bedenke, das ich ein Quadrat von der Kantenlänge 16 um den Mittelpunkt gezogen habe. Hierdurch will er
immer 8 Kästchen vom Rand (links & rechts) entfernt entlang fahren.

Ich erweitere die Grafik mit weiteren Information und werde einfach mal das gespannte Quadrat weglassen und
das Ergebnis hiervon auch mal zeigen.

Gruss R.

[markusj]

Bedenke, das ich ein Quadrat von der Kantenlänge 16 um den Mittelpunkt gezogen habe. Hierdurch will er
immer 8 Kästchen vom Rand (links & rechts) entfernt entlang fahren.
Schon klar, aber der erste Wegpunkt (der "Haken") ist komplett überflüssig. Nach der Karte könnte der Roboter auch direkt zum zweiten Punkt fahren. Genauso könnte der vierte Wegpunkt (der vor der Schräge zum zweiten Durchgang) übersprungen werden, um direkt vom Ende des ersten Durchganges zum Eingang des zweiten Durchganges zu fahren.

mfG
Markus

[Ritchie]

Du hast recht.

Ich habe jetzt nur die Standard "frei" routine aktiviert und hier sieht das ganze genauso "seltsam" aus.
Ich habe hier die Felder gelb markiert, welche die Routine auf Frei geprüft hat.

Meine Kostenroutine gibt immer 1 zurück, für eine Bewegung auf ein anderes Feld.
Edit 2: Ich vermute hier den Fehler.

Edit:
Und das zweite Bild zeigt, wie es eigentlich aussehen sollte.
Jetzt habe ich was zu tun :-)

Gruss R.

[Ritchie]

Hallo Zusammen,

nachdem ich dynamische Kosten eingefügt habe, zeigt sich das Suchergebenis schon deutlich besser.:)

Aber 100% optimal ist der immer noch nicht ...

Gruss R.

[markusj]

In der Tat. Wie bereits erwähnt, könntest du dir die Arbeit einfacher machen, wenn du den Radius des Roboters als 1 festlegst und stattdessen die Hindernisse vergrößerst. Da dein Roboter ja annähernd quadratisch zu sein scheint, dürfte der entstehende Verschnitt sich in einem akzeptablen Rahmen bewegen.

mfG
Markus

Edit: Nachtrag zu deinem zweiten Post: Sieht besser aus, ja. Aber der Weg vom ersten zum zweiten Durchgang geht besser ... Und auch der Anfang ist komisch. Was meinst du eigentlich mit dynamischen Kosten?

[Ritchie]

Hallo,

ich gebe Dir recht, das die ganze Sache noch nicht wirklich sauber ist.
Die Wegberechnung ist jetzt besser, aber gefallen tut sie mir noch nicht.
Deine Einwände sind korrekt. Hier scheint noch was faul zu sein.

Auch will der Sucher -Algo. plötzlich wieder in die Ecke fahren, wenn ich das Ziel oberhalb der linke Ecke setze.

Ich habe derzeit nur eine einfach Kostenrechnung, da ich mich gestern nicht mehr darum kümmern konnte.
Schliesslich hat man doch hierbei eine Menge zu lesen, bevor ich an den Code gehen kann. Ich bin nämlich erst
in den Anfängen von A*.



inline int CostValue(int xo, int yo, int x, int y)
{
if (xo - x != 0 && yo - y != 0)
return 2;
else
return 1;
}


Wobei Xo,Yo die alte Position und X,Y die neue Position ist. Hier wird nur geprüft, ob er diagonal fahren will.

Gruss R.

[markusj]

Die Kostenfunktion erklärt zumindest einige Irrwege (und macht, davon abgesehen, den A* obsolet weil ohne die Richtungsinformation eine vollständige Suche durchgeführt wird). Da die Kosten für eine diagonale Bewegung gleich den Kosten einer Bewegung entlang beider Koordinatenachsen gesetzt werden, kann der Algorithmus die Richtung frei wählen! Davon abgesehen erfüllt diese Kostenfunktion die A*-Bedingungen nicht mehr, da sie die Distanz überschätzt: sqrt(1² + 1²) < 1 + 1

mfG
Markus

[Ritchie]

Hallo,

so, ich habe das ganze nochmals überarbeitet. :rolleyes: Jetzt hoffe ich doch, das jetzt auch die A* Funktionen besser durchkommt und keine reine Suchfunktion über alle Felder vorhanden ist.

Edit:
Nochmals viele Dank an Markus für die Hilfe.

Gruss R.