Von a nach b

**i_make_it** · 11.01.2016, 12:51

Zitat von HaWe

das mit dem "Niveau eines Unistudiums" halte ich für hahnbüchen, ich habe es als reiner Hobbybastler mit Lego gemacht. Odometrie braucht nur etwas Trigonometrie.

@ HaWe: Wenn Du meinen Text aufmerksam liest und Dir die Links ansiehst, stellst Du fest das ich nicht von Odometrie schreibe sondern von Kartierung und wie sich ein Roboter selbst darin verortet.
Also Occupancy Grid/Vektorkarten und SLAM.
Sowie Korrektur der Karten beim mehrfachen durchfahren des selben Raums um Messungenauigkeiten zu elliminieren.
Also Koppelnavigation, Kalmanfilter, Monte-Carlo-Lokalisierung etc.
Bei Kartierung mit Eigenbewegung, ortsfesten Hindernissen UND beweglichen Hindernissen (Menschen) erstellt man Zeitdiskrete Karten und integriert diese dann wieder um die ortsfesten Hindernisse zu filtern. Diese sind ja entscheident für die Routenplanung bei Ausweichmanövern.
Es bringt ja nichts dem Menschen auszuweichen und dann vor der Wand zu stehen. Also beim Ausweichmanöver die Ortsfesten Hindernisse mit berücksichtigen wenn z.B. der Mensch vorne links ist aber rechts dann nicht mehr genug Platz ist um hinter dem Menschen weiter zu kommen.
Dan greift nicht das einfache Ausweichen sondern die Routenplanung muß die Ausweichroute möglichst in Echtzeit berechnen. (Oder man bleibt stehen und wartet bis der Mensch weg ist)

Die Aufgabenstellung ist eigentlich genauso anspruchsvoll wie ein fahrerloses Auto das am Straßenverkehr teilnehmen soll.
Wenn das mit etwas Trigonometrie machbar ist, dann geh damit mal zum Patentamt bevor Mercedes, BMW und Co. das selbst anmelden. (Sorry der musste sein)

HaWe · 11.01.2016, 13:14

na, aber jetzt...

die Odometrie ist doch die Basis der eigenen Positionsbestimmung per Koppelnavigation, um sie dann anschließend in die eingespeicherte Karte einzuprojizieren.

D.h., man braucht eine Karte der Räume und den Startpunkt des Roboters, den Rest der Wegefindung macht der Roboter per Odometrie-Messungen (das ist ja die besagte Koppel-Navigation).
Nach dem Motto:
2m geradeaus,
dann 30° nach rechts,
dann 4 meter geradeaus,
dann 90° links,
dann 1m geradeaus
- dann...: Sie haben das Ziel erreicht!

So funktioniert das, wo ist das Problem?

Selbst dafür wären jetzt Karten noch nicht mal zwingend notwendig,
a-Bär: Odometrie ist ungenau, und so kann man die (bekannten) Wände in der eingepeicherten Karte bereits als Navigationshilfe mitverwenden, um die Odometrieposition zu berichtigen (wenn man sich in der Mitte des Gangs wähnt, aber plötzlich doch an der Wand anstösst). IMUs (Gyros) machen es NOCH etwas einfacher, aber es muss ja für das Projekt nicht gleich 100% perfekt sein.

Fürs Umfahren von Hindernissen gibt es übrigens auch den Bug- oder Bug2-Algorithmus, und ganz ohne feste Steuer-regeln noch den Astern (A*), aber das ist dann schon ein ganz klein wenig schwieriger (aber auch mit Lego bereits gelöst).

**i_make_it** · 11.01.2016, 13:46

@HaWe: Dein Ansatz funktioniert bei vollständig bekannten Karten.
Nicht ortsfeste Hindernisse (Menschen) bedeuten automatisch die Karten sind nicht vollständig bekannt.
Nimm deinen Ansatz mal beim Autofahren und stelle dann Fest das eine Tagesbaustelle deine 4 Meter gradeaus blockieren.
Schon fällt dein System in sich zusammen. (ein Tag warten bis das Hinderniss wieder weg ist)
Sobald bewegliche Hindernisse ins Spiel kommen wird das alles viel spannender (komplizierter)
Und das ausweichen vor Menschen ist halt Teil der Aufgabenstellung.
Eine einfache Pfadplanung in einer Umgebung nur mit ortsfesten Hindernissen ist ein Anfang, so habe ich in den 90ern auch mal angefangen und werde es mit meinem Großneffen auch wieder so machen. Aber es geht hier ja um eine konkrete Aufgabenstellung bei der die Randbedingungen festgelegt sind.

Wobei ich mir die Frage stelle ob die Lehrer die diese Aufgabe formuliert haben sich der Komplexität derselben bewust sind.

HaWe · 11.01.2016, 14:55

mein Ansatz funktioniert auch bei nicht störungsfrei befahrbaren Routen.
Denn wenn ein Hindernis auftaucht, gibt es 2 Möglichkeiten:
1. kurz stoppen und warten, ob es sich von alleine wieder wegbewegt
2. wenn es nach einer bestimmten Wartezeit nicht weg ist, dann im Bogen mit Abstand umfahren, bis man wieder ein Stück weiter vorn auf der geplanten Kurslinie gelandet ist.

Kein Lehrer wird erwarten, dass ein solches Schüler-Modell in allen erdenklichen Situationen 100% funktioniert, aber in ausgesuchten Standardsituationen gibt es einfache Lösungsstrategien.

Wären da nicht die 5 kg Zuladung, wäre es ein ideales Modell für Lego:
wegen Speicher, Encoder für Odometrie, ein oder mehrere Ultraschallsensoren, nötigenfalls Sensormultiplexer, parallel-läufigen Firmware-Sensor-Tasks (die automatisch Sensorzustände im Hintergrund auswerten, z.B. automatisch Encoderwerte weiterzählen, ähnlich wie Linux-Demons) sowie Multitaskingfähigkeit und damit der Möglichkeit für eine Subsumption-Programmarchitektur (Behaviour-events), um strukturiert auf Situationen reagieren zu können. Als Lego-NXT-Projekt für 500g Zuladung könnte ich da aus dem Stegreif jede Menge praktische Tipps geben, die extrem schnell umzusetzen sind (wenn die erlaubt sind).

Alles schon gemacht.

Mit einfacher AVR-Programmierung ist das aber eher nicht - oder nur mit ungeheurem Aufwand - zu machen.

**Rabenauge** · 11.01.2016, 14:56

Im Grunde kann das jedes Spielzeugauto, was ausreichend gross ist (bissel was muss rein und ne Ladeplattform brauchen wir auch), und wo man den passenden Motor (wie sie der Wild Thumper z.B. hat) einbauen kann. Ungefedert ist besser, die kann man auch "mal" gnadenlos überladen, dauerhaft muss es das ja nicht aushalten.

Kartierung würd ich lassen (das verlangt mit Sicherheit _kein_ Lehrer an irgendeiner Schule), und dann reicht nen Arduino völlig aus- oder eben der Pi, der aus undurchsichtigen Gründen scheinbar verwendet werden soll.
Beim Pi gehts natürlich mit Karte- mit nem Arduino ansatzweise noch (soo präzise muss die auch wieder nich sein, man kann alles übertreiben). Im Grunde genügt ne einfache, zweidimensionale Matrix, dynamisch muss die hier nicht sein.
Wenn ich da die Umgebung in halbmetergrosse Quadrate aufteile (genau genug um auch noch ne Tür zu finden), und die als "befahrbar oder nicht" markiere, geht das, denke ich.

Wir haben hier nen riesigen Vorteil: das Einsatzgebiet ist bekannt.
Somit kann man die Karte bereits im Vorfeld erzeugen, und einfach ablegen.
Gegebenenfalls auch mehrere mögliche, auf SD-Karte z.B. (auch das geht mitm Arduino locker ab).
Die Feinheiten erledigen wir dann mit Odometrie (die sich, z.B. an bekannten Punkten, wie Türen, wieder mal kalibrieren lässt) und entsprechenden Sensoren- nen paar US-Sensoren vorne und seitlich erledigen das.
Hier gibts echt keinen Grund für schwere Waffen...

Möglicher Aufbau: drei US-Sensoren in der Front (zweie genügen wohl auch, aber einer mehr schadet nicht), an jeder Seite noch einer. Hinten- nur wenn aktives Ausweichen wirklich gefordert wird, und somit Rangiermanöver anfallen können. Ansonsten brauchen wir den nicht, wenn Hindernisse erkannt werden, halten wir einfach an, oder versuchen, sie vorwärts zu umfahren.
Odometrie mittels Encoder am Motor (einfache Sache, da fertig zu kaufen), auch ne Mauskamera wäre denkbar- und präziser.
Kriegt man auch noch mit nem Arduino hin. Einzig der Bodenabstand muss mittels anderer Linse angepasst werden, aber dann funktioniert das hervorragend.
Die zu fahrende Strecke messen wir grob aus und übertragen sie als "Karte" in ne zweidimensionale Matrix. Soll das unbedingt im Vorfeld bereits passiert sein, dann eben auf ne SD-Karte, nen zusätzlichen EEPROM oder sonst irgend was.
Dort ist sogar ein ganzer Plan des Gebäudes möglich- wir brauchen es nur rudimentär!
Auflösung: Quadrate von 50x50cm, wenn genug Speicher da ist, kann man sie kleiner wählen, dann wirds präziser.

Bei unbekannten Hindernissen wird gestoppt, den (vorher bekannten) Weg können wir direkt in der Karte ablegen.
Falls man mehr will: einfach eine komplette Karte des Einsatzgebietes ablegen, die bekannte Hindernisse bereits enthält. Dann müssen, wenn ne unbekannte Strecke gefahren werden soll, nur Start-und Zielpunkt noch in die Karte eingefügt werden.
Das würde immer noch mit nem Arduino gehen: die "Karte" auf nen kleines Touchdisplay zeichnen, und dann wird nur Start-und Zielpunkt live eingegeben. Würde mit nem normalen Arduino wohl etwas eng, aber nen Mega2560 packt auch das noch.
Und: diese Variante wär für Zuschauer natürlich beeindruckend, das macht einfach was her....
Geht mitm Pi auch, für den gibts ja auch so handliche Touchscreens.
Die Wegberechnung kann man durchaus so machen, wie HAWE das bereits beschrieben hatte, da gibts einige, nicht allzu schwierige, Vorgehensweisen.
Auch erweiterbar ist es: "Fahre von A nach B, OHNE über C zu fahren" oder anderes...

Somit nen durchaus überschaubarer Aufwand, wobei ein Pi die Sache komplizierter macht, als es nötig wär...es ist ganz sicher mit nem Arduino Mega 2560 lösbar, und das dann schon recht komfortabel.
Passende Motortreiber gibts zu Hauf, ebenso US-Sensoren, Displays usw.

Ich persönlich würd versuchen, die Nutzlast runter zu handeln, einfach, weil die vieles an der Geschichte unnötig aufwendig macht: nur deshalb braucht man nen stärkeren Antrieb, nur deshalb dann auch ein grösseres Chassis (ohne den Quatsch könnt nen RP6 das nämlich locker erledigen!)...
Aber da fällt mir ne Alternative ein: an das Fahrzeug (kann dann nen recht einfaches Roboterchassis sein) einfach nen Anhänger dran.
Dann _geht_ das mit nem RP5 (ggf. bissel Ballast rein, damit er das zieht, weiss nicht, wieviel Grip die haben), und für die Nutzlast reicht irgendein Bruder-Spielzeuganhänger.
Zum rangieren besser was einachsiges.....

HaWe · 11.01.2016, 16:21

ps,
andere, flexiblere Umfahr-Methoden bieten Bug oder Bug2.

pps,
ja, ntl hat Rabenauge Recht, das habe ich vorrausgesetzt: die Karte ist ja bekannt und muss selbstverständlich vorher in einem groben Raster eingespeichert werden.

ppps
und ich weiß ntl, dass Rabenauge den Mega liebt, so wie ich den NXT - wegen seiner integrierten, nahezu idiotensicher-einfachen Programmierung (z.B. NXC) und (gerade noch ausreichenden) Anschlussmöglichkeiten für Encodermotoren und verschiedenste Sensoren, und ein Display und Sound und BT und ein Batteriefach und Steuer-Buttons sind auch schon eingebaut.

**i_make_it** · 11.01.2016, 16:47

Bei einer Raster Karte (occupancy Grid) und Türen mit 80cm Breite, würde ich ein Raster von maximal 40cm nehmen. bei einem 50cm Raster kann es passieren, das die Rastergrenze genau in die Türmitte fällt. dann enthalten beide Rasterflächen sowohl 40cm freien Raum und 10cm Wand. im ungünstigsten Fall kann es durch Kollissionen mit dem Türramen dazu kommen das dann die Tür aus der Karte eliminiert wird.
ich selbt habe mit dem Durchmesser meines damaligen Roboters (MIT Rugwarrior) angefangen und bin dann zu einem Raster mit dem Radius das Roboters als Zellengröße übergegangen.

Bei den US Sensoren kann man etwas sparen, wenn man 2 Stück schwenkbar macht. Beim RP5 habe ich zwei Stück die seitlich auf Servos sitzen, damit bekomme ich 360° hin bei 36 Messwerten. Bei Gradeausfahrt schwenken die immer nur um 60°, damit decke ich 120° ab.

Und ich habe ja schon ein paar mal geschrieben. Man kann anhalten und warten bis das bewegliche Hinderniss weg ist. Ist aber die Umfahrung des Hindernisses gefordert wird es knackig. Die Bug Algorithmen sind wunderbar für ortsfeste Hindernisse, Bei beweglichen Hindernissen bekommt man da schnell seinen Spaß (Wenn Mensch steht und sich dann ungünstig bewegt).

Deshalb habe ich ja auch gefragt, ob sich die Lehrer da bewusst sind was für eine Aufgabenstellung sie da formuliert haben.
Oder ob die Aufgabenstellung falsch verstanden wurde.
Sollte es z.B. nicht um bewegliche sondern um "nicht statische" Hindernisse gehen, wirds so einfach das man mit Bug arbeiten kann.
"nicht statische" Hindernisse sind unbewegliche Körper die bei jedem Durchlauf zufällig verteilt werden, sich aber wärend des Durchlaufs nicht bewegen.
Es kommt also auf die genaue Aufgabenstellung an welchen Aufwand man betreiben muß.
Wobei ich mir aber nicht vorstellen kann das eine Schule eine Aufgabe stellt die nicht benotet wird aber dem Schüler nicht abschätzbare Kosten aufbürdet.
Ich habe auf der Fachschule auch verschiedene Projekte bekommen die als mündliche Note bewertet wurden, aber da wurde entweder das Material gestellt oder die Aufgabe musste nicht in Hardware ausgeführt werden sondern nur berechnet, Materiallisten erstellt, Kosten und Zeiten berechnet werden und dann präsentiert werden.
Wer die Möglichkeit hatte, konnte wenn er wollte die Lösung auch in Hardware abgeben, aber dafür gab es dann keinen einzigen Punkt mehr.
Mich würde also auch brennend die Schule interessieren die sowas als Aufgabe stellt.

HaWe · 11.01.2016, 17:43

als Karten-Rasterbreite hat sich bewährt:
gut die Diagonale des Roboters, denn dann ist ein Feld gerade so groß, dass er darauf fahren und wenden kann.
Das ist aber nur für automatische Wege-Suche wichtig, denn auf Flächen kann er sich ja sowieso frei bewegen, zur aktuellen Positionsberchnung sogar im mm-Maßstab (float-Werte), die kriegt man ja eh über die Odometrie.

ps
wenn sich Personen oder Hindernisse bewegen, kann man warten, bis sie weg sind.
Wenn sie feststehen, kann man sie im Bogen oder per Bug(2) umfahren. Das ist kein Hexenwerk.

Sollte man beim Umfahren auf ein neues Hindernis stoßen, kann man es ebenfalls umfahren - gerade das macht der Bug2 automatisch, und man muss ja nicht gegen Gegner antreten, die einem bewusst durch hin- und her-dribbeln den Weg verstellen - es ist ja nur auf Schüler-Niveau.

**Rabenauge** · 11.01.2016, 18:55

Stimmt natürlich: man kann US-Sensoren auch schwenken. Sparen wird man dabei aber höchstens Anschlüsse (viel auch nich), selbst ein Billigservo ist nicht billiger zu haben als ein HC-SR 04 (da krieg ich fünfe von für nen Zehner). Und: schwenken braucht Zeit. Ich stelle mir gerade nen Schulkorridor voller neugieriger, gehässiger Kids vor, die es dem Fahrzeug so schwer wie möglich machen wollen. Da ist keine Zeit für sowas. Schon gar nicht, wenn die sich auch noch bewegen...
Allerdings: unter solchen Umständen ist die Aufgabe wohl so oder so _nicht_ zu bewältigen.
Einzelnen, "zufällig" daherkommenden Personen ausweichen dagegen schon: entweder stoppen bis die Bahn wieder frei ist oder eben irgendwie umfahren. Ich wäre hier für stoppen-Menschen sind nämlich unberechenbar. Es gibt kaum ne Möglichkeit, zu ermitteln, ob die entgegen kommende (oder vorausgehende, wie auch immer..)Person weiter laufen wird (hier kann man sie recht simpel umfahren) oder aber selbst ausweichen wird- dann wird es chaotisch.
Zumal wir hier von nem Roboter reden, der sicherlich seine Nutzlast nicht in Sekundenbruchteilen beschleunigen oder abbremsen können wird- damit könnte man Menschen wiederum austricksen. Das aber können wir wohl vergessen. Auch weil das im Fehlerfalle böse ausgehen kann.
Obendrein erfordert das auch recht hohe Geschwindigkeiten, wo wir wieder mit US-Sensoren nicht mehr auskämen, so viel sind 4m nicht...die Billigdinger schaffen die oft nicht mal.
Und über alles, was da helfen könnte (Wärmebild wäre ne recht gute Möglichkeit, sollte nen PI auch schaffen) reden wir nicht in Zusammenhang mit nem Schüler-Projekt.
Also fahren wir recht langsam, bleiben bei erkannten, ungeplanten Hindernissen erst mal stehen und warten ab, was passiert (sonst nämlich kann man den Roboter austricksen, indem man einfach vor ihm campiert): wenn sich das Hindernis ne Weile nicht bewegt (kann man ja schon noch detektieren mit US), umfahren wir es.
Muss ja auch nicht zwingend ein Schüler sein, sondern die Putzfrau kann ja mal ihren Eimer vergessen haben oder so, also können wir nicht ewig warten.
Man schafft es übrigens nicht, nen sich-bewegenden Menschen mittels Servo und US-Sensor im Auge zu behalten, auf kürzere Distanz (und allzu lang können wir nich, wenn wir noch durchkommen wollen) ist das zu langsam.

Das würde ich, wenn denn das Chassis einsatzbereit ist, mal austesten: wie schnell kann ich fahren, ausweichen, bremsen, und auf welche Entfernungen muss ich dann die Umgebung wirklich sondieren. Das dann mal mit normaler Schrittgeschwindigkeit kombinieren und dann die Sensoren so nutzen, dass der maximal nötige Bereich grade noch abgedeckt wird. Sonst bekommt man ganz schnell ein Zeitproblem.
Gegen rennende Kids oder nen hingeworfenen Ball gibts _so_ ohnehin kein Mittel, das sind Probleme, an denen sich Profis die Zähne aus beissen.
Allenfalls ne gute "Panzerung", mehr ist nicht. Ich denke aber, der Lehrer wird sich überreden lassen, das Ganze unter "Laborbedingungen" (einzelne, normal laufende Leute, keine Fussbälle usw.) anzuerkennen.
Sonst nämlich gerät das sehr schnell ins uferlose...