Crowds control

virtual humans, AI, 3D stuffs…

ml-class

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.

Screenshot

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 !

Changes

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 !

Airport hall populated with Golaem Crowd

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 !

Hosted WebGL toy

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 !

 

Learning WebGL

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.

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

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.
Passing_through_a_narrow_passage_using_naive_or_follow-the-leader_approach
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.

Linear_interpolation_between_formations
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.
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.

How simple rules determine pedestrian behavior and crowd disasters

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) !
Posterous theme by Cory Watilo
  
​