Crowds control

Formation sketching

Wed, 09 Nov 2011 06:51:00 -0800

I have updated the Group navigation state-of-the-art report with an interesting article I read a few weeks ago :

Qin Gu and Zhigang Deng. Formation Sketching: An Approach to Stylize Groups in Crowd Simulation. In Graphics Interface. University Houston, Delmar Thomson Learning, 2011.

I've also set up a static page for the report at www.crowdscontrol.net/pages/group-navigation-state-of-the-art-report

Permalink | Leave a comment »

ml-class

Tue, 08 Nov 2011 14:51:30 -0800

I've been pretty busy lately following the wonderful machine learning Stanford open course of professor Andrew Ng.

When I learned about this Stanford initiative this summer I was really interested and decided to follow one course just to see how it was done. I chose machine learning over AI because I felt I had more to learn in that field, as a matter of fact I have followed a machine learning course in my final MSc year but never put what I learnt into practice and just remembered enough to impress a recruiter during an interview. I didn't consider following the database course, but I'm sure I'ld have learn more, but perhaps having less fun...

I'm roughly halfway through the course, here's my takeover for the moment.

It IS possible to deliver a compelling video course, the key aspects: short segments (~10 minutes), good video and audio quality, simple slides and colored doodles.

The quizzes, both those during the videos and the review questions, are very good to memorize stuffs.

The simple programming exercises debunk the complexity of the algorithms. The use of Octave (a free alternative to Matlab) allows you to focus on the maths not on technical time-consuming stuffs.

I like the way professor Ng puts the emphasis on the intuition of how the system works before he takes us for a tour of the machinery.

Neural networks back propagation is not a magical trick, it's actually a cost optimization relying on the cost gradient.

Anyway, I think I'd now be able to start tinkering with machine learning in some projects. I hope this experiment will be renewed, I'd like to take another class next semester !

Permalink | Leave a comment »

Changes

Sun, 16 Oct 2011 08:38:00 -0700

I've been pretty busy this past few months, busy sending resume, cover letters and doing interviews.

Let's go back in time a little bit, in March my girlfriend and I moved from Rennes to Paris (actually Versailles) for her new work. As I didn't want to quit my current job at Golaem (and they didn't want me to leave) we decided I was to work remotly from home and come back to Rennes ~2 times per month. I was able to work quite efficiently but quickly felt isolated working alone in my home office.

In late June, I knew this wasn't working for me. From July, I worked from a Golaem's partner office in Paris. This solved the social isolation problem, but as I didn't worked at all with my officemates, I still had no work interaction beside some mails and IM. I know lots of people work this way without any problem but it seems I personally need to have real time work interactions to keep me motivated.

Anyway, I started looking for a job and now I've found a pretty good one ! In January, I'll be lead developper at Masa Group working on high level AI technology.

PS. I've converted my "Group navigation state-of-the-art" report to Latex and created a github repository to make the sources openly available, check it here !

Permalink | Leave a comment »

Airport hall populated with Golaem Crowd

Thu, 15 Sep 2011 05:40:57 -0700

A new showcase video of Golaem Crowd has been published a few days ago. It features our new integration with the rendering engine VRay, but most importantly (from my point of view) it shows the capabilities of our navigation engine. The animation is not that good though, especially compared to the new things we're developing.

Anyway this is a great showcase for the navigation engine I've been developing since more than 2 years. The path following is natural and the collision avoidances are smooth !

Please enjoy !

Permalink | Leave a comment »

Hosted WebGL toy

Tue, 30 Aug 2011 14:55:00 -0700

I'm so trendy, I now have a brand new github account !

I'm using it both as a git repo for my WebGL experiments and, thanks to their well thought pages feature as a hosting facility for the project itself. You can check this awesome work at paperplane.crowdscontrol.net. Stable versions of the project will be published there.

Don't get too excited though, there's nothing impressive to show yet, just a crate to manipulate with the mouse. This is the basis for my world conquest ! my hopefully, someday, working WebGL toy. Anyway there's a ton of things I've done for the first time with this little website and spinning crate: working JavaScript, git repository, light css, markdown files, and of course WebGL.

This is so lame for the moment I'm wondering why I'm even writing this, but, heh, I'm a little proud !

Permalink | Leave a comment »

Learning WebGL

Sun, 21 Aug 2011 04:32:00 -0700

So this is my new home project, I'm learning WebGL.

I haven't worked with a new platform in a long time (except 3DVIA Studio, but let's just say it's not that fun) and I'm getting quite bored by the usual C++ I'm doing at work; I'm just speaking about the code part, I'm hopefully very interested by the algorithms and software architecture parts. I have several reasons to chose WebGL :

I'm a little familiar with the 3D on the web thing and most of what I've seen has not delivered on its promises (VRML, papervision, MPEG-4 System, O3D...);
Some guys are doing really amazing things in webGL;
I never used directly OpenGL or shaders, webGL is an opportunity to get back those basics;
Practice javascript.

Anyway, I'm currently doing those tutorials, so far (I'm at lesson 8) they are really good ! But, as I thing you can't learn anything without a real project, the objective is to do a working little webapp. My current goal is to implement a Reynolds-style bird flocking algorithm, I've never implemented those kind of things in 3D and I don't need lots of assets to get something ! Once I got this working I'll work on a shephering game; nothing is designed yet but I think it might be fun.

I'm currently looking at high level 3D libraries for webGL, I was wondering if someone had done a little comparison of those.

Permalink | Leave a comment »

Autonomous agents nursery

Wed, 10 Aug 2011 00:23:35 -0700

Finally, we've got some Golaem Crowd animated eye candy to show to the world !

Our partner Mikros Image have produced a wonderfull short showcasing our plugin !

We're now ready to take on the world !

Agents order and more videos at http://golaem.com/golaem-project.

Permalink | Leave a comment »

Group Navigation State-of-the-art report

Tue, 21 Jun 2011 09:00:00 -0700

21/06/11 - First complete version of the report as it was published in three parts on the blog (Part 1 - Part 2 - Part 3).

17/10/11 : new LaTeX version of the report, sources can be checked-out on github.

Group Navigation State-of-the-art report

Permalink | Leave a comment »

Group Navigation State-of-the-art report - Part 3, Who's in charge?

Sun, 19 Jun 2011 08:01:00 -0700

Part 1 - Part 2 - Part 3 - Full article

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=1).

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.

Permalink | Leave a comment »

How simple rules determine pedestrian behavior and crowd disasters

Tue, 14 Jun 2011 00:56:00 -0700

Reading french magazine Marianne this week-end, I was intrigued by a small short talking about the work of two CNRS researchers on crowd dynamics.

Knowing the prior work of those two researchers (Medhi Moussaïd and Guy Theraulaz), in particular on small social groups (see my posts on group navigation part1, part2, part 3 to come) I found the work the article is talking about.

This article present an cognitive science approach to autonomous navigation based on observation and experimentation. It is quite similar to some of Julien Pettré's work.

To compute the motion of entities, the presented model relies on two simple heuristics computing the direction and the speed of the movement depending on the distance to collision for the available directions. To this "intentionnal" movements, a contact force is added to take into account the occurence of unavoidable collision in high density cases. This addition is interesting as it save the main model from handling those difficult cases ; I should try this !

In the prior art section, the authors compare heuristic base model (such as theirs) to force base model (such as the social forces by Dirk Helbing, on of the authors). They say, and having implemented social forces I agree, that these models are hard to tune and ahve inherent flaws because they model reaction of one-on-one interactions and doesn't provide a valid solution to combine those forces. Those models are alos very dependent on the framerate due to their integrative nature. This prior art section is really incomplete though, they doesn't talk about other experiment based models (such as Julien Pettré's) nor about geometric methods which are really popular (RVO and co.). Their method is not compared to these approaches. I'll read Medhi Moussaïd Phd Thesis (in french) to see if the comparison work is done in it.

Anyway, and to go back to Marianne's article, I'm impressed by the communication work that's been done as they're cited by general public press (another article in Les Echos was just published) !

Permalink | Leave a comment »

Group navigation state-of-the-art report - Part 2, Stay grouped!

Thu, 19 May 2011 01:43:00 -0700

Part 1 - Part 2 - Part 3 - Full article

Stay grouped!

In order to get a valid simulation of group navigation we first have to design the behavior of the group members. In this part we’ll study two families of methods to obtain groups: using local rules or following a designed formation. Finally we’ll focus on how a member’s individual navigation behavior is affected when part of a group.

Emergence

In most modern navigation engine, the simulated entities are autonomous, their behavior rely on their local "perception” to take action not on an external choreographer. With this approach in mind, several works relies on decentralized behavior to enforce group constraints.

Flocking

At the core of Reynolds’ work (Reynolds 1987; 1999), three steering behaviors allows entities to flock. For any given entity in the group, separation makes him move apart too close neighbors, alignment makes him go in the same direction as other members and cohesion makes him move towards the group’s COM (center of mass). These simple behaviors allow the emergence of a flock. Others took inspiration from this work and adapt it to their architecture using voting steering behaviors (Hostetler and Kearney 2002) or relying on specific environment abstraction such as grids (Loscos, Marchal, and Meyer 2003) or roadmaps (O Burchan Bayazit, Lien, and Amato 2003; Kamphuis and Overmars 2004).

Social relations

In his recent paper, Moussaïd (Moussaïd et al. 2010), extends the social force model (Helbing, Farkas, and Vicsek 2000) to obtain flocking as well as more structured small formation introducing a communication force. The gaze of group members is attracted by the center of interest of the group; here its center of mass (COM) is used. The communication force tries to limit the gaze deviation by decelerating the entity thus enabling the observed V-like formation (cf. part 1).

In order to take into account social relations between members of the group, Qiu uses a member-to-member influence matrix (Qiu et al. 2010). This matrix is taken into account when computing the attraction between members of the group. This approach allows the definition of one or more attractive (or repulsive) members of the group such as more talkative persons or tourist guides.

More rigid formations

Local rules can also exhibit a more strict formation. Taking inspiration from molecular crystals, Balch and Hybinette designed the attachment sites method (Balch and Hybinette 2000). Each entity, given its desired formation, computes several attachment sites on its neighbors and steers to reach the nearest available. The resulting formation arrangement is a direct result of the attachment sites position and it can scale to any number of group members. But as the attachment rules are local, no control on the formation overall shape is possible.

Choreography

While groups whose members are implementing local rules can exhibit convincing behavior, they can’t take into account the group as a whole and thus are not fully controllable. If an exact group arrangement is needed, some of the behavior must be deported to an upper level of control (Musse and Thalmann 2001). In this part we’ll study the three features needed to make a group stay in a given formation: the formation design, the slot assignment and the formation hold.

Design

A formation is basically a list of slots to which members of the group will be assigned. As we focus on pedestrian navigation, a slot is basically a 2D position relative to the group “center”. In a military context two properties of the slot must be added, as we saw in part 1: the orientation and the role (i.e which kind of entity should be assigned to this slot).

Such a formation definition can be designed manually following military principles or artistic concerns (Dawson 2002). Another approach has been taken by Karamouzas and Overmars (Karamouzas and Overmars 2010), they extracted from the data collected by Moussaïd et al. (Moussaïd et al. 2010) a set of typical formations for small social groups of 2 to 4 members. The following figure shows the three kinds of formations they get for groups of 3; similar formations are obtained for groups of 2 or 4.

Assign

We now assume the formation design is chosen and defines as many slots as group members; if not, simple techniques can be used to select the used slots or create needed slots (Silveira, Prestes, and Nedel 2008). The next needed step before our entities can navigate as a group, is to assign each of them to a slot. This part might seem trivial but should be implemented right to avoid destroying the simulation credibility with traffic jams between members of the same groups.

Implementation-oriented papers (Dawson 2002; Millington 2006) describe different solutions and their quality. As everyone should expect, random or index-based (ith members with ith slot) assignment are most of the time really bad: the entities might have to cross each others and to circle around the group to get to their slot. To avoid this bad result, one solution could be to, sequentially assign to each entity, its closest free spot, this solution is easy to implement and might work but last entities might end up to far slots as the closest one are already taken. The best solutions would be to globally minimize the distance the entities are covering to get to their slots but its implementation would lead to an O(n!) complexity as every permutation would have to be tested.

One solution to get a good result and keep a good complexity is a two steps process. First compute for each members of the group what is their cost to be assigned to which slot, allowing certain slot to be specialized for certain entity roles. Then, from the most expensive to assign to the cheapest assign entities to their preferred available slot. This solution might fail to get the optimal assignment but should have decent result while keeping a low complexity O(n2) (Millington 2006).

Another solution works only when no specialized slots are defined. Given a formation design, first sort the slots spatially; for a horizontal line formation, the slot might be sorted from left to right along a horizontal vector. Then sort the group members in the same way; finally assign the ith entity to the ith slot (Dawson 2002).

Maintain

The formation being built, entities are able to reach their slots and to arrange into the designed formation. Let’s see how they are able to maintain it while the group is moving.

In earlier work (Pottinger 1999), a simplistic approach is taken: once part of a formation, entities are no longer responsible for their steering, their position is set at each time step according to the formation. This solution is fine if the group steering (cf. part 3) is robust enough to handle the desired level of collision avoidance.

Using the latter solution, the members do not have an own steering behavior: it is difficult to get anything but a strictly followed formation. To allow formations of individuals, several works uses a more loose approach, members are given a local goal to reach in order to stay in formation and are in charge of fulfilling this goal. A simple approach is to provide each member with a simple “reach target” steering behavior where the target is its slot’s future position (Karamouzas and Overmars 2010; Schuerman et al. 2010). This approach works better if the slots are within navigable space as shown in Schuerman et al. videos. To avoid this problem, Silveira, Prestes and Nedel define a group potential map using slots as attractors and obstacles as repulsors thus providing to members a velocity that maintain the formation while keeping a smooth path when obstacle are present. It allows entity to break formation to pass through tight corridors and around small obstacles (Silveira et al. 2008).

Group members steering

Whether the group is a flock or a formation, the individual steering behaviors, the collision avoidance in particular, of its members has to be considered. We’ve seen that in some case the individual steering behaviors are disabled (Pottinger 1999). In most work though, the group navigation is designed to work in conjunction with its members’, the main problematic is to blend the individual behavior with the group orders.

In some architecture, each entity has several independent behaviors producing different steering orders that are blended together using weight and priorities. In this kind of approach the group orders are executed by another behavior and are part of the final blend (Moussaïd et al. 2010; Qiu 2010; Hostetler and Kearney 2002).

In most modern architecture, a pipeline of behaviors produce a steering order each element taking the previous into account while enforcing new constraints or orders, the last one being collision avoidance (Golaem n.d.; Mononen 2010). The group orders are implemented as a part of this pipeline, they are fed to the following elements among which the collision avoidance (Karamouzas and Overmars 2010b; Silveira et al. 2008).

Schuerman et al. state that while the same collision avoidance behavior can be used by the entities when they are part of a group, it must be adapted. As a matter of fact, collision avoidance algorithms such as RVO (Van den Berg et al. 2008) try to enforce a safe distance to obstacles and other entities that might forbid tight formations. A “boldness” factor is introduced controlling how likely an entity is to yield to other entities during steering. When a strict formation is desired the “boldness” factor of its members is set high making them only try to avoid imminent collisions (Schuerman et al. 2010).

Bibliography

Balch, Tucker, and Maria Hybinette. 2000. “Social potentials for scalable multi-robot formations.” Pp. 73-80 in IEEE International Conference on Robotics and Automation, vol. 1. San Francisco Retrieved (http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=844042).

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.

Dawson, Chad. 2002. “Formations.” Pp. 272-282 in AI Game Programming Wisdom, Steve Rabinedited by. Charles River Media Retrieved (http://introgamedev.com/resource_aiwisdom.html).

Golaem. n.d. “Golaem Path.” Retrieved (http://www.golaem.com/content/products/golaem-sdk/features).

Helbing, Dirk, Illés Farkas, and Tamás Vicsek. 2000. “Simulating dynamical features of escape panic.” Nature (407):487-490.

Hostetler, Terry R, and Joseph K Kearney. 2002. “Strolling down the avenue with a few close friends.” Pp. 7-14 in Third Eurographics Irish Workshop on Computer Graphics. Dublin.

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.

Loscos, Céline, David Marchal, and Alexandre Meyer. 2003. “Intuitive Crowd Behaviour in Dense Urban Environments using Local Laws.” Proceedings of the Theory and Practice of Computer Graphics 122.

Millington, Ian. 2006. “Movement.” Pp. 41-202 in Artificial intelligence for games, David H Eberlyedited by. Morgan Kaufmann.

Mononen, Mikko. 2010. “Navigation Loop.” Paris Game/AI Conference 2010. Retrieved (http://digestingduck.blogspot.com/2010/07/my-paris-game-ai-conference.html).

Moussaïd, Mehdi, Niriaska Perozo, Simon Garnier, Dirk Helbing, and Guy Theraulaz. 2010. “The Walking Behaviour of Pedestrian Social Groups and Its Impact on Crowd Dynamics” Giuseppe Chiricoedited by. PLoS ONE 5(4):e10047.

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.

Pottinger, Dave. 1999. “Implementing Coordinated Movement.” Gamasutra. Retrieved April 20, 2011 (http://www.gamasutra.com/view/feature/3314/implementing_coordinated_movement.php?print=1).

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.

Reynolds, Craig W. 1987. “Flocks, herds and schools: A distributed behavioral model.” Pp. 25-34 in 1987 International Conference and Exhibition on Computer Graphics and Interactive Techniques, vol. 21.

Reynolds, Craig W. 1999. “Steering behaviors for autonomous characters.” Game Developers Conference 1999.

Silveira, Renato, Edson Prestes, and Luciana P Nedel. 2008. “Managing coherent groups” Gerard J Kim, Hong Qin, and Nadia Magnenat-Thalmannedited by. Computer Animation And Virtual Worlds 19(3-4):295-305.

Permalink | Leave a comment »

Group navigation state-of-the-art report - Part 1, Introduction and Taxonomy

Sun, 08 May 2011 11:23:00 -0700

Part 1 - Part 2 - Part 3 - Full article

Introduction

Autonomous human-like characters being able to navigate in a 3D environment finding their paths and avoiding collisions while exhibiting a convincing behavior is now fairly common. The popularity and the quality of recent work (Van den Berg, Lin, and Manocha 2008; Pettré et al. 2009; Ondrej et al. 2010; Mononen 2010) shows that the simulation of hundreds of navigating entities is now within the reach of almost everyone. But most of these work focus on simulating lonely entities taking their neighbors into account only to avoid collisions. Like real ones, our virtual humans should be able to walk down the road with their group of friends. Like real ones, our virtual soldiers must be able to march on enemy positions while staying in formation. And like real ones, our virtual tourists have to be able to enjoy their tour of the Mont Saint-Michel following their guide’s umbrella.

Before we start designing and implementing group navigation behaviors in Golaem Path (Golaem n.d.), let’s first see what others have done. This document is a state-of-the-art study of existing work concerning group and formations navigation with a focus on algorithms and implementations. The first part defines the different categories of navigating groups we’re interested in. The second part focuses on how the group members can stay grouped or in formation during navigation. The third and last part talks about the group’s navigation from path planning to steering and collision avoidance.

Taxonomy

Before we talk velocity, steering behaviors and gradient descent, let’s first present the kind of groups we’re trying to make navigate, their characteristics and their constraints. In this part we’ll divide navigating groups in three categories, flocks, formations and small groups resulting of social influences.

Flocks

A flock is primarily a group of bird traveling together but it can be applied to other animal species as well as humans (e.g. a flock of school children is crossing the street to the swimming pool). Entities in a flock travel at roughly the same speed and form a cohesive group without strict arrangement. In what must be the two most cited articles in the field (Reynolds 1987; 1999), Reynolds studied empirically how flocks members move relatively to each others. With simple behaviors he was able to recreate a flock of autonomous entities, we’ll dig into more details in part 2.

Formation

While flocks do not follow more rules than the cohesion of the group, formations are a kind of group arrangement where members need to enforce strict rules. Both in a combat or a parade, the spatial arrangement, i.e. the relative positions of members, is designed for a precise purpose, tactic or aesthetic; it is the first rule that needs to be followed. Secondly, in a combat context, formation gets much of its usefulness from overlapping fields of fire and sight, that’s why the orientation is another rule to be followed (Dawson 2002). The last rule is to assign entities having the right role to the right slot: archers at the back, footsoldiers facing the enemy. As navigation and military simulation are important for real time strategy games, interesting and working solutions has been developed early: Dave Pottinger, who worked on the Age of Empire series, presented his in a Gamasutra article (Pottinger 1999).

Small Social Groups

See the full gallery on Posterous

Beyond amorphous flocks and rigid military formations, groups that are more common in our everyday life are small and their spatial configuration is the result of social factors and crowd density. Two recent survey focuses on those small social groups (Moussaïd et al. 2010; Peters, Ennis, and O'Sullivan 2009), they lead to the same conclusions.

The two studies were conducted from videos taken at public spaces (in France and Ireland). Their observations show that: there are more groups than single pedestrians, groups of more than four are very rare and most of the groups are, indeed, pairs.

More interesting, it appears the formation adopted by the observed groups is influenced both by the lateral clearance to nearby obstacles and by the social interaction between members of the group. When motion is not constrained (i.e. when obstacles are far and the crowd density is low) a group tends to adopt an abreast formation that facilitates dialog between its members. When facing navigation constraints, to reduce its frontal width, the group compact the formation. And when the lateral space between each member become too thin, i.e. when members are shoulder-to-shoulder, the formation is staggered. The bending of the group is, most of the time, forward (V-like formation) to maintain good communication when a backward bending (inversed-V-like or wedge formation) would be more flexible moving against an opposite flow.

Finally, while groups tend to avoid collisions, with other pedestrians or with obstacles, as a whole they are able to split if needed merging back afterwards.

Bibliography

Dawson, Chad. 2002. “Formations.” Pp. 272-282 in AI Game Programming Wisdom, Steve Rabinedited by. Charles River Media Retrieved (http://introgamedev.com/resource_aiwisdom.html).

Golaem. n.d. “Golaem Path.” Retrieved (http://www.golaem.com/content/products/golaem-sdk/features).

Mononen, Mikko. 2010. “Navigation Loop.” Paris Game/AI Conference 2010. Retrieved (http://digestingduck.blogspot.com/2010/07/my-paris-game-ai-conference.html).

Ondrej, Jan, Julien Pettré, Anne-Hélene Olivier, and Stéphane Donikian. 2010. “A synthetic-vision based steering approach for crowd simulation.” in The 37th International Conference and Exhibition on Computer Graphics and Interactive Techniques.

Peters, Christopher, Cathy Ennis, and Carol O'Sullivan. 2009. “Modeling groups of plausible virtual pedestrians.” IEEE Computer Graphics and Applications 29(4):54-63.

Pettré, Julien, Jan Ondrej, Anne-Hélene Olivier, Armel Crétual, and Stéphane Donikian. 2009. “Experiment-based Modeling, Simulation and Validation of Interactions between Virtual Walkers.” Symposium on Computer animation 1-10.

Pottinger, Dave. 1999. “Implementing Coordinated Movement.” Gamasutra. Retrieved April 20, 2011 (http://www.gamasutra.com/view/feature/3314/implementing_coordinated_movement.php?print=1).

Reynolds, Craig W. 1999. “Steering behaviors for autonomous characters.” Game Developers Conference 1999.

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.

Sheep herd photography taken from http://flic.kr/p/Yuy89

Bastille Day military parade photography taken from http://flic.kr/p/57KrxH

Permalink | Leave a comment »

Golaem Crowd launch

Fri, 29 Apr 2011 02:19:04 -0700

For the past few months we've been working at Golaem on our new product: Golaem Crowd, a Maya plugin dedicated to crowd simulation for the VFX and animation market. While I didn't work on the Maya integration, my work on Golaem Path (navigation mesh generation and navigation behaviors) is a major part of the software and provides much added value.

For the past hours lots of vfx news sites covered the launch and the generated buzz is pretty amazing !

For further information, check www.golaem.com/crowd

Permalink | Leave a comment »

Crowds Control recommends: Artificial Intelligence for Games by Ian Millington

Fri, 25 Feb 2011 05:19:00 -0800

@MJKlaim i've got this one. In fact, im trying to get an overview on what's actually implemented in the real world.

Permalink | Leave a comment »

"Founders at work": Testimonials from the history of IT

Mon, 03 Jan 2011 13:47:21 -0800

I've finished reading "Founders at work" by Jessica Livingston during the past holidays. It's been a very interesting read. There's two reasons why I liked this book.

First, it is a valuable resource concerning IT History, a topic I am fond of. As a matter of fact I think anyone should know well the history of his field of expertise. The lack of chronological references in the computer science courses I followed at school didn't allow me to understand properly how and why technologies (languages, hardware architectures...) rises and falls.

Second, this books shows that there's no magic recipe for a successful product or business. Some founders are technology enthusiasts, some are driven by money only, some wanted to succeed, some just wanted to have fun. This results in very different companies almost all achieving some success.

There's a particular excerpt I particularly liked from the interview of Philip Greenspun, co-founder of ArsDigita, it sums up what are my thought on the job of software engineer (and why I insist not to be a programmer).

To my mind, a programmer is not an engineer, because an engineer is somebody who starts with a social problem that an organization or a society has and says, "OK, here's this problem that we have - how can we solve it?" The engineer comes up with a clever, cost-effective solution to address that problem, builds it, tests it to make sure it solves the problem. That's engineering. If you look at civil engineers, architects, they're all dealing directly with the customer and going through the whole process.

[...]

I want them [computer science students] to be able to sit with the publisher of an online community or an e-commerce site and say "OK, I've looked at your business and your goals; here are some ideas that we can bring in from these 10 other sites that I built, these 100 other sites that I've used." And be an equal partner in the design, not just a coder.

[...]

I was very careful about trying to encourage these people to have an independent professional reputation, so there's code that had their name on it and that they took responsibility for, documentation that explained what problem they were trying to solve, what alternatives they considered, what the strengths and limitations of this particular implementation that they were releasing were, maybe a white paper on what lessons they learned from a project. I tried to get the programmers to write [...].

Permalink | Leave a comment »

The most relevant entry point on computational geometry I know

Fri, 10 Dec 2010 14:41:00 -0800

(Originally a response to @MikkoMononen)

Permalink | Leave a comment »

On crowd simulation validation

Wed, 01 Dec 2010 02:23:48 -0800

This is a response to Mikko's latest post in more than 140 characters...

Autonomous agents navigation is a very wide topic applied to a wide range of specific domains: Military simulation, public spaces design, games, CG FX and animation, training...

Each of this field has its definitions of a 'valid' human-like characters and while the artistic aspect is very important in games or animation it is not for military simulations for exemple. Validations methods are numerous and each is suited for a few parameters only:

Motion captured data in labs can be used to check agents trajectories and velocities in various scenarios (cf. Julien Pettré work) ;
Survey can evaluate various visual aspects of virtual humans (cf. Rachel McDonnell work);
Real world video footage can be treated to validate a simulation output;
Hand measured flows (e.g. number of pedestrians per minutes passing through a door) can validate some aspects too;
but most of the time though, the only validation is the expert's opinion (movie director, military instructor...)

Anyway, in the end, validity comes in consideration only after CPU/GPU/memory usage...

Permalink | Leave a comment »

CASA 2010 report (part 2)

Tue, 30 Nov 2010 07:57:06 -0800

I've been pretty lazy on this blog this past months... Anyway here's the end of the CASA report.

Crowd Simulation Workshop

There was many presentations during that day, more or less interesting, a few of them staid in my mind since then.

The first one was titled "On the interface between steering and animation for autonomous characters" and was presented by Petros Faloutsos.

The authors worked on a problem that every one trying to work on autonomous characters has to face: how to obtain a smooth animation AND an efficient steering behavior (particularly collision avoidance).

As a matter of fact the two problematics are solved separately with, most of the time, a top-down approach:

the steering part is solved in 2D using sliding discs to represent entities, the decision being velocity changes;
the animation engine then chooses the best motion to match the computed velocity.

In 'dumb' mode steering can compute velocities that are unattainable using available motion which results in foot sliding and awkward motions. When less dumb, steering has access to a velocity model describing which velocities are valid, this model can be provided directly from the animation engine. But in order to be manageable in terms of computation complexity, this velocity model is often simplistic and the animation problems still occur.

The approach presented here is quite different, no more disc motion planning, but a footprint planner. Constrained by bio-mechanical rules expressing the distance between the two feet, their sizes as well as the pedestrian body size, the planner place footprints in order to reach a goal and avoid collision. The presented videos was impressive, but the 'real' paper still have to be published, Faloutsos was talking about SIGGRAPH Asia but it seems they didn't make it.

The following presentation I'd like to focus on is Jan Ondrej "Collision avoidance from synthetic vision"

Jan is a Phd Student working under the supervision of Julien Pettré in the Bunraku research group, of which Golaem spun off. This presentation was in fact a real-conditions rehearsal of Jan SIGGRAPH presentation of his paper.

The presented work is quite unique, it propose to solve collision avoidance problem using vision algorithm. A low resolution render of simplified geometry is computed for each entity from its point of view, the result is used by a rather simple algorithm to compute a collision free velocity. And, yes, its quite efficient, and the resulting planning is good (perhaps too good to be human-like, though), anyway let's see the result.

My major take away on this is the inherent advantage of this kind of vision based algorithm: visibility occlusions handling for free (entities hiding each other, walls of difference heights...). What is costly using traditional geometry queries is almost free here thanks to the render phase. I hope I'll be able to experiment with this soon !

The rest of the workshop features other interesting talk about various aspects of crowd simulations including :

An overview of Legion software;
A presentation of the work done by Disney Imagineering R&D department and SpirOps on crowd simulation in theme parks;
An overview of Ming Lin's UNC Gamma group work;
Various presentation about Dublin Trinity college GV2's work on a populated virtual Dublin.

An interesting workshop and the chance to meet the cream of crowd simulation researchers !

Permalink | Leave a comment »

CASA 2010 report (part 1)

Tue, 22 Jun 2010 19:31:23 -0700

Well It's been a long time since I posted here... I've been pretty busy since the beginning of 2010. Anyway, here's a report of the part of this year CASA I attended to. CASA, the yearly conference on Computer Animation and Social Agents, was held in St Malo, France, from 31/05/10 to 03/06/10 (further information here). As its name implies, the conference focuses are :

Animation techniques (motion capture, motion control, physics-based animation...)
Social agents (emotions, facial animation, crowd simulation...)

During the conference, I only attended to Craig W. Reynolds keynote and to the collocated crowd simulation workshop.

Craig W. Reynolds Keynote

Craig Reynolds is to autonomous agents navigation what Louis Pasteur is to vaccination, he virtually invented the field. His seminal work of 1987 introduced steering behavior, simple rules to models the way autonomous agents navigate in groups. When I worked on the bibliography of my master's thesis, I was amazed to see that almost every paper I read was citing this 1987 paper or its 1999 little brother ; Google scholar count more than 3000 citations ! One other thing that is quite interesting about Reynolds work is its rarity, I personally know only those two articles (and google scholar tends to agree). Needless to say I was really eager to attend to the legend's talk. Well, I was quite disappointed. The talk he gave was titled "Crowds and emergent teamwork", it presented Reynolds observation on emergent constructions in nature, done mostly by insects (ants, termites, bees...), and his attempts to design autonomous agents able to do the same. The final model gave agents simple rules to add bricks to the construction. The same king of emergent construction was observed. The rest of the keynote was filled by what seems to be the entire flickr account of the host : insects construction (no global plan but a functional emergent structure), human constructions (everything is designed globally)... Some aspects of the keynote were interesting but nothing really new, controversial or brilliant... I do think my expectation were too high though... The crowd simulation workshop report will follow shortly...

Permalink | Leave a comment »

std::vector is NOT a std::vector containing bools

Sun, 14 Feb 2010 21:29:46 -0800

Everything in the title, but let me explain... Lately I've spent a lot of time trying to make a serialization/deserialization work with the huge piece of software I'm working on at Golaem. Anyway I came across a strange compiler error when trying to deserialize a std::vector<bool>. Here's what our serialization engine is like :

template<T>
void read(std::vector<T> & myVector, Bitstream myStream)
{
  unsigned int size;
  read(size,myStream);
  vector.resize(size);
  for (unsigned int i = 0 ; i < size ; i++)
  {
    read(vector[i],stream);
  }
}
void read(bool & myBool, Bitstream stream)
{
  ...
}
template<T>
void write(const std::vector<T> & myVector, Bitstream myStream)
{
  unsigned int size;
  write((unsigned int)myVector.size(),myStream);
  for (unsigned int i = 0 ; i < myVector.size() ; i++)
  {
    write(vector[i],stream);
  }
}
void write(const bool & myBool, Bitstream stream)
{
  ...
}

The serialization worked ok, but when trying the deserialization I got a cryptic compiler error :

impossible to convert from 'std::_Vb_reference<_Sizet,_Difft,_MycontTy>' to 'bool &'

WTF ? This code worked perfectly for doubles, ints and other basic types bools should be fine no ? After a quick google and follow links session I stopped on the cplusplus.com reference page of the std::vector. You should go and read this page completly, yep now ! I give you a few seconds... OK you should've finished now, and yeah, you read well, std::vector<bool> is a template specialization of std::vector<T> and it does not have the the same properties : std::vector<bool>::operator[] doesn't returns a reference to a bool but a specially defined type. I love C++ and especially the STL... Yes, in most cases it's transparent because this type defines a transtyping operator to bool. Yes, it is designed to save space as each element of a std::vector<bool> takes only 1 bit. But, it is inconsistent (std::deque<bool> is a std::deque of bools), opposed to the basic principles of c++ templates, and, apparently not normalized (see this open letter wrote by Herb Sutter the day i turned 15). Another good joke from our pals at C++ ISO committee...

Permalink | Leave a comment »