A NEW COLLISION AVOIDANCE MODEL WITH SEMI IMPLICIT RANDOM BATCH RESOLUTION∗

Research on crowd simulation has important and wide range of applications. The main difficulty is how to lead all particles with a same and simple rule, especially when particles are numerous. Firstly we propose a two-dimensional agent-based collision avoidance model, which is a N-particles Newtonian system where three interaction forces are designed to mimic deviation, deceleration and aligning actions of agents when avoiding collisions. Secondly, direct simulation of the N-particles Newtonian system is time-consuming, since the computational complexity is O(N2), we therefore propose an efficient algorithm, called the semi-implicit random batch method with kernel splitting (SRBMS) which reduces the computational complexity to O(N) and converges to the proposed collision avoidance model with a convergence rate equal to 1/2. SRBMS is a combination of the Random Batch method (S. Jin, L. Li, and J.-G. Liu, Random batch methods (RBM) for interacting particle systems, J. Comput. Phys., 400:108877, 2020) and the kernel splitting strategy. Finally, various tests are presented to show robustness and efficiency of the proposed model and the numerical resolution.