PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Bewegungsmessung und Positionserkennung mit "Sharp-Rada



sep
18.08.2005, 18:04
Zunächst eine kurze Einführung:
Ich habe einen SHARP - Sensor der mir Entferungen ab 15 cm bis etwa 80 cm auf 1 cm genau und bis 180 cm auf ca. 3 cm genau mißt. Möglicherweise lässt sich die Genauigkeit steigern. Ist das Hindernis weiter als 180 cm entfernt, erkennt der Sensor dies als "zu weit".

Der Sensor ist auf einen Schrittmotor montiert der 200 Schritte à 1,8° ausführen kann. Noch habe ich keine Nullpositionserkennung eingebaut, aber die kommt noch. (Magnet + Reed-Schalter)

Nun kann ich also den Sensor irgendwohin stellen und einen Rundumscan machen.
Dann trage ich ihn eine kleine Strecke weiter und drehe ihn ein wenig und mache noch einen Scan.
Das soll, wie leicht zu erraten ist, die Bewegung eines Roboters simulieren.

Nun will ich aus den beiden Scans die Bewegungsrichtung und die Drehung um die Hochachse errechnen. Dabei dachte ich an eine Art Korrelationsrechnung der beiden Datensätze.

Ich habe dazu folgende Arbeit gefunden: http://www.medialab.ch/archiv/pdf_studien_diplomarbeiten/1sa04/Roboternavigation.pdf
Nun ist meine Frage an euch: Hat sich bereits einer von euch darüber Gedanken gemacht, wie soetwas zu realisieren ist?

In ferner Zukunft kommt zu diesem Problem noch dazu, dass nicht nur die momentane Bewegung ermittelt werden soll sondern auch die Absolutposition in einer Karte, die durch wiederholtes Messen gelernt werden soll. Aber zunächst wäre ich schon zufrieden, wenn ich überhaupt meine Bewegung ermitteln könnte.

19.08.2005, 12:31
Hallo

Hab mir da auch schon ein paar Gedanken darueber gemacht (wer wohl nicht :-)

Hier ist ne alternative Loesung:
http://rossum.sourceforge.net/papers/Localization/

Fuer die Rotation waere ein "Angle Histogramm" ev. etwas, damit lassen sich v.a. Waende, etc finden. Vergleicht man dann zwei Scans, die in etwa der gleichen Umgebung gemacht wurden, so kann man die Rotation berechnen. Gibt noch ne weitergehende Methode, die damit dann auch die x, und y Translationen findet. Finde das Paper jetzt gerade nicht mehr...ev. mal googeln.

Je nach Umgebung kann man auch irgendwelche Objekte ("landmarks") suchen, hier waeren das wohl Ecken, und in einem zweiten Scan versuchen, dieselbe Ecke wieder zu finden => Positionsdifferenz

Kennst Du Where am I? von J. Borenstein? Da hats x solche Algorithmen drin
http://www-personal.umich.edu/~johannb/shared/pos96rep.pdf

Welchen Sharp verwendest Du, den 20-150cm Typ?
(Hab meinen gestern gekillt (=verpolt); mal schauen, wie schnell micromaus liefert...)

mfg
Fritzli

sep
19.08.2005, 13:50
Hier ist ne alternative Loesung:
http://rossum.sourceforge.net/papers/Localization/

Was ist daran alternativ? :D
Das ist doch genau das was ich machen (möchte).

Ich habe mir gestern mal meine Mathe-sachen aus dem letzten Semester angeschaut und ein bisschen mit VB simuliert.

Wenn man ein Feld a mit Zahlen hat (Entfernungs-Werte eines Rundumscans)
Und ein weiteres Feld b, dass ebenfalls soclhe Werte beinhaltet, jedoch um einen konstanten drehwinkel versetzt (Sensor wurde zwischen den Scans gedreht)

Ausserdem sind die Zahlen stark "verrauscht"

Und nun berechnet man die summen:


For j = 1 to anz
For i = 1 to anz
nj=i+j
if (nj > anz) nj -= nj
s(j)+=a(i)*b(nj)
Next i
Next j

Zum Schluß sucht man das Maximum der Werte in s(j), und damit hat man auch den Drehwinkel (nämlich j)

cool was?
Leider sind recht viele Multiply-Accumulate-Operationen nötig


Fuer die Rotation waere ein "Angle Histogramm" ev. etwas, damit lassen sich v.a. Waende, etc finden. Vergleicht man dann zwei Scans, die in etwa der gleichen Umgebung gemacht wurden, so kann man die Rotation berechnen. Gibt noch ne weitergehende Methode, die damit dann auch die x, und y Translationen findet. Finde das Paper jetzt gerade nicht mehr...ev. mal googeln.

genauso wie ich oben beschrieben hab... Juhu...
Man muss nur die x-y-Verschiebung auf das b-Feld anwenden... dazu braucht man jeweils noch eine For-Schleife, und s wird 3-dimensional



Je nach Umgebung kann man auch irgendwelche Objekte ("landmarks") suchen, hier waeren das wohl Ecken, und in einem zweiten Scan versuchen, dieselbe Ecke wieder zu finden => Positionsdifferenz


zu ungenau, da Landmarken nur schlecht erkannt werden können, die Korrelation berücksichtigt darüberhinaus _alle_ sichtbaren Punkte und kann daher auch recht viel Rauschen wegstecken




Kennst Du Where am I? von J. Borenstein? Da hats x solche Algorithmen drin
http://www-personal.umich.edu/~johannb/shared/pos96rep.pdf

habs noch nicht durchgelesen, das war mir einfach zu lange :D


Welchen Sharp verwendest Du, den 20-150cm Typ?
(Hab meinen gestern gekillt (=verpolt); mal schauen, wie schnell micromaus liefert...)
Genau den...

Fritzli
19.08.2005, 16:00
Hallo


Was ist daran alternativ?
Das ist doch genau das was ich machen (möchte).

Ich muss zugeben, dass ich den von Dir angegebenen Artikel nur sehr schnell überflogen habe...


genauso wie ich oben beschrieben hab... Juhu...

Äehm, nein.
Schau Dir das Winkel-Histogramm mal genauer an, dass ist KEINE Korrelation mit irgendwas.


Man muss nur die x-y-Verschiebung auf das b-Feld anwenden... dazu braucht man jeweils noch eine For-Schleife, und s wird 3-dimensional
Wie soll das gehen? Wenn Du Sowohl Rotation als auch Translation hast, wird das meiner Meinung nach nicht mehr funktionieren. Falls Du eines davon kennst, dann gehts.


zu ungenau, da Landmarken nur schlecht erkannt werden können
Yep, das ist das Problem bei natürlichen Landmarken, man muss sie erst finden (ähnliches Problem bei Stereo-Vision)

mfg
Fritzli

sep
19.08.2005, 17:11
Wie soll das gehen? Wenn Du Sowohl Rotation als auch Translation hast, wird das meiner Meinung nach nicht mehr funktionieren. Falls Du eines davon kennst, dann gehts.

Ich postuliere hier mal, ohne es geprüft zu haben. Die X/Y-Verschiebung ist halt recht einfach zu ermitteln, man braucht nur Matrix-Zeilen und-Spalten zu verschieben, zu deutsch, einfach dien index um einen offset verschieben. (Die Matrix ist eigentlich eine Art Bitmap, die den Rundumscan darstellt)
Das blöde bei der Drehung ist, dass man dazu die Matrix rotieren muss... Und zwar in kleinen schritten. Wenn du also eine 400x400 Grafik in 1,8-Grad schritten drehen willst, dauet das ewig.

Vor allem hat mein ATmega8 ja kaum soviel RAM, als dass da sowas reinpassen würde...


Schau Dir das Winkel-Histogramm mal genauer an, dass ist KEINE Korrelation mit irgendwas.

Womit du recht hast - Asche auf mein Haupt... Aber der Vorgang ist der Korrelation sehr ähnlich, allerdings möglicherweise Rechenzeitsparsamer

sep
19.08.2005, 17:13
Auch ein schöner Text, leider voller Rectschreibfehler :D
http://bordeaux.informatik.uni-bremen.de/referate/lokalisation-referat.pdf

Fritzli
19.08.2005, 17:51
Hallo


Ich postuliere hier mal, ohne es geprüft zu haben. Die X/Y-Verschiebung ist halt recht einfach zu ermitteln, man braucht nur Matrix-Zeilen und-Spalten zu verschieben, zu deutsch, einfach dien index um einen offset verschieben. (Die Matrix ist eigentlich eine Art Bitmap, die den Rundumscan darstellt)
Das blöde bei der Drehung ist, dass man dazu die Matrix rotieren muss... Und zwar in kleinen schritten. Wenn du also eine 400x400 Grafik in 1,8-Grad schritten drehen willst, dauet das ewig.

Ok, jetzt hab ich gemerkt, was Du meinst. Eine solche Korrelation von zwei Scans müsste theoretisch funktionieren, das Problem ist nur, dass Du für jeden Rotationswinkel sämtliche Translationsmöglichkeiten durchprobieren musst, um dann von allen Möglichkeiten, den besten match zu nehmen, aber da werden die benötigten Durchläufe ballistisch => es geht ewig. Durch Odometrie-Schätzung liesse sich das allerdings etwas beschleunigen.

Wenn ich dann sowas mal implementiere, werde ich den Ansatz des Rossum-Projekts (mein link) nehmen: Eine Matrix-Karte und dann jeweils die Vektoren eintragen. Die Zelle auf der am meisten Vektoren enden ist dann die ungefähre aktuelle Position.


http://bordeaux.informatik.uni-bremen.de/referate/lokalisation-referat.pdf
Seite 14 haben wir ja genau, was ich ganz oben gemeint habe. Taugt aber nur für relative Positionsmessungen zwischen einzelnen Scans.


Vor allem hat mein ATmega8 ja kaum soviel RAM, als dass da sowas reinpassen würde...
Das wär dann ein Job für diese Mini-ATX, gumstix oder eben dann per Funk auf einen ausgewachsenen PC, aber das wär dann eben nicht mehr autonom...

Gruess
Fritzli

sep
20.08.2005, 22:26
Wääh ich komm nicht vorran. Ich wollte mir Testdaten erzeugen um die Algorithmen testen zu können.
Die Rotation aller Punkte um einen konstanten Winkel ist ja sehr einfach, da die Messwerte einfach "ringsum" in einem Array stehen - man muss dieses Array nur rotieren.
Jedoch in diesen Kreis-Koordinaten eine ordentliche X- oder Y-Verschiebung hinzubekommen ist fast unmöglich. Im Prinzip wärs ja einfach, aber in der Realität scheitert es bei mir an Rundunksproblematiken...

Fritzli
20.08.2005, 22:55
Hallo

Wie rechnest Du denn genau? Double sollte eigentlich für sowas mehr als genug Genauigkeit haben.

Gruess
Fritzli

sep
20.08.2005, 23:23
Nein das Problem war, dass ich zunächst ja einfach 200 Messwerte habe - Entfernungen die alle 1,8° gemessen wurden.

Also hat man sozusagen 200 Vektoren in Kreiskoordinaten

Das genaugenommen zweimal, also 2x 200 Werte.

Wenn nun die zweiten Werte gegenüber den ersten Verdreht sein sollen, ist das sehr leicht - man "shiftet" einfach das eine Feld gegenüber dem anderen.

Will man aber eine X- oder Y-Verschiebung zieht das eine heftige Rechnerei nach sich, denn zunächst müssen die Werte in karthesische Koordinaten gewandelt werden, dann um ein dX und dY verschoben und nun, und das ist das Problem, in Kreiskoordinaten zurückgewandelt werden - jedoch dürfen die Vektoren nur in 1,8°-Schritten stehen...
Da aber durch die X-/Y-Verschiebung die ursprünglichen Vektoren nicht mehr passen, gibt es üble Rundgsfehler.

Beispiel:
Stell dir vor, du hast eine analoge Armbanduhr.
Du nimmst 12 Vektoren, die vom Mittelpunkt auf die Zahlen zeigen.
Vektor 0 auf 12 Uhr, Vektor 1 auf 1 Uhr etc...

Wenn du nun die Vektoren drehen willst ist das sehr leicht, du "shiftest" sie einfach: Aus Vektor 12 := Vektor 11, aus Vektor 11 := Vektor 10 ...

Wenn du aber die Uhr unter den Vektoren weg, ein Stück zur Seite bewegst, den Vektoren-Mittelpunkt also konstant hälst, so zeigen nun nur noch ein paar Vektoren auf Punkte auf der Uhr - denn die Winkelteilung zwischen den Vektoren ist fix, nur die Vektor-Länge ist variabel.

sep
22.08.2005, 21:08
So! jetzt hab ich erstmal ein paar Demo-Scans gemacht.

In der Grafik oben sieht man die grafische Auswertung davon.
Blau sind die Punkte der ersten Messung
Rot sind die Punkte der zweiten Messung (um ca. 90° gedreht und ca. 5 cm verschoben)
Grün sind die roten Punkte, gedreht um die 268,2° also die "drehkompensierten" Punkte

Die Balkengrafiken stellen die Messwerte, "so wie sie im Speicher liegen" dar, also langer Balken = große Entfernung, der Reihe nach, bei "0°" beginnend.

Ganz unten sieht man das "Korrelationsergebnis" Der Algorithmus meint, das das Bild um 268,2° = 360-(90° + 1 Schritt) gedreht wurde, also ist das Ergebnis "verkehrt herum" gemessen...
Egal. Was mich aber sehr freut ist, dass die Verschiebung um 5cm praktisch keine Auswirkungen auf die Messung hat, die 1,8° Abweichung kann ich auch beim Verschieben verzittert haben...

Die Auswertung dauert auf dem ATmega8 etwa eine Sekunde, ohne jede Optimierung. Wenn man die zulässige Drehung auf +-45° beschränken würde und die Rechnung optimieren würde (Assembler statt C ...)
müsste das locker in 200 ms erledigt sein.

Da dauert ja das Scannen doch wesentlich länger :D

Fritzli
22.08.2005, 21:18
Hallo

Das sieht ja gut aus! Und läuft angenehm schnell. 1s ist im Vergleich zum Scannen vernachlässigbar.
Sind das echte Sensordaten oder simulierte?

Ich schätze, dass das Ergebnis für grössere Translationen/Rotationen/Kombinationen von beidem etwas mieser ausfallen könnte. Kannst Du das ev. mal testen?

Ich schätze, das nächste Zeil dürfte sein, auch die Translation zu berechnen (?)

Darf man mal einen Blick auf den Code werfen?

mfg
Fritzli

sep
22.08.2005, 21:31
Das sind echte Sensordaten (JUCHUUU) weil ich es nicht hinbekommen habe gute Sensordaten zu simulieren :D
letztendlich war es halt einfacher gleich zu messen :D

Ja vermutlich wird das Ergebnis für größere Abweichungen deutlich schlechter.

Welchen Code möchtest du denn haben? (Ist mir noch etwas peinlich alles zu posten, das ist so wirr zusammenprogrammiert und ohne jede Struktur...)
Wenn das ganze volkommen ist, veröffentliche ich den Code, mit Fotos, Bauanleitung etc...

Der Code für die Korrelation ist folgender:

lcd_clear();
lcd_print_string("Korrelation läuft");
uint8_t w=0;
uint32_t max=0;
for (uint8_t i=0; i<200;i++)
{
uint32_t sum=0;
for(uint8_t j=0;j<200;j++)
{
uint16_t dj = j+i;
if (dj>=200)dj -=200;
sum+=messungenA[j]*messungenB[dj];
}

if (max < sum)
{
max=sum;
w=i;
}
}

lcd_clear();
lcd_print_string("Drehung um ");
lcd_print_uint8(w);
lcd_print_string(" Schritte");

Fritzli
22.08.2005, 21:35
Merci, mehr wollte ich auch nicht haben.
Ein paar Fragen zum uC:

- wie schnell wird der getaktet?
- hat das Ding nen Hardware-Multiplizierer?

mfg
Fritzli

sep
22.08.2005, 21:44
Unter vernünftigen Bedingungen(*) beeinflusst die Verschiebung die Ergebnise sehr wenig.

Eine Verschiebung um ca. 12 cm bringt eine Ungenauigkeit von 2-3 Schritten = 3,6° bis 4,2° mit sich, ich finde das ist tolerabel. Schließlich ist die Auflösung des Sensors eh nur 1 Schritt = 1,8° ...

Die Genauigkeit könnte man nun weiter steigern, wenn man nachher beim X-Y-Korrelieren auch noch 5 Winkelschritte einbeziehen würde.

____
(*) Vernünftige Bedingungen sind: Die Hindernisse sind weiter als 12 cm entfernt und werden durch die Verschiebung nicht (oder nur geringfügig) verdeckt.

sep
22.08.2005, 21:55
Ich meine, er läuft im Moment auf 1MHz, interner Oszillator.

irgendwann bohre ich ihn mal auf 8MHz auf... bislang hab ich mich nicht getraut. Eigentlich wollte ich ihn ja auf externer Quarz 4MHz proggen, komischerweise ist stattdessen interner Oszillator 1MHz draus geworden, so wie es aussieht muss man gerade das invertierte eingeben...

Hardware-Multiplizierer? Du meinst ob er in einem Takt-Schritt multiplizieren kann? Ich glaube Ja, denn es gibt den Assemblerbefehl MUL etc. und nirgendwo steht, dass der länger braucht als andere Befehle.

sep
25.08.2005, 19:53
So: Neuester Stand.

Nachdem mir gerade aufgefallen ist, dass ich Trottel in meinem Auswertungsprogramm ein "(1/2)" vergessen hab, und deswegen die ganze Korrelation nicht viel bringen konnte (alle Winkel falsch...)

... hab ich das ausgebügelt und nun ein paar Messungen gemacht.
Wie genau das ganze wirklich ist, ist ein bisschen schlecht abzuschätzen, aber so wie es aussieht scheint sich die Messungenauigkeit doch wieder im cm-Bereich abzuspielen.

Blöd ist noch, dass schon mein Notebook ein, zwei Minuten an der Korrelation rechnet. Aber noch ist auch nichts optimiert. Jetzt wo das Prinzip funktioniert werde ich mich an die Optimierungen wagen.

Jedenfalls ein nettes Bild:
Blau sind wieder die Punkte der 1. Messung
Rot die der 2. Messung
Schwarz die Roten Punkte um die ermittelte Verschiebung verschoben, also die "korrigierten" Punkte

1 Kasten entspricht etwa 1 cm,
das Programm behauptet die Verschiebung wären -4 Kästen in Y-Richtung
Könnte etwa hinkommen, ich hab das ganze um ca. 5 cm (Augemaß) in diese Richtung verschoben.

Die türkisen Linien sind die Objekte, deren Punkte ich zuordnen konnte...

mpetz
25.08.2005, 21:33
Hi,
ich hab auch sowas programmiert. Ich habe einen Sharp GP2D12 auf einem Servo sitzen und messe nach jedem schritt (insgesamt 180 grad, da sind bei mir 230 schritte). Dabei brauche ich insgesamt ca. 16 Sekunden, viel schneller dürfte es laut Datenblatt des Sensors auch nicht gehen, habe aber noch Optimierungsideen, die es etwa auf 14 Sek. drücken könnten.

In der ersten Version die jetzt läuft speichere ich die Punkte als Vektoren ab und es können immer mehr werden, da der Scanner dauernd läuft (s. Ansicht links). Im der rechten Ansicht habe ich ein Raster aufgesetzt und jedem feld eine Wertigkeit anhand der enthaltenen Punkte gegeben (schwarz=viele punkt im feld). So kann ich jetzt schon sehr gut Wände etc. erkennen, die Einstellung der Wertigkeit ist dabei Variabel. Der Vorteil ist, das ich mit den weiteren Sensoren am Roboter, die auch Ihre Daten mit einbringen, ab z.B. 3 Punkten im Feld, sicher von einem Objekt ausgehen kann. Die Rastergröße ist auch variabel einstellbar und die Ansichten können mit dem Schieber in der Mitte auch gezoomt werden. Sollte die Ansicht größer werden, erscheinen auch Scrollbalken.

Da ich dieses Semester an der Uni auch an dem dortigen Roboter mit festen GP2D12 Sensoren (glaub es waren 17) ein Ähnliches Projekt entwickelt habe, ist eine grobe Navigation zwar mit den Vektoren möglich (addition der Vektoren->Hinderniswertigkeit in einer Richtung), aber um Objekte, wie Wände zu erkennen und on-the-fly Durchgänge zu finden, eignet sich das Raster sehr gut.

Im Moment (diese Nacht *g*) arbeite ich daran, das ich nicht nur die Vektorpunkte beachte sondern auch den Vektor vom Roboter zum Punkt, denn dort ist ja frei. Es wird dann also bei jedem Rasterfeld eine Anzahl Punkte (=belegt) + eine Anzahl schneidender Vektoren (=frei) geben, welches mehr hat, wird recht bekommen, so kann ich hoffentlich ein noch genaueres Bild der Umgebung erzeugen, bzw. besonders "unsaubere" Messungen rausfiltern.

P.S. Startpunkt des Roboters ist (0|0), alle Sensor Vektoren werden von der aktuellen Position des Roboters gespeichert, es ist also ein Scannen während dem Fahren möglich (noch nicht umgesetzt). Meine Position will ich dabei durch die Fahrdaten (fahre mit Schrittmotoren) + 2 Laserscannern (aus der Laserfunkmaus) gewinnen. Erste Tests lassen mich da zuversichtlich stimmen, eine gute Genauigkeit auf flachem Untergund zu bekommen.

sep
25.08.2005, 22:00
wie kommst du darauf, dass 230 Schritte 16s benötigen? Im Datenblatt steht nur, dass die erste Messung etwas unter 50ms benötigt, wenn alle Messungen solange brauchen, brauchen 200 Schritte 10s - ist es das was du meinst?

Was für einen Controller verwendest du?

Wenn ich dich richtig verstehe, willst du nur erkennen ob Hindernisse im Weg sind und diesen aus dem Weg gehen?

Was um alles in der Welt ist eine Laserfunkmaus? Meinst du optische Mäuse? Wenn ja - wie genau sind die? (Meine war nicht sehr genau, daher hab ichs gelassen...)

mpetz
25.08.2005, 22:48
das sind optische mäuse, aber neuerdings mit laser halt statt ir:
https://www.roboternetz.de/phpBB2/zeigebeitrag.php?t=6894&highlight=lasermaus
https://www.roboternetz.de/phpBB2/zeigebeitrag.php?t=11548&highlight=lasermaus

okay, du hast recht, ich warte ja auch nur 16ms auf die spannung, das datenblatt nennt ja 5ms (nach dem ersten). 16ms sind mit meinem board wohl die untere grenze. dazu kommt bei mir nochmal 52ms wartezeit, bis der servo den schritt gedreht hat, wobei ich dies nicht berechnet habe, sondern ich nur bei dieser wartezeit verwertbare ergebnisse bekomme (sonst fehler), warum dies so ist, weiss ich nicht (wird wohl aber eher an meinem board liegen, das diese zeit zum senden o.ä. braucht), macht also: 230 * (16+52) = 15,64 Sek.

ich will damit nicht nur aus dem weg gehen, sondern komplett kartographieren und anhand der karte dann zu bestimmten punkten fahren können. kernziel ist also die kartographie und daran auch die objekterkennung (bwsonders halt wände, stühle etc.)

mpetz
25.08.2005, 22:53
p.s. der punkt in der mitte unten in der ersten ansicht, ist der mittelpunkt des scanners (des servos bzw. auf dem roboter).

Fritzli
26.08.2005, 10:28
Hallo

Ok, mal was zum Thema Sharp-Messperiode: Die 38.3 +/- 9.6ms beziehen sich auf alle Messungen, nicht nur auf die erste. Die max. 5ms ist die Zeit zwischen Ende der eigentlichen Messung (sind glaub ich ca. 40 LED-Impulse), bis das entsprechende Signal am Ausgang (stabil) anliegt.
Somit duerften die 52ms von mpetz erklaert sein, der Servo spielt da natuerlich auch noch ne Rolle

mfg
Fritzli

mpetz
26.08.2005, 14:07
Hatte ich doch richtig gesehn zu erst, es liegt schon an den Sharps diese Pause. Viel schneller wird man also leider mit einem Sharp nicht kommen pro 180 Grad (ca. 16 Sek.). Ich werde noch zwei weitere Sharp Heute montieren jeweils nach rechts und links (90 Grad), damit muss ich nur noch 90 Grad gesamt drehen und decke dann insgesamt 270 Grad ab (4 wäre natürlich dann noch schöner, gibt meine Kontruktion leider grade nicht her). Da die Pausen gleich bleiben hätte ich dann eine Scanzeit von: 115 * (16+52) = 7,82 Sek. (Ist denke ich noch auf um die 5 zu drücken)

Die selbe Zeit natürlich auch mit 4 Sensoren und dann 360 Grad abdeckung. Finde ich schon relativ gut, hat jemand von euch so einen Scanner schonmal auf einem Roboter während der Fahrt verwendet?

Aufrund der Tatsache, das wenn ich alle Vektoren speichere und behalte, mir der speicher sehr schnell ausgeht, hab ich nun die linke Ansicht als reine Scanansicht (um den roboter) gemacht. es werden also nach jedem Durchgang die vektoren wieder gelöscht. das raster rechts ist nun quasi eine Karte (gerastert halt) der Punkte aus der Scanmessung in gewertete Rasterfelder darstellt.

Ein Rasterfeld steht bei mir auf 0 (Initialwert) für unbekannt, < 0 ist frei und > 0 ist belegt (Gegenstand). Wie gesagt, jeder Sensorpunkt in dem Rasterfeld erhöht die Wertigkeit um eins, jeder schneidende Vektor erniedrigt die Wertigkeit um eins.

Leider habe ich die Berechnung für die schneidenden Vektoren noch nicht ganz geschafft, hat da jemand eine Idee? Ich könnte natürlich alle Rasterfelder als Ebenen in dem Vektorraum betrachten und prüfen ob der Vektor die Ebene schneidet, dafür müsste ich aber alle Rasterfelder abarbeiten (sind bei mir im Moment 200*200=40000 Felder a 5*5cm, decke damit 10x10m ab -> nicht grade so viel und schon ganz schön mächtig!). Ich könnte aber auch nur die Rasterfelder bis zum Vektorpunkt nehmen, das sind schonmal sehr sehr viel weniger, gibt es eine andere möglichkeit?

zefram
26.08.2005, 14:18
Leider habe ich die Berechnung für die schneidenden Vektoren noch nicht ganz geschafft, hat da jemand eine Idee? ...
Ich könnte aber auch nur die Rasterfelder bis zum Vektorpunkt nehmen, das sind schonmal sehr sehr viel weniger, gibt es eine andere möglichkeit?

Nutze doch den Bresenham Algorithmus um effizient alle Rasterpunkte vom Start- zum Zielpunkt des Vektors zu durchlaufen.

mpetz
26.08.2005, 15:01
sehr gut, danke!!! Genau damit kann ich es lösen...

sep
26.08.2005, 15:21
Naja das klingt doch ganz vernünftig...
Solange mein Rundumscan nicht länger zum Scannen braucht als zum Berechnen ist ja alles gut :D

Leider kann ich euch so spontan nicht sagen, wie schnell ich den Sensor jedoch auf jeden Fall eher langsamer, denn zwischen den einzelnen Schritten warte ich auf jeden Fall 50 ms und dazu kommt noch die unbekannte Dauer für eeprom_write_byte()

Wenns schneller gehen soll, braucht man halt mehr Sensoren.

Manf
26.08.2005, 15:38
Die Betrachtung der Messzeit und der Pausen für das Drehen ist für eine maximale Genauigkeit sicher von Vorteil. Man verschenkt dabei nichts an Auflösung. Ein völlig anderer Ansatz ist, mal zu sehen was herauskommt wenn man eine kontinuierliche Abstandsverschiebung mit begrenzter Geschwindigkeit zuläßt.

Als Anregung ein Bild vor der Spannung eines Gp2D12 vor einem in den Schraubstock eingespannten schwingenden Plastiklineal, (links unbewegt, rechts schwingend mit einer Frequenz von ca. 3,5Hz ). Die Kurve ist nicht sinusförmig wegen der Nichtlinearität der Kennlinie.

Wenn der Sensor den mitteleren Abstand seiner 32 Einzelmessungen pro 40ms ausgibt, dann sollte sich ja bei etwa 32Hz eine Nullstelle für einen sinusförmige Abstandsfunktion ergeben. Mal sehen was sich für die Scangeschwindigkeit daraus ableiten läßt.
Manfred

https://www.roboternetz.de/phpBB2/zeigebeitrag.php?p=107303#107303

https://www.roboternetz.de/phpBB2/album_pic.php?pic_id=495

mpetz
26.08.2005, 15:55
@Manf du willst also nicht stoppen und dadurch zeit sparen?

hab aber nicht verstanden, wie du dann diese wartezeit bis das signal stabil ist bzw. bis ein neues angefragtes kommt verkürzen willst? oder geht es dir nur um eine minimale noch rauszubekommende verbesserung durch wegfallen des servo anfahren?

sep
26.08.2005, 16:00
Aber nun hätte ich noch eine weitere Frage an euch: Wenn ich nun also einen Rundumscan mache, erhalte ich Entfernungen.

Dazu Bild 1. (erklaer1.png)

Rot sind die Punkte der 1. Messung
Blau die der zweiten, zwischen den Messungen wurde der Roboter bewegt.
Das Grüne sollen Wände o.Ä. sein.

sep
26.08.2005, 16:01
Nun sollen die Messungen so verglichen werden, dass der Roboter erkennen kann, wie er bewegt wurde.

Dazu Bild 3 (erklaer3.png)

sep
26.08.2005, 16:01
Nun sind die Ursprünge übereinander gelegt, man kann schon das Messergebnis erahnen. Blöd ist nur dass hier Äpfel mit Birnen verglichen werden. Denn wenn die Entfernungen so verglichen werden, wären die Punkte der zweiten Messung so wie in Bild 2 (erklaer2.png) angeordnet.

sep
26.08.2005, 16:02
Um diesen Fehler zu vermeiden würde ich gerne die Punktwolken in kontinuierliche Kurven interpolieren, (am besten so, dass dabei massiv RAM frei wird...)
Und dann diese Kurven miteinander vergleichen. (Bild 4, erklaer4.png)

sep
26.08.2005, 16:09
Sorry, das ich so viele Posts hintereinander reingehauen hab, aber ich wollte, dass die Grafiken an die richtigen Stellen kommen... UNd man kann wohl nur 3 Anhänge an einen Post hängen?

Egal - jedenfalls suche ich jetzt eine sinnvolle Interpolations-gedingse die bei 200 Punkten nicht ewig braucht, am besten "relevante" Punkte stärker bewertet (Punkte mit nahen Nachbarn oder Punkte die mit ihren Nachbarn in einer Linie liegen) und die sich obendrein nachher leicht miteinander vergleichen lässt...
Leider fällt mir dazu spontan nur "Spline-Interpolation", und die ist nicht sehr RAM-Schonend...

Vielelicht lass ichs auch einfach und lebe mit dem Fehler...

Manf
26.08.2005, 16:19
hab aber nicht verstanden, wie du dann diese wartezeit bis das signal stabil ist bzw. bis ein neues angefragtes kommt verkürzen willst? oder geht es dir nur um eine minimale noch rauszubekommende verbesserung durch wegfallen des servo anfahren?

am besten "relevante" Punkte stärker bewertet (Punkte mit nahen Nachbarn oder Punkte die mit ihren Nachbarn in einer Linie liegen) und die sich obendrein nachher leicht miteinander vergleichen lässt...
Mir ginbg es nicht um die genauere Messung von Einzelpunkten eher um die Mittelung einer Reihe von Punkten die gleiche Werte Liefern und Verzicht auf Start Stop pro Punkt.
(wie gesagt nur als Anregung)
Manfred

mpetz
26.08.2005, 16:35
@Manf Ah okay, da lässt sich wirklich vllt noch was rausholen! Werde das Morgen mal ausprobieren, für Heute ist die Zeit leider aus =(. Im angehängten Bild mein aktueller Status beim scannen (wohlgemerkt hat sich der Ort des Scans geändert). Habe also nun durch den Bresenham-Algorithmus auch die freien Felder mit ermittelt. Einziges wichtiges, das ich noch hab ist, das ich bisher einen ganz freien Scan nicht beachte also wenn meine Messung > 60cm ist (hab z.Zt. 60cm als Obergrenze eingestellt), werden z.Zt. keine freien Felder gesetzt.

@sep dein Ansatz die Position anhand der Umgebung zu bestimmen bzw. die Bewegung finde ich auch sehr interessant, das könnte als weitere Komponente in meine Odometrie einfliessen. Hab jetzt nicht mehr die Zeit leider, werde mir das am we mal genau anschauen. Wenn du da eine Lösung hast nur her damit, vllt ist die auch mit solchen Rasterfeldern wie ich sie nutze möglich.

sep
26.08.2005, 16:39
Naja, wie ich versucht habe bildlich zu machen, kann man auch einelne Punkte nur bedingt miteinander vergleichen. Deswegen würde ich gerne Kurven hineinlegen.

Du meinst Du willst eigentlich nur eine Rastergrafik erzeugen, und die dann vergleichen. Ich würde gerne auf so eine Rastergrafik verzichten, denn soviel RAM hab ich nicht. Daher die Idee mit der interpolierten Kurve.

Jedenfalls bin ich dahintergekommen, dass nur Punkte, die vom selben Hindernis stammen (und daher meist eng beieinanderliegen) wirklich aussagekräftig sind. Wenn ein Hindernis nur von ein, zwei Punkten abgedeckt wird, kann es sein, dass es beim zweiten Scan gar nicht gesehen wird, weil es zwischen den Punkten liegt.

Aus Sicht der Hinderniserkennung ist das natürlich anders. Aber zunächst würde ich erst gerne meine Position exakt in einer Karte bestimmen können.

Fritzli
26.08.2005, 16:42
Hallo

@Manf: meinst Du sowas in der Art: http://zuff.info/SharpGP2D12_E.html
Sonst wärs ein weiterer Ansatz.

mfg
Fritzli

Manf
26.08.2005, 16:49
Das ist auch ein interessanter Link.
Ich finde alles richtig was gesagt wurde und lese sehr interessiert mit. Ich wollte nur betonen, dass man die Präzision in einer natürlichen Umgebung nicht überschätzen sollte, aber das wude ja auch schon geschieben:

Wenn ein Hindernis nur von ein, zwei Punkten abgedeckt wird, kann es sein, dass es beim zweiten Scan gar nicht gesehen wird, weil es zwischen den Punkten liegt.
Manfred

mpetz
26.08.2005, 16:57
Wenn ein Hindernis nur von ein, zwei Punkten abgedeckt wird, kann es sein, dass es beim zweiten Scan gar nicht gesehen wird, weil es zwischen den Punkten liegt.

Ich sehe dieses Problem auch, daher wird bei mir im Moment 2 addiert wenn eins erkannt wird und nur 1 subtrahiert wenn nicht. So in der weise wollte ich arbeiten, lässt sich vllt. noch optimieren. Bei meinem Ansatz sind Objekte kleiner als die Rastergröße/2 nicht immer zu erkennen. Da mein Raster aber aktuell 5cm sind (scheint berechenbar, wohlgemerkt von einem Notebook) ist das für mich okay.

sep
26.08.2005, 21:03
:D Auf dem mega ist das natürlich nicht berechenbar :D
Und du wirst sehr schmale Hindernisse übersehen. Aber das macht vermutlich nix, denn manche anderen Hindernisse (Glasscheiben) kannst du ja auch nicht erkennen. Also brauchst du eh Ultraschall o.ä.

sep
27.08.2005, 16:12
Aktueller Stand:

Ich versuche die Scan-Punkte durch Linien zu verbinden und die Linien zu "optimieren", Punkte die praktisch zwischen ihren Nachbarn liegen fliegen raus.

Dann vergleiche ich die Punkte der 2. Messung mit den Linien.
Das geht schnell wenn keine Drehung berücksichtigt wird, leider sind die Ergebnisse dann eher unbrauchbar, wenn trotzdem ein wenig gedreht wurde...
Umgekehrt ist die Dreh-Erkennung allein ebenso ungenau...
Zusammen dauert das ganze auf dem Notenbook über 2 Minuten, obwohl nur Verschiebungen von maximal +-10 cm erlaubt sind (Drehungen von +-10 Schritten = +-18°)

Und wirklich gut ist das Ergebnis auch nicht :(
Die Messwerte stimmen zwar mit den von Hand ermittelten überein, aber wenn man nachher die Punktwolken ansieht, könnte es doch noch etwas besser passen...

Immerhin ist der RAM-Bedarf nicht so hoch. (bzw könnte gut optimiert werden)
Und mit etwas Glück könnte ein Teil der DV noch währen des Scannens stattfinden, während sowieso auf den Sensor gewartet wird.

sep
27.08.2005, 16:13
und hier noch das Bild zur Korrelation

Manf
27.08.2005, 17:32
Ich versuche die Scan-Punkte durch Linien zu verbinden und die Linien zu "optimieren", Punkte die praktisch zwischen ihren Nachbarn liegen fliegen raus.
Kann man das auch umkehren?
Punkte die nicht in der nähe ihrer Nacharn liegen sind vieleicht Meßfehler, Störungen, haben vielleicht speziell auch Kantenfehler bei der Sharp Messung, die ja darauf aufbaut dass der ganze Leuchtfleck reflektiert wird.

Wenn man nur Punkte drin läßt dernen rechter und linker Nachbar in der Nähe liegen, dann hat man vielleicht eher ein störungsarmes Bild mit einigermaßen gesicherten Konturen, und ein bisschen weniger zu berechnen.

Im nächsten Durchgang kann man dann einige von dicht beieinander liegenden Punkten auch noch weglassen.
Manfred

sep
29.08.2005, 22:31
Naja, das Problem sind halt relativ schmale Hindernisse. Eine Sprudelflasche in 1m Entfernung bekommt hat gerade mal ein, maximal zwei Punkte ab - und wenn die dann noch schlecht erkannt werden (Glas=durchsichtig) wars das halt.

Ich denke ich mache in (ferner) Zukunft dreierlei:
1.) Bewegungserkennung (aus den Scan-Daten Eigenbewegung ermitteln)
2.) Hinderniserkennung (hier ist jeder (!!) Punkt wichtig, auch vielleicht fehlerhafte)
3.) Kartennavigation (Orientierung anhand einer Landkarte...)

Alle drei Aufgaben verlangen nach unterschiedlichen, gegensätzlichen Ansätzen.
Die Kartennavigation z.B. ist nie wirklich genau, daher kann aus ihr nur bedingt auf die Bewegung geschlossen werden.

sep
08.09.2005, 18:46
Ich habe jetzt eine funktionierende Lösung. Zwar keine wirklich gute, dafür aber eine recht fixe...

Ich vergleiche einfach die Punkte, so als ob sich nichts geändert hätte, also ich rechne einfach die X-Differenz aller Punkte zu den Punkten der vorrigen Messung aus - wobei Punkte in X-Richtung (und -X - Richtung) stärker gewichtet werden, dasselbe für die Y-Richtung.

Die Drehung kann ich ja mit einem ähnlichen Verfahren recht sauber erkennen.

In der Grafik sieht man mal das Ergebnis. (Blau sind die Punkte der 1. Messung, Rot die der 2. Messung, Grün sind die um die erkannte Verschiebung / Drehung korrigierten roten Punkte)

Für geringere Verschiebungen sind die Ergebnisse deutlich besser, aber ich wollte damit zeigen, dass auch größere Verschiebungen noch aktzeptabel erkannt werden.

Und immerhin geht die Berechnung (jedenfalls bislang auf dem PC) mit "lichtgeschwindigkeit" und skaliert linear zur Anzahl der Punkte.
Somit ist der begrenzende Faktor nur noch der SHARP-Sensor...

Nächste Woche werde ich, wenn ich dazukomme, versuchen präzisere Messungen zu machen.

sep
13.09.2005, 18:40
Leider hat sich dieses Verfahren als zu ungenau erwiesen - es ist zwar "unglaublich" schnell, dafür aber schnell verwirrt, wenn nicht alle Wände rechtwinklig sind...

Da ich früher oder später sowieso eine kleine Kartenavigation einbauen wollte, hab ich beschlossen diesen Ansatz weiter zu verfolgen. Um neuerkannte Punkte in der Karte hinzuzufügen, muss ja deren Position aus Referenzpunkten möglichst genau ermittelt werden.

Also erzeuge ich direkt aus meinen Scan-Daten ein Linienmuster und vergleiche die Punkte der zweiten Messung dann mit den Linien.
Das lässt sich ganz gut optimieren.
- Da Wände meistens gerade sind, können sie durch wenige Stützpunkte ersetzt werden.
- Punkte die nicht in der Nähe einer Geraden sind brauchen nicht verglichen werden.

Bis jetzt läuft das ganze ersteinmal nur auf dem PC. Aber die Ergebnisse sind gut. Mit ein bisschen Arbeit dürfte sich das ganze auch deutlich optimieren lassen. Die nächsten Tage werde ich mal ein paar Versuchsmessungen machen.
Wenn das alles klappt werde ich das ganze auf den AVR "portieren".

Im Anhang ein Bild, das den aktuellen Stand wiederspiegelt.

Blau sind die Punkte der ersten Messung, man sieht die eingezeichneten genäherten Geraden.
Rot sind die Punkte der zweiten Messung, dabei die blassroten die, die für die Korrelation berücksichtigt werden.
Und grün letztendlich die roten, verschobenen Punkte...