87

Technical Research |Establishing Model Methodology

86

Technical Research |Establishing Model Methodology

Reciprocal Velocity Obstacles

The RVO approach accounts for the reactive behavior of other agents by assuming that all agents make similar collision-avoidance reasonings within navigation. The diagrams above shows how the paths of two agents have opposite preferred velocities and how each agent calculates a combined velocity from the union of velocities from other agents.

From Jur Van Den Berg, Ming Lin, and Dinesh Manocha, “Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation,” 2008 IEEE International Conference on Robotics and Automation, (May 2008): 1928-1932, https://doi.org/10.1109/robot.2008.4543489.

2-Dimensional Cellular Automata

The Cellular Automata approach divides a space into a grid of cells. Rule 30 (introduced at the end of chapter 2.1) is an example of a 1-Dimensional Cellular Automata that utilizes simple rules to specify the next color of a cell based on its color and its neighbors. This concept can then be used to calculate position amongst the grid as a way to establish pathfinding.

From Hubert Klüpfel, “A Cellular automaton model for crowd movement and egress simulation,” (July 2003): 33-35, accessed December 26, 2019, https://www.researchgate.net/publication/29800160_A_Cellular_automaton_model_for_crowd_movement_and_egress_simulation.

Social Forces

The Social Forces approach utilizes “social forces” that are “a measure for the internal motivations of the individuals to perform certain actions.” The diagrams above shows how this can produce the formation of lanes as well as follow behaviors for agents with the same desired walking directions through narrow doors.

From Dirk Helbing and Péter Molnár, “Social Force Model for Pedestrian Dynamics,” Physical Review E 51, no. 5 (1995): 15-17, doi:10.1103/PhysRevE.51.4282.

Adaptive Roadmaps

The Adaptive Roadmaps approach utilizes Adaptive Elastic ROadmaps (AERO) to perform global path planning for each agent. The diagrams above shows how dynamic obsticles such as cars can affect paths leading to the resulting goal.

From Avneesh Sud et al., “Real-time Navigation of Independent Agents Using Adaptive Roadmaps,” ACM SIGGRAPH 2008, (2008): doi:10.1145/1401132.1401207.