|
c't Projekte - c't-Bot und c't-Sim -
Mailinglisten
[Voriger (Datum)]
[Nächster (Datum)]
[Voriger (Thread)]
[Nächster (Thread)]
[Nach Datum][Nach Thread]
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
|
|