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/Ga...euristics.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.