Dokumentation für Programm BahnPlaner

Schwerpunktpraktikum Technische Informatik

von

Yi Wang	307082	Informatik
Bin He	291158	Informatik

Einleitung

Zielsetzung

Für das Thema Fußballroboter ist ein Programm unter Betriebsystem Linux benötigt, das die Ist-Bahn eines Fahrzeugs zeigt, und mit dem auch eine Soll-Bahn bestimmt werden kann. Dieses Programm soll mit C++ Sprache programmiert werden, und eine graphische Benutzerschnittstelle unter Linux besitzen.

Programmierungsumgebung

Die Programmsprache ist C++, dazu ist die Klassenbibliothek QT 3.2.1 verwendet. QT ist die von der norwegischen Firma Trolltech (http://www.trolltech.com) entwickelte C++ Klassenbibliothek, die eine einfache und portable GUI Programmierung ermöglicht. Mit QT entwickelte Programme sind sofort ohne zusätzlichen Portierungsaufwand sowohl unter allen Unix- wie auch unter allen Windows-Systemen lauffähig. Sie müssen lediglich mit den entsprechenden Compilern (Visual C++ oder Borland C++ unter Windows-Systemen oder dem auf dem jeweiligen Unix-System angebotenen gcc Compiler) kompiliert und gelinkt werden.

Um weitere Tragbarkeit zu erhalten, sind die wichtigen Algorithmen mit Standard C++ programmiert.

Konzepte

Um das Programm zu erklären sind folgende Konzepte wichtig:

Vector: (double x, double y, double α)

Das Paar (x, y) zeigt die Position (Kartesische Koordination) des Fahrzeugs.

α zeigt die Richtung (Borgen) des Fahrzeugs.

Bahn

Eine Bahn bedeutet in diesem Programm meistens die Soll-Bahn, ein Pfad, entlang den sich das Fahrzeug bewegen soll. Eine Ist-Bahn bezeichnet sich hier Track.

Design-Point

Die Schlüsselpunkte, die der Benutzer bei Bestimmung der Bahn eingibt. Ein Desigen-Point besteht hauptsächlich aus Vector vect (x, y, α), Zeit t, und Geschwindigkeit v, was bedeutet, dass das Fahrzeug beim Zeitpunkt t mit der Geschwindigkeit v auf der Position (x, y) und zwar in der Richtung α sein muss.

Bahn-Strecke

Eine Bahn bestimmt sich durch eine Reihe von Design-Point. Zwischen zwei benachbarten Desigh-Points ist eine Bahn-Strecke, die aus zwei Borgen und einer Gerade besteht. Die drei sind glatt miteinander gebunden. Die Gerade ist immer zwischen den Borgen. Und um den Algorithmus zu vereinfachen, besitzen die Borgen immer den festen Radius. Der feste Radius soll so klein wie möglich sein, um einen kürzeren Weg zu erhalten.

Eine Bahn mit drei Design-Points, und zwei Bahn-Strecke.

Funktionen und Bedienungen

Bestimmung einer Soll-Bahn

Wie oben schone erwähnt ist, besteht eine Soll-Bahn aus eine Reihe von Design-Points, die vom Benutzer eingegeben sind. Der zugehörige Vector (Position und Richtung) kann sowohl mit der Maus virtuell als auch mit der Tastatur in den Textfelde eingegeben werden. Der zugehörige Zeitpunkt und die Geschwindigkeit müssen auch in geeigneten Textfelde ausgefüllt werden. Sobald mehr als zwei Desigen-Points eingegeben sind, wird die geeignete Soll-Bahn gezeichnet werden. Wie in einem normale Bildverarbeitungsprogramm kann die Ansicht der Bahnen auch vergrößert (zoom in) und verkleinert (zoom out) und gezogen (drag) werden. Die Berechnung der Soll-Bahn ist der wichtigste Algorithmus dieses Programm.

Speichern und wieder Einlesen einer Soll-Bahn

Eine entworfene Soll-Bahn kann durch ein Klicken auf der Menu „SaveBahn“ in eine Datei gespeichert werden, um sie später wieder aufzurufen, und zwar durch ein Klicken auf der Menu „LoadBahn“. Mit einer quasi XML-Format ist die Datei einfach lesbar und verarbeitbar auch ohne diese Programm. Ein Beispiel davon ist folgende:

<BahnPlan>

<BahnDesignPt Speed="0" id="0" time="0" >

<Vect x="177" y="-88" alpha="4.25357" />

</BahnDesignPt>

<BahnDesignPt Speed="10" id="1" time="96" >

<Vect x="-157" y="794" alpha="0.819867" />

</BahnDesignPt>

<BahnDesignPt Speed="30" id="2" time="140" >

<Vect x="1137" y="834" alpha="4.12831" />

</BahnDesignPt>

<BahnDesignPt Speed="20" id="3" time="250" >

<Vect x="705" y="-18" alpha="1.65679" />

</BahnDesignPt>

<BahnDesignPt Speed="0" id="4" time="300" >

<Vect x="11" y="564" alpha="5.16384" />

</BahnDesignPt>

</BahnPlan>

Exportieren eine Kommandoliste

Als Ergebnis kann die ausgerechnet Soll-Bahn in der Datei in Form einer Kommandoliste exportiert werden. Jedes Kommando endet mit 0d0a (Return). Zwei Typen von Kommando sind verwendet:

Lenkungskommando ($Lttttllll)

tttt: 4-stellige hexadezimale Zahl zeigt den Zeitstempel in Millisekunden

llll: 4-stellige Hex hexadezimale Zahl zwischen 0x1800 bis 0x2100 zeigt den Lenkungswert (rechts - links)

Vorschubskommando ($Vttttvvvv)

tttt: 4-stellige hexadezimale Zahl zeigt den Zeitstempel in Millisekunden

vvvv: 4-stellige Hex hexadezimale Zahl zeigt den Vorschubswert

Ein Beispiel davon ist folgende:

$V00000400

$L000032dc

$L00042d00

$V005e03e8

$L005e32dc

$L006032dc

$V00610c6a

$L00612d00

$L008a32dc

$L008c2d00

$V008b0bb8

Importieren und Zeichnung einer Ist-Bahn

Ein Klicken auf der Menu „Import“ führt zu dem Importieren eine Ist-Bahn. Nach dem Selektieren der richtigen Datei, wird sie auf dem Bildschirm gezeichnet. Der Startpunkt wird gleich wie den der Soll-Bahn gesetzt, wenn eine Soll-Bahn existiert. Sonst wird der Defaultwert (0,0,0) verwendet.

Die Datei hierbei besteht aus eine Reihe von Kommando $GttttRV, der endet natürlich auch mit 0d0a, und bedeutet folgende:

tttt: 4-stellige hexadezimale Zahl zeigt den Zeitstempel in Millisekunden

R: welche Rad mit L (linke Rad) oder R (rechte Rad)

V: Richtung mit V (nach vorne) oder H (nach hinten)

Die Berechnung der Ist-Bahn ist auch eine wichtige Algorithmus dieses Programm.

Festlegung der Parametern

Folgende Parameter können im Programm von Benutzer festgelegt werden:

Parameter	Beschreibung
MinR	Der feste Radius
PlusA	Beschleunigung des Fahrzeugs
NegA	Verlangsamung des Fahrzeugs
MaxSpeed	Maximale Geschwindigkeit
SpeedFact	Geschwindigkeitsfaktor
MinSpeedHold	Die Länge, das Fahrzeug mit der gewünscht Geschwindigkeit fahren muss

Wichtige Algorithmen

Berechnung der Soll-Bahn

Geometrischer Teil

Der geometrische Teil der Berechnung der Soll-Bahn ist in die Berechnungen jeder Bahn-Strecke verteilt. Wie oben schon erwähnt wird besteht eine Bahn-Strecke aus eine Gerade und zwei Borgen mit festem Radius. Dann ist jedes Borgen auf einem der zwei schon festgelegten Kandidatenkreise.

Zuerst muss aus je zwei Kandidatenkreise einer selektiert wird, d.h. einer von Startvektor und einer von Endvektor, und zwar mit folgender Regel:

Die beiden Kreise dürfen nicht miteinander überlappen.

Der Abstand zwischen den beiden Kreisen soll der kürzeste sein.

Nachdem man für jeden Vektor einen Kreis selektiert hat, ist die tangentiale Gerade von den beiden Kreisen zu berechnen. Nach folgender Methode:

Wenn beide Kreise linker Kreis bzw. rechter Kreis sind, ist die außen tangentiale Gerade zu berechnen.

Wenn ein Kreis linker Kreis und anderer rechter Kreis ist, ist die innern tangentiale Gerade zu berechnen.

Geschwindigkeitsteil

Nach der Ausführung des geometrischen Teils des Algorithmus, erhält man die gesamte Länge der Soll-Bahn, was für den Geschwindigkeitsteil des Algorithmus benötigt ist. Im Modell der Berechnung der Geschwindigkeit sind 3 Typen von Strecke verwendet, auf denen das Fahrzeug mit konstanter Geschwindigkeit fährt, mit konstanter Beschleunigung beschleunigt oder mit konstanter Verlangsamung gebremst wird.

Das allgemeine Modell ist wie folgende gezeichnet. Bei der Falle, dass die Anfangs- bzw. Endgeschwindigkeit gleich Null ist, ist t0 bzw. t4 auch gleich Null.

Da die Zeit schon festgelegt ist, ist der Abstand, den das Fahrzeug schaffen kann, nach oben und nach unten begrenzt.

Die obere Grenze des Abstands ist folgende:

Die untere Grenze des Abstands ist folgende:

Berechnung der Ist-Bahn

In die beiden Vorderräder der Fahrzeuge sind inkrementelle Wegemesssysteme eingebaut, die den abgefahrenen Weg der beiden Räder als Vielfache eine Weglänge step messen. Dabei steht wiederum ein wichtige Algorithmus, das aus dieser Schritteinformation die Ist-Bahn berechnet, d.h., jedem Zeitpunkt einen Vector (Position und Richtung) zuordnet.

Die Schritteinformation besteht aus einem Zeitstempel t, linkem Schritt l (1, 0, -1) und rechtem Schritt r (1, 0, -1), und bedeutet, dass das linke bzw. rechte Rad des Fahrzeugs auf Zeitpunkt t stehen beleibt, oder einen Schritt nach vorne oder hinten fährt, wobei darf jedes Mal sich nur eine Rad einen Schritt bewegt. D.h. für (l, r) sind nur 4 Kombinationen möglich: (0, 1), (0, -1), (1, 0), (-1, 0).

Da die Achselänge und die Schrittlänge schon bekannt sind, ist der Betrag der Richtungsänderung Ω konstant und gleich Schrittlänge / Achselänge. Kombinationen

(1, 0) und (0, -1) führen zu eine Zunahme der Richtung α um Ω, während (0, 1) und (-1, 0) zu eine Abnahme um Ω.

Struktur des Programms

Liste der Klassen

Dateiname	Klassename	Beschreibung
form1.h form1.cpp moc_form1.cpp	MainWindow Haupte Fenster, dient zur Benutzerschnittstelle. ViewerWidget Ein Bereich in MainWindow, wo die Bahnen gezeichnet werden. SpeedWidget Ein Bereich in MainWindow, wo die Geschwindigkeiten gezeichnet werden.
BahnDesign.h BahnDesign.cpp	BahnDesign	Die Klasse, die die Soll-Bahn verwaltet.
CoordTrans.h CoordTrans.cpp	CoordTrans	Die Klasse, die die Dienste „Zoom In“, „Zoom Out“ und „Move“ für Bahnen-Viewer liefert.
SpeedList.h SpeedList.cpp	SpeedList	Die Klasse, die eine Liste von Geschwindigkeit mit Zeitstempel behält.
CtlPointList.h CtlPointList.cpp	CtlPointList	Die Klasse, die eine Liste von Kommandos mit Zeitstempel behält.
Track.h Track.cpp	Track	Die Klasse, die die Ist-Bahn verwaltet, d.h. eine Liste von Positionen mit Zeitstempel behält.

9

wy

2004-03-10T12:36:00