-         

Seite 1 von 3 123 LetzteLetzte
Ergebnis 1 bis 10 von 21

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

  1. #1
    Erfahrener Benutzer Begeisterter Techniker
    Registriert seit
    07.11.2004
    Beiträge
    332

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

    Anzeige

    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.
    Miniaturansichten angehängter Grafiken Miniaturansichten angehängter Grafiken kSCADA1.jpg  
    Kaum macht man es richtig, schon funktioniert's ...

  2. #2
    Erfahrener Benutzer Roboter Genie
    Registriert seit
    20.08.2008
    Ort
    Karlsruhe
    Alter
    30
    Beiträge
    1.221
    Ü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
    Tiny ASURO Library: Thread und sf.net Seite

  3. #3
    Erfahrener Benutzer Begeisterter Techniker
    Registriert seit
    07.11.2004
    Beiträge
    332
    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.
    Kaum macht man es richtig, schon funktioniert's ...

  4. #4
    Erfahrener Benutzer Fleißiges Mitglied
    Registriert seit
    09.12.2010
    Ort
    Nähe Wien
    Alter
    27
    Beiträge
    108
    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.

  5. #5
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    06.08.2008
    Ort
    Graz
    Beiträge
    505
    Hi,
    man kann in der Feldbewertung Felder die nahe einem Hinderniss sind, höher bewerten, damit wird dann ein Abstand eingehalten.
    LG!
    alles über meinen Rasenmäherroboter (wer Tippfehler findet darf sie gedanklich ausbessern, nur für besonders kreative Fehler behalte ich mir ein Copyright vor.)

  6. #6
    Erfahrener Benutzer Begeisterter Techniker
    Registriert seit
    07.11.2004
    Beiträge
    332
    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.
    Kaum macht man es richtig, schon funktioniert's ...

  7. #7
    Erfahrener Benutzer Begeisterter Techniker
    Registriert seit
    07.11.2004
    Beiträge
    332
    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:
    Code:
          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.
    Miniaturansichten angehängter Grafiken Miniaturansichten angehängter Grafiken kScada3.jpg  
    Kaum macht man es richtig, schon funktioniert's ...

  8. #8
    Erfahrener Benutzer Roboter-Spezialist
    Registriert seit
    06.08.2008
    Ort
    Graz
    Beiträge
    505
    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!
    alles über meinen Rasenmäherroboter (wer Tippfehler findet darf sie gedanklich ausbessern, nur für besonders kreative Fehler behalte ich mir ein Copyright vor.)

  9. #9
    Erfahrener Benutzer Roboter Genie
    Registriert seit
    20.08.2008
    Ort
    Karlsruhe
    Alter
    30
    Beiträge
    1.221
    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
    Tiny ASURO Library: Thread und sf.net Seite

  10. #10
    Erfahrener Benutzer Begeisterter Techniker
    Registriert seit
    07.11.2004
    Beiträge
    332
    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.
    Kaum macht man es richtig, schon funktioniert's ...

Seite 1 von 3 123 LetzteLetzte

Ähnliche Themen

  1. Fernsteuerung Simprop Star 8
    Von holzi im Forum Elektronik
    Antworten: 1
    Letzter Beitrag: 10.10.2010, 11:10
  2. ref: pathfinder mit a*star-algorithmus
    Von nomad im Forum Software, Algorithmen und KI
    Antworten: 0
    Letzter Beitrag: 18.06.2010, 09:20
  3. Mein STAR²
    Von Spion im Forum Vorstellungen+Bilder von fertigen Projekten/Bots
    Antworten: 16
    Letzter Beitrag: 12.10.2006, 22:12
  4. Vergleich in ASM, wenn gleich oder größer gehe zu....
    Von Thomass im Forum Assembler-Programmierung
    Antworten: 7
    Letzter Beitrag: 20.06.2006, 16:34
  5. Antworten: 7
    Letzter Beitrag: 11.02.2006, 19:30

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •