Aggregation and Foraging in Robotics - L2 PDF

Aggregation, foraging, flocking Prof. Tamara Petrović Prof. Đula Nađ Prof. Stjepan Bogdan Ana Milas, Marijana Peti, Marko Križmančić Introduction aggregation – assembling the swarm around the point of interest BEECLUST algor...

Aggregation, foraging, flocking Prof. Tamara Petrović Prof. Đula Nađ Prof. Stjepan Bogdan Ana Milas, Marijana Peti, Marko Križmančić Introduction aggregation – assembling the swarm around the point of interest BEECLUST algorithm foraging – seeking for nutrition (animals) in robots - searching for a target, shortest part, etc. previous example (Swarmanoid) comparison of stochastic strategies flocking Reynolds rules 2 BEECLUST 3 Introduction biological inspired algorithm – young honeybee behavior temperature patterns in honeybee hive (32-38) growth and development directly related to temperature for proper sensing, the temperature gradient should be stronger 1D single bee experiments show that bees can find the thermal sweet spot what happens when moving to 2D ? Thomas Schmickl, Heiko Hamann. BEECLUST: A Swarm Algorithm Derived from Honeybees: Derivation of the Algorithm, Analysis by Mathematical Models, and Implementation on a Robot 4 Swarm, 2011. Bio-Inspired Computing and Networking Introduction for 2D everything works for higher gradient lower gradient on larger area creates a problem for a bee Thomas Schmickl, Heiko Hamann. BEECLUST: A Swarm Algorithm Derived from Honeybees: Derivation of the Algorithm, Analysis by Mathematical Models, and Implementation on a Robot 5 Swarm, 2011. Bio-Inspired Computing and Networking Single bee behavior bee moving in a low temperature gradient how can we describe this? is there convergence in sight? 6 Bee swarm behavior bees in thermal gradient how can we describe this? what is aiding convergence? 7 Without gradient? what are the bees doing when the temperature drops? why is there assembly even with much lower gradient? 8 Social impact? do bees even feel the gradient? 9 Extracting algorithms from observation? a single bee seem to move randomly potentially it prefers the regions with high temperature it does not stay there and can not find the ideal spot additional single bee behaviors wall following, static bees seem to stay longer in cluster when temperature is higher bees seems are less likely to stop when encountering another bee 10 BEECLUST algorithm 1. bee moves randomly in correlated random walk can be reduce to random direction choosing 2. if bee hits wall there is a small probability of stopping else bee turns away (random direction) from wall and continues (in experiment P=0.05) 3. if bee meets another bee it stay with higher probability otherwise it continues to step 1. (in experiment P=0.4) 4. if the bee stopped, the bee waits depending on local temperature, the closer to the optimum, the longer it waits most important rule 5. after waiting time, the bee moves to step 1 11 BEECLUST algorithm flow chart when applied to robot Michael Bodi, Ronald Thenius , Martina Szopek , Thomas Schmickl & Karl Crailsheim (2012) Interaction of robot swarms using the honeybee-inspired control algorithm BEECLUST, Mathematical 12 and Computer Modelling of Dynamical System. BEECLUST algorithm on robot temperature replaced with luminance 13 Parameters that can be controlled wait time (for BEECLUST) has most impact on aggregation chosen as: nonlinear dependency (with max waiting time 66s and e in 0- 180) velocity often constant or uniform distribution when treated separately orientation has more impact on system performance different stochastic selection yield very different movements 14 Modeling swarm dynamics (exp.) shifting from micro to macro definition of N zones of arena (5 in BEECLUST paper) spatial separation robots can belong to two groups: free (F), aggregated (A) diffusion (δ) between zones aggregation rate (α) aggregation reduction (β) 15 Modeling swarm dynamics (exp.) ends up with a differential equation for dynamics of free/aggregated agents 16 Modeling swarm dynamics (exp.) the modeling concept is called Stock and flow compartments are stocks, and robots flow between them discretizes environment – loss of spatial detail other approaches shown in paper as well use of partial differential equations to allow continuous spatial modeling benefit of macroscopic modeling can estimate impact of parameters on overall swarm dynamics no need to run complete experiment with set 17 Stochastic search strategies 18 Introduction the goal for a robot is to find targets of interest in least time  covering least area stochastic vs. deterministic search use random movements like animals perform crosshatch, lawn mower, spiral patterns predators in nature use stochastic strategies rather than deterministic strategy depends on food density which is best? Hybrid? David Puljiz, Maja Varga, Stjepan Bogdan, Stochastic search strategies in 2D using agents with limited perception, IFAC Proceedings Volumes, Volume 45, Issue 22, 2012. 19 Random walk strategies a 2D robot motion is modeled simply as heading (ψ(k)) can be selected as: uniform distribution from [0,2π] Gaussian distribution w/o varying mean Cauchy distribution w/o varying peak location random walk with memory 20 Levy walk/flight in sense also a random walk, but defines step size together with heading efficient for covering larger areas heading is selected from a uniform distribution the step L is selected from a stable distribution Gauss, Cauchy and Levy count as stable can be approximated using two uniform distributions (impelemntation) 21 Comparison of random walk strategies single robot, but can be extrapolated to multiple 22 Comparison of random walk strategies Levy walks with Cauchy and Levy step selection 23 Comparison of random walk strategies Levy walks appear to cover most area in same search time 24 How does it compare agains deterministic patterns? comparing time to find the targets on smaller areas deterministic wins stochastics gain with increasing area why? 25 How does it compare agains deterministic patterns? comparing time to find the targets on smaller areas deterministic wins stochastics gain with increasing area why? farther tagets need longer time for deterministic stochastic searches far and close “equally” 26 Flocking Next lecture 27 Craig W. Reynolds. 1987. Flocks, herds and schools: A distributed behavioral model. SIGGRAPH Comput. Graph. 21, 4 (July 1987), 25–34. https://doi.org/10.1145/37402.37406 Reading assinment to better prepare and allow discussion of the Reynolds flocking rules a PDF will be uploaded to the materials section on FERWeb can be found for free online Craig W. Reynolds. 1987. Flocks, herds and schools: A distributed behavioral model. SIGGRAPH Comput. Graph. 21, 4 (July 1987), 25–34. https://doi.org/10.1145/37402.37406 28 Questions? 29