In this paper, two intuitive and highly efficient solutions are proposed for global planning and local avoidance. We introduce guide and repel vectors to study global planning, which generates a steady and smooth navigation field through a simple and efficient bilinear interpolation method. In addition, this paper proposes a novel velocity-based approach to simulate the local avoidance of agents based on least-effort principle. During the local avoidance phase, humans slightly adjust their motions, so that the energy required to perform a step becomes minimal. The two solutions are integrated into one system, which finally simulates the natural-looking navigation and interaction behavior of agents.
As virtual reality technology develops, crowd simulation technology is paid
increasing attention. According to different modeling granularities, existing crowd
models can be generally classified into two categories, namely, macroscopic and
microscopic approaches. The former models a crowd as continuous flow of fluid
[
Main Contribution: Based on previous research, two intuitive and highly efficient solutions are proposed in this paper for global planning and collision avoidance.
We introduce guide and repel vectors to study global planning, which generates a steady and smooth navigation field through a simple and efficient bilinear interpolation method. In addition, we propose a novel velocity-based approach to simulating the collision avoidance of agents through the observation of human behavior in avoiding dynamic obstacles in real life. 2
In this section, we briefly discuss prior literature on global planning and local
avoidance, which are the two key issues in crowd modeling technology.
Global Planning: To navigate a complex environment, a high-level path
planning technology is needed. The most popular crowd navigation technologies
include graph search and potential fields. Graph-based algorithms are widely used
in global planning [
To compute a global path to the goal for each agent, we decompose the environment into grids, which have different size and are represented by rectangles. When static obstacles are dense, our method will subdivide the environment until each mixed grid is almost occupied by obstacles; when static obstacles are sparse, our decomposition method roughly divides the environment into several grids, then merges the empty grids, and forms a large empty area.
We use a four-connected graph to organize the empty grids. The connective graph is defined to be the graph that has a vertex for each grid and an edge between two vertices only if the corresponding grids share a segment on their boundaries. A path over this graph is computed, such that following the path from any vertex leads to the vertex corresponding to the grid containing the goal state. The resulting directed graph defines a successor for every grid, except the goal grid. The successor of a grid is the next grid on the path to the goal grid. Each grid with a successor is termed as an intermediate grid, and the intermediate grid has only one successor. Specially, the goal grid has no successor. See Figure 1 for an illustration. We assume that each grid has four adjacent grids (because the graph is fourconnected). A grid must be set as the successor of the grid. The shared boundary is called exit face, and the others are called repel faces. See Figure 2 for an illustration. To obtain a proper transition from the current grid to successor, we introduce two types of vector fields, i.e., those corresponding to grids in the decomposition, which we call guide vector fields, and those corresponding to faces, which we call repel vector fields. A guide vector field guides an agent through the grid to the exit face, which leads to the successor grid. Repel vector fields prevent an improper grid transition, i.e., a transition from the current grid to a grid that is not the successor is prohibited. For the repel vector on repel faces, its direction is orthogonal to the face and points inward. For the repel vector on the exit face, its direction is orthogonal to the exit face and points outward. The guide vector fields always point toward the exit face. In the case of the goal grid, all repel and guide vector fields point inward to the goal state.
The different sizes between adjacent grids pose a difficulty in choosing the
appropriate repel or guide vector fields. Zhang et al. [
Considering that the grid size might differ, two cases are considered for f2. Figure 4 shows that when the current position of agent (xi,yi ) locates below the green-dotted line, f2=fvirtual, when (xi,yi ) locates above the green-dotted line, f2=f21. fvirtual represents the repel vector on the virtual face, and f21 represents the repel vector on the exit face. We suppose that α = 0.5 and β = 0.5. We can calculate the navigation vector of each spot in the configuration space using Equation (3). Disregarding other agents, each agent can move step by step along the direction of Vnav to the goal state. Figure 5(a) shows an example for the navigation fields, and Figure 5(b) shows the path of an agent moving from the initial point to the goal state. No steep turn exists in the corners, and the whole path is smooth, which vividly simulates the human behavior when turning in our real life. Two main challenges occur in local collision avoidance, namely, collision prediction and collision avoidance. In this section, we describe our collision avoidance model. In our problem setting, we are given a virtual environment where n agents PN={P1, . . . , Pn} have to navigate toward their specified goal without colliding with the environment and with one another. For simplicity, we assume that each agent moves on a plane and is modeled as a disc with radius ri, and its personal space is modeled as a disc with radius ρi. At a fixed time t, the agent Pi is at the position xi(t), defined by the disc center, and moves with velocity vi(t). This velocity is limited by a maximum speed uimax, i.e., kvi(t)k ≤ uimax. For notational convenience, we will not explicitly indicate the time dependence.
In every simulation step, the agent Pi has a desired velocity vdes(t), whose
i
orientation is Vnav, which have been computed in Section 3, and magnitude is
uides, which is closely related to the crowd density ρ according to Fang et al. [
Vnav kVnavk udes = i uimax ρ ≤ ρmin
uimin + ρmρa−xρ−mρimnin ∗ (uimax − uimin) ρmin < ρ < ρmax u¯ ρ ≥ ρmax In the above equations, ρmin and ρmax are the minimum and maximum crowd density thresholds, respectively. u is the average speed of all agents, which are in the vision range of Pi ’s vision range. (4) (5)
An agent configuration is defined by its position and velocity. Koh and Zhou proposed a relative frame model for collision prediction. Source agent is denoted as the agent that avoids a target agent. Figure 6 shows the relative frame between a source agent and a target agent, where vr is the relative velocity between the source and target agents; θs and θg are the orientation of the source and target agents, respectively; θr is the relative orientation between the source and target agents. Rg=rg+ρs, it means that the target agent should not invade the personal space of the source agent.
The collision zone is defined as a region of space where the source agent should prevent collision with the target agent, i.e., collision is predicted in future if θrmin ≤ θr ≤ θrmax (6) and if the two agents do not change their speed and orientation.
When a collision has been predicted, we then compute the time to collision (ttc); if ttc is less than a certain anticipation time t, the target agent is inserted into a set of agents that are on the collision course with the source agent. In real-life, an individual tries to avoid a limited number of other pedestrians, usually those that are on the collision course with him in the coming short time. Similarly, the source agent tries to evade N agents with which will collide first. In our implementation, N is less than 4. 4.3
The least-effort principle originates from the field of psychology and states that
given different possibilities of actions, people select the one that requires the
least effort [
We first retrieve a set of candidate relative orientation Or, such that the orientation of relative velocity can be selected to resolve the collision with the agents who are on the collision course. According to condition (6), the collision can be avoided if the source agent selects a new relative velocity vnew, that r satisfies the condition ¬(θrmin ≤ θrnew ≤ θrmax) (7) To avoid unrealistic orientation deviate, we bound the max angle deviation θimax to π2 . We can compute Or by combining condition (7) and θimax.
We then retrieve the set of candidate relative speed Ur. When Or is determined, the max relative speed urmax= vides +kvj k and the min relative speed urmin= vides − kvj k .
Having retrieving Or and Ur, we select an optimal pair P =(ur,θr), where ur ∈ Ur ∧ θr ∈ Or, so that the expenditure energy for the source agent is minimum. See Figure 7(a) for an illustration.
vinew = vrnew + vj Δui = kvinewk − vdes
i Δθi = arccos
vinew · vides kvinewk ∗ vides (8) (9) (10) f (ur, θr) = α ∗ uΔmuaix + β ∗ θmax Δθi where umax=1.5m/s is the maximal value for speed changed, and θmax= π2 is the maximum angle deviation. The constants α and β define the weights of specific cost terms and can vary among the agents to simulate a wide variety of avoidance behavior.
Computing the minimum value of Equation (11) is time-consuming. Thus, we restrict the domain Or to a discrete set of orientation samples (the default size of the discretization step is set to 0.01π). Similarly, we discretize the domain Ur into a set of adjacent speed samples (the default distance between adjacent samples is set to 0.05). Assuming that the discretized set of Or is Or and that of Ur is Ur , then the set of admissible relative velocity is
F AVr = {urθr | ur ∈ Ur ∧ θr ∈ Or} In the above equations, Δui is the value for speed changed, and Δi is the angle deviation of the source agent. The cost function is (11) (12) (14) The discretized cost function is vnew = r
argmin
V cand∈F AVr ( α ∗ vcand + vj −
vides umax + β ∗ arccos
(vcand + vj ) · vides kvcand + vj k ∗ vides ) (13) Having retrieving vnew, the optimal new velocity for the source agent is easy to r compute. We then update the source agent position into
xinew = xi + vinew ∗ Δt 4.4
We divide imminent collision into two cases (Figure 7(b)(c)). In case (b), we introduce the concept of relative tangential velocity, which is equivalent to applying a tangential force to separate the two agents. In case (c), we introduce the concept of repel velocity, which is equivalent to applying a repulsive force to separate the two agents immediately. 4.5
An agent Ai also needs to avoid colliding with the static obstacles of the environment. In our simulations, such obstacles are modeled as axis aligned boxes. Collisions are resolved by following an approach similar to the one described above.
We first retrieve the nearest obstacles of the agent Ai that are inside the visual field of the agent. We then compute the maximum and minimum orientations among the vectors lined from the current position of Ai ’s to each vertex of the convex polygon obstacle. The maximum and minimum orientations are θrmax and θrmin, respectively, which have been discussed above. Finally, we use a least-effort criterion to select an optimal velocity for the agent Ai.
We test our approach against a wide range of scenarios. These scenarios range from the simple interactions between pairs of agents to more challenging and large test cases as follows:
Squeeze: Two agents have to avoid a head-on collision while walking in an opposite direction (Figure 8(a)).
Overtake: An agent moves down a hallway and encounters a slower agent in front (Figure 8(b)).
Square: Four agents are placed on the vertex of a square and have to walk toward their diagonal position (Figure 8(c)).
Complex environment: Three hundred agents walk through an environment filled with many obstacles and have to evacuate from the exit (Figure 8(d)). In this paper, we present a novel integrated framework for navigation and interaction behavior. A creative global path planning algorithm and a bilinear interpolation method were used to compute the navigation fields. A least-effort criterion was also employed in the local avoidance to achieve realistic local movements. 7
This research was supported by National Natural Science Foundation of China (No. 60473109), NSFC-Guangdong Union Foundation of China (No.U0735001). We would like to thank the anonymous reviewers for their suggestions and comments.