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.