Inhaltsverzeichnis:

"Smarticle" -Roboterschwärme Verwandeln Zufälliges Verhalten In Kollektive Intelligenz
"Smarticle" -Roboterschwärme Verwandeln Zufälliges Verhalten In Kollektive Intelligenz

Video: "Smarticle" -Roboterschwärme Verwandeln Zufälliges Verhalten In Kollektive Intelligenz

Отличия серверных жестких дисков от десктопных
Video: smarticle.ru База знаний интернет предпринимателя 2023, Februar
Anonim

Neue Algorithmen zeigen, wie sehr einfache Roboter dazu gebracht werden können, als Gruppe zusammenzuarbeiten.

Bild
Bild

Aus dem Quanta Magazine (Originalgeschichte finden Sie hier).

In einem Labor am Georgia Institute of Technology führen Physiker Experimente mit Robotern durch, die aussehen, als stammten sie aus dem Dollar-Laden. Die Roboter können sich nicht durch den Weltraum bewegen. Sie können nicht kommunizieren. Meistens flattern sie mit den kleinen Armen wie Käfer auf dem Rücken.

Aber setzen Sie viele dieser Objekte zusammen und Sie erhalten etwas aus dem Nichts: Sie schlagen sich gegenseitig, stupsen sich gegenseitig an und verwickeln sich miteinander. Und schließlich beginnen sie als Einheit zu arbeiten.

Die Forscher lernen, wie sie diese Systeme so steuern können, dass sie ähnlich wie Bienenschwärme oder Ameisenkolonien funktionieren: Jeder Einzelne reagiert auf die gleichen grundlegenden Anweisungen. Aber wenn der Schwarm zusammenkommt, können seine Mitglieder komplexe Verhaltensweisen ohne zentrale Richtung ausführen.

"Unsere gesamte Perspektive lautet: Was ist das einfachste Rechenmodell, mit dem diese komplizierten Aufgaben gelöst werden können?" sagte Dana Randall, Informatikerin bei Georgia Tech und eine der führenden Forscherinnen des Projekts. "Wir suchen Eleganz und Einfachheit."

Als Informatiker denkt Randall algorithmisch über das Problem nach: Was ist der grundlegendste Satz von Anweisungen, die einzelne Elemente in einem Schwarm ausführen können, basierend auf den mageren Daten, die sie sammeln können, was unweigerlich zu dem komplexen kollektiven Verhalten führen wird, das Forscher wünschen ? Im vergangenen November haben Randall und Kollegen einen Algorithmus veröffentlicht, der sicherstellt, dass sich ein idealisierter Partikelschwarm koordiniert bewegt.

Die Arbeit mit diesen Robotern, die als „Smarticles“bezeichnet werden, ist Teil eines breiteren Interesses an der Machbarkeit und Anwendung selbstorganisierender Roboter. Weitere Beispiele sind Roboter in Tröpfchengröße, die an der Universität von Colorado entwickelt werden, Kilobot-Schwärme an der Harvard University und Swarmanoide aus einem Pionierlabor in Belgien. In vielen dieser Fälle besteht die Idee darin, in der Natur vorkommende emergente Phänomene nachzuahmen, wie die regulierte Bewegung einer dezentralen Kolonie von Ameisen oder die unbewusste, selbstprogrammierende Anordnung von DNA-Molekülen.

"Wir wissen, was das Kollektiv tun soll, aber um es zu programmieren, müssen wir wissen, was jeder Agent auf individueller Ebene tun muss", sagte Melvin Gauci, ein Forscher bei Harvard, der an Schwarmrobotik arbeitet. "Zwischen diesen beiden Ebenen zu wechseln, ist eine große Herausforderung."

Hüten Sie sich vor Führern

Daniel Goldman ist Physiker an der Georgia Tech und leitet die Experimente mit Smarticles (ein Portmanteau von „Smart Active Particles“). Sein grundlegendes wissenschaftliches Interesse gilt der Physik aktiver körniger Materialien, die ihre eigene Form ändern können. In einem Dia-Deck, das er zu Konferenzen mitbringt, enthält er einen Clip aus Spider-Man 3, der die Geburt des Superschurken Sandman zeigt: Lose Sandkörner durch die Wüste und erstarren dann in die Form eines Mannes. Smarticles sind Goldmans Methode, um aktive körnige Materialien in einem Labor zu testen.

„Sie geben uns die Möglichkeit, mithilfe der Geometrie die Eigenschaften eines Materials zu steuern. Wenn Sie Ihre Augen verwischen, können Sie sich diese Sammlung von Smarticles als echtes Material vorstellen “, sagte Goldman.

Die Smarticles haben kurze Arme, wie die Zinken einer Heftklammer, die sie hin und her schwingen können. Sie reagieren auf Licht und Töne mit unterschiedlichen Frequenzen. Sie können auch so programmiert werden, dass sie die Geschwindigkeit anpassen, mit der sie ihre Arme als Reaktion auf die anderen Smarticles schwingen, denen sie in ihrer unmittelbaren Umgebung begegnen.

Es gibt einige grundlegende Manöver, die ein Schwarm von Smarticles ausführen soll: Kompression (Zusammenpacken), Expansion (Ausbreitung) und Fortbewegung. Diese Manöver könnten als Bausteine ​​für kompliziertere Leistungen dienen, aber selbst die grundlegendsten Funktionen wie die Komprimierung sind schwer zu konstruieren, wenn keiner der Smarticles eine Vorstellung davon hat, wo sie in Bezug auf die Gesamtgruppe positioniert sind.

Um die Chance und die Herausforderung zu verstehen, komplexes Verhalten aus einfachen Teilen zu konstruieren, sollte man bedenken, was ein einzelner Smarticle weiß. Und die Antwort lautet: nicht viel. Es kann nicht sehen, es hat ein begrenztes Gedächtnis und das einzige, was es über die anderen Smarticles weiß, mit denen es koordinieren soll, ist, was es lernen kann, wenn es auf seine unmittelbaren Nachbarn trifft.

"Stellen Sie sich eine Person bei einem Rockkonzert mit geschlossenen Augen vor", sagte Joshua Daymude, ein Doktorand der Informatik an der Arizona State University, der am Smarticles-Projekt arbeitet.

Eine Strategie wäre, einen Anführer zu ernennen, der den Schwarm orchestriert, aber dieser Ansatz ist anfällig für Störungen - wenn der Anführer fällt, fällt der gesamte Schwarm. Eine andere Möglichkeit besteht darin, jedem Roboter im Schwarm eine einzigartige Aufgabe zu geben. Dies ist jedoch in großem Maßstab unpraktisch. "Die individuelle Programmierung von 1.000 Robotern ist im Grunde genommen eine unmögliche Aufgabe", sagte Jeff Dusek, Forscher am Olin College of Engineering und ehemaliges Mitglied der Forschungsgruppe für selbstorganisierende Systeme in Harvard, wo er an Unterwasserroboterschwärmen arbeitete. Aber "wenn jeder Agent die gleichen Regeln befolgt, ist Ihr Code genau der gleiche, unabhängig davon, ob Sie 10 oder 1 000 oder 10 000 Agenten haben."

Ein Algorithmus zum Programmieren eines Schwarms hat zwei Eigenschaften. Erstens ist es verteilt, was bedeutet, dass es für jedes einzelne Partikel im System separat ausgeführt wird (die Art und Weise, wie jede Ameise der Armee dieselben einfachen Anweisungen ausführt, basierend auf dem, was sie über ihre lokale Umgebung wahrnimmt). Zweitens beinhaltet es Zufälligkeit. Das heißt, wenn eine Ameise der Armee beispielsweise fünf andere Ameisen in der Nähe erkennt, besteht möglicherweise eine Wahrscheinlichkeit von 20 Prozent, dass sie sich nach links und eine Wahrscheinlichkeit von 80 Prozent nach rechts bewegt. Randomisierte Algorithmen stehen im Gegensatz zu deterministischen Algorithmen, bei denen jeder Schritt vollständig durch das Vorhergehende bestimmt wird.

Zufälligkeit scheint in einem Algorithmus unerwünscht zu sein - schließlich möchten Sie bei der Implementierung eines Verfahrens normalerweise die Gewissheit über das Ergebnis. Zufälligkeit bringt aber auch einige überraschende Leistungsvorteile mit sich, die unter anderem randomisierte Algorithmen für die Anwendung auf Smarticle-Schwärme gut geeignet machen.

Zufällige Garantien

Im Jahr 2015 diskutierten Goldman und Randall über die Möglichkeit, Regeln zu finden, die Goldmans Smarticles dazu bringen würden, als Gruppe kohärent zu agieren. Randall erkannte, dass das Schwarmverhalten, nach dem Goldman suchte, dem Verhalten idealisierter Partikelsysteme ähnelte, die in der Informatik untersucht wurden.

"Ich dachte:" Ich weiß genau, was los ist ", sagte Randall.

Für Randall ähnelte das Verhalten der Smarticles neu auftretenden Phänomenen, die von Informatikern in vielen anderen Kontexten modelliert wurden. Eines der bekanntesten Beispiele ist die Bildung getrennter Stadtteile. In den späten 1960er Jahren wollte der Ökonom Thomas Schelling verstehen, wie sich die Segregation von Wohnungen auswirkt, wenn keine zentralisierte Macht vorhanden ist, die Menschen nach Hautfarbe in Stadtteile sortiert. Er stellte sich eine hypothetische Person vor, die seine Nachbarn ansah und sich entschied, anderswohin zu ziehen, basierend darauf, wie viele von ihnen wie er aussahen. Als die Person umzog, transportierte Schelling ihn zu einer zufälligen Stelle im Wohnungsgitter, wo er den algorithmischen Prozess wiederholte, seine Nachbarn zu beobachten und zu entscheiden, ob er bleiben oder gehen sollte. Schelling entdeckte, dass nach seinen Regeln die Trennung von Wohngebieten praktisch garantiert ist, selbst wenn Einzelpersonen es vorziehen, in verschiedenen Stadtteilen zu leben.

Randall erkannte, dass Smarticles in einem Schwarm Menschen im Schelling-Modell ähneln. In beiden Fällen müssen Einzelpersonen Entscheidungen treffen, ohne ihre globale Position zu kennen (sie wissen nur, was sie um sich herum sehen können). Und in Schellings Modell können die Entscheidungen mit einem Element der Zufälligkeit getroffen werden - wenn Ihre Nachbarn anders aussehen als Sie, besteht möglicherweise eine hohe Wahrscheinlichkeit, dass Sie sich bewegen, aber auch eine geringe Wahrscheinlichkeit, dass Sie sich dafür entscheiden, in Position zu bleiben.

Im Jahr 2016 veröffentlichten Randall und ihre Mitarbeiter ein Papier, in dem sie sich idealisierte Partikel vorstellten, die auf einem Gitter leben, und entschieden, ob sie sich bewegen oder bleiben sollen, basierend auf der Anzahl der anderen Partikel, die sie um sich herum beobachteten. Die Entscheidungsfindung war probabilistisch - Partikel "rollten" im Wesentlichen jedes Mal einen gewichteten Würfel, wenn sie eine Wahl treffen mussten. Randall und ihre Co-Autoren haben bewiesen, dass sie, wenn sie den Würfel richtig gewichtet haben, garantiert einen komprimierten Schwarm haben (auf die gleiche Weise hätte Schelling beweisen können, dass Segregation die richtige Toleranz für Individuen ist, wenn er die Toleranz des Einzelnen für Vielfalt auf das richtige Niveau setzt unvermeidlich). Durch Anpassen der Parameter im Algorithmus könnten sie auch garantieren, dass sich ein Partikelschwarm in einen erweiterten Zustand bewegt.

Die Zufälligkeit des Algorithmus hilft Partikeln in einem Schwarm, nicht in lokal komprimierten Zuständen hängen zu bleiben, in denen viele isolierte Untergruppen zusammengefasst sind, der Schwarm insgesamt jedoch nicht komprimiert wird. Die Zufälligkeit stellt sicher, dass Personen, die in kleinen komprimierten Gruppen landen, möglicherweise weiterhin an einen neuen Ort ziehen und den Prozess so lange am Leben halten, bis ein komprimierter Gesamtzustand erreicht ist. (Es ist nur eine kleine Zufälligkeit erforderlich, um Partikel aus lokal komprimierten Zuständen herauszustoßen - es ist viel mehr erforderlich, um sie aus einem global komprimierten Zustand herauszustoßen.)

In die Welt

Es ist eine Sache zu beweisen, dass Partikel in einer theoretischen Welt einen einfachen Algorithmus ausführen und bestimmte Schwarmverhalten erreichen können. Die Implementierung des Algorithmus in billigen, fehlerhaften, realen Smarticles, die in einer Box herumklirren, ist eine andere.

"Unsere theoretischen Mitarbeiter haben Möglichkeiten gefunden, diese Dinge zu programmieren, aber wir stehen erst am Anfang und können noch nicht sagen, dass diese Schemata direkt übertragen wurden", sagte Goldman.

Ein Problem bestand darin, die Smarticles dazu zu bringen, sich als Gruppe zu bewegen. Wenn die Forscher Smarticles auf engstem Raum packen würden, würde das Ensemble zunächst nur zufällig herumstolpern.

Aber eines Tages beobachteten die Physiker diese chaotische Bewegung, als die Batterie in einem der Smarticles starb. Goldman und seine Mitarbeiter bemerkten, dass sich der Schwarm plötzlich in Richtung der inaktiven Einheit bewegte. Die Forscher meldeten diesen versehentlichen Befund ihren Informatik-Mitarbeitern, die den Hinweis ergriffen hatten. Die Arbeit führte zur jüngsten Entwicklung des Algorithmus, der immer einen idealisierten Schwarm dazu bringt, sich in eine bestimmte Richtung zu bewegen.

Nach und nach rücken die Informatik-Experimente und die physikalischen näher zusammen. Die Forscher hoffen, irgendwann theoretisch beweisen zu können, dass ein grundlegender Algorithmus, der auf verteilte Weise in einer großen Sammlung kleiner, billiger Roboter implementiert ist, garantiert ein bestimmtes Schwarmverhalten erzeugt.

"Wir möchten zu einem Punkt gelangen, an dem die Batterien nicht leer sind und wir ein Phänomen gefunden haben", sagte Daymude. "Wir möchten, dass es absichtlicher ist."

Anmerkung des Herausgebers (23.04.18): Ben Rollins wurde fälschlicherweise das Schreiben dieser Geschichte zugeschrieben. Der Autor ist Kevin Hartnett.

Nachdruck mit freundlicher Genehmigung des Quanta Magazine, einer redaktionell unabhängigen Veröffentlichung der Simons Foundation, deren Aufgabe es ist, das Verständnis der Öffentlichkeit für die Wissenschaft zu verbessern, indem Forschungsentwicklungen und -trends in den Bereichen Mathematik sowie Physik und Biowissenschaften behandelt werden.

Beliebt nach Thema