# Position-Based Formation Control Scheme for Crowds Using Short Range Distance (SRD)
###### Abstract  
In crowd simulation, representing crowd behavior in complex dynamic environments is one of the biggest challenges. In this paper, we propose new algorithms to make crowds satisfy a given formation while they are moving towards a destination. For this, we apply the _Position Based Dynamics_ (PBD) framework, but introduce a new formation constraint based on a so-called _Short Range Destination_ (SRD). The SRD is a short-term goal to which an agent must move in formation. In addition, a grid structure that we use for neighbor search is also used for congestion control. Depending on the congestion value, the agents in the cell may break the formation and instead exhibit emergent behaviors such as collision avoidance, but must automatically restore the original formation once the situation is resolved. Smooth movement of agents is also achieved by adding special behaviors when they are moving along the path that the user specifies. From several experiments, we show that the proposed scheme is capable of exhibiting natural aggregate behavior of crowds in real time, even for a highly condensed environment. crowd simulation; position-based dynamics; crowd formation; collision avoidance +
Footnote †: journal:  
methods to assist agents in avoiding collisions with others by defining a personal space around each agent within which they can interact [6]. While this method can produce more realistic crowd representations, it may not be suitable for real-time simulation because of the high computational cost. In this paper, we apply position-based dynamics (PBD) for crowd simulation [7]. The PBD was originally developed for the simulation of solid objects; furthermore, it has been applied to simulate complicated objects such as fluids and articulated rigid bodies [8]. Unlike classical dynamic simulations, which use the relationship between force and acceleration and update the position through numerical integration, the PBD uses a constraint-based approach to compute the position directly. Because it directly computes the position, the method is considered a highly controllable, easy to implement, and stable physical simulation method [7]. When we apply the PBD to the crowd simulation problem, we have an advantage: natural aggregate group movements at a reasonable computational cost regardless of the size of the crowd, although it may not show sophisticated individual movements [4]. However, even though the PBD is good for aggregate behavior, it still does not consider formation control because it focuses on designing collision-avoidance models. In this research, we address the problem of crowd formation control here. Our hypothesis is that the PBD is also good for crowd formation control. Because the crowd formation should look like a specific shape, each agent should be placed at a particular position. This can be seen as enforcing position constraints for all agents, which can be naturally integrated within the current PBD framework. In some prior research for crowd formation control, the start and finish positions of each individual must be set to satisfy the given formation. The crowd formation transformation technique with a least-effort pair assignment method [1; 9] is one of the formation control research methods. In this study, the start and end positions of the crowd must be predefined for a particular formation, and the path between them must also be pre-calculated. Therefore, it is quite difficult to obtain collision-free paths when there are dynamically moving obstacles in the environment. Basically, the PBD uses constraints to control the movement of objects. For example, a distance constraint between two objects allows them to remain a certain distance apart during the simulation. When we apply it to the crowd formation problem, we can set the obstacle avoidance and formation control constraints simultaneously, allowing flexible control of crowd formation in environments with dynamic obstacles.