Neue Wege finden, um für einen intelligenten Schwarm zusammenzuarbeiten

Neue Algorithmen zeigen, wie ein Schwarm einfacher Roboter dazu gebracht werden kann, als Ganzes zusammenzuarbeiten

Im Labor des Georgia Institute of Technology experimentieren Physiker mit Robotern, die aussehen, als wären sie in einem "All for 1 $" -Laden gekauft worden. Roboter können sich nicht im Weltraum bewegen oder miteinander kommunizieren. Im Grunde winken sie mit ihren kleinen Händen wie Käfer auf dem Rücken.

Wenn Sie jedoch viele dieser Geräte zusammenbauen, können Sie etwas aus dem Nichts herausholen: Sie drücken, schieben und greifen ineinander. Infolgedessen beginnen sie als Ganzes zu arbeiten.

Die Forscher untersuchen, wie solche Systeme so gesteuert werden können, dass sie ähnlich wie ein Bienenschwarm oder eine Ameisenkolonie funktionieren: Jedes Individuum handelt auf der Grundlage derselben Regeln, aber mehrere versammelte Individuen können ohne zentrale Kontrolle ein komplexes Verhalten zeigen.

„Unser Ansatz lautet wie folgt: Um herauszufinden, welches Rechenmodell am einfachsten ist, um diese komplexen Aufgaben zu erfüllen? Dana Randall , IT-Spezialistin bei Georgettech, einer der Projektleiter. "Wir suchen Eleganz und Einfachheit."

Randol als Programmierer nähert sich der Aufgabe aus der Sicht von Algorithmen: Was ist der einfachste Befehlssatz, auf dessen Grundlage einzelne Einheiten des Schwarms arbeiten können, basierend auf den mageren Daten, die sie sammeln können, was unweigerlich zu dem komplexen gemeinsamen Verhalten führen wird, das für Forscher notwendig ist? Im vergangenen November haben Randall und Kollegen einen Algorithmus veröffentlicht, um sicherzustellen, dass sich ein idealer Partikelschwarm kontrolliert bewegen kann.

Arbeiten Sie mit solchen Robotern, die Wissenschaftler "Smarticles" [Smarticles; smart - smart, Partikel - Partikel / ca. transl.] - Teil der Forschung auf dem Gebiet der Möglichkeit der Schaffung und des Nutzens selbstorganisierender Roboter. Andere ähnliche Beispiele sind tropfengroße Roboter , die an der Universität von Colorado entwickelt werden, Schwärme von " Kilobots " von der Harvard University und Svarmanoidie vom belgischen Labor. In vielen Fällen besteht die Idee darin, ein natürliches Phänomen nachzuahmen, beispielsweise eine hoch organisierte Bewegung einer dezentralen Ameisenkolonie oder eine unbewusste, selbstprogrammierende Anordnung von DNA-Molekülen.

"Wir wissen, was wir von einem ganzen Schwarm wollen, aber um es zu programmieren, müssen Sie herausfinden, was jeder Agent separat tun sollte", sagte Melvin Gauchi , ein Forscher in Harvard, der in der Gruppenrobotik arbeitet . "Der schwierigste Teil liegt zwischen diesen beiden Ebenen."


Dana Randall und Dan Goldman im Goldman Lab

Achten Sie auf die Führer

Daniel Goldman ist ein Physiker aus Georgetch, der das Smarticle-Experiment durchführt. Er interessiert sich hauptsächlich für die Physik aktiver körniger Materialien, die ihre Form ändern können. Zu seinen Folien für Konferenzen gehört ein Moment aus dem Film Spider-Man 3, der die Entstehung eines Superschurken Sandman demonstriert - einzelne Sandkörner, die in der Wüste verstreut sind, sammeln sich in Form eines Mannes. Smartphones sind Goldmans Methode, aktive körnige Materialien in einem Labor zu testen.

„Sie geben uns die Möglichkeit, mithilfe der Geometrie die Materialeigenschaften zu steuern. Wenn Sie Ihre Augen defokussieren, können Sie sich vorstellen, dass diese Reihe von Smartphones echtes Material ist “, sagte Goldman.

Smarticles haben kurze Gliedmaßen, die sie hin und her schwingen können. Sie reagieren auf Licht und Ton unterschiedlicher Frequenzen. Sie können so programmiert werden, dass sie die Geschwindigkeit von wehenden Gliedmaßen als Reaktion auf die Aktionen anderer Smartphones in unmittelbarer Nähe ändern.

Smartphones können verschiedene Aktionen ausführen: Zusammenstellen (Stapeln), Erweitern (Verteilen) und Verschieben. Diese Manöver können als Grundlage für die Ausführung komplexerer Funktionen dienen, aber selbst solche Aufgaben sind recht schwierig zu lösen, da Smartphones nicht verstehen, wie sie sich in Bezug auf die gesamte Gruppe befinden.

Um die Möglichkeiten und Schwierigkeiten zu verstehen, die mit der Programmierung komplexer Verhaltensweisen verbunden sind, die sich aus einfachen Teilen ergeben, sollte berücksichtigt werden, was jedem einzelnen Smarticle genau bekannt ist. Nicht so sehr. Er kann nicht sehen, sein Gedächtnis ist begrenzt und alles, was er über andere Smartphones weiß, mit denen er Aktionen koordinieren muss, erfährt er, wenn er auf seine unmittelbaren Nachbarn trifft.

"Stellen Sie sich einen Mann bei einem Rockkonzert mit geschlossenen Augen vor", sagte Joshua Daimad, ein Doktorand der Informatik der Arizona University, der an einem Smartphone-Projekt arbeitet.



Eine Strategie könnte darin bestehen, einen Anführer für die Verwaltung des Schwarms zu ernennen - dieser Ansatz ist jedoch anfällig. Wenn der Anführer leidet, wird der gesamte Schwarm versagen. Die andere besteht darin, jedem Roboter eine einzigartige Aufgabe im Schwarm zu geben, aber im großen Maßstab ist dieser Ansatz unpraktisch. "1000 Roboter einzeln zu programmieren ist fast unmöglich", sagte Jeff Dasek , Forscher am Harlin College of Engineering in Olin und ehemaliges Mitglied der Forschungsgruppe für selbstorganisierende Systeme in Harvard, die an Schwärmen von Unterwasserrobotern arbeitet . "Wenn jedoch jedes Mitglied der Gruppe nach denselben Regeln arbeitet, ändert sich Ihr Code nicht, unabhängig davon, ob Sie 10 Roboter, 1.000 oder 10.000 haben."

Der Schwarmalgorithmus hat zwei Eigenschaften. Erstens ist es verteilt, das heißt, es arbeitet separat auf jedem der Partikel des Systems (da jede Nomadenameise abhängig von den von der Umgebung empfangenen Informationen die einfachsten Aktionen ausführt). Zweitens enthält es ein Element des Zufalls. Dies bedeutet, dass wenn beispielsweise eine Nomadenameise die Anwesenheit von fünf anderen Ameisen in der Nähe wahrnimmt, sie sich mit einer Wahrscheinlichkeit von 20% nach links und mit einer Wahrscheinlichkeit von 80% nach rechts bewegt. Algorithmen unterscheiden sich zufällig von deterministischen Algorithmen, bei denen jede Stufe vollständig von den vorherigen bestimmt wird.

Zufälligkeit scheint für Algorithmen unnötig zu sein - schließlich möchten Sie bei der Implementierung einer Prozedur normalerweise ein bestimmtes Ergebnis erzielen. Zufälligkeit hat jedoch unerwartete Leistungsvorteile, wodurch zufällige Algorithmen für die Verwendung in Schwärmen gut geeignet sind.

Zufällige Garantien

Im Jahr 2015 diskutierten Goldman und Randall die Möglichkeit, Regeln zu finden, nach denen Smartphones als Ganzes zusammenarbeiten können. Randall erkannte, dass das Verhalten, das Goldman den Schwarm führen wollte, dem Verhalten idealisierter Partikelsysteme, die in der Informatik untersucht wurden, sehr ähnlich war.

"Und ich dachte sofort: Ich weiß genau, was zu tun ist", sagte Randall.

Für Randall ähnelte das Verhalten von Smartphones einem Phänomen, das von Informatikern in vielen anderen Kontexten modelliert wurde. Eines der bekanntesten Beispiele ist die Entstehung von getrennten Gebieten. In den späten 1960er Jahren wollte der Ökonom Thomas Schelling verstehen, wie die Trennung nach Gebieten erfolgt, wenn keine zentrale Kraft vorhanden ist, die die Menschen nach Hautfarbe sortiert. Er stellte sich eine hypothetische Person vor, die seine Nachbarn ansah und sich für einen Schritt entschied, basierend darauf, wie viele Nachbarn genau wie er aussahen. Wenn eine Person umzog, brachte Schelling sie an einen zufälligen Ort in der Siedlung, wo der algorithmische Prozess der Beobachtung und Entscheidungsfindung wiederholt wurde. Schelling stellte fest, dass nach seinen Regeln die Entstehung einer Segregation der Bewohner fast garantiert ist, auch wenn manche Menschen es vorziehen, in verschiedenen Gebieten zu leben.


William Savoy, Doktorand in Goldmans Labor

Randall erkannte, dass Smartphones in ihrem Schwarm Menschen im Schelling-Modell ähneln. In beiden Fällen müssen einzelne Einheiten Entscheidungen treffen, ohne ihre Position im globalen System zu kennen (sie wissen nur, was sie in unmittelbarer Nähe sehen). Im Schelling-Modell können Entscheidungen mit einem zufälligen Element getroffen werden. Wenn sich die Nachbarn von Ihnen unterscheiden, besteht die Möglichkeit, dass Sie sich bewegen, und es besteht die Möglichkeit, dass Sie bleiben.

Im Jahr 2016 veröffentlichten Randol und Kollegen eine Arbeit, in der idealisierte Partikel beschrieben wurden, die auf einem Gitter leben und je nach Anzahl der um sie herum beobachteten Partikel entscheiden, ob sie bleiben oder sich bewegen sollen. Die getroffenen Entscheidungen waren probabilistisch - jedes Mal, wenn die Partikel einen gewichteten Würfel zur Auswahl „warfen“. Randall et al. Haben gezeigt, dass Sie bei korrekter Zuordnung des Gewichtswürfels das Auftreten eines dichten Schwarms garantieren können (genau wie Schelling beweisen könnte, dass eine Segregation auftritt, wenn die Bewohner des Gebiets auf der richtigen Ebene für Vielfalt toleriert werden). Durch Anpassen des Algorithmus könnten sie auch sicherstellen, dass sich ein Partikelschwarm in einem ausgedehnten Zustand bewegt.

Die Zufälligkeit des Algorithmus hilft Partikeln im Schwarm zu vermeiden, dass sie in lokalen Robben stecken bleiben, wenn sich viele isolierte Untergruppen zusammen ansammeln, der gesamte Schwarm jedoch nicht verdichtet wird. Durch Zufälligkeit wird sichergestellt, dass einige Einheiten beim Erscheinen kleiner Siegel immer noch an einen anderen Ort ziehen und der Vorgang fortgesetzt wird, bis ein allgemeines Siegel erreicht ist. Um lokale Siegel zu vermeiden, ist ein wenig Zufälligkeit erforderlich. Für den Übergang von einem global komprimierten in einen erweiterten Zustand ist viel mehr erforderlich.

In die reale Welt

Zu beweisen, dass Teilchen in der theoretischen Welt durch Ausführen eines einfachen Algorithmus ein bestimmtes Verhalten in einem Schwarm erreichen können, ist eine Sache. Den Algorithmus in billigen, fehleranfälligen, echten Smartphones zu implementieren, Gliedmaßen in einer Box anzuklicken - ist völlig anders.

"Unsere theoretischen Kollegen wissen, wie sie diese Dinge programmieren sollen, aber wir stehen noch am Anfang der Reise und können nicht sagen, dass diese Pläne direkt übertragen wurden", sagte Goldman.

Ein Problem bestand darin, Smartphones zusammenzubringen. Als die Forscher Smartphones auf engstem Raum einschlossen, zuckte diese Gruppe zunächst einfach versehentlich. Aber einmal, als Physiker diese chaotische Bewegung beobachteten, starb eine Batterie in einem der Smartphones. Goldman und Kollegen bemerkten, dass sich der Schwarm plötzlich in Richtung einer festen Einheit bewegte. Die Forscher berichteten den Theoretikern über diesen unerwarteten Fund und griffen diesen Hinweis auf. Die Arbeit führte zur Schaffung einer neuen Version des Algorithmus, die es dem idealisierten Schwarm ermöglicht, sich immer in eine bestimmte Richtung zu bewegen.

Nach und nach rücken die Experimente am Computer und die physikalischen Experimente näher zusammen. Die Forscher hoffen, endlich theoretisch beweisen zu können, dass der grundlegende Algorithmus, der durch eine übliche Methode in einem großen Schwarm kleiner, billiger Roboter implementiert wird, garantiert zum gewünschten Schwarmverhalten führt.

"Wir möchten einen Zustand erreichen, in dem wir nicht nur ein Phänomen erkennen, wenn die Batterie leer ist", sagte Daimad. "Wir wollen, dass dies etwas von der Kategorie der absichtlichen Leistung ist."