# Position-Based Formation Control Scheme for Crowds Using Short Range Distance (SRD)
## 3 Proposed Algorithms
### Proposed Algorithms
#### 3.3.2 Degree of Congestion  
Many techniques have been proposed to optimize crowd simulations. Among them, discretizing the space is one of the effective methods to speed up neighbor search [20]. For example, a two-dimensional space can be partitioned into a grid structure [21], called the bin/spatial grid, and partitioned cells are indexed and used to find the neighbor. In our approach, we apply this technique for searching the neighbors, and also embed extra information in each cell for congestion control. Each cell maintains the list of agents when they are in the cell. This list is dynamically updated as the agents pass through the cell. When we need a list of neighbors for a particular agent, we can restrict the search area to the cell of the agent, which improves overall performance.  
In this paper, we also use the grid structure to control congestion. Since each cell has a list of agents inside, we can easily know how many of them belong to other groups. Mathematically, let us denote the congestion value as \(E\in\mathbb{N}\). Then, the value \(E_{m}\) of the cell \(m\) can be calculated using Equation (9):  
\[E_{k}=\begin{cases}\alpha\ \rightarrow\ (e_{k}=\varnothing)\\ \beta\ \rightarrow\ [(\forall a,b),\ (a\
eq b),\ e_{k}\in\{G_{a},\ G_{b}\}]\\ \gamma_{a}\ \rightarrow\ (e_{k}\in\exists!G_{b})\end{cases} \tag{9}\]  
where \(e_{k}\) is a grid cell, \(E_{k}\) is the congestion of that grid space, \(\gamma_{a}\) is the identifier of a group, and \(\alpha\) and \(\beta\) are constants.  
\(E_{k}\) takes the value \(a\) if there are no agents in the cell \(e_{k}\), takes \(\beta\) if there are more than two different groups in the cell, and takes \(\gamma_{a}\) if there is only one group of agents. Practically, we set \(\alpha\) to \(-2\) and \(\beta\) to \(-1\). For example, in Figure 12, \(E_{6}\) is \(\beta\) because different groups of agents share space \(e_{6}\). The space \(e_{3}\) and \(e_{7}\) is empty, so \(E_{3}\) and \(E_{7}\) are \(\alpha\).  
Agents would think that other agents belonging to different groups as moving obstacles. They must avoid these obstacles, if they are aware of the obstacles, using the congestion value in the neighbor detection step. However, because the agents are connected by the formation constraint, it is difficult for them to make a decision to break the formation constraint. Nevertheless, the formation constraint is the soft constraint that can be broken temporally for an emergency situation. In our work, we let the agent determine whether to break the formation constraint or not by checking the congestion value. If an agent decides to break the soft constraint, it stops to maintain the formation and then performs collision avoidance instead. When the agent finds that there are no dynamic obstacles in the neighboring space, as shown in \(e_{3}\) in Figure 12, the formation constraint is recovered, and they are trying to move to their SRDs. Note that this decision is quite local because it only works for agents in a particular cell. That is, the behavioral changes of the agents are limited to the cell in which the agents are located. This makes the aggregate behavior of whole crowds natural, even if agents are in a highly congested area. This is one of the advantages over other algorithms.  
Figure 12: Neighborhood detection of agents in a grid space. Space 6 is shared by different agents and they perceive each other as obstacles.  
In terms of dealing with agents in the same group, when an agent meets other agents in the same group, it will not take an action to avoid them if they are under a formation constraint. Even if they are not under the formation constraint, they would not avoid each other but perform the cohesive movement, which is the natural motion for real crowds. This cohesive movement results in collective avoidance between groups.