Denkanstoß gesucht: Labyrinth Roboter - Strecke merken

Ahoi!
Ich bin Schüler, 12. Jahrgang.Kenntnisse ins Sachen Informatik würde ich eingeschränkt nennen :D
Habe zwar Informatik LK,aber wirklich gut bin ich nicht (interessiert mich einfach nur und macht mir Spass,wenns klappt :D ).

Wir haben in unserem Seminarfach jetzt die Aufgabe bekommen,einen Roboter (RCX, die Legogeräte halt) zu basteln und programmieren,der selbstständig durch ein Labyrinth fährt und Daten sammelt,wodurch er beim 2. durchlauf das Labyrinth kennen sollte und somit auch schneller als beim ersten mal ist.
Es wird keine schleifen oder ähnliches geben,d.h. wodurch ,wenn man immer links fährt,ewig im Kreis fährt.Also brauch ich dafür keinen aufwendigen Algorithmus.
Der zweite Teil der Aufgabe macht mir allerdings noch zu schaffen.Inwiefern soll es möglich sein,die gefahrene Strecke zu speichern und eventuelle Umwege zu vermeiden? Hat jemand ne idee?

Im Notfall lass ich den Roboter beim ersten mal einfach mit gedrosselter Geschwindigkeit fahren und erhöhe sie beim zweiten mal :D Er würde jedenfalls schneller durchs Labyrinth kommen :P

Hallo,
das Projekt hört sich ja echt interesant an. Ich hab da mal profi-wetbewerbe gesehen...

Wenn Du beim ersten Durchlauf dich immer links hältst. kommt es bestimmt vor, dass du in einer Sackgasse landest und dadurch wieder zu einem Punkt kommst an dem Du schon mal warst. Das kannst Du Dir dann beim 2. Durchlauf sparen.
Du mußt allso immer Deine Position kennen und bei jeder Abzweigung merken.

Viel Spaß,
Drew

Nicht gezwungener Weise. Es wird ja ein Labyrinth mit "links markierung, rechts markierung" sein.Ergo wenn ich in eine Sackgasse komme,dreht der Roboter rechts,weil er denkt es sei eine rechtskurve,fährt ein stück,denkt es sei wieder ne rechtskurve,dreht sich und fährt dann weiter.Ergo fahre ich immer außen dranlang.
Oder hab ich da einen Denkfehler? ^^

Hi,
ich hab mal ein Ausschnitt aus einem Labyrinth angehängt. Alle Gänge, in denen Du zweimal warst kannst Du Dir das nächste mal saren, oder?

Drew

Jau,jetzt müsst ich nur noch wissen,wie ich das in ne Programmierung verpacke.Also ihr müsst mir keinen quelltext posten,aber son grober formulierter algorithmus wäre geil :D Hat jemand ne Idee?

Hi,

ich hab irgendwie das gefühl, dass dir dashier kaum jemand liefern wird, es iss ja nich gerade gar keine arbeit...

ich hoffe mal ihr programmiert die teile in C...

ich hab so die vermutung dass das einfachste sein wird, die gefahrene strecke beim ersten mal einfach komplett zu speichern (in variablen, denke gemessene zeit die er in ne richtung fährt

so könnte er quasi wenn er nach von dir genanntem prinzip den weg durch das labyrinth sucht also alles aufzeichnen...
ich hatte auch mal so ein lego system, wenn ich mich recht erinnere fährt der immer gleich schnell sollte also gut möglich sein zumindest ein maßstabsgetreues wegaufzeichnen sehr leicht über gefahrene zeit mit richtung möglich sein

das würd ich an deiner stelle aber schon wegen der masse an werten (ausser ihr habt n mini-labyrinth) in nem 2-dimensionalen (oder einfach 2 einzelnen) array speichern...

dabei muss man halt auch aufpassen, dass die richtung beachtet wird :D
und wenn man dann die dateien der arrays verwendet kann man den ort genau bestimmen, wo er war, bezogen auf den startpunkt

danach noch überprüfen ob man irgendwo werte hat die sich überschneiden und wenn ja dann kann man den zwischenteil per for-schleife rausschneiden...

naja, wird n komplexer code aber ich bin sicher du schaffst das :D

LG Pr0gm4n

Hi!
Es könnte eventuell ausreichen, wenn Du nur die Reihenfolge der 90° Abbiegungen speicherst. ALso rechts, links, rechts usw.
Wenn Du jetzt am Ende der Sackgasse bist, musst Du ja 180° drehen. Ab hier musst Du jetzt auf dem Rückweg die Abbiegungen mit den vorherigen vergleichen (natürlich umgekehrt) bis Du an eine Stelle kommst, wo sie nicht mehr übereinstimmen. Im gezeichneten Fall oben wäre das am grünen Kreis. Hier würdest Du merken, dass es einen anderen Weg (nämlich geradeaus) anstelle des gekommen Wegs (nämlich rechts) gibt. Jetzt könntest Du alle gleichen Abbiegungen im Array löschen (Hin und Rückweg) und den Weg bis dahin als "gesichert" annehmen, mit der neuen Abbiegung statt links, rechts.
Ob das möglich ist hängt auch ein bisschen von den verwendeten Sensorn ab, die wir nicht kennen, denn der Bot muss an jeder Stelle prüfen, ob er auch abbiegen könnte.
Gruß

Hi Alex,

du brauchst sicher die Wegstrecken zwischen den Drehungen.

folgendes ist Unsinn:

Zitat:

---

Es könnte eventuell ausreichen, wenn Du nur die Reihenfolge der 90° Abbiegungen speicherst.

---

Das gibt sofort falsche Ergebnisse, wenn du über eine Stelle mit Linksdrehung bei der Hinfahrt, bei der Rückfahrt gerade fährst, dann wird erst die nächste Biegung als vergleich herangezogen, was das ganze System durcheinander bringt.
Du brauchst auf der Rückfahrt aus der Sackgasse die Abstände, um bei Geradeausfahrt fest zu stellen, wo bei der Hinfahrt eine Biegung war. Diese Situation ist eine der möglichen Situationen, die den Beginn der Sackgasse anzeigen.

Eine Rat kann ich dir geben:
Bevor du zu programmieren beginnst, musst du ein brauchbares Verfahren haben, mit dem sich die Sackgassen vermeiden lassen. Denk dir was aus und teste es mit Papier und Bleistift auf gezeichneten Labyrinthen. Mach das so lange, bis es perfekt ist. Frage nötigenfalls hier. Wenn das Verfahren perfekt ist, dann gehe an die programmiertechnische Umsetzung. Da werden wieder Fragen auftauchen.

Wichtig ist, dass man Problemanalyse und Programmierung nicht zusammenwirft. Das gäbe nämlich zu viel Fragen auf einmal. Besser schön der Reihe nach.

grüsse,
Hannes

Zitat:

---

Zitat von Gock

...Ob das möglich ist hängt auch ein bisschen von den verwendeten Sensorn ab, die wir nicht kennen, denn der Bot muss an jeder Stelle prüfen, ob er auch abbiegen könnte.

---

Genaues und vollständiges Lesen der Threads erspart Zeit und vermeidet Missverständisse.
Natürlich funktioniert das nicht, wenn er nur einen Bumper vorne hat. Bei Robotern, die jederzeit prüfen können, ob sie rechts oder links abbiegen können, ist die beschriebene Vorgehensweise empfehlenswert.
Die Software muss natürlich immer auf die Hardware abgestimmt sein, sonst ist jede Diskussion überflüssig. Du solltest daher erklären, wie der Bot (vor allem Sensoren) aufgebaut ist oder werden soll.
Gruß

Hallo,
ich gehe davon aus, dass das Labyrinth sich in Quadrate aufteilen läßt. Die Länge eines Gangs ist also immer das Vielfache von der Breite. Das ist so weil es überall waagrechte und senkrechte Gänge gibt. (Ich gehe davonaus, dass alle Gänge gleich breit sind.)
Du kannst also Dein Labyrinth in Quadrate einteilen. Du kannst bei Deinen Bewegungen (Ich meine natürlich die Deines Roboters;-)) immer von Quadrat zu Quatrat fahren und beim abspeichern kannst Du Dir sehr viel Speicher sparen, wenn Du Dir merkst in welchem Quadrat Du warst.

Das mit den Sensoren ist natürlich noch eine offenen Frage. Woher weißt Du, wann Du wo abbiegen kannst?

Drew

Hallo Gock,

im Allgemeinen ist es nicht sinnvoll, zuerst die Sensorik zu planen und dann erst den Algo. Besser ist es, zu schauen, welche Algorithmen gibt es, was können sie und und was brauchen sie an Sensorik, Rechenleistung, Speicherplatz. Und dann ist zu entscheiden.

Wenn ein Algo Wegmessung braucht und ein anderer die Fähigkeit Abzweigungen nach rechts zu erkennen, dann schaut man am besten, was genau jeder Algo kann und wie Aufwändig die jeweilige Sensorik ist.

Wenn man sich zu früh auf eine bestimmte Sensorik festlegt, kann es sehr leicht sein, dass man sich unnötig einschränkt und es kann ebenso leicht sein, dass man unnötig teure Ausstattung einbaut.

Sehe gerade, dass Drew gepostet hat.

Das mit den Quadraten ist natürlich auch eine Möglichkeit, nur kennen wir die Gestaltung des Labyrints nicht. Da fehlt ein wenig Info über die genaue Aufgabenstellung. Auch diesen Algo könnte man ausarbeiten und wewerten.

grüsse,
Hannes

hi,
also wie schon paar mal gesagt, wären paar mehr infos net schlecht.
also sensoren an den rädern sind meiner meinung nach unerlässlich.
ein plan wär die hindernisse beim ersten durchlauf zu speichern, und dann einfach vor dem 2. durchlauf ne bahnplnung zu machen, z.b. a+ algo, sollte da ja funktionieren, wenn alles bekannt ist. brauchst halt ne gute positionsbestimmung.
mfg jeffrey

So,ich meld mich auch mal wieder^^

Wenn ich das recht herauslese bestätigt das eigentlich nur meine Meinung,dass die Aufgabe nahezu unlösbar unter den gegebenen Vorraussetzungen ist.
Wir haben nämlich maximal 2 Lichtsensoren und 2 Touch sensoren,mehr nicht.
Die 2 Lichtsensoren,da bin ich mir nach zig tests per bleistift in testlabyrinthen sicher^^, brauch ich um immer auf der Linie zu bleiben.Demnach kann ich also nicht entscheiden,ob es möglicherweise auch noch einen weg rechts oder geradeaus gab.

Oder hat jemand nen plan wie ich auf der Linie bleibe mit nur einem Sensor?

Bisher sieht der Plan in etwa so aus:

Beide Lichtsensoren recht dicht beieinander (Labyrinthbegrenzung ist 2 cm breit),sodass der eine beim optimalen Geradeausfahren schwarz,der andere weiß ist.
Hat mein Roboter einen leichten rechtsdrall,wird der 1. sensor weiß,das ist Zustand 2,bei dem er solange links schwenkt bis sensor 1 wieder schwarz ist.
Hat er leichten linksdrall kommt Zustand 3 zustande,bei dem Sensor 1 weiß ist,aber sensor 2,der ja dicht bei 1,aber sonst weiß ist,schwarz ist.Dann wird rechts geschwenkt bis Sensor 1 wieder schwarz ist.
Zustand 4 soll sein,dass wenn beide schwarz sind,er nach rechts drehen soll.

Das ist meiner Meinung nach auch der einzig logisch mögliche Algorithmus der mich einigermaßen sicher durchs labyrinth bringt.
Das Problem ist halt,wie schaffe ich es dann beim 2. mal schneller?^^

(Dabei ist anzumerken,dass die 2. Aufgabe,also das speichern und auswerten des Weges, keine starke gewichtung hat,sondern nur als kniffliger Bonus dienen soll.)

Mein Bot:

Code:

---


  o--o------|
  |        |
 ()|        |()
  |        |
  |        |
  |___  ___|
      ()

---

() = Räder (unteres ist schwenkbar)
o = Lichtsensoren

Hi,

wenn ich mich richtig erinnere gibts sogar beim Robotics Invention System ein Beispiel wie man Linienfolgen mit nur einem Sensor hinkriegt:

man fährt solange gradeaus wie der eine sensor schwarz zeigt, zeigt er weiss dreht man ca. 90° nach rechts (und schaut immer ob ned wieder schwarz iss) und wenn da nix war dann dreht man 180° nach links... dann hat er den strich wieder gefunden und das ganze geht von neuem los

glaube beim invention system war das da so dass man nur ner kreisbahn folgen musste --> man wusste dass die linie immer rechts von der aktuellen posi des lichtsensors ist wenn der weiss sieht :D

LG Pr0gm4n

hi,
für den rcx gibt´s doch drehzalsensoren, touchsensoren bruchst du ja nicht, also kannst du ja die beiden freien anschlüße für die drehzahl erfassung nutzen.
mfg jeffrey

Hallo Alex,

wie sieht das Labyrinth genau aus? Poste mal ein Bild. Anscheinend ist es aufgemalt, aber wie genau?

grüsse,
Hannes

Hm,zeichnen wird schwierig,ich versuchs zu erklären:

Randdicke: 2 cm, nur 90° Winkel.Es wird auch keine stellen geben,an denen man dauerhaft im kreis fährt,wenn man immer links fahren würde.Lücken in der Wand werden so

Code:

---

  |      |
  |      |
___|      |
          |
___      |
  |      |
  |      |

---

Hi,

also an jeffrey, wie kommst du darauf dass man die tastsensoren nicht braucht ?!?

ohne die tastsensoren findet er den weg ja nicht (oder täusch ich mich jetz)

also ich geh im moment davon aus, dass das einfach ein weißer untergrund iss auf dem die "wände" des labyrinths aufgebaut werden

das iss alles, man muss zur anderen seite und beim 2. mal soll er sich sackgassen gemerkt haben

LG Pr0gm4n

Ah,

danke jetzt wirds auch klarer. Darum fährst du an der Innenseite des linken Streifens entlang.

Um eine Sackgasse zu vermeiden, muss er das Ende und auch den Anfang der Sackgasse erkennen. Was hast du herausgefunden?

grüsse,
Hannes

Sackgassen wollte ich bisher so managen,dass sie einfach als 2 rechtskurven erkannt werden.Sollte eig kein problem machen. Nur zur späteren Speicherung und unterscheidung wäre es ganz gut sie als sackgasse auch zu erkennen.