Flocking Algorithm - Lecture Notes PDF

Aggregation, foraging, flocking Prof. Tamara Petrović Prof. Đula Nađ Prof. Stjepan Bogdan Ana Milas, Marijana Peti, Marko Križmančić Reading assignment anyone? to better prepare and allow discussion of the Reynolds flocking rules a...

Aggregation, foraging, flocking Prof. Tamara Petrović Prof. Đula Nađ Prof. Stjepan Bogdan Ana Milas, Marijana Peti, Marko Križmančić Reading assignment anyone? 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 how hard was it to read/understand? 2 What is flocking? aggregation with movement? motivation for flocking in nature improving survival, social activities upper limits of agents? think about fish, starlings 3 What is flocking? agents act only based on their own local information simulate perception to emulate local information similarity to particle systems geometry vs. point agent interactions guided by external state 4 About the paper based in computer graphics different aspects and terms compared to robotics actors agent (process, behavior, states) geometric flight kinematics unusual reference frames (e.g., Y is up) time context 1986. object-oriented programming becoming a dominant paradigm microscopic or macroscopic approach? “…one of the charming aspects of the work reported here is not knowing how a simulation is going to proceed…” 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 5 About the paper simple agent modelling (boid) maximum, minimum speed, maximum acceleration control input can be force (if mass is considered) or acceleration directly fully-actuated agents external physical aspects ignored gravity, buoyancy, effects due to embodiment good enough for a project with ground robots attitude (orientation) treated separately for 2D case only heading (yaw) is of importance 6 About the paper – Control perspective deals with low to midlevel control reactive behaviors think Roomba when decision making is added it will be centralized since agents migration urge is a small step towards this 7 Distributed reading assignment aggregate into your groups potentially as for project table each person in group will choose a color colors denote the expert group you will be part of due to balancing issues (green team has somewhat less work) experts will convene and study materials for their topic talk among each other to consolidate important parts of the material experts will go back to their respective groups each of the group members will in brief describe their topic and conclusions 8 Distributed reading assignment what rules/behaviors did you observe? which behaviors are complementary and which not? what is the preferred priority of those? why would we need to prioritize them? how are the boids seeing their world? how can we control the swarm movement? what is the best obstacle avoidance approach? which one seems to perform worse? 9 Agent model defined with mass position (x,y for 2D space) velocity (x’, y’ for 2D space) course (for 2D space) – simply atan2(y’,x’) keep last when undefined physical limitations maximum force and speed can use 2D kinematic model but keep mind of saturations divergence from real vehicles (no dynamics) allows instant changes no friction, damping 10 Agent vision flocking depends on limited, localized information avoid using the global knowledge neighborhood elements distance and FoV angle more complex recommendations forward weighted sensitivity (better depth perception) elliptical detection area 11 Basic agent behaviors collision avoidance (separation) velocity vector matching (alignment) flock centering (cohesion) 12 Separation repel agents so they do not collide each neighbors in the distance acts with a repulsive force in nature closer neighbors seem to impact more quadratic or cubic in nature rather than linear algorithm create forces in opposite directions e.g., substract position vectors weight forces based on distance sum into single separation force 13 Alignment ensure agents travel in same direction important component to achieve emergent flocking algorithm find average velocity vector create force/acceleration based on the difference between agent and average velocity vector 14 Cohesion attract agents to form a group border agent attracted inwards inside agents more or less neutral having local attraction is better allows flock bifurcation in obstacle scenarios follow leader or global central force do not allow bifurcation depends on the vision field of the animal murky water vs. clean air algorithm find center of mass by averaging sum of positions (local center) generate attraction force from agent to center of mass 15 Controlling the roaming migratory urge globally acting force towards a desired position acceleration should be bounded (non-dominant) static and dynamic targets can be done instantly but more natural is to ease in slowly closes birds start to follow the migratory urge spreads through the swarm with a delay 16 Avoiding obstacles obstacles generate force field simple implementation problems: constant influence (rather than perception based) – impact from passed obstacles problem with direct approach – reducing movement rather than steering away uniform lateral acceleration from center point (rather than object surface) touch sensor when close to obstacle a sensor is emulated good for surface following 17 Avoiding obstacles steer to avoid steer towards silhouette edge object projection on the vision plane of the agent silhouette enlarged by clearance size steer towards nearest point 18 Putting it all together problem of combining accelerations into a physical acceleration vector Obstacle Migration avoidance 19 Putting it all together – Combining accelerations using strength parameter potential for component canceling (indecision) prioritized acceleration allocation fulfil first the acceleration vectors that are highest priority if obstacle is close this acceleration is more important than e.g., cohesion expert systems empirical approach to prioritization 20 FoV impact on performance the more FoV the better – but lateral is preferred in nature flocking animals tend to have small binocular overlap but large lateral FoV E. Soria, F. Schiano and D. Floreano, "The Influence of Limited Visual Sensing on the Reynolds Flocking Algorithm," 2019 Third IEEE International Conference on Robotic Computing (IRC), 2019, pp. 138-145, doi: 10.1109/IRC.2019.00028. 21 FoV impact on performance order prefers lateral vision flock order (alignment) connectivity prefers large FoV graph connectivity E. Soria, F. Schiano and D. Floreano, "The Influence of Limited Visual Sensing on the Reynolds Flocking Algorithm," 2019 Third IEEE International Conference on Robotic Computing (IRC), 2019, pp. 138-145, doi: 10.1109/IRC.2019.00028. 22 Initial conditions different start behavior based on initial conditions position and velocity randomly assigned for testing use a random generator that is repeatable allows reproduction of the simulation run easier fine-tuning of parameters test for different initial conditions/adjust for tricky cases 23 Application of Reynolds rules modelling of fish, bird behavior modelling herd behavior (2D) case modelling traffic more advanced behavior like containment or path following modelling human crowd movement science applications flocking simulation to investigate natural behaviors on different stimuli 24 Implementation consideration in nature the complexity is in constant time (O(1)) naïve computer implementation is O(n2) each agent looks at each agent to decide if it is within FoV problem with scaling distributing to one device/agent still gives linear complexity O(n) needs communication of data spatial organization approach complexity O(n) maintain a grid/quadtree of agent locations each agent accessing only agents in grid online implementation by Reynolds https://opensteer.sourceforge.net/ (keep in mind: 2004 last edit) 25 Online simulators https://eater.net/boids https://jumpoffboids.netlify.app/ https://www.harmendeweerd.nl/boids/ https://processing.org/examples/flocking.html 26 Alternate simple and advanced behaviors seek and flee vector from agent to/away from target pursuit and evade need predictor to estimate target movement linear predictor gives position in future and then you can use seek behaviour Reynolds, Craig. (2002). Steering Behaviors For Autonomous Characters. 27 Alternate simple and advanced behaviors offset pursuit compute target point offset from predicted future position and seek arrival use seek but control speed based on distance linear gives longer convergence, tanh is better Reynolds, Craig. (2002). Steering Behaviors For Autonomous Characters. 28 Advanced behaviours wander (can be used as explore/forage) random walk constrained to a sphere in front of the agent path following tube around the ideal path project the predicted position to path and calculate steering force Reynolds, Craig. (2002). Steering Behaviors For Autonomous Characters. 29 Advanced behaviours containment similar approach to path following flow field following used for directing the swarm Reynolds, Craig. (2002). Steering Behaviors For Autonomous Characters. 30 Other behaviours unaligned collision avoidance more natural avoidance when path crossed - people on square leader following interpose shadow arrival docking hide 31 Questions? 32 Online simulators for 2nd lecture https://natureofcode.com/book/chapter-6-autonomous-agents/ 33 Advanced behaviours pursuit need predictor to estimate target movement linear predictor gives position in future and then you can use seek behaviour multiply the vector with T T can be larger when further, smaller when closer (proportional with distance) evasion analog to pursuit, but flee is used for steering away compare with interception approaches in literature optimal vs suboptimal when looking at nature 34