Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Algorithms & Applications Group
Roadmap-Based Techniques for Simulating Group Behaviors

The objective of our research is to develop efficient techniques for simulating group behaviors. We investigate how agents can work cooperatively to perform tasks, plan paths in dynamic environments, or influence another group of agents to locations in an environment. Our goal is create a framework for simulating and controlling communities of characters that can dynamically interact with each other and their environment. There are many important applications of this system, ranging from civil crowd control (e.g., planning exit strategies from buildings or sporting event venues), to education and training (e.g., providing museum exhibits or training systems), to entertainment (e.g., interactive games). While there are existing methods that focus on the simulation aspect, there is a lack of methods that support the interaction and control (or steering) of multiple groups of agents.

This work focuses on a framework that addresses these challenges by integrating roadmap-based path planning with agent-based modeling. Our initial work introduced the idea of integrating roadmap-based path planning with agent-based emergent behavior. That initial work studied single group behaviors such as covering and a simple multiple group shepherding behavior and established that this hybrid approach has promise. Currently, we are extending our approach to support a greater range of scenarios that involve:

  • large numbers of agents (e.g., crowd control in emergency situations),
  • agents that adaptively and dynamically select among different behaviors (e.g., switching to evasive behaviors when enemies are detected), and
  • dynamic and arbitrary groupings and coordination of agents (e.g., coordinated group patrols or pursuits).

Our general strategy is to integrate multi-agent simulation with roadmap-based path planning. We use a graph-based representation (roadmap) of the environment that encodes representative feasible pathways and also other important information about the environment, e.g., the locations of exits, safe areas for evacuation, clearings in forests, or hiding spots. Our framework provides a uniform way to model, select/combine, and specialize common basis behaviors to create new emergent behaviors. Improved scalability and more complex group behaviors and interactions are supported by mechanisms designed specifically to handle the modeling of dynamic group formation, intra- and inter-group interaction, and the customization of behaviors based on group membership.

Below we list some of our current focuses and provide links to pages providing more details.

Evacuation Planning with Direction and Ingress/Egress

One application of our work is evacuation planning. By being able to simulate agents that are evacuating an area, we can study the effects of things such as the number and placement of exits, how losing exits affects evacuation routes and times, or how evacuation times vary depending on the number, type and placement of barriers and directing agents available to control the evacuating agents.

In our initial work in this area, we study a scenario where some agents are attempting to evacuate the first floor of a building. The agents have to find paths to the safe areas. They use their knowledge of the environment (a roadmap) and information they learn about the situation by discovering barriers blocking routes or from directing agents (e.g., emergency response personal or posted signs) indicating which exists to use/avoid and/or which safe areas they should evacuate to.

Ingress and Egress with Multiple Modes of Transportation

We have extended our evacuation behavior to be applicable to ingress and egress for a variety of agent types including pedestrians, cars, and buses. Ingress and egress simulations can be a useful tool for studying the effect of design decisions on the flow of agent movement as a crowd exits an area under normal circumstances. This type of simulation can be used to determine before hand the effect of design decisions and enable exploration of potential improvements. We have been able to show that our simulation framework can be tuned to be sensitive to local design changes in the virtual buildings and in complex parking lot structures. Our work differs from many evacuation systems in that we support grouping restrictions between agents, and model scenarios with multiple modes of transportation with physically realistic dynamics for pedestrians and vehicles (e.g., individuals walk from a building to their own cars and leave only when all people in the group arrive). We have shown how local maneuvers executed by the agents permit them to form coordinated valid motion trajectories in potentially restricted environments, and resolve the deadlocks that arise between agents in mixed-flow parking lot scenarios. Our approach allows us to map complex environments and we use our motion planning library to generate paths that are feasible for both types of agents.

Environmental Design

Evacuation and egress simulations can be a useful tool in determining the effect of design decisions on the flow of agent movement. This type of simulation can be used to determine beforehand the effect of such design decisions and potential improvements that can be made. In this work, we look at how agent movement is effected by the environment in real world, large scale virtual environments and investigate metrics to analyze the flow. We have also investigated aspects of building design that can be optimized. Architectural features that we have explored to optimize include pillar placement in simple corridors and doorway placement in buildings. We have also studied agent placement for information dispersement in an evacuation. The metrics we have utilized are tuned to the specific scenarios studied, which include continuous flow pedestrian movement, building evacuation, and agent encounters. While the initial focus of this work was on building design, we are working to extend this study to robot teams working among crowds of pedestrians.

Pursuit-Evasion Techniques

Pursuit-and-evasion are commonly studied behaviors. One group of agents, the pursuers, attempts to find and capture another group of agents, the evaders. The evaders attempt to remain undetected and once detected, attempt to escape and hide from the pursuers. We look at aspects of pursuit-evasion which involve studying searching techniques, pursuit strategies and evasion heuristics.

Reciprocally-Rotating Velocity Obstacles

Reciprocally-Rotating Velocity Obstacles (RRVO) is a scalable collision avoidance technique for multi-agent systems that generalizes Reciprocal Velocity Obstacles (RVO). In this work, we empower agents to actively rotate in order to avoid collision with each other. Whereas before, agents were generally assumed to be represented as circles, RRVO relaxes this assumption to allow for any convex polygon. The resulting method allows one to more accurately model their agents, and permits more realistic motion in the form of rotation. RRVO has application in any multi-agent simulation, including evacuation, pursuit-evasion, urban planning, and more.

Reciprocally-Rotating Velocity Obstacles, Andrew Giese, Daniel Latypov, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. to appear, Hong Kong, China, Jun 2014. Also, Technical Report, TR13-009, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, TX U.S.A., Oct 2013.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Reciprocally-Rotating Velocity Obstacles, Andrew Giese, Masters Thesis, Department of Computer Science and Engineering, Texas A&M University, College Station, USA, May 2014.
Masters Thesis(ps, pdf, abstract)

Multi-Robot Caravanning, Jory Denny, Andrew Giese, Aditya Mahadevan, Arnaud Marfaing, Rachel Glockenmeier, Colton Revia, Samuel Rodriguez, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), pp. 5722 - 5729, Tokyo, Japan, Nov 2013.
Proceedings(pdf, abstract)

Optimizing Aspects of Pedestrian Traffic in Building Designs, Samuel Rodriguez, Yinghua Zhang, Nicholas Gans, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), Nov 2013.
Proceedings(pdf, abstract)

Improving Aggregate Behavior in Parking Lots with Appropriate Local Maneuvers, Samuel Rodriguez, Andrew Giese, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), Nov 2013.
Proceedings(pdf, abstract)

Environmental Effect on Egress Simulation, Samuel Rodriguez, Andrew Giese, Nancy M. Amato, Saeid Zarrinmehr, Firas Al-Douri, Mark Clayton, In Proc. of the 5th Intern. Conf. on Motion in Games (MIG), 2012, in Lecture Notes in Computer Science (LNCS), pp. to appear, Rennes, Brittany, France, Nov 2012.
Proceedings(ps, pdf, abstract)

A Sampling-Based Approach to Probabilistic Pursuit Evasion, Aditya Mahadevan, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 3192 - 3199, St. Paul, Minnesota, USA, May 2012.
Proceedings(pdf, abstract)

Roadmap-Based Techniques for Modeling Group Behaviors in Multi-Agent Systems, Samuel Rodriguez, Ph.D. Thesis, Department of Computer Science and Engineering, Texas A&M University, Jan 2012.
Ph.D. Thesis(ps, pdf, abstract)

Roadmap-Based Level Clearing of Buildings, Samuel Rodriguez, Nancy M. Amato, In Proc. of the 4th Intern. Conf. on Motion in Games (MIG), 2011, in Lecture Notes in Computer Science (LNCS), pp. 340-352, Edinburgh, UK, Oct 2011.
Proceedings(ps, pdf, abstract)

Toward Realistic Pursuit-Evasion Using a Roadmap-Based Approach, Samuel Rodriguez, Jory Denny, Juan Burgos, Aditya Mahadevan, Kasra Manavi, Luke Murray, Anton Kodochygov, Takis Zourntos, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 1738-1745, May 2011.
Proceedings(ps, pdf, abstract)

Roadmap-Based Pursuit-Evasion in 3D Structures, Samuel Rodriguez, Jory Denny, Aditya Mahadevan, Jeremy (Cong-Trung) Vu, Juan Burgos, Takis Zourntos, Nancy M. Amato, In Proc. of 24th Intern. Conf. on Computer Animation and Social Agents (CASA), 2011, in Transactions on Edutainment, pp. to appear, May 2011.
Proceedings(ps, pdf, abstract)

Utilizing Roadmaps in Evacuation Planning, Samuel Rodriguez, Nancy M. Amato, In Proc. of 24th Intern. Conf. on Computer Animation and Social Agents (CASA), 2011, in Intern. J. of Virtual Reality (IJVR), pp. 67-73, May 2011.
Proceedings(ps, pdf, abstract)

Toward Simulating Realistic Pursuit-Evasion Using a Roadmap-Based Approach, Samuel Rodriguez, Jory Denny, Takis Zourntos, Nancy M. Amato, In Proc. of the 3rd Intern. Conf. on Motion in Games (MIG), 2010, in Lecture Notes in Computer Science (LNCS), pp. 82-93, Nov 2010.
Proceedings(ps, pdf, abstract)

Behavior-Based Evacuation Planning, Sam Rodriguez, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 350-355, Anchorage, AK, May 2010.
Proceedings(ps, pdf, abstract)

A Framework for Planning Motion in Environments with Moving Obstacles, Sam Rodriguez, Jyh-Ming Lien, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), pp. 3309-3314, Oct 2007.
Proceedings(ps, pdf, abstract)

Swarming Behavior Using Probabilistic Roadmap Techniques, O. Burchan Bayazit, Jyh-Ming Lien, Nancy M. Amato, Lecture Notes in Computer Science, 3342/2005:112-125, Jan 2005.
Journal(ps, pdf, abstract)

Shepherding Behaviors, Jyh-Ming Lien, O. Burchan Bayazit, Ross T. Sowell, Samuel Rodriguez, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 4159-4164, New Orleans, Apr 2004. Also, Technical Report, TR03-006, Parasol Laboratory, Department of Computer Science, Texas A&M University, Nov 2003.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Better Group Behaviors using Rule-Based Roadmaps, O. Burchan Bayazit, Jyh-Ming Lien, Nancy M. Amato, In Proc. Int. Wkshp. on Alg. Found. of Rob. (WAFR), pp. 95-111, Nice, France, Dec 2002.
Proceedings(ps, pdf, abstract)

Roadmap-Based Flocking for Complex Environments, O. Burchan Bayazit, Jyh-Ming Lien, Nancy M. Amato, In Proc. Pacific Conf. on Computer Graphics and App. (PG), pp. 104-113, Beijing, China, Oct 2002. Also, Technical Report, TR02-003, Parasol Laboratory, Department of Computer Science, Texas A&M University, Apr 2002.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Supported by NSF

Project Alumni:O. Burchan Bayazit,Andrew Giese,Jyh-Ming Lien