c't

c't-Projekte - Mailinglisten


[Voriger (Datum)] [Nächster (Datum)] [Voriger (Thread)] [Nächster (Thread)]
[Nach Datum][Nach Thread]

Re: [ct-bot] bot_drive_area() -> überarbeitet -> Pfadplanung

Absender: Timo Sandmann
Datum: Mi, 17.09.2008 16:06:42
In-reply-to: <48C139945BA47F4DB4DE05DF62CD57AA03D9A29AD6@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>
References: <000001c91830$68e450e0$0400a8c0@mexpnew> <EDE147DE-F11D-48F1-AA7B-30CC1C5BA2B0@xxxxxxxxxxxxxxx> <48C139945BA47F4DB4DE05DF62CD57AA03D9A29AD6@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>


Hi,

Am 17.09.2008 um 13:32 schrieb Menzel, Frank IT-OO4:
Hallo Timo,
ok, mein Algorithmus soll die Pfadplanung sein. Wenn der Bot auf der Karte ganz unten steht und seinen Weg nach ganz oben planen will, sind das im ungünstigsten Fall 10 Meter, die ja auch die Karte enthält. Nun müssen aus der hochauflösenden Karte im 1. Step die Hindernisinfos rausextrahiert werden und in eine andere Datenstruktur importiert werden. Jedes Objekt dieser Datenstruktur stellt ebenfalls eine Koordinate dar. Ist ein Objekt als Hindernis markiert, kann der Bot genau diese Position nicht anfahren und fällt bei der Pfadplanung raus. Jedes Objekt muss wiederum Bezug zu seinen Nachbarpositionen haben. Und bei dieser Datenstruktur habe ich mir eine 2. niedrigauflösende Karte vorgestellt. Aber selbst bei geringer Auflösung ist die Datenstruktur zu groß für den Ram bei Planung über 10 Meter. Vielleicht bin ich hier zu einseitig orientiert aber wie kann denn sonst die Datenstruktur (Objekt muss einen Zählerwert besitzen und Beziehungen zu 4 Nachbarpositionen) realisiert werden ?

wie weit muss der Zähler denn zählen können?
So wie ich das jetzt verstehe, baut der Planungsalgo dann auf Grund der Map eine Datenstruktur auf, die mit der eigentlichen Map nichts mehr zu tun hat (nicht vom Scan-Verhalten gepflegt wird). Das ist ja völlig ok und steht in keinem Widerspruch zu dem, wie das Map-System gedacht ist. Passt die Datenstruktur nicht mehr ins RAM, spricht nichts dagegen, nicht benötigte Teile auf die MMC auszulagern. Das Problem ist dann aber, dass auf die MMC nur exklusiv zugegriffen werden kann, was viel Synchronisierungsaufwand bedeutet. Damit wären wir dann wieder beim Thema Mini-Betriebssystem / Multithreaded-Bot-Firmware, das schon mal angesprochen wurde und halbwegs im Sand verlaufen ist...

Wobei ich vermutlich genau andersherum vorgehen würde, nämlich aus den als frei bekannten Wegen Vektoren (dann braucht man nur Start- und Endpunkt zu speichern) erstellen, einen möglichst langen, zusammenhängen Pfad solcher Vektoren suchen und dann anschließend nur noch lokal (an Start- und Zielpunkt der ganzen Pfadplanung) einen Weg zum bzw. vom ersten / letzten Vektor suchen. Welches Verfahren aber nun wann besser ist und sich vor allem besser auf dem Bot implementieren lässt, ist eine andere Frage. Aber das Eine schließt das andere ja nicht aus, im Gegenteil, es wäre sicherlich interessant verschiedene / alternative Ansätze zu haben.


Aus meiner Sicht stehen einem guten Planer zur Zeit vor allem zwei ungelöste Probleme im Weg: * Die bereits angesprochene Tatsache, dass ein Verhalten nur einmal aktiv sein kann und dass es keine globalen Synchronisierungsmechanismen gibt. * Das Lokalisierungsproblem, ohne dessen Lösung sich der Bot komplett auf seine Odometrie verlassen muss.


Grüße,
Timo