Post on 05-Apr-2015
transcript
1
Schwärme – steering behaviors
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
2
Schwärme – steering behaviors
Tierreich – Schwärme, Schulen, Herden…
Wanderheuschrecken - 500 Mrd.
Dreistachelige Stichlinge - 500 Mrd.
Springböcke - 70.000
Monarchfalter - 50 – 100 Mio.
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
3
Schwärme – steering behaviors
Schwärme • regelbasiertes Verhalten in dezentralen homogenen Systemen
• Wechselwirkung vieler einzelner Denkprozesse können zur• Effizienzsteigerung des Gesamtsystems• Leistungverschlechterung des Gesamtsystems führen
• Untersuchungsansatz der Wissenschaft
‚Unter welchen Bedingungen führt Interaktion von Individuen zur Effizienzsteigerung bzw. Leistungsverschlechterung
des Gesamtsystems?‘
• Untersuchungsstrategie• Simulation des komplexen Verhaltens von Fisch- und Vogelschwärmen
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
4
Schwärme – steering behaviors
Schwärme – historischer Abriss
biologisch – bis weit ins 20. Jh. – schwieriges Problem- bis in die 30er Jahre – Annahme von Gedankenübertragung von Vögeln
1965 – These über Sphären - Bedürfnis eines Individduums in die Sphäre des anderen einzudringen- erklärt Schwarmzusammenhalt, jedoch keine komplexen Schwarmverhalten
1985 – Susan Amkraut & Micheal Girard „Eurhythmy“
- Animationssequenz eines Taubenschwarms
- anziehende Kraft – Zusammenhalt der Gruppe
- abstoßende Kraft – verhindert Zusammenstoß der Tiere
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
5
Schwärme – steering behaviors
Schwärme – historischer Abriss II
1987 – Computerwissenschaftler Craig Reynolds- Beobachtung von Amselschwärmen in der Mittagspause
- Suche nach einem Führungstier - erfolglos
Schlussfolgerung- Schwarmverhalten ist Überlagerung der Bewegung einzelner Tiere
- Einzeltiere folgen einfachen Regeln
Schwarm – Modell - Grundlage heutiger autonomer Robotersysteme
bis heute - Erweiterung, Verfeinerung des Schwarmmodells
- zahlreiche Verwendung in Film- und Spieleindustrie
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
6
Schwärme – steering behaviors
Schwarmmodell (nach Craig Reynolds)
• große Anzahl künstlicher Objekte (Boids) deren Bewegungsmuster Schwärmen ähneln
• Grundmodell basiert auf drei einfachen Regeln
Reaktionen eines Boids auf Position und Geschwindigkeit seiner Nachbarn
• Boids• einzelne simulierte Kreatur• Punkt-Masse – Objekte mit Position und Geschwindigkeit
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
7
Schwärme – steering behaviors
Schwarmmodell (nach Craig Reynolds) II
Separation (Kollisionvermeidung)
• Abstand zu anderen Individuen halten (Menschen in der Fußgängerzone)
• meist nur unmittelbares Umfeld
• Beachtung anderer in eigener Bewegungsbahn
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
8
Schwärme – steering behaviors
Schwarmmodell (nach Craig Reynolds) III
Alignment (Ausrichten)
• Versuch sich dem Verhalten einer Gruppe anzugleichen
• Angleichen des Richtungs-vektors an den Durchschnitts-richtungsvektor der Umgebung
• Nach Anpassung vollzieht die Gruppe Richtungsänderungen als Einheit
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
9
Schwärme – steering behaviors
Schwarmmodell (nach Craig Reynolds) IV
Cohesion (Zusammenhalt)
• zuständig für den zusam-menhalt einer Gruppe
• Zusteuerung auf die durschnittliche Position der Umgebung
• nur in Verbindung mit Separation, sonst steuern alle auf einen Punkt zu
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
10
Schwärme – steering behaviors
Schwarmmodell (nach Craig Reynolds) V
Flocking
• Verhaltensweise, die es Individuen erlaubt, sich einer Gruppe anzuschließen
• Kombination von separation, cohesion und alignment
• Gewichtung der Steuersignale beeinflusst Form des Schwarms
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
11
Schwärme – steering behaviors
Steering Behaviors• logische Weiterentwicklung des Boids-Modell
• zusätzliche Steuerungsverhalten • z.B. Regeln zum Hindernisausweichen• wieder ausschließlich Strategien basierend auf lokalen Informationen
• „Steering Behaviors“ – Craig Reynolds, 1999• Verhaltensweisen für die unterste Steuerungsebene koplexer autonomer
Systeme
• „Steering Behaviors“ – Robin Green, 2000• enstand als Teil der Entwicklung des Spiels „Dungeon Master 2“
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
12
Schwärme – steering behaviors
Steering Behaviors IIGrundlegende Steuerfertigkeiten eines einzelnen Individuums
• seek and flee• pursuit, evasion and offset pursuit• arrival• obstacle avoidance• path following
Steuerfertigkeiten eines Gruppenmitglieds• separation• cohesion• alignment• flocking• leader following
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
13
Schwärme – steering behaviors
Steering Behaviors IIa
seek and flee
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
14
Schwärme – steering behaviors
Steering Behaviors IIb
arrival
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
15
Schwärme – steering behaviors
Steering Behaviors IIc
obstacle avoidance
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
16
Schwärme – steering behaviors
Steering Behaviors IId
path following
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
17
Schwärme – steering behaviors
Steering Behaviors IIe
leader following
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
18
Schwärme – steering behaviors
Steering Behaviors IIf
queuing
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
19
Schwärme – steering behaviors
Simulation mit steering behaviors
action selectionZiele – Strategien – Planung
steeringPfadberechnung - Steuerung
locomotionAnimation - Bewegung
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
20
Schwärme – steering behaviors
action selection (‚mind‘)• vorgegebenes Regelwerk
• Gehirn des autonomen Fahrzeugs• Erzeugen des endgültigen Steuervektors
• einzelne Verhalten (‚Rolle der Sensoren‘)• Möglichkeit zur zweckdienlichen Analyse der Umwelt
• Erzeugen eines eigenen Steuervektors für das entsprechende Verhalten
• gewichtetes Zusammensetzen der Einzelvektoren• Verschiedenste Implemetierungen möglich
• z.B. simpleMind – priorityMind
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
21
Schwärme – steering behaviors
action Selection – simpleMind• einfachste Art der Implementierung
• Zuordnung: Verhalten Einfluss
• Beispiel
• Produkte aus Einzelvektoren und deren Einfluss
• Addition der Produkte zum Engültigen Steuervektor (evtl. Normierung)
• Separation oder ObstacleAvoidance oft höhere Priorität
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
Verhalten Einfluss
Separation 4
Cohesion 5
Alignment 3
22
Schwärme – steering behaviors
action Selection – priorityMind• Unterdrücken einzelner Verhalten möglich
• Einfluss (siehe simpleMind) entspricht prozentualem Anteil an der maximal einsetzbaren Kraft des Fahrzeugs
• priorityMind verteilt die maximal verwendbare Kraft an die Einzelverhalten
• Beispiel
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert
23
Schwärme – steering behaviors
Quellen - Links
„steering behaviors“
http://www.steeringbehaviors.de/
Craig Reynolds: „Boids“, „steering behaviors“
http://www.red3d.com/cwr/
Swarm - Distributed programming of autonomous robots
http://www.irobot.com/rd/p07_Swarm.asp
Roboter-Herden und simuliertes Schwarmverhalten
http://www.schwarmverhalten.de/
Aktorik, Lernen, Motion Tracking, diverse RoboterHK Kognitive Robotik IILehrstuhl für Künstliche Intelligenz, Institut für Informatik, HU-Berlin
Behrang Alavi, Ferry Bachmann, Frank Holfert