Schwarm-Computing
Vorwort
Die Natur ist dem Menschen in vielen Bereichen ein Vorbild, sei es im Flugzeug- oder Autobau anhand der Stromlinienform von Vögeln oder Fischen.
Die Tragflächen der Flugzeuge wurden gewissermaßen ebenfalls von Vögeln abgekupfert, nämlich anhand der Flügelform.
Man sieht die Natur hat einiges zu bieten und wird für zukünftige Technologien immer wieder Anstoßpunkte bieten!
Ich beschreibe in der folgenden Ausarbeitung wie die Intelligenz von sozialen staatenbildenten Insekten wie Ameisen oder Bienen auf Probleme in unsere heutigen Zeit übertragen werden können.
Zuerst erkläre ich im Kapitel „Ameisenalgorithmus“ nach welchem Prinzip ein Ameisenstaat funktioniert, im zweiten Teil des Kapitels zeige ich dann auf wie man das Verhalten in einen Algorithmus übertragen kann, die wiederum im Kapitel „Roboterschwarm“ die Grundlagen der Informatik darstellen um daraus künstliche Schwarmintelligenz zu schaffen.
Einordung Themengebiet
Das Themengebiet Schwarmintelligenz lässt sich nur schwer eingrenzen. Der hier untersuchte Schwerpunkt liegt im Dreieck von Biologie, Mathematik und Informatik. Als Grundsäule der Schwarmintelligenz muss man die Natur als Vorbild untersuchen, bevor man natürliche Verhaltensweisen in künstliche Systeme übertragen werden können muss man diese verstanden und entschlüsselt haben, dafür legen Biologen den Grundstein. Darauf aufbauend können die Methoden der Natur verallgemeinert auf Modelle übertragen werden, das Handwerkszeug dafür liefert die Mathematik: Formeln beschreiben die Natur und bieten Parameter um das Verhalten zu justieren. Die Informatik bietet letztendlich die Möglichkeit, die Modelle in Form von Algorithmen und Programmen zum Laufen zu bringen.
Etwas außerhalb dieses Dreiecks, können die Anwendungsgebiete von Schwarmintelligenz gesehen werden. Alle umfasst der Grundgedanke der Bionik, Erfindungen der belebten Natur zu entschlüsseln und in innovativen Techniken umzusetzen [Wik07a]. Beispielsweise werden die Ergebnisse der Schwarmintelligenz direkt angewandt in Bereichen von künstlicher Intelligenz, Multiagentensystemen und Robotik. Außerdem lassen sich die Resultate auf Optimierungsprobleme übertragen. [vgl. MB07]
Ameisenalgorithmus
Vorbild Ameise:
Ameisenstraße auf dem direkten Weg zwischen Futter und Nest [EP07]
Ameisen finden fast immer einen direkten Weg zwischen Nest und Futterquelle. Doch wie stellen Ameisen dies an, da ein Grashalm schon ein unüberwindbares Hindernis darstellt und sie nicht von einer Königin gesteuert werden?
Ameisen wurden im Laufe der Evolution der Natur so angepasst, dass sie auch in großem Durcheinander ihre Existenz sichern. Bei Ameisen gibt es keinen zentralen Punkt, von dem aus alles gelenkt wird, dass führt zu einem hohen Maß an Selbstorganisation. Das bewirkt, dass der komplette Staat auch weiter funktioniert wenn einzelne Ameisen wegfallen.
Dies zeigt sich bei der Futtersuche, hier bedienen sich Ameisen einer raffinierten Methode und zwar haben alle Ameisen am Hinterleib, eine Drüse aus der sie einen chemischen Lockstoff Namens Pheromon ausstoßen.
Nachfolgende Ameisen orientieren sich dann an der Duftspur des Vorgängers, wobei sie dem Pheromon nicht automatisch folgen. Sondern lediglich mit einer höheren Wahrscheinlichkeit den stärker markierten Weg einschlagen. Durch dieses Prinzip bildet sich recht schnell eine Ameisenstraße auf dem kürzesten Weg zwischen Nest und Futterquelle.
Doch wie funktioniert dieses Prinzip?
Zur Verdeutlichung folgender Erklärungsversuch:
Nehmen wir an Ameisen suchen einen Weg zwischen dem Ameisenhaufen und der Futterquelle.
Es bestehen 2 Wegalternativen um ein Hindernis zu umgehen. Der längere Weg A ist doppelt so lang wie der kürzere Weg B.
Es starten immer 2 Ameisen pro Minute vom Ameisenhaufen.
Bei Beginn (Minute 0) starten 2 Ameisen, wobei diese noch keinen markierten Weg vorfinden, und das Hindernis nicht überblicken können nehmen wir deshalb an, dass die eine Ameise den längeren Weg einschlägt und die andere den kürzeren.
Nach einer halben Minute ist die Ameise, die den kürzeren Weg gewählt hat schon an der Futterquelle angekommen. Die andere Ameise hat hingegen erst die Hälfte des Weges A zurückgelegt.
Diese Ameise kommt erst nach einer Minute an der Futterquelle an, in dieser Zeit jedoch hat die erste Ameise schon wieder den Ameisenhaufen erreicht.
Während jetzt die nächsten beiden Ameisen das Nest verlassen, finden diese schon die Informationen ihrer Vorgänger vor.
Sie werden mit einer höheren Wahrscheinlichkeit den kürzeren Weg B wählen, da dieser schon mit 2 Pheromoneinheiten markiert ist, der längere Weg A hingegen nur mit einer.
Da die weiteren Ameisen eher Weg B einschlagen erhöht sich auch dessen Anziehungskraft, weil er mit immer mehr Pheromoneinheiten gekennzeichnet wird.
So bildet sich dann innerhalb kürzester Zeit eine Ameisenstraße auf dem kürzeren Weg B.
Ein kürzerer Weg kann deshalb gefunden werden, da dieser in einer Zeiteinheit öfters durchlaufen werden kann, als ein längerer Weg.
Diese Eigenschaft lockt nun in der nächsten Zeiteinheit, wieder ein paar Ameisen mehr auf den kürzeren Weg, seine Anziehungskraft wird dann langsam aber sicher immer stärker, bis am Ende fast alle Ameisen den kürzeren Weg benutzen.
Die Pheromonspur ist also eine Art kollektives Gedächtnis der Ameisenkolonie.
Wichtig dabei ist, dass die Ameisen nicht automatisch den stärker markierten Weg benutzen, sondern lediglich den stärker markierten Weg mit einer höheren Wahrscheinlichkeit auswählen. Sonst könnte es passieren, dass bei einer zufälligen Wegsuche ein schlechterer Weg nur deshalb benutzt wird da er stärker markiert ist.
Weichen aber Ameisen vom Weg ab, finden diese eventuell einen kürzeren/besseren Weg und machen ihre Artgenossen durch ihre Pheromonspur auf diesen Weg aufmerksam …
So entsteht fast immer auf dem kürzesten Weg die Ameisenstraße. [vgl. Ama07]
Übertragen des Prinzips auf einen Algorithmus
Travelling Salesman Problem mit Ant Colony Optimization [entnommen aus MB07]
Ant System (AS)
Um die Fähigkeit der Ameisen, einen kürzesten Weg zu konstruieren, in eine modellierte Welt zu übertragen, bietet sich statt der Suche nach Futter das Travelling Salesman Problem (TSP) an. Dabei geht es darum, die kürzeste Reise durch n Städte zu finden, ohne dabei eine Stadt mehrfach zu besuchen.
Das Problem ist abstrakt, einfach zu verstehen und wurde als klassisches Shortest-Path-Problem schon oft untersucht.
Unter mathematischer Betrachtung zeigt sich, dass n! mögliche Touren für den Reisenden existieren. Das Problem lässt sich ebenfalls darstellen als Graph (N,E) mit der Menge der Städte N und deren Verbindungen E. Der Graph muss nicht symmetrisch sein und die hier vorgestellte Lösung kann verallgemeinert werden für das Asymetric Travelling Salesman Problem (ASTP). Dass sich in der Praxis schon bei einer kleinen Anzahl von Städten nicht alle Touren und deren Längen berechnen lassen, liegt auf der Hand. Das TSP ist NP-äquivalent, und deshalb in annehmbarer Rechenzeit nicht optimal zulösen.
Das in [BDT99] beschriebene Ant System (AS) beruht auf der oben beschriebenen Futtersuche von Ameisen. Dabei werden Ameisen simuliert, die durch den Graphen reisen, wobei die Zeit diskretisiert wird. Das Ant System liefert eine Heuristik für die Lösung des TSP. Das Verhalten der Ameisen wird dabei durch die folgenden Formeln und Algorithmus 1 beschrieben.
Die Distanz zwischen zwei Städten i und j wird nach Formel 1 definiert als euklidischer Abstand
, der Kehrwert
stellt die Attraktivität für die Wahl eines Pfades dar. Das Pheromon befindet sich auf dem Weg zwischen zwei Städten i, j und wird als Variable
dargestellt. In
spiegelt sich der Lernprozess der Ameisen wieder, die Werte ändern sich bei jeder Iteration.
(1)
Zudem modelliert man eine Art Gedächtnis:
ist die Menge der Städte, die die Ameise k noch zu besuchen hat, wenn sie sich in Stadt i befindet. Im Ant System wird der Übergang einer Ameise von einer Stadt in die nächste als Wahrscheinlichkeit nach Formel 2 beschrieben.
(2)
Eine Ameise k wandert aus Stadt i in diejenige nächste Stadt j, deren Verbindung die höchste Wahrscheinlichkeit
hat. In die Formel gehen die Attraktivität
eines Pfades und das dorthin führende Pheromon ein. Über zwei Parameter α und β kann das Verhalten der Ameisen genauer justiert werden, beispielsweise ob sie eher explorativ neue Wege ausprobieren.
Formel 3 beschreibt, wie viel Pheromon eine Ameise einem Pfad hinzufügt. Wie der Algorithmus 1 zeigt, geschieht dies im Ant System erst, nachdem eine vollständige Tour konstruiert wurde, während Ameisen in der Natur den Weg nur während des Beschreitens markieren können. Die Größe des hinzugefügten Betrags
ist abhängig von der Länge
der Tour
, die die Ameise k beschritten hat. Der Parameter Q ist frei wählbar. Beste Ergebnisse zeigen sich jedoch, wenn sich Q in der Größenordnung der zu erwartenden Länge
befindet. Im Ant System konstruiert jede Ameise eine komplette Tour pro Zeiteinheit.
berechnet sich dann wie in Formel 3 angegeben. Gehört eine Kante ( i , j ) des Graphen dabei nicht zur gewählten Tour
der Ameise k, so wird dort auch kein Pheromon hinterlassen.
(3)
Im Übergang zwischen zwei Zeiteinheiten wird das Pheromon auf allen Kanten aktualisiert. Die Summe der Pheromone der einzelnen Ameisen
wird auf allen Pfaden hinzuaddiert. Zusätzlich wird in Formel 4 die natürliche Evaporation p der Pheromone durch eine einfache Multiplikation modelliert.
(4)
Da das hinzugefügte Pheromon von der Länge der Tour abhängt und die virtuellen Ameisen auf den Pfaden mit dem meisten Pheromon laufen, wird wie im biologischen Vorbild die kürzeste Tour konstruiert. Ein Problem des AS ist, dass es gegen lokale Optima konvergieren kann, anstatt nach einer globalen besten Lösung zu suchen.
Eine Erweiterung des AS wird im folgenden als Ant Colony System beschrieben.
Ant Colony System (ACS)
Das Ant Colony System (ACS) basiert auf dem Algorithmus und den Formeln des einfacheren AS, fügt jedoch Erweiterungen hinzu, um das Verhalten des Algorithmus zu optimieren. Zum einen ist die Übergangsregel für die Wahl der Stadt eine andere. Eine Ameise k wählt im ACS die nächste Stadt j nach Formel 5, wobei
ähnlich wie im AS mit der Wahrscheinlichkeit nach Funktion 6 bestimmt wird.
(5)
Dabei ist q eine über das Intervall [0,1] gleichverteilte Zufallsvariable und q0 stellt einen zusätzlichen Parameter dar (0≤q0 ≤1). Für q>q0 ist die Übergangsregel gleich der aus dem AS, für q ≤ q0 macht ACS Gebrauch von dem bisher gelernten Wissen über das Problem. ACS kann so besser eine gefundene Lösung weiter optimieren, statt neue mögliche Lösungen zu suchen.
(6)
Eine zweite Änderung macht ACS an der virtuellen Pheromonspur, die von den Ameisen gelegt wird. Im ACS darf nur die Ameise, die die beste Tour generiert hat, zum Schluss einer Iteration Duftstoffe ablegen. Das veranlasst die Ameisen in der nächsten Iteration des Algorithmus dazu, in der Nähe dieser Lösung zu suchen. Hinzu kommt jedoch, dass jede Ameise schon auf ihrer Reise die Konzentration des Pheromons auf den Kanten verändert. Entgegen dem natürlichen Vorbild vermindert sie jedoch
, statt es zu erhöhen. Das hat den Effekt, dass diese Pfade für andere Ameisen uninteressanter werden, wodurch sich die Touren mehr durchmischen und die Ameisen
quasi nicht hintereinander herlaufen. So wird die Wahrscheinlichkeit erhöht, dass eine Ameise eine bessere Tour findet als die bisher bekannte. Zusätzlich führt das ACS zum Gedächtnis der Ameisen noch eine Kandidatenliste ein. Ausgehend von einem Startpunkt i in einer Iteration enthält diese Liste eine Anzahl von c Städten, die dem Ausgangspunkt i gemäß der Distanz
am nächsten sind. Diese Kandidaten werden dann zuerst bereist.
Abbildung 1: Konstruktion kürzester Strecke mit ACS [BDT99]
Abbildung 1 zeigt ein aktives ACS. Die Dicke der Linien zeigt die Verteilung des Pheromons (links). Neben sehr stark markierten Kanten gibt es solche, die etwas weniger Konzentration vorweisen und solche, die kaum mit Duftstoffen behaftet wurden. Das Bild zeigt außerdem die im weiteren Verlauf gefundene beste Lösung (rechts). Die Pfade, die eine geringere Pheromonkonzentration aufweisen, können als alternative Routen angesehen werden. Diese werden vor allem dann relevant, wenn man von einem statischen TSP zu einem dynamischen Problem übergeht: Fügt man Knoten in den Graphen ein oder nimmt man welche heraus, so ist das ACS wie in [BDT99] beschrieben in der Lage, schnell eine neue optimale Lösung zu finden.
Ant Colony Optimization (ACO)
Die in den Abschnitten Ant System und Ant Colony System beschriebenen Algorithmen stellen Metaheuristiken für TSP dar. Weitere Optimierungen sind in [BDT99] beschrieben: Beispielsweise kann innerhalb der virtuellen Ameisenkolonie ein Ranking eingeführt werden, das von der Länge der gefundenen Strecken abhängt. Die Menge des abgesonderten Pheromons ist dann proportional zum Rang der Ameise zu bestimmen. Die vorgestellten Verfahren werden unter dem Begriff Ant Colony Optimization (ACO) zusammengefasst. ACO kann immer dann eingesetzt werden, wenn ein kürzester Weg durch einen Graphen gesucht wird. Auf diese abstrakte Sicht lassen sich neben TSP viele Probleme reduzieren, zumal die Distanzfunktion (vgl. Formel 1) frei definiert werden kann. Beispielsweise kann das Job Scheduling Problem mit ACO gelöst werden. Hierbei geht es darum, eine bestimmte Menge von Jobs auf eine vorgegebene Menge von Maschinen zu verteilen. […]
ACO wird für Optimierungsprobleme eingesetzt. Ein Vorteil liegt vor allem darin, dass das Problem dynamisch sein kann, sich der Graph und die Distanzen der Knoten also ändern dürfen. Wie verschiedene Experimente in [BDT99] gezeigt haben, liefert ACO bessere Ergebnisse als andere Verfahren. […]
Analog zu ACO versucht man auch das Verhalten von Bienen, die Nektar sammeln, zu modellieren und Optimierungsprobleme damit zu lösen.
Java - Applet
Für die Verdeutlichung des TSP habe ich freundlicher Weise ein Java-Applet zur Verfügung gestellt bekommen. Das Applet zeigt das Problem eines Fernreisenden, der eine Tour durch Europa machen muss und nicht zweimal die gleiche Stadt besuchen darf. Das Problem wird mit den im vorherigen Kapitel beschriebenen Algorithmen gelöst, wobei die virtuellen "Ameisen" genau wie die natürlichen Ameisen nicht immer die optimale Lösung finden. Die Lösungen sind aber stets ziemlich nahe am Optimum [vgl. Ama07].
[Applet] Hier geht's zum Applet!
weitere Anwendungsbeispiele:
Antnet:
Antnet ist ein auf Ameisenalgorithmen basierendes Routingkonzept für paketbasierende Netzwerke.
Das Netz besteht aus einer Menge von Knoten, jeder einzelne Knoten hat einen oder mehrere Nachbarknoten. Darin gibt es vorwärts und rückwärts laufende Ameisen. Eine vorwärts laufende Ameise startet an ihrem Quellknoten (Der jeweilige Quellknoten erzeugt die virtuellen Ameisen) und begibt sich zu ihrem Zielknoten. Dabei wird sie wie die anderen Daten auch ganz normal durchs Netz geroutet, steht in denselben Warteschlangen und benötigt die gleiche Zeit als normale Pakete. Unterwegs sammelt die virtuelle Ameise Informationen über den aktuellen Traffic, den sie in einem Stack speichert. Sie speichert auch an welchen Knoten sie vorbei kommt und wie lange sie zwischen zwei Knoten braucht, damit kann sie ihre Tour rekonstruieren.
Der Weg der Ameise von der Quelle zum Ziel wird durch Routingtabellen der Knoten bestimmt. Durch die Routingtabellen wissen die Router über welchen Nachbarn sie ein Paket am schnellsten zum Ziel schicken können.
Am Zielknoten erzeugt die vorwärts laufende Ameise eine rückwärts laufende Ameise, übergibt der neuen Ameise ihren Stack und stirbt dann.
Die rückwärts laufende Ameise benutzt nun den gleichen Weg der vorwärts laufenden Ameise und aktualisiert die Daten in den Routingtabellen.[Wik07b][MB07]
AntNet zeigt sich bezüglich Durchsatz und Delay besser als andere Algorithmen wie beispielsweise OSPF
[
Wik07c]
Logistik:
Zeit ist Geld, dieser Spruch triff vollkommen auf die Logistikunternehmen zu, denn diese müssen Ware innerhalb kürzester Zeit an Kunden ausliefern.
In diesem Sektor ist deshalb eine genaue Planung der Routen ein Zentraler Punkt, denn kürzere Routen sparen Zeit, Benzin und somit auch Geld bzw. durch kürzere Routen kann man mehr Güter innerhalb der gleichen Zeit ausliefern.
Und genau hier bringen Verfahren wie das ACO viele Vorteile mit sich. Laut [EP07] hat der Einsatz des Computerprogramms Antroute bei dem Lebensmittellogistiker Number 1 Logistics Group eine Verbesserung in Sachen Performance wie Kostenreduzierung oder Flottenoptimierung bewirkt.
Filme:
Auch Filme kann man mit Hilfe von Software, die unter dem Aspektpunkt von Schwarmintelligenz arbeiten, ziemlich verbessern. Das beste Beispiel hierfür ist die "Der Herr der Ringe™" Filmtrilogie.
In "Der Herr der Ringe™"; wurde ein Programm Namens "Massive" verwendet. Das Programm haben sie für die Trilogie angepasst.
Dieses Programm ermöglichte es die großen Schlachten in "Der Herr der Ringe™" dar zustellen. Das besondere daran ist das jede Figur, die auch als Agenten bezeichnet werden, eigene Verhaltensmuster aufweist, d.h. jede Person kann sehen, hören, sich in seiner Umgebung zurechtfinden und eigene Entscheidungen treffen. Sieht der Agent beispielsweise einen gegnerischen Agenten, dann bewegt er sich auf diesen zu und beginnt einen Kampf. Andernfalls läuft er immer weiter bis er auf einen Feind trifft. Im schlimmsten Fall findet er keinen Gegner, möglicherweise verlässt er dann das Schlachtfeld. Diese Funktion war von den Entwicklern so eigentlich nicht vorgesehen, bewirkte aber in dem Film "Die Zwei Türme™" das es auch flüchtende Soldaten, bei der Schlacht um Helms Klamm gab. Während des Kampfes kommunizieren die Agenten. Agent A sagt beispielsweise: "Ich greife dich oben an". Agent B antwortet dann: "Okay, dann wehre ich oben ab". Wenn Agent B aber nun nicht so schlau ist wie Agent A sagt er: "Okay, ich wehre unten ab", das Resultat daraus ist, dass er fällt. [HdR]
Die Fledermausschwärme in "Batman begins" wurden ebenfalls durch ein Programm erschaffen, dass die Fledermäuse intelligent wie echte Schwärme durch Schwarmintelligenz agieren ließ.
Roboterschwarm [vgl. SBo07]
Ich möchte in diesem Abschnitt, nun erklären wie ein Roboterschwarm funktionieren kann, was man dafür für Vorraussetzungen braucht und wie so ein Roboterscharm praktisch aussehen kann bzw. funktioniert.
Ich möchte dies anhand des „Swarm-bots project“erklären. Dieses Projekt, wurde von dem Programm "Future and Emerging Technologies" der Europäischen Gemeinschaft (IST-2000-31010) gefördert. Das Ziel des Projektes war es, neue Annäherungen an die Planung und Umsetzung von Selbst- Organisierenden und Selbst-Zusammenbauenden Werkzeugen(Robotern) zu untersuchen.
Das Projekt wurde am 31. März 2005 erfolgreich abgeschlossen.
Modell eines s-Bot’s [SBo07]
s-Bot:
Der s-Bot stellt einen völlig autonomen Roboter dar. Er ist dazu fähig grundlegende Aufgaben wie autonome Navigation, Vorstellung seines Umgebungsklimas, greifen von Gegenständen zu meistern.
Ein s-Bot ist auch in der Lage sich mit anderen s-Bots zu verständigen, oder zu ihnen eine Verbindung mit seinen Greifern aufzubauen, dadurch bildet er dann einen SWARM-Bot.
swarm-Bot [SBo07]
swarm-Bot:
Ein swarm-Bot kann verschiedene Forschungen durchführen, kann navigieren und kann Gegenstände transportieren.
Da in einem swarm-Bot mehrere s-Bots zu einem Ganzen werden, ist ein swarm-Bot zu Dingen fähig die ein einzelner s-Bot nicht bewältigen könnte, wie z.B. die Überquerung einer Schlucht, oder ähnlichem.
Kommunikation zwischen den Robotern:
Der Farbring dient zur Kommunikation [SBo07]
Jeder s-Bot besitzt einen Ring indem verschieden farbige LED’s ein RGB-Spektrum widerspiegeln. Jede Farbe besitzt verschiedene Anweisungen oder Informationen, die die anderen s-Bots, mit ihren Kameras wahrnehmen können.
Die s-Bots verständigen sich zusätzlich via Warnsignalen (Pieptöne) untereinander.
Die Roboter kommunizieren also Dezentral und müssen sich deshalb selbst organisieren, fast so wie Ameisen oder andere Insekten.
Man könnte die Kommunikation auch per WLAN oder andern Mitteln realisieren. Wie in [Wissen07] beschrieben würde die Kommunikation dann etwa so aussehen: Roboter A sendet eine codierte Zahl, Roboter 2 empfängt diese Zahl erhöht den Zahlenwert um eins und schickt diese wiederum weiter. So wird die Zahl immer größer umso weiter man sich von der Quelle (in diesem Fall Roboter 1) entfernt.
Andere Roboter können dieser virtuellen Pheromonspur nun anhand der aufsteigenden Zahlencodes zur Quelle folgen.
Was kann man mit einem swarm-Bot realisieren?
Mehrere s-Bots finden gemeinsam das Ziel [SBo07a]
Wenn man mehrere s-Bots einsetzt kann man mit ihnen z.B. ein Gegenstand finden und auch transportieren.
Es werden mehrere s-Bots wahllos um ein blaubeleuchtetes Nest herumplaziert. Ihre Aufgabe ist es nun das rotbeleuchtete Ziel zu finden, sich daran fest zumachen und das Ziel zum Nest zu bringen, keiner der Roboter kann aber das ganze Spielfeld überblicken, sie sehen alle nur was direkt um sie herum passiert.
Die Roboter werden zunächst einmal wahllos herumfahren, bis ein Roboter das Nest mit seiner Kamera ausmacht, er platziert sich am Nest und verändert sein Farbe in gelb. Die anderen Roboter die ihn jetzt sehen wissen er hat das Nest gefunden, und bilden nun eine Kette, indem sie sich in einem bestimmten Abstand voneinander entfernt aufstellen. Wenn die Kette das Ziel erreicht kuppelt sich ein freier Roboter an und passt seine Farbe der des Ziels an. Der Gegenstand wird nun entlang der Roboterlinie zurück zum Nest gezogen, wobei sich die freiwerdenden Roboter mit an das Ziel ankuppeln können.
Die Kette könnte man als das Pheromon der Ameisen interpretieren, an dem sie den schnellsten Weg zurück finden.
[ Film SBo07a]
Eine weitere Funktion eines swarm-Bots ist es z.B. das er einen Abgrund erkennen kann und deshalb rechtzeitig ausweicht. Dabei ist die Verbindung mehrerer s-Bots hilfreich, denn diese verhindert, dass ein s-Bot abstürzt
[ Film SBo07b]
Der swarm-Bot überquert eine Spalte [SBo07]
Durch die Eigenschaft aus mehreren s-Bots einen flexiblen swarm-Bot zu machen, der seine Form je nach Lage anpassen kann, bieten sich Möglichkeiten von denen ein einzelner s-Bot nur Träumen kann, wie beispielsweise eine Schlucht zu überqueren. [ Film SBo07c]
Einzelnd sind die s-Bots autonome Roboter, doch im Verbund zu einem swarm-Bot verhalten sie sich ähnlich wie die Tiere in einem Schwarm und zeigen ein intelligentes Schwarmverhalten, sie organisieren sich selbst, kommunizieren miteinander,…
Dadurch erlangen die Roboter Fähig- und Möglichkeiten, um Dinge zu meistern, die sie als Einzelner niemals bewältigt hätten. Beispielsweise das Überqueren einer Schlucht die größer ist als der Roboter, eine Stufe zu erklimmen die höher ist als der Roboter oder ein Gegenstand zu ziehen der schwerer ist als der Roboter.
Diese Robotersystem arbeiten ohne eine zentrale Steuerung (dezentral), und kommunizieren über einfache Signale.
Das wird alles durch speziell angepasste und weiterentwickelte Algorithmen realisiert. Die Algorithmen können andere s-Bots direkt durch Signale signalisieren etwas zu tun. Diese Signale führen dazu das in den Robotern bestimmte Verhaltensmuster ablaufen: z.B. beim Bau einer Treppe, wenn hier ein Roboter A neben einem anderen Roboter B und neben Roboter A steht kein weiterer Roboter, dann fordert Roboter A Roboter B auf: "Bitte greife mich und hebe mich an!". Roboter B folgt dieser Anweisung falls sich kein Roboter auf ihm befindet. Andernfalls verneint er die Anfrage. [vgl. MB07]
Laut [GH06] kann das Verfahren der kollektiven Intelligenz also Schwarmverhalten in 5-10 Jahren Marktreife erlangen!
Anwendungsbeispiele von Roboterschwärmen im Alltag:
Dass uns Roboterschwärme in naher Zukunft tatkräftig unterstützen werden, ist heutzutage nichts fiktionales mehr. Computerschwärme sollen einmal in vielen Bereichen unseres Lebens eingesetzt werden, meist in den Bereichen in welchen es gefährlich (z.B. Bergbau, Lawinenopfersuche,…) oder schmutzig (Putzkraft,…) ist.
Hier stelle ich ein paar Anwendungsbeispiele vor, die zum Teil schon in Planung sind oder erst in ferner Zukunft realisiert werden.
Die elektronische Krankenschwester:
Im Januar 2007 startete das Fraunhofer-Institut für Arbeitswirtschaft und Organisation IAO das Projekt IWARD, in dem Projekt geht es darum die dezentrale Intelligenz so zu verbessern, das man kleine Roboter in Krankenhäuser schicken kann, diese könnten dort dann beim Putzen oder bei auffinden von Personal helfen. [IAO07][iWARD07]
EU-MOP:
Das Flugzeug bringt die Roboter an die Unglücksstelle, dort suchen sie das Öl und bauen eine flexible Barriere auf [IPA07]
Jährlich gelangen bis zu 8,8 Millionen Tonnen Öl ins Meer. Dadurch wird unsere Natur übermäßig belastet. Leider kommen herkömmliche Ölbekämfungsmittel immer wieder an ihre Grenzen. Deshalb startete das Fraunhofer Institut für Produktionstechnik und Automatisierung IPA das Forschungsprojekt EU-MOP (Elimination Units for Maritime Oil Pollutions), durch dieses Projekt soll ein Ölbekämpfungssystem konzipiert werden das flexibel, robust und universell einsetzbar ist. Dies wird mit Hilfe eines Roboterschwarms erreicht, die Roboter werden aus einem Flugzeug direkt über dem Teppich abgeworfen. Sie orten dann selbstständig den Ölteppich und ordnen sich um ihn herum an. Durch ankoppeln der einzelnen Roboter aneinander entsteht eine Barriere, die verhindert dass der Ölteppich abdriftet. [BM04][IPA07]
Selbstständige Container:
Für die nähere Zukunft sind auch selbstständige „denkende“ Gegenstände vorstellbar. Etwa Container die mit Elektronik bestückt sind, sich dadurch selbst organisieren und eigenständig handeln können.
Sie könnten dann wie die Ameisen kollektiv den kürzesten Weg zu ihrem Bestimmungsort finden. Beispielsweise sagt dann Container 01 am Pier zu Transport-Roboter 02: "Bring mich zur Abfertigung ans Kai." [vgl. MF07]
Definitionen:
Schwarm:
Ein Schwarm ist ein Zusammenschluss mehrerer Einzelakture zu einem Verband, indem es keine Hierarchie/ Rangordnung und auch kein Leittier gibt. Die Einzelakture eines Schwarms bewegen sich koordiniert und organisieren sich selbst.
Kollektive Intelligenz/ Schwarmintelligenz:
Unter Schwarmintelligenz versteht man die scheinbare gemeinsame Intelligenz von sozialen Insekten (wie z.B. Ameisen).
Dabei bringen eine große Zahl kommunizierender Einzelakture eine Leistung hervor, welche die geistigen Fähigkeiten eines Einzelnen übersteigen [AS06]
Roboterschwarm:
Ein Roboterschwarm ist eine Gruppe mehrerer Roboter. Diese Roboter lösen gemeinsam verschiedene Probleme, helfen sich oder erfüllen andere Aufgaben.
Dabei kommunizieren sie auf die unterschiedlichste Art und Weise miteinander.
Ein Roboterschwarm ist demnach also der künstliche Verwandte eines Tierschwarms, denn er handelt nach einem ähnlichen Muster, wie z.B. der Schwarmintelligenz
Literatur:
[Ama07] |
Ameisenalgorithmus: Schwarm-Intelligenz wie Ameisen ihr Futter finden |
[AS06] |
Strässle Andrea: Wie die Natur. In FACTS 28/06 S. 46-49 http://www.antoptima.ch/admin/pdfrassegna3/Facts_28_06.pdf |
[BDT99] |
Bonabeau, Eric; Dorigo, Marco; Theraulaz, Guy: Swarm Intelligence: From Natural to Artificial Systems(Santa Fe Institute Studies in the Sciences of Complexity Proceedings). Oxford University Press, 1999 |
[BM04] |
Niesing Birgit: Gemeinsam schlau. In Fraunhofer Magazin 3.2004 S.54ff |
[EP07] |
Papini Emanuele; Optimieren um zu konkurrenzieren. |
[GH06] |
Honsel Gregor: Die Hype-Zyklen neuer Technologien. In Spiegel online (21.08.06) http://www.spiegel.de/netzwelt/tech/0,1518,443717,00.html |
[HdR] |
Der Herr der Ringe™: Die Zwei Türme™ Die Anhänge Teil 4 Die Schlacht um Mittelerde beginnt. |
[IAO07] |
Fraunhofer Gesellschaft: Presseinformation vom 31.01.07. Die elektronische Krankenschwester http://www.fraunhofer.de/fhg/press/pi/2007/01/Presseinformation31012007.jsp |
[IPA07] |
Fraunhofer Institut für Produktionstechnik und Automatisierung: Forschungsprojekt: |
[iWARD07] |
IWARD-Project: Projekt Website von IWARD. http://www.iward.eu/cms/ Version: 13.04.07 |
[MB07] |
Böhmer Matthias; Schwarmintelligenz – Von natürlichen zu künstlichen Systemen. Seminar Informationstechnik Feb. 07 |
[MF07] |
Flohr Manfred: Chip Report Intelligent im Schwarm. Ausgabe 02/2007 S.82ff |
[SBo07] |
Swarm-bots project homepage. http://www.swarm-bots.org. Version: März 07 |
[SBo07a] |
Swarm-bots project: http://www.swarm-bots.org/dllink.php?id=743&type=movies |
[SBo07b] |
Swarm-bots project: http://swarm-bots.org/dllink.php?id=643&type=movies |
[SBo07c] |
Swarm-bots project: http://swarm-bots.org/dllink.php?id=509&type=movies |
[Wik07a] |
Wikipedia: Bionik. http://de.wikipedia.org/wiki/Bionik Version 06.06.07 |
[Wik07b] |
Wikipedia: Antnet. http://de.wikipedia.org/wiki/Antnet Version 12.04.07 |
[Wik07c] |
Wikipedia: Open Shortest Path First. |
[Wissen07] |
wissenschaft.de News vom 19.05.05: Roboter im Rudel. |