Rückwärtsschnitt, bitte Hilfe für einfachstes Rechnen

Guten Tag, alle,

bei der Bahnplanung bzw. Navigation von einfachen Robotern (hier im Hobbybereich) stellt sich immer wieder das Problem, mit Hilfe von drei Baken an bekannten Orten den Roboter seine Position errechnen zu lassen. Da die Rechenleistung und der verfügbare Speicher der üblicherweise eingesetzten Mikrocontroller gering ist, bin ich auf der Suche nach einer möglichst einfachen Lösung.

Natürlich stehen meine Wünsche einer sauberen Berechnung entgegen: möglichst Integer soweit es geht - floating point so wenig wie möglich, möglichst wenig Speicherverbrauch, möglichst wenig transzendente Funktionen (ein atan braucht bei einem 20 MHz / 8 Bit-Rechner EWIG), und so weiter.

Bitte kann mir jemand Tipps geben? Danke schon mal jetzt sagt der
oberallgeier

Eintrag gesperrt

10306 Views

Hallo,

die erste Frage, die sich stellt, benötigst Du einen räumlichen Rückwärtsschnitt oder einen klassischen Rückwärtsschnitt in der Ebene?

Für trigonometrische Funktionen werden fast immer schnelle (native) Codes eingesetzt, sodass in keiner Programmiersprache das Rad neu erfunden wird. Iteratives Verfahren für verschiedene trigonometrische Funktionen haben wir als MATLAB-Code hier zusammengetragen. Für den ATAN lautet dieser:

 
% HINWEIS:
%  Berechnung der ATAN-Funktion [RAD]
%  Download von: http://diegeodaeten.de
%  @version 1.0
%  @author Michael Loesler - http://derletztekick.com
%
 
function myarctan(x);
xreihe = x;
 
temp=0;
n=1;
 
while (abs(temp-xreihe)>=1e-12)
    temp=xreihe;
    xreihe=xreihe+(-1)^n*x^(2*n+1)/(2*n+1)
    n=n+1;
end

Die Konvergenz kannst Du hier selbst beeinflussen. Im Moment ist 1E-12 eingestellt. Du kannst also testen, ob das bei Dir einen Vorteil hat, diese Funktion zu implementieren, da das Potenzieren letztlich auch Zeit benötigt.

Hilft Dir das weiter?

Schöne Grüße
Micha

--
applied-geodesy.org - OpenSource Least-Squares Adjustment Software for Geodetic Sciences

Tags:
Rückwärtsschnitt

Eintrag gesperrt

10604 Views

Hallo Michael,

danke für die schnelle Antwort und entschuldige bitte, dass ich die Anzahl der Dimensionen nicht angegeben hatte. Für den Hobbybereich sind zwei Dimensionen praktisch immer ausreichend - und schon kompliziert genug abzuarbeiten.

"Naive" Codes waren mir bis dato unbekannt - schön - wieder was gelernt. Ich (wir) werde(n) mal den Code überarbeiten und über den Erfolg, dh. Einsparung an Maschinencode-Länge, berichten.

Nochmals danke und liebe Grüße aus dem oberen Allgäu sagt der Joe
DerAltevomBerg

Eintrag gesperrt

10348 Views

Hallo Joe,

entschuldige bitte, dass ich die Anzahl der Dimensionen nicht angegeben hatte.

Du musst Dich hier nicht entschuldigen ;-)

"Naive" Codes waren mir bis dato unbekannt - schön - wieder was gelernt.

Ironie? Ein Tippfehler meinerseits: Native sollte es werden aber fürs T hat es nicht mehr gereicht.

Ich (wir) werde(n) mal den Code überarbeiten und über den Erfolg berichten.

Das wäre schön!

Schöne Grüße
Micha

--
applied-geodesy.org - OpenSource Least-Squares Adjustment Software for Geodetic Sciences

Tags:
Rückwärtsschnitt

Eintrag gesperrt

10198 Views

Grüß Dich, MichaeL,

*ichgrinsmireins* oder eher uuuuups. Da habe ich ja ganz schön danebengegriffen. Keine Ironie, ein simpler Tippfehler meinerseits oder hast Du das editiert? Völlig egal, denn, wenn wir den Sprachkundigen Glauben schenken wollen, dann ist naiv und nativ ziemlich eng verwandt bzw. vom selben Stamm. So wie ich Dich verstehe, ist die Bezeichnung, mathematisch gesehen, sowieso fast gehupft wie gesprungen. Denn ich kann mir gut vorstellen, dass mancher Mathelehrer eine native Vollgasrechnerei gerne als naiv bezeichnen würde . . .

Eintrag gesperrt

10042 Views

Moin,

Keine Ironie, ein simpler Tippfehler meinerseits oder hast Du das editiert?

Ich hatte nach Deinem (indirekten) Hinweis mein Posting um ein T bereichert.

Denn ich kann mir gut vorstellen, dass mancher Mathelehrer eine native Vollgasrechnerei gerne als naiv bezeichnen würde . . .

In jedem Fall wird es schwer, das noch einmal zu optimieren - was Du ja gern hättest. Aber wenn Du den Versuch nicht scheust, wissen wir bald mehr. Die restliche Berechnung ist dann Schema-F.

Schöne Grüße
Micha

--
applied-geodesy.org - OpenSource Least-Squares Adjustment Software for Geodetic Sciences

Eintrag gesperrt

10708 Views

Hallo Michael,

längere Boarderferien, der Winter im Allgemeinen oder eher meine Faulheit haben die Antwort verzögert. Dabei hat die meiste Arbeit der Kollege Sternthaler gemacht . . . . Immerhin sind einige hübsche Fortschritte erzielt worden.

my-, n-, s-atan - ein transzendentaler Spaziergang
--------------------------------------------------

Vergleich - gerechnet auf ATMEL ATmega8, 8 Mhz, Compiler ist eine AVR-Variante des GCC

atan . . . . . die Funktion aus der AVR-Atmel-Library
my-atan . . . eine eigene Funktion auf Basis nativen Codes
n-atan . . . . näherungsweise Berechnung
nach http://de.wikipedia.org/wiki/Arkustangens_und_Arkuskotangens#N.C3.A4herungsweise_Berechnung
s-atan . . . . superschnelle Näherung
Supernäherungsfunktion von http://www.lightsoft.co.uk/PD/stu/stuchat37.html

Codelängen und Laufzeitmessungen :

atan . . . . . .940 Byte . . . . .1,1 ms
my-atan . . 1816 Byte . . . . 10,9 ms min
. . . . . . . . . . . . . . .. . . . . 21,9 ms max
n-atan. . . . 880 Byte . . . . . 0,51 ms
vergleiche hierzu auch Xcel-blatt N_atan-2
s-atan . . . . .866 Byte . . . . .0,76 ms

Die Laufzeitmessungen wurden jeweils bereinigt um die leere Schleife mit einer Stoppuhr und entsprechend vielen Wiederholungen durchgeführt. Ein Codebeispiel in C für den ATmega8 gibt es hier:
http://oberallgeier.ob.funpic.de/test_div_atan.c
und eine Exceltabelle zu den Kontrollrechnungen hier:
http://oberallgeier.ob.funpic.de/N_atan-2.xls

Jedenfalls danke ich Dir sehr herzlich für Deinen Denkanstoss, ohne dem Sternthaler und ich den Weg nicht gefunden hätten. Dir alles Gute

Josef, der
oberallgeier

Eintrag gesperrt

10929 Views

Guten morgen Josef,

ich bin echt begeistert, muss ich sagen, was Du da alles für Näherungen für den ATAN noch gefunden hast:

(x + 0.43157974 * x*x*x)/(1 + 0.76443945 * x*x + 0.05831938 * x*x*x*x)

oder

if (x < 1)
  x / ( 1 + 0.28 * x * x );
else
  M_PI / 2 - x / ( x * x + 0.28 );

Hast Du neben der Laufzeit auch mal geschaut, wie gut das Ergebnis ist? Ich habe mal testweise den ATAN(0.75) gezogen und für die beiden o.g. Codes folgende Ergebnisse erhalten: 0.643496722039098 und 0.647948164146868. Die richtige Lösung liegt bei 0.643501108793284 und weicht nur um wenige Stellen von der Lösung des ersten aufgeführten Codes ab.

und eine Exceltabelle zu den Kontrollrechnungen hier:
http://oberallgeier.ob.funpic.de/N_atan-2.xls

Der Link scheint defekt zu sein...

Jedenfalls danke ich Dir sehr herzlich für Deinen Denkanstoss,

Wenn ich Dein Ergebnis richtig deute, war mein Vorschlag der zeitintensivste; gut, dass Du noch andere gefunden hast ;-)

Schöne Grüße
Micha

--
applied-geodesy.org - OpenSource Least-Squares Adjustment Software for Geodetic Sciences

Eintrag gesperrt

10128 Views

Hallo Michael,

tut mir leid, dass der Link bei Dir nicht aufgeht, der verweist nämlich auf eine hübsche Tabelle mit Vergleichsrechnungen in 0,1°-Schritten mit einem Fehlerdiagramm. Ich versuchs nochmal, sonst könnte ich das bei Interesse natürlich auch per Mail senden:

http://oberallgeier.ob.funpic.de/N_atan-2.xls

[image]

Nachdem nun die Berechnung in einer fassbaren Methode mit angemessener Genauigkeit vorliegt, kann die Navigationsaufgabe mit Suche/Auswahl/Festlegung der Sensorik weitergehen. Nochmal danke für Deine Hilfe und viele Grüße aus dem sonnigen Süden
Josef

Eintrag gesperrt

10735 Views

Hallo Josef,

tut mir leid, dass der Link bei Dir nicht aufgeht,

Heute gehts?! Gestern wurde der Download mit 0kb angezeigt; heute sind es ein par kb mehr. Insofern: Danke!

Nachdem nun die Berechnung in einer fassbaren Methode mit angemessener Genauigkeit vorliegt,

Das wäre meine nächste Frage gewesen. Ich sehe in Deinem ersten Tabellenblatt, dass der Winkel zB 0.3° vom Soll-Winkel abweicht (60° zu 59,744°). Welche Genauigkeiten sind bei Deinen Anwendungen denn relevant?
(Überschlag mittels Bogenformel: 0.3° auf 10m --> 5cm Querfehler)

Nochmal danke für Deine Hilfe und viele Grüße aus dem sonnigen Süden

Keine Ursache und weiterhin viel Erfolg!

Micha

--
applied-geodesy.org - OpenSource Least-Squares Adjustment Software for Geodetic Sciences

Eintrag gesperrt

10040 Views

Hi Micha,

gaaanz oben hatte ich meine Aufgabenstellung grob qualitativ umrissen:

... Bahnplanung bzw. Navigation von einfachen Robotern (hier im Hobbybereich)...

Quantitativ sieht ein Eckpunkt etwa so aus, dass mit den üblichen Messmethoden (bzw. mit dem finanzellen Aufwand) im Hobbybereich eine Winkelmessung auf 1° Genauigkeit schon als sehr gut angesehen werden kann. Da nutzt dann eine Rechnung auf noch so viele signifikante Stellen auch nix mehr. Bei einem üblichen Bewegungsbereich von 5m x 5m, vermutlich sind 10m x 10m keine sinnvolle Größe mehr, kann man damit die Position ausreichend genau bestimmen. GPS scheidet bei mir aus, da die angepeilten Gerätchen indoor (vorzugsweise mit zwei Rädern) fahren. So sind wir mit dieser eher groben Genauigkeit zufrieden und wollen sehen, ob wir damit eine zufriedenstellende Lösung mit Sensorik und Auswertung finden. Aber das wird nun wieder eine ganze Weile dauern müssen.

Dir inzwischen schöne Grüße

Eintrag gesperrt

10050 Views

RSS-Feed dieser Diskussion

Das GEO-Forum
http://forum.diegeodaeten.de

Rückwärtsschnitt, bitte Hilfe für einfachstes Rechnen (Geodäsie/Vermessung)