Überlegungen zum Mapbuilding

[Reinald]

Hallo zusammen,

So, dann wären wir also bei Step 1 :

Ich hatte nicht an ein dynamisches Array gedacht. Ich bin davon ausgegangen, daß man sich erstmal in einem festen Array bewegt. Um die Sache im Mikro-Controller nicht unnötig zu komplizieren, geht man erstmal von individuell, aber fest definierten Rasterweiten aus. Je nach größe des Bots und dem Terrain können das 5cm Steps sein oder vielleicht auch 20cm - das hängt halt von den individuellen Anforderungen ab. Dabei würde ich in erster Näherung auch nur von einem flachen Terrain ausgehen.

Im Folgenden werde ich die Rastereinheit "Pixel" nennen, das scheint mir passend.

Pro Pixel wollte ich ein halbes Byte für den Wert nehmen, das scheint nicht ganz deutlich geworden zu sein. Also nicht den Sensorwert speichern. Meine Planung sieht mehrere unabhängige Senoren vor. Gespeichert zu werden braucht dann nur das Gesamtergebnis als "da kann ich hinfahren" oder "da kann ich nicht hinfahren". Daneben sind aber möglicherweise noch andere Zustände Interressant:
- Wo bin ich?
- Wo stehen Baken?
- Unbekannte "tote Winkel", die noch nicht "gescannt" sind.
- Wiedersprüchliche Informationen der unterschiedlichen Sensoren / Unsicherer Wert

Wenn man alles zusammenzählt, kommt man möglicherweise mit weniger als 4 bit hin, aber das erscheint mir auch im Hinblick auf die Speicherorganisation praktisch. Wenn man noch die Unterscheidung auf andere "Mitspieler" hinbekommt, dann können also auch noch andere Zustände ins Spiel kommen.

Gruß
Reinald

[MrNiemand]

Naja ich bin da eigentlich sowieso ehr für Vektorbasiered:

Denn ich kuck da dabei natürlich auf meine 3D Oberfläche, und ich befürchte es sieht hässlich aus, wenn versucht wird, aus den Feldinformationen die Hindernisskoordinaten zu berechen
(Beispiel: ein Hinderniss geht 3Felder nach rechts und 1Feld nach hinten. (Ergebniss zeigt Paint denk ich mal recht deuchtlich wenn man eine Linie zeichnet).

Aber zu den festen Feldern, wäre es nicht sinnvoller auf weniger Bit zurück zu greifen? 32kybte effektiv handeln halte ich z.B. für machbar aber *4 wären das 128kbyte, das ist schon eine ganze Menge mehr.

Evl kann man doch krumme werte wie 2bit oder so recht einfach verwenden, da das ganze ja sowieso auf einen externen Ram auf µC Seite rausläuft, kann die Layer Wahl leicht durch Tooglen der Adressleitungen erledigt werden.

Evl macht es doch z.b. mehr Sinn Infos wie Standort des Bots oder Standort von Baken einfach absolut zu speichern mit ihren Koordinatenwerten (warum z.b. 512*512bit verschwenden für eine Bake)?

[marvin42x]

Ich bin jetzt nicht sicher ob ich was falsch interpretiere.
Bei 4 bit als x
Und 4 bit als y
sehen ich ein Quadrat mit einer Kantenlänge von 16 Pixel vor mir?

Wenn ich mir ein Wohnzimmer vorstelle, sagen wir mal 5 x 5 Meter.
Bei einem Raster von 20cm wäre das ein Quadrat von 25 x 25 Pixel.

Ein Infrarot Entfernungssensor liefert im Idealfall Werte die auf wenige Zentimeter bis hin zu einem Zentimeter genau sein können.

Wenn ich zwischen Stuhl und Wand durch will muss ich vorher wissen ob das geht oder nicht.

Ich sehe hier zwei Anforderungen:
Grobes Raste für “Wo bin ich im allgemeinen“
Feines Raster für „Fahr ich dagegen oder dran vorbei“

Ich vermute, das wird man mit 4bits nicht hinbekommen.

Kann aber auch sein das ich was missverstehe.

Netter Gruß

[Reinald]

@Marvin: 4 bit PRO Pixel. Also:
Zimmer 5x5m Raster 20cm --> 25x25 Pixel --> 625 pixel *0,5Byte --> 313Byte Speicherbedarf.

Zimmer 5x5m Raster 1cm --> 500x500 Pixel --> 250k pixel *0,5Byte --> 125kByte Speicherbedarf

Die 4 Bits hätte ich vorgesehen, um den Pixeln etwas mehr Informationsgehalt zu verpassen, also zwischen schwarz und weiß noch ein bischen abstufen zu können. Ich bin sicher, die Anforderung dafür taucht auf (frei, besetzt, unbekannt, wiedersprüchliche Infos, andere Agenten, ...)

jetzt nachvollziehbarer erklärt?

@MrNiemand:
Natürlich ist verkorbasiert eigentlich die saubere Lösung.
mit 8Bit Genauigkeit könnte man im obigen Beispiel eine Genauigkeit von 2cm erreichen, in einem Koordinatensystem mit 5m Kantenlänge. Allerdings braucht man pro Vektor 4 Byte (in 2D). Bei Vergleichbarem Speicherbedarf kann man 7812 Vektoren modellieren, gegenüber 62,5k Pixeln. Wenn man mal davon ausgeht, eine Fläche innerhalb des Koordinatensystems (256*256) zu beschreiben, und dabei nur die kürzest-möglichen Vektoren zu verwenden, kann man mit ca. 1000 Vektoren einmal die Außenkontour abfahren, oder schon recht komplexe Konturen innerhalb des Systems zusammenbauen.

In der Praxis wird allerdings eher 16 oder 32Bit integer Genauigkeit gefragt sein, wenn nicht sogar Floating Point.

Was mir allerdings völlig unklar ist: Wie gut kann der AVR mit Vektoren rechnen? Insbesonders, wenn nicht die kürzestmögliche Schrittweite gewählt wird? Es soll ja auch ein guter Teil auf einem Micro-Controller laufen können.

Gruß
Reinald

[marvin42x]

Danke Reinald.
Dann ist das klar, dann ist die Frage die ich vorher in den Raum gestellt habe noch gültig.

Zitat:
Auch die Datengröße der Koordinaten müsste man mal abschätzen.
Ob 8 bit, 16 oder was weis ich.

Damit entscheidet sich ja im wesendlich der Speicher und auch Kommunikationsbedarf.

Netter Gruß

[Reinald]

Hallo Marvin,

ich habe den Datenbedarf mit 4 Bit angenommen - wo siehst Du den Bedarf für 8 Bit oder 16 Bit pro koordinate?

Was hältst du von einer Vektorbasierten Lösung? Das scheint auch im Bezug auf den Speicherbedarf attraktiv zu sein, aber kann man im AVR-Mikrocontroller damit effizient rechnen? Die Vektoren ermitteln aus passenden Sensordaten? Das erscheint mir bei einer "Bitmap"-Karte doch etwas einfacher zu sein.

Gruß
Reinald

[PicNick]

Ihr habt euch offenbar auf sowas wie 0/1 (befahrbar/nicht befahrbar)
eingeschossen. Und ihr wollt tatsächlich ALLE Koordinaten in einem Array X x Y ablegen ?

[Reinald]

@PicNick: es ist halt eine naheliegende und einfache Lösung. Aber vielleicht hast Du eine bessere Idee? Flexibler und Leistungsfähiger ist vermutlich eine vektorbasierte Variante, die Frage ist wie das aussehen soll und ob das in einem Mikrocontroller noch zu verarbeiten ist.

Gruß
Reinald

[PicNick]

Würde sagen, das Mindeste wär wohl eine RLE Speicherung, das spart Platz und ist auch für den µC kaum ein Problem. (RLE brauch ich nicht zu erläutern ?)

[marvin42x]

Bitmap bzw. Array:
Da ich glaube, es gibt zwei Gruppen, das ist Reinal und MrNiemand auf der einen Seite PicNick und ich auf der anderen Seite, die noch an einander vorbeireden
Möchte ich sicherheitshalber zwei Sätze von mir ins Spielfeld zurück rollen:

Zitat :
1. „Das wird ja ein netter Abend“. (Der hat nun überhaupt nichts mit der Sache zu tun

2. „Des Weiteren ob der Robi Arrays benutzt oder nur Koordinaten von Hindernissen und dem „Zaun„ des Gebietes was er schon gescannt hat speichert.“

Der Begriff Koordinate bedeutet in unserem Fall doch, dass man den Ort eines Pixels mit einer Längenangabe und einer Breitenangabe beschreiben muss damit man ihm eine Eigenschaft wie z.B. frei oder Hindernis zuweisen kann.
Diese Längen und –Breitenangabe wird im Moment m.E. unter den Tisch fallen gelassen.
Sie ist aber der wahre Speicherfresser.
Und Hier lohnt es sich mit intelligenten Strategien Einspaarungen vorzunehmen.

Das gesagte betrifft jetzt erstmal nur den Punkt Array.

Netter Gruß

Edit:
Ich werde mich bemühen schneller zu schreiben damit ich hier "just in Time " bin und nicht hinterher hinke.