Crowd simulation has been one of the core techniques in many industries including entertainment, transportation and architecture for many years. Particularly, computer games and feature films have many scenes where numerous agents move together. To create those crowd scenes, we need a technique to obtain collision-free paths for each individual. Various approaches have been proposed till now, under the category of multi-agent path planning techniques. One of the most popular methods is the velocity obstacles (VO) method. It can predict where the other moving objects might be in the future within the pre-defined time duration by extrapolating their velocities; hence, collisions are avoided accordingly ^[1]. These methods formulate a set of collision regions in the velocity domain from all neighboring characters and static obstacles at each time frame and use an optimization technique to find an optimal velocity that is as close as possible to the preferred velocity and does not intersect with the collision region. This continuous optimal speed selection creates collision-free paths for every individual. Extensions of the original idea have been proposed, such as HRVO (hybrid reciprocal velocity obstacle) ^[2], ORCA (optimal reciprocal collision avoidance) ^[3], and AVO (acceleration velocity obstacle) ^[4], which have their own advantages and disadvantages. Because these methods can produce collision-free paths for many three-dimensional (3D) characters successfully, they have been integrated into current commercial game engines, such as Unity or Unreal.

However, in many cases, collision-free paths alone do not suffice. If game designers or movie directors were able to control crowds so that they arrive at a particular position in a particular order, it would be possible to express various effects. For example, an entire crowd can be moved from an initial position to a target position at the same time, and could be made to engage with enemies. However, none of the previous studies ^[2][3][4] consider these critical time constraints when simulating multi-agents. Instead, they are concerned with ensuring that no collisions occur while the agents move to their target positions. In this study, we try to obtain the collision-free paths for crowds, subject to arrival-time constraints. Since we assume that agents have zero knowledge about the environment, they do not know how long it takes to get to the intended position. Therefore, it is very difficult to set the absolute arrival time. Instead, our algorithm focuses on the relative time difference among the agents’ arrivals. This would give the arrival-order constraints over the crowds. For example, all agents could be made to arrive at their intended position simultaneously, or given an initial line formation, we can make them arrive at their target positions from left to right. As another example, we can make moving objects symmetrically arrive at the targeted positions at the video games, or the films. Furthermore, we can control the arrival times of drones to give more impressive effects to attendances. In summary, supporting the relative arrival times of objects to specific positions can further increase the controllability of objects.

To solve the ordered arrival-time constraint, this study proposes algorithms featuring three main contributions. First, to meet the time constraints, we put a velocity-adjustment layer on top of the existing ORCA method. This layer adjusts the velocities of all agents so that they arrive at their target positions in a particular order. Whereas the original ORCA method has a fixed range of speed, the proposed method allows the maximum speed parameter to change, to meet the time constraints. Although the original ORCA algorithm creates collision-free paths for multiple agents, it cannot be used to control their relative arrival times. That is, it cannot control the order in which the agents arrive. However, the proposed methods not only produce the collision-free paths, but also satisfy the arrival-time constraints.

Second, to find a set of waypoints for a highly complicated environment, a modified PRM (probabilistic roadmap) method is proposed, which can reduce the potential future collisions for multiple agents. The modification scatters the shared waypoints of multiple agents slightly so that the agents can have different waypoints; this has the effect of reducing future collisions.

Third, a novel user interface is proposed for setting the time constraints. Usually, the timeline interface has been widely used for time-domain multimedia applications. However, it is not efficient for multi-agent simulation because a timeline must be given for each agent. If hundreds of agents are to be simulated, then the same number of timelines must be created, which is not easy to control. The novel interface instead integrates the time constraints with the environment. Specifically, it is assumed that the y-axis (up vector) of the environment is a time domain. When the target position of each agent is set up, another time point is allowed for setting their arrival time. The farther the point is from the ground, the later the agent arrives at the goal. A key point is that the time point does not represent the absolute time of arrival. Instead, the gap between two time points is of significance, as it represents the time difference between two arrival times. Through a series of experiments, it was verified that the proposed algorithm could exactly create paths for many agents satisfying diverse time constraints in real-time. Furthermore, a new user interface is proposed that can be used to set constraints around 30 percent faster than the timeline interface.