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

[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.

[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.