About

My name is Clodéric Mars, I'm a sofware engineer specialized in AI for simulations and games. I previously worked at Golaem and joined Masa in 2012. This is a place where I irregularely post vaguely interesting stuffs about my professional interests.

Site

Group navigation state-of-the-art report - Part 3, Who's in charge?

The full article is available here.

Who’s in charge?

In the previous part, we studied how group members are able to maintain cohesion or stay in formation. In this part, we’ll study how the group, a whole, is able to make navigation decisions: path planning, path following, steering (including collision avoidance) and formation changes.

Anchor

While some behavior might be decentralized (c.f. part 1), in order to leverage groups in a context where we need to make them go from A to B, top-down decision making is needed (Musse and Thalmann 2001). A group level process will be able to make the group move while each of its member follows. We call anchor a virtual object that group members use as a reference for their formation or flocking behaviors and to which they delegate some navigation processes. It aggregates various data relative to the group, such as its position, orientation and velocity and it’s where the group level decision-making is done.

Leader

Trying to enforce a strict equivalence between simulated entities and actual characters, lots of works rely on a leader-followers approach. In such approach, one member of a group is the leader where the others are the followers. The leader takes responsibility for the whole group regarding the navigation; it becomes the anchor of the group (Loscos et al. 2003; Qiu et al. 2010). The implementation of such an approach using a navigation engine for independent entities is straightforward: the leader is similar to an independent entity; while the followers uses a subset of the default processes and maintain a reference to their leader.

But the leader can’t reuse the exact same processes of an independent entity. Its navigation must take into account the bulk of the whole group as well as the different locomotion constraints of its followers. It is also better to differentiate the the leader’s own attributes (position, orientation and velocity) from the anchor’s (Millington 2006). Taking all these constraints into account makes the decision-making process of the leader very different from the other members.

Group entity

Noting that the leader-based approach as several flaws, a growing proportion of architectures chose to move the group anchor from the leader to a virtual group entity (Schuerman et al. 2010; Silveira et al. 2008; Karamouzas and Overmars 2010b). This virtual entity is similar to any other simulated entities but doesn’t have visual or physic (i.e. regarding collision detection) representation. In such architecture, the group members are identical to one another. In Schuerman et al. (Schuerman et al. 2010) work, other entities detect groups entities during their collision avoidance process, trying to avoid collisions with groups as the whole. Entities are thus able to simulate the fact that pedestrians tend to avoid to pass through a group. The group entity creates a one level deep hierarchy of entities. This approach can be taken a step further to create groups of groups and so on (Schuerman et al. 2010; Millington 2006) allowing a more structured crowd.

Path Planning/Following

One of the reasons for group navigation is to factorize a costly aspect of navigation: path planning. As a matter of fact the members of a group are expected to follow the same high-level path through the environment, a single query should be sufficient for the whole group.

The most important aspect of group level path planning is to choose how to take the bulk of the group into account. Contrary to a single entity where its bulk can’t be changed and thus is a hard constraint, a group can reconfigure in order to pass through narrower corridors. The query has to be tuned in order to prefer paths on which the group, in its current spatial configuration, can navigate but be able to select narrow passages if necessary. This implies that the cost of falling back to a narrower spatial configuration can be compared to the cost of taking a longer path (Kamphuis and Overmars 2004; Pottinger 1999; Bayazit et al. 2003).

Once the path is computed, the path following process is able to provide local steering orders resulting in the entity following the path. Adapted to groups, this process makes the anchor follow the path. In some work (Bayazit et al. 2003; Pottinger 1999), the group level path following is also responsible for environment aware formation adaptation, allowing the formation to change when the clearance to obstacles changes. The following figure shows how a formation change allows a group to pass through a narrow passage more smoothly.

Collision Avoidance

Groups tend to stay coherent when navigating between obstacles and among other pedestrians, that’s why several work features group level collision avoidance. Numbers of existing algorithm for entities can be applied directly or adapted for group level collision avoidance. As we noted for path planning and following, the main difference between groups and single entities is that their bulk is not a hard constraint. The spatial configuration of a group can be adapted to occupy less frontal space, less longitudinal space or both.

Schuerman et al. consider the bulk of the group as a disc allowing them to use RVO (Schuerman et al. 2010; van den Berg et al. 2008). The resulting collision avoidance is very conservative as the disc is, most of time greatly overestimating the real footprint of the group. Karamouzas and Overmars adapted their own collision avoidance algorithm, based on velocity space sampling and sweep collision test, to work on the oriented bounding box of the group (Karamouzas and Overmars 2010a; 2010b). They further extend the algorithm by allowing formation adaptation. In practice, they generate samples based on velocity changes and formation changes interpolating the current formation with a library of valid formation. Each sample is weighted depending on its distance from the desired velocity and the desired formation and its time to collision. The number of candidate formations is limited to 15 as there’s 5 possible formations and 3 interpolations computed per formation. These limits lower the number of considered samples, preserving the performances of the algorithm.

Peters et al. rule based navigation method is able to handle both formation adaptation and group splitting which is not supported by the previously described methods (Peters et al. 2009). Unfortunately the article doesn’t provide many details on the algorithm.

Those group level navigation methods allows the group to take responsibility for a part of collision avoidance and more easily preserve the group cohesions. The members’ own navigation behaviors are still necessary both to preserve individual behaviors and to avoid remaining collisions.

Conclusion

This review was limited to the navigation aspect of the group, it is supposed to answer to the question: “How to make a group navigate in my simulation/game?”. A group is, most of the time, the result of social interactions and relations between individuals that have other consequences beyond navigation strategy: body language, facial expressions, and speech… For a simulated group to be believable those other aspects must be addressed.

This state-of-the art study was instrumental in the design of Golaem Path upcoming group navigation features (Golaem n.d.). I hope others developers or even researchers in the field will find it useful. I’ll try to update its content as other works come to my knowledge or are published.

Bibliography

• Bayazit, O Burchan, Jyh-Ming Lien, and Nancy M Amato. 2003. “Better group behaviors in complex environments using global roadmaps.” Pp. 362-370 in 8th International conference on Artificial Life.
• Golaem. n.d. “Golaem Path.” Retrieved (http://www.golaem.com/content/products/golaem-sdk/features).
• Kamphuis, Arno, and Mark H Overmars. 2004. “Finding paths for coherent groups using clearance.” Pp. 19-28 in 2004 ACM SIGGRAPH/Eurographics symposium on Computer Animation.
• Karamouzas, Ioannis, and Mark H Overmars. 2010a. “Simulating Human Collision Avoidance Using a Velocity-Based Approach.” Pp. 125–134 in VRIPHYS 10: 7th Workshop on Virtual Reality Interactions and Physical Simulations. Eurographics Association Retrieved (http://people.cs.uu.nl/ioannis/interactions/).
• Karamouzas, Ioannis, and Mark H Overmars. 2010b. “Simulating the local behaviour of small pedestrian groups.” Pp. 183-190 in 17th ACM Symposium on Virtual Reality Software and Technology. Hong Kong.
• Millington, Ian. 2006. “Movement.” Pp. 41-202 in Artificial intelligence for games, David H Eberlyedited by. Morgan Kaufmann.
• Musse, Soraia Raupp, and Daniel Thalmann. 2001. “Hierarchical Model for Real Time Simulation of Virtual Human Crowds.” Transactions on Visualization and Computer Graphics 7(2):152-164.
• Peters, Christopher, Cathy Ennis, and Carol O’Sullivan. 2009. “Modeling groups of plausible virtual pedestrians.” IEEE Computer Graphics and Applications 29(4):54–63.
• Pottinger, Dave. 1999. “Implementing Coordinated Movement.” Gamasutra. Retrieved April 20, 2011 (http://www.gamasutra.com/view/feature/3314/implementing_coordinated_movement.php?print=).
• Qiu, Fasheng, Xiaolin Hu, Xue Wang, and Saurav Karmakar. 2010. “Modeling social group structures in pedestrian crowds.” Simulation Modelling Practice and Theory 18:190-205.
• Schuerman, Matthew, Shawn Singh, Mubbasir Kapadia, and Petros Faloutsos. 2010. “Situation agents: agent-based externalized steering logic.” in International Conference on Computer Animation and Social Agents, 2010.
• van den Berg, Jur, Ming C Lin, and Dinesh Manocha. 2008. “Reciprocal Velocity Obstacles for real-time multi-agent navigation.” International Conference on Robotics and Automation 1928–1935.