Che bello...

...quando le cose iniziano a funzionare.

Tra qualche anno, son certo che la programmazione GPGPU sarà all'ordine del giorno ed esisteranno efficaci strumenti di supporto allo sviluppo e al debug.

Fino ad allora resterà puro autolesionismo.

ARM about to create connectionist's paradise

ARM is developing a new kind of architecture which is supposed to run a simulation of the human brain. We're not talking about an artificial intelligence here, the project is about  the reconstruction of the neuronal topology. In other words, they could prove that connectionist paradigm is right, that is, the brains cause the minds.

SpiNNaker, that's the name of the system, is based on a chip developed by Steve Furber, the father of ARM's 32-bit RISC processor. Every chip will contain 20 cores on a single die; one of them is designated as a "head" and the others run the "neuron simulation".

All cores are interconnected on the die itselft, and all processors (thousands in the final system) are interconnected through a "Globally Asynchronous Locally Synchronous" architecture. The simulated neurons can "fire" to any other neuron in about 1ms, which is practically the same of humans.

Obviously, Furber and his team are far from recreating the 90billion neurons topology of human brain; according to the well known Moore's law, in a couple of decades a full simulation would be possible but, meanwhile, better models of the brain could be studied and exploited.

Fascinating complexity

Here we go, another little step towards Master Degree! "Complex systems" is achieved and with full score, thanks to a crowd simulation based on Craig Reynolds' BOIDS and rendered by my own 3D engine "PLT".

I love emerging models - as one can easily foresee by reading the name of this blog - and BOIDS is no exception. A few rules and parameters, two constraints and a bit of randomness and we have a hell of algorithm, almost chaotic and showing a lot of unexpected and non-designed behaviours: formation of queues, spontaneous groups, and so on. Michele and I did a validation study, basing on the previous works of Crystals' Project, a joint effort in crowds simulation. Our model worked well, mathing the expected timings and behaviours, at least with reasonable agents' density; being BOIDS a simple reactive multi-agent system, our pedestrian do not embedded sufficient "intelligence" and can easily fall in many subtle cul-de-sac. It's a good result, anyway, and leaves a lot of space for further investigation.

The BOIDS are back in town!

During the last lesson of complex systems course, prof. Vizzari showed a crowd simulation based on BOIDS, an intriguing model invented by Craig Reynolds in 1986 that simulates bird flocks, fish schools and all that kind of self-organizing masses of living stuff. The basic model is based on three simple assumptions:

1. each boid moves toward the other flockmates (cohesion)
2. each boid moves away from crowded situations (separation)
3. each boid follows the direction of the rest of the flock (alignment)

Even in its simplest formulation the model works very well, and gives a pleasant feeling of viability. I turned the model from 3D to 2D, by putting all boids on the y=0 plane, and here we go: we have a simple crowd simulator.

There exist several approaches to crowd simulation (like cellular automata or multi-agent systems) but I do think that BOIDS have many interesting capabilities.

In fact, one of the open issues in crowd simulations is the sponteneous formation of groups because of common goals, shared costumes, socio-political aspects, familiar relationships and so on. BOIDS leave a lot of space for embedding this wide spectrum of behaviours, whilst the model itself mantains the proxemic distances between people and let them gather peacefully, by the rules decribed above.

The video I embed shows my model in a simple scenario made of four groups (yellow, red, green and blue). Green people have their own goal to follow; red and blue have a shared one. Yellow people just walk around the space, with no specific purpose. In the middle of the screen there's a strong repulsor which keeps boids away. The dynamic works as I expect: there's the formation of clusters, boids belonging to the same group tend to aggregate and find their way even in overcrowded situations. What's fascinating is the emerging, unexpected behaviour of yellow ones: some of them hold still, some dodge the crowd, many other enter the moving groups and follow them wherever they go, conditioned by the first rule.Very nice.

Hajj - the annual pilgrimage to Mecca - is
one the most interesting scenario to simulate

Still, there's a lot of work to do that I'll share with my brilliant coursemate Michele. For instance, we'll try to identify the correct parameters that fit the experimental results, incorporating Elias Canetti's proxemic dynamics as well. We also could find a way to introduce different kind of non-penetrable contraints (walls, doors, and such). There's the problem of instructing complex goals (like finding a way to an exit in non-straight situations or following a leader), with an eye to stability and realism. Finally, there's lot of optimization to do: I wrote the code as general classes and new rules can be easily introduced by pushing a new function pointer to a "rules" vector. That's very flessible, allows a very rapid prototyping but it's very inefficient: the naive algorithm is O(n²), because every boid's position needs to be compared with the rest of the flock, and every rule is computed on its own, adding a costant factor. Too slow for serious business like sport events, concerts, and religious pilgrimages, just to name a few of the typical simulations that require millions of individuals at once.