Old Well

Comp 790 Research: Density Modeling and Control via Intention Filters

Sahil Narang & Andrew Best

  1. Goal of Project
  2. Motivation
  3. Current State of the Art
  4. What We Plan to Achieve
  5. Tentative Schedule
  6. Update, November 2013
  7. References

Goal of the Project

We aim to develop a set of Intention Filters to solve the following:

  1. Reduce the tendency of RVO agents to achieve high density
  2. Better represent the effect of obstacles and how these constraints relate to agent density

What is your Motivation

We are motivated by the recent advances in crowd simulation and the potential applications of an ideal simulator in designing evacuation plans for large structures, studying crowd behavior, crowd simulation in computer graphics, motion planning, video gaming, traffic engineering and architecture design. We are further motivated by the necessity to increase modelling scope accuracy as it relates to crowd behavior. We seek to produce more realistic pedestrian simulations that produce results even more aligned with human crowds than those we have.

What is the current state of the art in this project area?

There has been a great deal of work in the pedestrian dynamics community in devising models for pedestrian motion and interaction. The research has largely focused on three approaches: cellular automata (CA), social forces (SF) and reciprocal velocity obstacles.

1. Cellular Automata

These techniques aim to work by discretizing the simulation domain into a grid of cells. An agent may occupy at most one cell and a cell may contain no more than a single agent. Pedestrians move from cell to cell based on various techniques. These approaches were quite common in simulating vehicular traffic. Blue and Adler first applied these techniques to pedestrians using a set of crafted rules for determining pedestrian movement and showed that they were able to reproduce observable pedestrian phenomena in both uni-directional and bi-directional flows [3, 4]. Other approaches applied probabilistic techniques to determine agent movement and augmented the functionality with scalar and vector fields to reproduce emergent phenomena [5]. CA-based approaches tend to exhibit some artefacts due to the discretization of the space. There has been extensive research to understand and mitigate these effects. Kirchner et al. examined the impact of the size of the cells [6]. Maniccam investigated the impact of exchanging square cells for hexagonal cells [7]. Yamamoto et al. introduced the real-coded cellular automata" to minimize the aliasing artifacts which arise from traversing a rectilinear grid [8]. CA-based approaches remain an active branch of research; these methods have been used as a basis to simulate complex scenarios with more elaborate pedestrian behaviors. [9, 10].

2. Social Forces Models

These models treat pedestrians like mass-particles and applies Newtonian-like physics to evolve the simulation. Helbing introduced the first such model in which each agent was motivated by a driving force which served to lead the agent towards a goal [11]. The agent would interact with obstacles and agents in the environment through the superpositioning of repulsive forces. Later SF-based models explored alternate formulations of the repulsive forces or novel forces including, compression and friction forces for evacuation [12], relative-velocity-dependent forces [13, 14], and group formations [15]. A more complete overview can be found in [16]. SF-based models have been shown to exhibit self-organizing behaviors [17].

3. Velocity Obstacle Models

Agent interactions are based on velocity obstacles (VO). One agent denies a set of velocities for another agent which would lead to an inevitable collision. Agents then select a velocity outside of this set for a collision-free path. Originally, each agent assumed that all other agents were non-responsive [2]. Later VO-based models introduced alternative VO formulations which assumed that agents were aware that those around them would also respond [18, 19, 1]. Pedestrian simulation using VO-based models has been shown to exhibit self-organizing behaviors and varying flow through a bottleneck [20] as well as accurate microscopic interactions between individual pedestrians [21].

Recently, Curtis et. al. proposed the notion of “intention filters” which can thought of as a third cognitive level between global and local planners. Architecturally, it sits at the interface between the global and local components. Its purpose is to adapt the intention (i.e. preferred velocity) to local dynamic conditions. It does this by using reasoning whose scope is on the order of 100 seconds. An intention filter affords greater control over agent crowd behavior. The algorithms used by the global and local planners inherently encode a particular space of behaviors. These behaviors can be tuned by tweaking parameters and, in some cases, the algorithms can be extended to incorporate additional parameters and behaviors. Ultimately, these efforts are constrained by the underlying models used. By inserting an intention filter, one can provide a new model which can complement the global and local planners’ models. Working in conjunction, this new system can produce behaviors which may otherwise be impossible to achieve with the global and local planners alone.

What do you plan to achieve during the course project?

We have devised a set of scenarios for which current Pedestrian Simulation models create inhuman densities and agent interactions. These scenarios are:

  1. Bottleneck Hallway: A large number of agents are trying to get through a bottleneck at the end of a hallway. ORCA Helbing
  2. Concert Floor: A large number of agents are trying to get the best spot infront of a concert stage. ORCA Helbing
  3. Ticket Kiosk: A large number of agents are crowding around a ticket booth, trying to get to the window. ORCA Helbing
As shown by the bottleneck and crowding simulations, the RVO agents tend to achieve higher density rather easily. They exhibit higher densities than human crowds do in similar situations, and get to those high densities too fast compared to humans. We aim to introduce a local density parameter in the ORCA model in order to effectively negate this tendency of RVO agents. Furthermore, we intend to reduce the agents ' tendancy to walk directly against obstacles when there is no density requiring them to do so.

Tentative Schedule

By end of Week 3:

Detailed study and analysis of present models. Adding local density parameters to agents in ORCA model

By end of Week 6

Implementation of density based intention filters

By end of week 9

Test different intensity based intention filters.Compilation of results and analysis

November Update

1) Mathematical Formulation

Initial Implementation

The first alogirthmic implemenetation was done using a sampling method. Each agent class is given a half-angle Θ, which is sampled along intervals, creating sample angles Φ. At each time step, agents of the class test their globally derived preferred velocity (henceforth referred to as input velocity by comparing it to optional velocities offset by a rotation of Φ using a cost function defined below. The agent chooses the maximally effective preferred velocity at each timestep.

The cost function C(vtest, τ) is defined as the distance from the agent's goal point if the agent took vtest for some amount of time, τ.

C(Vtest, τ) = Pgoal - (Pagent + Vtest * τ)

Initial Results

To test the initial implementation, three experiments were performed.

  1. Agent passing a crowd

    An agent passes a crowd of slower moving agents. The normal FD Agent behavior would be to slow down and follow the slower moving agents to the goal point (directly below the agent). Our agents, which seek to avoid density if possible, plot a path around the slower agents and exit the scene 45% faster than previos FD sensitive agents.

  2. Agent Following a Solid Line

    As a reality check, an agent follows a crowd wider than the angle Θ it searches for optimum paths. The agent performs identically to previous FD Sensative agents.

  3. Agent passing through a Splitting Crowd

    In this scenario, the agent will pass through a crowd of dense agents as it splits into two groups. Although the agent will not be able to maintain its preferred velocity, it minimizes the impact to its velocity by sensing and responding to the decreased density in the parting crowd. Our method performs 20% better.

References

1. Van den Berg, J., Guy, S.J., Lin, M., Manocha, D.: Reciprocal n-body collision avoidance. In: Inter. Symp. on Robotics Research. (2009)
2. Fiorini, P., Shiller, Z.: Motion planning in dynamic environments using velocity obstacles. IJRR 17(7) (July 1998) 760-762
3. Blue, V.J., Adler, J.L.: Emergent fundamental pedestrian flows from cellular automata microsimulation. Transportation Research Record: Journal of the Transportation Research Board 1644 (1998) 29-36
4. Blue, V.J., Adler, J.L.: Cellular automata microsimulation of bidirectional pedestrian flows. Transportation Research Record: Journal of the Transportation Research Board 1678 (1999) 135-141
5. Burstedde, C., Klauck, K., Schadschneider, A., Zittartz, J.: Simulation of pedestrian dynamics using a two-dimensional cellular automaton. Physica A: Statistical Mechanics and its Applications 295 (2001) 507-525
6. Kirchner, A., Klupfel, H., Nishinari, K., Schadschneider, A., Schreckenberg, M.:Discretization effects and the influence of walking speed in cellular automata models for pedestrian dynamics. J. Stat. Mech. 2004 (October 2004)
7. Maniccam, S.: Trac jamming on hexagonal lattice. Physica A: Statistical Mechanics and its Applications 321 (2003) 653-664
8. Yamamoto, K., Kokubo, S., Nishinari, K.: Simulation for pedestrian dynamics by real-coded cellular automata (rca). Physica A: Statistical Mechanics and its Applications 379 (2007) 654-660
9. Bandini, S., Federici, M., Manzoni, S., Vizzari, G.: Towards a methodology for situated cellular agent based crowd simulations. Engineering societies in the agents world VI (2006) 203-220
10. Sarmady, S., Haron, F., Talib, A.: A cellular automata model for circular movements of pedestrians during tawaf. Simulation Modelling Practice and Theory (2010)
11. Helbing, D., Molnar, P.: Social force model for pedestrian dynamics. Phys. Rev. E 51(5) (May 1995) 4282-4286
12. Helbing, D., Farkas, I., Vicsek, T.: Simulating dynamical features of escape panic. Nature 407 (2000) 487-490
13. Yu, W.J., Chen, R., Dong, L.Y., Dai, S.Q.: Centrifugal force model for pedestrian dynamics. Phys. Rev. E 72 (Aug 2005) 026112
14. Chraibi, M., Seyfried, A., Schadschneider, A.: Generalized centrifugal-force model for pedestrian dynamics. Phys. Rev. E 82(4) (2010) 046111
15. Moussad, M., Perozo, N., Garnier, S., Helbing, D., Theraulaz, G.: The walking behavior of pedestrian social groups and its impact on crowd dynamics. PLoS
ONE 5(4) (2010)
16. Seyfried, A., Schadschneider, A., Kemloh, U., Chraibi, M.: Force-based models of pedestrian dynamics. Networks and Heterogeneous Media 6(3) (2011) 425-442
17. Helbing, D., Molnar, P., Farkas, I., Bolay, K.: Self-organizing pedestrian movement.
Environment and Planning B: Planning and Design 28(3) (2001) 361-383
18. Van den Berg, J., Lin, M., Manocha, D.: Reciprocal velocity obstacles for real-time
multi-agent navigation. ICRA (2008) 1928-1935
19. Van den Berg, J., Patil, S., Sewall, J., Manocha, D., Lin, M.: Interactive navigation
of multiple agents in crowded environments. In: I3D '08, New York, NY, USA,
ACM (2008) 139-147
20. Guy, S.J., Curtis, S., Lin, M.C., Manocha, D.: Least-effort trajectories lead to emergent crowd behaviors. Phys. Rev. E 85(1) (2012) 016110
21. Guy, S.J., Lin, M.C., Manocha, D.: Modeling collision avoidance behavior for virtual humans. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 2 - Volume 2. (2010) 575-582