Reply

Im Schwarm intelligenter

8. Juli 2021, 14:20 Uhr | Inka Krischke

Fortsetzung des Artikels von Teil 1

Überblick über bestehende Modelle

Im Laufe der Jahre wurden viele unterschiedliche Schwarmalgorithmen entwickelt. Die am häufigsten eingesetzten Modelle sind Artificial Bee Colony (ABC), Boids (Bird-oid object) und Ant Colony Optimization (ACO).

ABC – Artificial Bee Colony

ABC wurde 2005 entwickelt. Der Algorithmus ist vom Verhalten der Honigbiene bei der Suche nach Nahrungsquellen (Nektar) und dem anschließenden Informationsaustausch über diese Nahrungsquellen mit anderen Bienen im Bienenstock inspiriert. Der ABC-Algorithmus umfasst drei Phasen: die Employed Bee Phase, die Onlooker Bee Phase (Startphase) und die Scout Phase (Suchphase). Jede Arbeiterin (Employed Bee) wählt eine ihr bekannte Nahrungsquelle aus und bestimmt den nächstliegenden Ort. Dabei schätzt sie die dort vorhandene Nektarmenge ab und gibt die Information durch ihren Tanz im Bienenstock an die anderen Bienen weiter. Die Beobachterin (Onlooker Bee) beobachtet den Tanz der Arbeiterin, wählt auf der Grundlage dieser Information eine der Nahrungsquellen aus und begibt sich dorthin, um die vorhandene Nektarmenge zu sichten. Alte Nahrungsquellen werden durch die von Kundschafterinnen entdeckten neuen Nahrungsquellen ersetzt. Die beste Nahrungsquelle und die damit verbundene Position werden so konserviert.

Die Position einer Nahrungsquelle stellt das ‚Ziel‘ dar. Die in diesem Bereich gefundene Nektarmenge entspricht der ‚Qualität/Quantität‘, auch Fitness oder ‚Associated Solution‘ genannt. Die Anzahl der Arbeiterinnen entspricht somit der Anzahl der ‚Associated Solutions‘ innerhalb des Schwarms.

Ein anschauliches Beispiel für einen ABC-Algorithmus findet sich in der Landwirtschaft. Die Schwarmrobotik eignet sich insbesondere im Bereich Precision Farming, etwa bei großen Einsätzen in der Landwirtschaft, bei denen Drohnen für topografische und thermografische Zwecke eingesetzt werden.

In der Landwirtschaft liefert die Thermografie wichtige Informationen über die Umgebungsbedingungen, die auf andere Art und Weise schwer zu gewinnen sind. Wird eine Drohne mit einer Thermokamera ausgestattet, lässt sich die Temperatur im untersuchten Gebiet mit erstaunlicher Präzision messen. Dabei stehen verschiedene Temperaturwerte für unterschiedliche Merkmale der pflanzlichen Entwicklung. Der Einsatz von Drohnen im Precision Farming führt zu einer hohen Produkteffizienz und ermöglicht den Einsatz minimaler Ressourcen und damit Einsparungen.

Boids – Bird-oid Objects
Boids steht für eine Simulation künstlichen Lebens, die 1986 von Craig W. Reynolds entwickelt wurde. Es handelt sich dabei um einen Optimierungsalgorithmus, der vom natürlichen Verhalten von Schwarmvögeln inspiriert ist. Boids ist ein einfacher Algorithmus mit drei Regeln, die komplexes Verhalten in der Schwarmrobotik möglich machen: Zusammenhalt (Cohesion), Ausrichtung (Alignment) und Trennung (Separation).

Beim ACO-Algorithmus wird das Optimierungsproblem durch Suche des kürzesten Pfades in einem gewichteten Graphen gelöst.
Beim ACO-Algorithmus wird das Optimierungsproblem durch Suche des kürzesten Pfades in einem gewichteten Graphen gelöst.
© Johann Dréo

Zusammenhalt (Cohesion): Dieses Verhalten veranlasst Agenten dazu, die mittlere Position (den Massemittelpunkt) innerhalb der benachbarten Agenten aufzusuchen. Auf diese Weise bewegen sich die Boids immer innerhalb eines bestimmten Bereichs.

Ausrichtung (Alignment): Dieses Verhalten veranlasst einen bestimmten Agenten dazu, seine Position relativ zu weiteren Agenten in der Umgebung auszurichten und in dieselbe Richtung wie seine Nachbarn zu steuern. Genutzt wird eine Formel zur Definition der eigenen Geschwindigkeit aus den Geschwindigkeiten der Nachbarn in der Umgebung.

Eine künstliche Visualisierung der Pheromon-Intensität. Diese Art der Kommunikation ist eine der effektivsten in der Natur.
Eine künstliche Visualisierung der Pheromon-Intensität. Diese Art der Kommunikation ist eine der effektivsten in der Natur.
© A Multiple Pheromone Communication System for Swarm Robotics and Social Insects Research

Trennung (Separation): Dieses Verhalten veranlasst einen Agenten dazu, sich vom Nachbarn wegzubewegen, wenn der Abstand zwischen ihnen zu gering wird, um einen Zusammenstoß zu vermeiden. Dies garantiert zudem einen Mindestabstand zwischen allen Agenten.

Mit diesen einfachen Regeln ist es möglich, das Schwarmverhalten zu simulieren. Da sie allein jedoch oft nicht ausreichen, kann dieses Schwarmverhalten durch weitere, individuelle Regeln ergänzt werden, um eine komplexere oder sinnvollere Bewegung zu erreichen. Alle möglichen Formen allgemeinen Verhaltens können als Anziehung und Abstoßung von bestimmten Dingen modelliert werden, zum Beispiel ‚starker Wind‘, ‚Geschwindigkeitsbegrenzungen‘ oder ‚Hindernisvermeidung‘. Werden beispielsweise die drei Basis-Verhaltensweisen durch die Regel der Hindernisvermeidung ergänzt, wechselt der Schwarm seine Richtung, um auf dem Weg zum Zielpunkt Hindernisse zu vermeiden.

Einer der häufigsten Anwendungsfälle dieser Art von Algorithmen sind Suchaufgaben: Eine bestimmte Anzahl kleiner Drohnen mit Selbstlokalisierungs- und Messfunktionen übernimmt Suchmissionen in ländlichen, natürlichen oder komplexen Umgebungen, in denen der Zugang von Menschen oder großen Flugzeugen nur eingeschränkt möglich oder gefährlich ist. Die Eigenschaften der Schwarmintelligenz werden genutzt, um auf skalierbare Weise Probleme kooperativ zu lösen. Das Ausführen derselben Aufgabe durch eine einzelne Drohne würde mehr Zeit in Anspruch nehmen. Zudem müsste diese einzelne Drohne komplexer aufgebaut sein, was die Kosten erhöhen würde.

ACO – Ant Colony Optimization

Simulation einer Ameisenkolonie auf der Suche nach einer Nahrungsquelle anhand des ACO-Algorithmus.
Simulation einer Ameisenkolonie auf der Suche nach einer Nahrungsquelle anhand des ACO-Algorithmus.
© Reply

ACO ist eine probabilistische Technik, die Marco Dorigo 1992 entwickelt hat, um Computerprobleme nach dem Vorbild des Futtersuchverhaltens von Ameisen zu lösen. Das Modell basiert auf dem Ansatz, dass unabhängige Einheiten mit einfachen und unvorhersehbaren Verhaltensweisen miteinander kooperieren. Ziel jeder Ameise ist es, den optimalen Weg vom Nest zu einer oder mehreren Futterquelle(n) zu finden. Die Ameisen schwärmen willkürlich in unterschiedliche Richtungen aus und kehren zu ihrem Nest zurück, sobald sie eine Futterquelle gefunden haben. Auf ihrem Weg hinterlassen sie Pheromone auf dem Boden. Andere Ameisen folgen der ersten Ameise auf unterschiedlichen Wegen. Dieser Prozess wird solange wiederholt, bis nach einiger Zeit auf dem kürzesten Weg eine höhere Menge an Pheromonen zu finden ist als auf den anderen. Die Wahrscheinlichkeit steigt, dass dieser Weg eingeschlagen wird: Am Ende nehmen alle Ameisen den kürzesten Weg.

Pietro Ferrara
Pietro Ferrara ist Senior Consultant bei Concept Reply in Turin.
© Reply

Der ACO-Algorithmus bietet sich für komplexe Optimierungsprobleme wie das Traveling Salesman-Problem (TSP) oder das Vehicle Routing-Problem (VRP) an. So lässt sich die effizienteste Route zwischen zu besuchenden Punkten und Orten bestimmen. Der ACO-Algorithmus ist vor allem dann von Nutzen, wenn sich der Graph dynamisch verändert. Daher wurde dieser Algorithmus in der Vergangenheit bereits auf viele kombinatorische Optimierungsprobleme angewandt und trägt dazu bei, die jeweils optimale Lösung zu finden.

Dr. Christian Koetschan
Dr. Christian Koetschan ist Practice Lead Swarm Robotics bei Reply in München.
© Reply

Für die Nutzung von Schwarmrobotik sind die Art der Kommunikation, die Komplexität des Algorithmus im Hinblick auf die Berechnung und damit verbunden das Identifizieren möglicher Anwendungsfälle wichtig. Diese drei Punkte sind unterschiedlich komplex und stellen den Anwender vor diverse Herausforderungen. Die bisher genannten Anwendungsmöglichkeiten haben Beispielcharakter. Denn die aktuelle Forschung und Entwicklung zeigt, dass künftig viele weitere Anwendungsszenarien in Bereichen wie Verkehr – sowohl auf der Straße als auch in der Luft –, dem Überwachen und Kontrollieren großer Gebiete sowie dem Ausführen von Aufgaben in Gefahrenbereichen denkbar sind.


  1. Im Schwarm intelligenter
  2. Überblick über bestehende Modelle

Das könnte Sie auch interessieren

Verwandte Artikel

Reply AG

Robotik