Positionsbestimmung mittels Laufzeitmessung

[rockin_santa]

Hallo Zusammen,

Ich möchte meinem Bot (ATmega32, oder größer) die Positionsbestimmung über IR-Baken ermöglichen und schwanke zwischen 2 Möglichkeiten.

1.)
Mehrere feste bekannte IR-Baken mit codiertem Rundumlicht aufstellen und dem Bot einen drehbaren Empfänger geben, der den Winkel zwischen seiner Längsrichtung und dem Einfallwinkel ermitteln kann. Kombiniert mit einem Magnetfeldsensor als Kompass wäre man mit wenig Rechenaufwand in der Lage eine vektorielle Position zu ermitteln.

2.)
Mehrere feste bekannte IR-Baken aufstellen, die auf ein codiertes IR-Signal mit einem US-Signal antworten, dessen Laufzeit gemessen werden kann. Hierbei ist der Rechenaufwand erheblich mehr.

Aus der Sicht eines Programmieranfängers ist die erste Methode sicherlich attraktiver, allerdings hat sie 2 Nachteile:
- Es ist mehr mechanischer Aufwand, höherer Stromverbrauch, mehr Gewicht und mehr Volumen.
- Die Zeit, drei Baken mechanisch zu peilen dauert viel länger, als drei Laufzeitmessungen. Diese können sogar während der Fahrt erfolgen.
Aus diesen Gründen möchte ich die zweite Methode verwirklichen. Hierzu habe ich mir ein paar Gedanken zur Genauigkeit gemacht:

Als Areal habe ich meinen Garten mit annährend ebenem Rasen und einer maximalen Ausdehnung von knapp 30m zu jeder Seite.
Die Lichtgeschwindigkeit beträgt bekanntlich ca. 300.000 km/sek. Bei der Größe des Areals kann sie vernachlässigt werden.
Die Schallgeschwindigkeit liegt bei 343 m/sek. Wenn ich nun einem µC den 16bit-Timer starte, das IR-Licht aussende und das Zählregister auf Null setze, und das US-Signal interruptgesteuert das Zählregister auslesen läßt, habe ich einen Fehler von ein paar Takten.
Diese sind vernachlässigbar, da ich pro 10mm Abstand zum Sender 233 Takte habe (bei 8 MHz Systemtakt). Ohne Prescaler komm ich auf 2,8m Abstand, die ich mit dem 18bit-Timer messen kann. Zähle ich dann noch in einer Interruptroutine ein Register hoch, kann ich den ganzen Garten abdecken.
Mir würde eine Genauigkeit von 10cm völlig ausreichen, ich behaupte mal, das wird klappen.

Jetzt ist die Mathematik mein Problem. Drei Laufzeiten von festen Objekten wären in der Vektorrechnung 3 bekannte Ortsvektoren mit je einem bekannten Radius.
Allerdings weiß ich nicht, wie ich den Schnittpunkt dieser 3 Kreise berechnen kann. Zu Kreisen und Geraden oder Ebenen habe ich im Internet googelnderweise Material finden können, aber zu dem Problem mit 3 Kreisen, bzw. 2 Kreisen und der resultierenden Geraden und einem 3. Kreis finde ich nichts.

Hat sich hier schon mal jemand mit so einem Rechenverfahren auseinandergesetzt und ist zu einer Lösung gekommen oder hat Anregungen?

Abschließend sei noch erwähnt, dass die Positionsberechnungen in C auf dem µC erfolgen sollen. Allerdings ist es nicht zwingend, dass diese während der Fahrt erfolgen müssen.
Ich bin auch erstmal nicht an C-Code interessiert, sondern der grundlegenden mathematischen Lösung. Allerdings kann diese speziell sein, denn in jedem Fall schneiden sich 3 Kugeln in einem Punkt.

Zu guter Letzt würde mich auch interessieren, ob hier auch andere an diesem Problem arbeiten oder dieses System nutzen möchten, wenn das Mathematische soweit gelöst ist.

schönes Wochenende :)

rockin_santa

[user529]

laufzeitmessung:
du hast drei längen ( 2x bot-bake, 1x bakeA-bakeB), such nach sinussatz, damit kannst du dein dreieck vollständig bestimmen. die dritte länge brauchst du nur um zwischen den zwei möglichen punkten zu entscheiden (vo oder hinter der bakeA-bakeB linie)

winkelmessung:
befindet sich der bot in dem von den baken aufgespannten dreieck oder außerhalb?

mfg clemens

[rockin_santa]

winkelmessung:
befindet sich der bot in dem von den baken aufgespannten dreieck oder außerhalb?


Beides. Ich hätte mir soviele Baken aufgestellt, dass er an jedem Punkt mindestens 3 gehabt hätte, die in günstigem Winkel zueinander ständen. Hab von der Seefahrt her Erfahrung mit terrestrischer Navigation, wäre also kein Problem.

Allerdings bin ich von Deiner ersten Aussage mit dem Sinussatz begeistert. Da habe ich den Wald vor lauter Bäumen nicht gesehen. Dabei ist es so einfach, und ich dachte schon, ich muss hier mit wilden numerischen Lösungen oder Linearen Gleichungssystemen arbeiten, was bedeutet hätte, daß ich mich erstmal wieder tief in die Materie hätte begeben müssen.

Aber das ist der Schlüssel, besten Dank, user529 :)

schönes Wochenende

rockin_santa

[uwegw]

Zur Berechnung:
Man könnte erst aus jeweils einem Bakenpaar die Position bestimmen (bzw die zwei möglichen). Das gibt dann zweimal drei Positionen. Und dann schaut man, welche drei davon in derselben Gegend liegen. Das sind dann die wirklichen Messungen. Und aus diesen Positionen könnte man dann noch den Durchschnitt bilden (bzw Schwerpunkt des Dreiecks).

http://img228.imageshack.us/img228/1202/bakeol0.png

[rockin_santa]

Den Vorschlag von uwegw habe ich mir gerade mal angeschaut und bin auf die Kreisgleichungen gestoßen, mit denen man die 2 Schnittpunkte zweier Kreise vektoriell errechnen kann. Allerdings habe ich versucht, die Formel so aufzulösen, dass ich nur noch den Radius der Kreise einsetzen muss, um die Koordinaten der Schnittpunkte zu erhalten und die Formel dazu ist schon sehr umfangreich, wäre kompliziert, die zu programmieren.
Ist aber lösbar, also bin ich schon mal einen Schritt weiter.

Jetzt habe ich mir mal den Cosinussatz angesehen und bin auf folgende recht einfache Formeln zur Winkelberechnung gestoßen:

(alpha) = acos((a² - b² - c²) / (-2bc))
(beta) = acos((b² - c² - a²) / (-2ca))
(gamma) = acos((c² - a² - b²) / (-2ab))

Jetzt kann die Position einfach bestimmt werden, in dem man mit dem zugehörigen Winkel zu einer Bake (deren Ortsvektor bekannt ist) und dessen Abstand (ist ja auch bekannt) den Ortsvektor des Bots berechnet.
Auch hier könnte man aus 3 berechneten Orten ein Dreieck konstruieren, dessen Schwerpunkt die angenommene Position ist.

beste Grüße

rockin_santa

[user529]

nur über die winkel hast du das problem dass du nur eine länge pro dreieck BOT-BAKE- BAKE kennst.
den cos satz gleichsetzen und aus diesen gleichungen auf eine länge rückzurechnen ist eine möglichkeit, aber es muss auch einfacher möglich sein.

habs heir gezeichnet und verwendet bitte die bezeichneten Längen und winkel, damit wie alle den gleichen winkel mit alpha bezeichnen, das erspart viel sinnloses gerede.

wenn ihr weitere winkel oder längen bezeichnet haben wollt, werde ich sie hinzufügen.
http://img233.imageshack.us/img233/5950/bakecm3.jpg

mfg clemens

[rockin_santa]

irgendwie sieht das hier nach einem missverständnis aus:


nur über die winkel hast du das problem dass du nur eine länge pro dreieck BOT-BAKE- BAKE kennst.

Durch Laufzeitmessungen habe ich die Längen der Dreiecke, aber keine Winkel. Ich will ja letztendlich aus drei Abständen zu drei bekannten Ortsvektoren einen vierten unbekannten Ortsvektor berechnen.

Gruß

rockin_santa

[user529]

1.)
Mehrere feste bekannte IR-Baken mit codiertem Rundumlicht aufstellen und dem Bot einen drehbaren Empfänger geben, der den Winkel zwischen seiner Längsrichtung und dem Einfallwinkel ermitteln kann. Kombiniert mit einem Magnetfeldsensor als Kompass wäre man mit wenig Rechenaufwand in der Lage eine vektorielle Position zu ermitteln.

2.)
Mehrere feste bekannte IR-Baken aufstellen, die auf ein codiertes IR-Signal mit einem US-Signal antworten, dessen Laufzeit gemessen werden kann. Hierbei ist der Rechenaufwand erheblich mehr.


nein, kein missverständniss, da die zweite möglichkeit durck sin/cossatz mir ausreichend bearbeitet schien, wollte ich die erste möglichkeit aufarbeiten (das kompassmodul habe ich mir bei dieser skizze gespart, da ja drei baken vorhanden sind)

mfg clemens