## 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

- Referenzen:
  - AW: [ct-bot] bot_drive_area() -> überarbeitet
    - From: Frank Menzel
  - Re: [ct-bot] bot_drive_area() -> überarbeitet
    - From: Timo Sandmann
  - RE: [ct-bot] bot_drive_area() -> überarbeitet->Pfadplanung
    - From: Menzel, Frank IT-OO4

- Voriger (Datum): RE: [ct-bot] bot_drive_area() -> überarbeitet->Pfadplanung, Menzel, Frank IT-OO4
- Nächster (Datum): [ct-bot] Map delete..., Menzel, Frank IT-OO4
- Voriger (Thread): RE: [ct-bot] bot_drive_area() -> überarbeitet->Pfadplanung, Menzel, Frank IT-OO4
- Nächster (Thread): Re: AW: [ct-bot] bot_drive_area() -> überarbeitet, Timo Sandmann
- Indizes:
  - Datum
  - Thread