Wegfindung einer/mehrer Ameisen bei Hindernis
-
Hallo,
ich schreibe eine Ameisensimulation und möchte nun den nächsten Schritt wagen und Hindernisse in die Simulation einbauen.
Bis jetzt laufen sie zufällig rum. Wenn sie Futter finden, laufen sie zurück zum Nest.Hier eine Zeichnung, wie ich es meine:
http://abload.de/img/hindernisr1u7j.jpgJetzt möchte ich ihnen rechteckige Hindernisse in den Weg stellen.
Sie sollen nun das Hinderniss in Richtung des Nestes umschiffen, wenn sie auf dem Rückweg zum Nest sind.
So eine Ameise hat keinen großen Sichtradius. Sie fühlt mit Ihren Fühlern um sich herum, wenn Sie ein Hindernis trifft.Wie kann ich das realisieren? Die Ameise soll nachdem Sie einen freien "Schritt" gefunden hat den sie gehen kann, nicht im Kreis laufen oder immer hin und her?
Die Ameise soll sich quasi an dem Hinderniss "entlangtasten".
Es soll mehrere Rechtecke-Objekte (in einem Vektor) geben mit x,y, width und height.
Danke
-
Sie kann ganz ohne Weitsicht und absolute Koordinaten arbeiten, wenn sie bei Futtersuchen sich bei jedem Schritt merkt, wohin sich das Nest entfernt, und wenn sie beim Rückweg
http://de.wikipedia.org/wiki/Lösungsalgorithmen_für_Irrgärten#Pledge-Algorithmus
macht. Naja, leicht abgewandelt, als "zufällige" am Anfang (immer?) die richtige Zielrichtung die zum Nest nehmen. Oder als Zielrichtung erst aktuelisieren, wenn kein Kontakt mehr zum Hindernis? Weiß nicht, aber sowas auszutüftelt ist ja der Spaß am Ameisenprogrammieren.
-
Danke für den Hinweis mit dem Pledge Algorithmus, kannte ich noch nicht.
Werde ich mir morgen mal genauer zu Gemüte führen :).Ich bin beim googlen noch auf den A* Algorithmus gestoßen.
Wäre der auch was für mich? Der Vorteil ist da gibt es ein gutes Framework mit dem ich arbeiten könnte (MicroPather) und es soll sehr performant sein.
Nur weiß ich nicht, ob ich das mit den Rechteck-Objekten machen kann oder ne 2D int Matrix für die Hindernisse anlegen muss.
Danke und VG,
Furtano
-
Furtano schrieb:
Ich bin beim googlen noch auf den A* Algorithmus gestoßen.
Wäre der auch was für mich?Naja, dann wären es nicht mehr dumme Ameisen, sondern Elitesoldaten mit GPS-Navi oder erfahrene Taxifahrer.
Furtano schrieb:
Nur weiß ich nicht, ob ich das mit den Rechteck-Objekten machen kann oder ne 2D int Matrix für die Hindernisse anlegen muss.
Falls A* mit dem Framework Dir besser gefällt, dann ändere doch die Daten bei Bedarf. Kannst ja aus den Rechtecken eine Matrix bauen, wenn nötig. Dachte eh, daß die Rechtecke nicht als {links,oben,rechts,unten} vorliegen, sondern die Landkarte nur ein Bitmap-Image ist, wo ein Recheck reingemalt ist.
-
Ameisen verteilen beim Laufen Duftmarkierungen, an denen sie sich dann orientieren. Größere Intelligenz steckt da nicht dahinter, immer der Nase nach.
-
Bashar schrieb:
Ameisen verteilen beim Laufen Duftmarkierungen, an denen sie sich dann orientieren. Größere Intelligenz steckt da nicht dahinter, immer der Nase nach.
Das wäre supi nett zu programmieren!
Ich gehe mal davon aus, daß Ameisen zwei Sorten von Duftstoffen N und F (Nest und Futter) haben und daß die Welt eine große Matrix ist.
Tut eine Ameise einen Duftstoff wo ablegen, dann oxydiert er irgendwie am Sauerstoff pro Zeit chemisch ungefähr gleich und wird immer bitterer.
Eine Ameise, die Futter sucht, legt bei jedem Schritt auf ihr Feld mit einer geringen Wahrscheinlichkeit den Duftstoff N ab.
Eine Ameise, die ihr Nest sucht, legt bei jedem Schritt auf ihr Feld mit einer geringen Wahrscheinlichkeit den Duftstoff F ab.
Nest-Sucher gehen lieber auf Felder, deren N-Duftstoff noch nicht so weit oxydiert ist. Entsprechend Nahrungs-Sucher.
Wenn das nicht in einer Computersimulation fast schlagartig und sehr sehr schöne Ameisenstraßen baut, dann fresse ich einen Besen aus Schokolade.
Beweisen kann ich nix. Es gibt gar keinen Grund, daß die Ameisen sich zusammenraufen und eine Straße zusammenziehen zum Futterplatz. Oder?
-
Ich denke es ist noch einfacher. Es gibt nur einen Duftstoff, der von Ameisen gelegt wird wenn sie das Nest verlassen. (Alle Ameisen starten am Nest.) Wenn die Ameise wieder zurück zum Nest möchte, muss sie nur ihrer eigenen Duftspur folgen. Wenn sie mit gefundenem Futter zurückkehrt, legt sie auch beim zurückgehen wieder eine Duftspur. Ameisen folgen gerne stärkeren Duftspuren. So sollten sich eigentlich große "Hauptstraßen" mit kleinen Abzweigungen bilden, was Ameisen halt so machen. Klingt cool, vielleicht baue ich das mal mit bitmaps zusammen.
-
cooky451 schrieb:
Ich denke es ist noch einfacher.
Hab das Einfachere natürlich auch angedacht, immerhin wäre es viel weniger zu tippen. Kam aber nicht ohne zwei Stoffe alternde rum, und jetzt auch noch nicht.
Ich füchte, deine Ameise staut sich, wenn Futter leider weit genug weg ist, von selber an zufälligem Sammelpunkt, wo sich alle sammeln (Merkel) und findet das Futter nie.
Darum nahm ich zwei Stoffe, um nicht einem i-Hype zu verfallen.
-
Hmmm ich denke ich probier's mal aus, vielleicht hast du recht.
-
cooky451 schrieb:
Hmmm ich denke ich probier's mal aus, vielleicht hast du recht.
Ich suchte danach, wie eine Ameise nach hause kommt, nachdem sie Futter gefunden hat. Am besten, wenn sie weiß, wie weit das Nest weg ist. Am besten, sie hätte Entfernungsmarker nach Dyjkstra-Algo. Perfekt. Die anderen Ausschwärmer müssen nur ihren timestamp auf jedes Feld legen. NICHT ihren Abdruck, sondern ihre Uhrzeit. Bekloppt, so war chemie noch nie.
Das Ausaltern der Markierungen == timesstamp writing == irgewndwie bitter werden kam mir nur gerade in diesem Thread, irgedwie muss die Ameise ja nicht ganz zufällig hin- UND her- gehen. Das mit dem bloßen Anhäufen (bloßen Anhäufen!) der Lockstoffe hin und her war mir bisher zwar eingängig und glaubhaft "Ja, klingt logisch, da bauen die eine Straße, dann klappt das schon" (Weil es der Bio-Lehrer so sagte und wohl aug Profs dahinter, sonst hätte er es nicht so gelernt), aber meins von vorhin ist das erste Modell, was ich nachvollziehen kann, wo die Ameisen von selber eine Tendenz haben, mit krass wenig RAM von selber Straßen zu bauen. Bloßes Anhäufen und dumm hinlaufen kriege ich nicht hin zu glauben, so doof sind echte Ameisen nicht, das klappt nicht.
-
Hallo,
ihr folgt der falschen Spur.
Ameisen legen nur Pheromone, wenn sie Futter gefunden haben und auf dem Rückweg zum Nest sind. Nicht jedoch, wenn sie auf Futtersuche sind.
Zum Nest zurück finden sie z.B. anhand Landschaftsmarken, Sonnenstand oder elektromagnetischen Feld der Erde.
Sie wissen also, in welcher Richtung das Nest liegt.Also muss ich eine Art Pledge Algorithmus verwenden um Hindernisse zu überwinden.
Aber beim Pledge sucht er nur nach "irgendeinem" Ausgang. Ich suche jedoch nach einem Ausgang in der Richtung des Nestes. Wie kann man das machen?Danke und VG;
Furtano
-
volkard schrieb:
Tut eine Ameise einen Duftstoff wo ablegen, dann oxydiert er irgendwie am Sauerstoff pro Zeit chemisch ungefähr gleich und wird immer bitterer.
...
Nest-Sucher gehen lieber auf Felder, deren N-Duftstoff noch nicht so weit oxydiert ist.das klingt verkehrt, wenn N von futtersuchern abgegeben wird, ist N am aeltesten je naeher du dich dem nest begibst und damit mueste der N-Dufststoff eigentlich weiter oxidiert sein, esseiden man ist so nah dran, dass man die N-duftstoffe anderer findet. das alter der markierung wuerde also eher eine umgekehrte parabel darstellen, oder?
vielleicht sollte nicht das alter eine rolle spielen, sondern die dichte bei der abtastung. naeher am nest -> mehr N markeirungen. groessere futterquelle -> mehr andere armeisen -> mehr F markierungen.
dabei waere die abtastung eine art geigerzaehler pro ameise, wenn die rate zunimmt, ist sie auf dem richtigen weg, nimmt die rate ab, sollte sie vielleicht zurueck und eine andere richtung proben.
-
Furtano schrieb:
Ich suche jedoch nach einem Ausgang in der Richtung des Nestes.
wenn du 'fertig' bist mit einer pledge suche, bist du eigentlich so orientiert wie du es anfaenglich warst als du in den pledge reinkammst, wenn du also in die richtige richtung gehst, wird der algorithmus nichts an der richtung aendern (lediglich was an deinem offset
).
-
Bei den Labyrinthen die ich zum Pledge gefunden habe, ist der Ausgang aber oft in einer anderen Richtung und die Ameise steht dann in Richtung des Ausgangs, also in einer anderen da.
Bsp. Seite 2:
http://www.inf.fu-berlin.de/lehre/SS13/PS-ALGO/download/pledge_algorithm.pdf
-
Ist doch nur ne Frage wie du Ausgang definierst. So könnte alles Ausgang sein was eine Normale in Nestrichtung hat.
-
Furtano schrieb:
Bei den Labyrinthen die ich zum Pledge gefunden habe, ist der Ausgang aber oft in einer anderen Richtung und die Ameise steht dann in Richtung des Ausgangs, also in einer anderen da.
du willst doch garkeinen ausgang finden, dein ziel ist doch die umgehung eines hinternisses und das ist per definition dann geloest, wenn du weiter in deine richtung gehen kannst.
'ausgang' ist lediglich ein strech den dir dein gehirn spielt. der normale pledge algorithmus sollte keinen ausgang kennen, nur ein ziel und in deinem fall ist dein ziel "kann ich weitere in richtung x gehen"
-
Ok das verstehe ich, aber warum hört der Pledge hier auf wenn er die entgegengesetzte Ausgangslaufrichtung erreicht hat?
http://www.inf.fu-berlin.de/lehre/SS13/PS-ALGO/download/pledge_algorithm.pdf
Seite 2
-
Furtano schrieb:
Ok das verstehe ich, aber warum hört der Pledge hier auf wenn er die entgegengesetzte Ausgangslaufrichtung erreicht hat?
http://www.inf.fu-berlin.de/lehre/SS13/PS-ALGO/download/pledge_algorithm.pdf
Seite 2Tut er nicht, sondern er läuft brav noch außen rum, wurde nur nicht eingezeichnet, weil die Maus schon draußen war.
Ähm, wir haben bisher noch überhaupt nicht fprmuliert, was "außen" ist und woran die Maus das erkennt, und wie abgebrochen wird. Deine Ameisen brechen irgendwie an Nest ab mit der Suche, die Pledge-Mäuse irgendwie, wenn sie außen sind.
