Algorithmen zur Bahnplanung

Hallo, ich Arbeite derzeit an einem Seminar unter anderem über Bahnplanung und Navigation. Leider kenne ich mich in diesem Thema noch nicht so wirklich gut aus. Daher bräuchte ich Infos zu folgendem:

- Algorithmen zur Navigation und Bahnplanung
-> Welche gibt es?
-> EINFACHE Bücher oder Webseiten dazu?
(hab bisher was über A*, D Algos. gefunden, aber schlecht erklärt)

- Wie funktioniert Bahnplanung anhand von Kartenmodellen

Mir geht es erstmal darum einen Überblick zu bekommen. Ich hoffe hier kennt sich jemand damit aus.
Ach ja, es geht um einen Roboter mit Rädern und keinen auf Beinen oder so, falls das wichtig sein sollte.

Ich kann nur empfehlen, Du gehst in eine Hochschulbibliothek und leihst Dir dort welche, da Du Dir die vorgeschlagenen Bücher für eine Semesterarbeit wahrscheinlich eh nicht kaufen willst oder sie garnicht bekommst.
Dort bekommst Du auch die eine oder andere Doktorarbeit, da gibt es welche im VDE Verlag.
Später könnte ich Dir Namen nennen.
Gruß

Hallo JackBauer, willkommen im Forum.

Im Buch "Fahrbarer Selbstbauroboter" von U.W.Geitner aus dem elektor-Verlag ist ein Kapitel "Kleine Bewegungsgeometrie".
Mir hatt es sehr gut geholfen zu verstehen, wie ich von Punkt A nach B kommen unter Berücksichtigung meiner Richtung an Punkt A und dem Richtungswunsch für Punkt B.
Leider ist das Buch schon eine 'alte Schwarte' von 1990.
Trotzdem hier noch die ISBN: 3-921608-82-1

JackBauer,

hier ist eine Veröffentlichung, die mit Deinem Thema in Beziehung steht. Zumindest die Zitateliste sollte Dir weiterhelfen. Es gab auch eine interessante Arbeit in "Proc. of Underwater Technologies 2000,. 23-26 May 2000, Tokyo, Japan. " (Autor: Uwe R. Zimmer; Titel: "Embedding local metrical map patches in a globally consistent topological map"), die ich hier aber nicht anfügen kann, weil sie zu gross ist (875kB).

Ciao,

mare_crisium

Edit: Anhang gelöscht wg. Upload-Quota

@mare_crisium
oh man oh man, dein geposteter Text hat es aber schon faustdick hinter den Ohren. Zumindest ich habe da doch erhebliche Schierigkeiten noch zu folgen. Mal sehen wie weit ich komme. ;-)

@Sternthaler,

tut mir leid, was Einfacheres habe ich nicht gefunden. Ich erinnere mich noch finster an eine andere Methode, die, wenn ich mich nicht täusche, bei den beiden Marsrovers angewendet wird. Die ist aber mathematisch nicht wesentlich weniger anspruchsvoll. Wenn ich sie wiederfinde, werde ich sie auch posten. - Dass Du Dich überhaupt an so ein Ungetüm heranwagst, finde ich schon sehr tapfer!

mare_crisium

@Sternthaler und JackBauer,

hier habe ich die Beschreibung des A*-Algorithmus angehängt, die mir am besten verständlich erscheint. Die Web-Adresse der Quelle steht ganz oben. Dieses Verfahren ist anschaulicher und braucht keine grossen Vorkenntnisse in Mathematik.

mare_crisium

Edit: Anhang gelöscht wg. Upload-Quota

Hallo mare_crisium.
Na das ist doch auch für einen Mathe?-Hab-mal-davon-gehört-User lesbares Zeug. Wenn also der Handesvertreter seinen Weg mit A* plant, kommt er bestimmt leichter am Ziel an, als mit dem ersten Artikel von dir.

Eigendlich hatte ich bei der Frage von JackBauer eher an die geometrischen Grundlagen zum Einstellen von Radlenkung und/oder Geschwindigkeiten bei 2-rädriger Fortbewegung á la Asuro gedacht.
In den von dir geposteten Artikeln (ja, auch im ersten, so weit ich den überhaupt verstanden habe.) ist nichts dazu beschrieben, wie ich z.B. einen vorgegeben Kreis in Teilen abfahren kann, wenn ich die Geometrie meines Fahrzeugs kenne und diese Daten nutzen muss.

Jetzt auch mal ein Anhang von mir.
Im Excel-Blatt berechne ich anhand geometrischer Daten die zu fahrenden "Tik's" vom Asuro. Ein Tik ist ein messbarer Farbwechsel an der Odometrie, und gibt somit die gefahrene Wegstrecke an. (mal besser, mal schlechter) Die gesamte Berechnung beruht mehr oder weniger nur auf Pythagoras und PI, auch wenn die Formeln darin etwas 'verstrubbelt' sind. Ist vor allem auf eine INT-Berechnung getrimmt. Deshalb die oben rechts stehenden 'Zeilen' um 2 Faktoren zu ermitteln, die aus der Rad-Geometrie abgeleitet werden.

In Kombination mit dem A*-Dingsda, sollte nun alles beisammensein um Wege zu planen und auch auszuführen.

Buona notte Sternthaler,

danke für die Tabelle - jetzt verstehe ich besser, worauf JackBauer aus war. Trotzdem würde ich's gern nochmal mit Mathe versuchen. Ich hatte mir vor einiger Zeit 'mal die Formeln für die Koppelnavigation eines Roboters von der Art eines Asuro zusammengestellt. In der angehängten pdf-Datei habe ich die ganze Herleitungsorgie weggelassen und nur das Endergebnis aufgeschrieben. - Ich weiss, meine didaktischen Fähigkeiten sind stark unterentwickelt, aber es würde mich interessieren, ob Du das lesen und verstehen kannst!

Der Witz an der Geschichte ist, dass man mit diesem Algorithmus das Fahren in vorbestimmten Richtungen und das Ansteuern von Zielorten mit einfachen Regelkreisen (ein Fahrgeschwindigkeits- und ein Richtungsregler) verwirklichen kann. Und das ist wesentlich eleganter, als die gesamte Bahnkurve mit Hunderten von Zwischenorten festzunageln. Dabei bleibt nämlich meist unbeantwortet, was der arme Roboter machen soll, wenn er einen der Zwischenpunkte verfehlt! Mit einem geschickt gewählten Regelkonzept erledigt sich diese Frage ganz von alleine.

Ciao,

mare_crisium

Edit: Anhang gelöscht wg. Upload-Quota

Hallo mare_crisium, (noch eine Nachteule ;-) )
noch in der Firma, deshalb nur kurz mein 'Überflug'.
Im ganzen (auch für mich) recht gut verständliche.
Hier aber trotzdem ein paar Anmerkungen/Fragen:

- Bei Formel (1) wird angenommen, dass Nr und Nl bzw. Rr und Rl gleich sind? (gehe ich von aus, suche nur Bestätigung)

- Mir helfen bei Formeln allgemein die Einheiten. (1) also m/s und dann bei (2) bestimmt 1/s. (Nicht lebenswichtig, aber für Dummy's wie mich hilfreich)

- In Formel (7) verstehe ich absolut nicht, warum die px- und py-Anteile zur Berechnung von px' und py' gekreuzt werden und mal mit minus bzw. plus berechnet werden. (Grübel heute Nacht)
--- Ich sehe gerade, dass es doppelte Formelnummern gibt. Ich meine hier Formel (7) für die neue Fahrtrichtung ep'

- Bei der Berechnung der Abweichungen zur Ziel-Bestimmung ist mir klar wie es mit der Fahrt-Richtungs-Abweichung vor sich geht.
Bei der Ziel-Positions-Abweichung kann ich nicht folgen:
-- Start-Pos und Ziel-Pos berechnen eine Abweichung zum Startzeitpunkt. OK
-- Aktuelle Position wird laufend berechnet. OK
-- Ziel-Positions-Abweichung nun in Bezug zum ursprünglichen Start-Punkt? (Komme ich mit den Indices durcheinander?)

-- Und noch bei Formel (11): Als Fazit bedeutet dies doch, dass der Roboter dann je nach Entfernung zum Ziel die Geschwindigkeit anpasst? Somit müsste das letzte Stück Weg im 'Schneckentempo' zurückgelegt werden? Sollte hier eine Reglung mit Schwellwert sinnvoll sein?

Sonst ist das Ganze sehr lesbar. Kopie schon angefertigt ;-)

Gruß Sternthaler

[Edit 23:30]Was ich noch vermisse, sind Angaben über die X-, Y-Koordinaten bzw. die Einheiten von Start- und gewünschter Ziel-Position. Ist die ganze Mathematik da Einheitentolerant? Mein Startpunkt liegt bei 0/0, mein Ziel bei X/Y. Aber wie weit ist das weg? Meter / Dezimeter /Kilometer?
Wenn ich die Geschwindigkeit in m/s berechne, müsste dann wahrscheinlich meine Zielkoordinate auch in Metern als Abstand/X/Y angegeben werden. Richtig?