# Position-Based Formation Control Scheme for Crowds Using Short Range Distance (SRD)
## 3 Proposed Algorithms  
### Overview  
The original PBD algorithm was first applied to crowd simulation by [PERSON] et al. [4]. Compared to other studies, this method has shown that it can avoid dynamic obstacles reliably and quickly, even in dense situations. However, because this crowd simulation focused on natural representations of agent collision avoidance, it did not consider the formation control problem. In this paper, we propose a new method that can handle collision avoidance and formation control. Figure 3 is an overview of our method, which expands the original crowd simulation using the PBD method. In this process, _Computing the degree of congestion_ and Determining behavior phases were added and Determining the velocity phase was modified for this purpose. Each step in Figure 3 is described below. 1. Velocity planning and blending: Given a planned velocity that leads the agent to the final destination, each agent blends the current velocity with the planned velocity together. Then, the future position is predicted from the blended velocity;  
Figure 3: A flowchart of the crowd formation control method expanded from the crowd simulation using PBD. Detecting neighborhoods: This step updates the local information. It includes the presence or absence of agents in neighboring spaces, the number of neighboring agents, and the number of agents belonging to other groups. Each agent can detect neighborhoods using this local information;
3. Computing the degree of congestion: This step uses the local information explored in the previous step. The degree of congestion calculated with the local information is then mapped onto the grid space;
4. Determining behavior: In this step, the soft constraints, such as the formation constraint, are enforced. After that, the agent determines whether to follow the soft constraints or not;
5. Stabilization: Since agents are rigid bodies, interpenetration is not allowed. In this step, hard constraints are enforced so that neighboring agents are repositioned to prevent them from being penetrated by each other;
6. Solving constraints: This is a step to solve the constraints. Constraints are set to control the distance between neighboring agents and avoid obstacles in the previous steps. At this stage, it predicts the future position after solving the constraints;
7. Determining the velocity: The velocity is derived from the difference between the predicted future position and the current position in the constraint-solving step. The speed limit of the agent is set in advance to increase stability. Furthermore, this method applies the steering behavior technique to prevent sudden changes in the velocity of agents when moving along the path [14]. Through these processes, the agent is moved by the final velocity. Algorithm 1 is a pseudocode representation of the flow chart above. ```
1:loop
2: plan Group Positions (\(P_{1},\ \ldots,\ P_{m}\))
3: update SRD (\(s_{1},\ \ldots,\ s_{n}\))
4:for all agents \(i\)do
5:\(v_{i}\ \leftarrow\ v_{i}+\Delta tw_{i}f_{ext}(p_{i})\)
6:\(p_{i}^{*}\ \leftarrow\ p_{i}+\Delta tv_{i}\)
7:endfor
8: update Local Information (\(e_{1},\ \ldots,\ e_{l}\))
9: set Degree Of Congestion (\(E_{1},\ \ldots,\ E_{l}\))
10:for all agents \(i\)do
11: set Soft Constraints (\(p_{i}^{*}\))
12: set Hard Constraints (\(p_{i}^{*}\))
13:endfor
14:while constraint iteration \(N\)do
15:for all constraint \(C\)do
16: Solve (\(C,\Delta t\))
17:endfor
18:endwhile
19:for all agents \(i\)do
20:\(v_{i}\leftarrow(p_{i}^{*}-p_{i})/\Delta t\)
21: add Steering Velocity(\(v_{i}\))
22:\(p_{i}\gets p_{i}^{*}\)
23:endfor
24:endloop
```  
**Algorithm 1** Crowd formation control using SRD  
In Algorithm 1, each group of agents \(G_{a},\ a\in\{1,\ 2,\ \ldots,\ m\}\) has a position \(P_{a}\in\mathbb{R}^{3}\), which is set by averaging all the positions of the agent in the group. From lines 2 to 3, the group position is planned and an SRD is updated for  
planner, where \(\Delta t\) is the time unit.