Bernardino Frola

Contatti

Lavoro di tesi In breve

Vi parlo brevemente di cosa mi occupo nel mio lavoro di tesi:

  • Modelli compotamentali interattivi per grandi quanti quantità di NPC ("non-playable character"), come ad esempio:
    • Umani: folle, formazioni;
    • Animali: stormi, branchi;
    • Altro: veicoli, flotte.
  • GPGPU, modelli comportamentali su hardware grafico.
    • Esecuzione efficiente (parallela) di interrogazioni spaziali (chi sono i miei vicini?).
  • Intelligenza artificiale:
    • Pianificazione e ricerca percorsi;
    • Comportamento di basso livello (gestione collisioni, seguire percorsi, evitare vicini, ...);

Seminari

  • Modelli comportamentali su GPU con CUDA (17/11/08) - Slide
  • Modelli comportamentali interattivi per la simulazione di folle - Parte1 [ 1 ] - [ 2 ] (06/06/08) - sono discussi gli approcci seguiti fino ad oggi. Riassumendo, questi approcci si possono suddividere nelle seguenti categorie:
    • Dinamiche particellari (fisica e fluidi);
    • Discretizzazione dell'ambiente.
    • Forze sociali;
    • Regole (locali e ambientali); (qui termina la prima divisione delle slide)
    • Modelli congnitivi;
    • Navigazione globale;
  • Modelli comportamentali interattivi per la simulazione di folle - Parte2 (13/06/08) - affronta un discorso orientato alle prestazioni.
    • Quanti agenti si riesce a simulare in real-time.
    • Quali sono le tecniche di ottimizzazione maggiormente adottate.

Qualche dettaglio

Cosa si vorrebbe fare

  • L'ambito è la simulazione di modelli comportamentali.
  • L'obbiettivo è realizzare un sistema orientato ai grandi numeri
  • L'idea è partire da un sistema esistente ed ottimizzarlo
    • Il sistema esistente è la libreria OpenSteer, frutto della passione di Craig Reynolds per i modelli comportamentali.
    • L'ottimizzazione è l'utilizzo della GPU via nVidia CUDA.

Cosa si è fatto

Prima fase del lavoro è stata modellare il calcolo del vicinato in CUDA, cercando di "tirare" al massimo le prestazioni.
La scelta struttura dati da utilizzare ha svolto un ruolo fondamentantale. Tale scelta è stata ispirata da un modello per per il calcolo delle collisioni su GPU utilizzato dalla nVidia. Al centro dell'attenzione si pone il metodo di immagazzinamento ed ordinamento dei dati in memoria, punto cruciale di qualunque realizzazione in CUDA. Lo studio è proseguito alla ricerda di sistemi di caching delle informazioni più adatte allo scopo.
In contemporanea si è proceduto nella strutturazione del sistema per la simulazione di modelli comportamentali. Sono stati tradotti in CUDA le sezioni fondamentali della libreria OpenSteer. Tra queste ritroviamo la gestione dei comportamenti alla base del flocking, ovvero, separazione, coesione ed allineamento.
Il risultato di queste fasi è un sistema di simulazione ancora povero di dettagli ma realizzato completamente in CUDA, in grado di raggiungere prestazioni ben oltre i limiti imposti dalla normale computazione su CPU.
Allo stato attuale, con una versione del sistema che tinene conto per ogni agente un numero esiguo di vicini (7) e basato su una grafica estremamente semplice è possibile simulare 128K boids a circa 25fps, 250K a 12 e 512K a circa 6 (dettagli sul commento al video [1])

Cosa si sta facendo

Attualmente il lavoro continua nella ottimizzazione delle prestazioni e della memoria in uso. Questo coinvolge nuovi sistemi di hashing dei dati e l'utilizzo della famosa shared memory sulla quale le nuove GPU nVdia possono contare. Allo stesso modo continuano gli sforzi nell'aumentare le features e la generalità del sistema di simulazione.

Bibliografia

  • AISeek (2005), Intelligence for NewWorlds. A Whitepaper.
  • BALLERINI, M.; CABIBBO, M.; CANDELIER, N.; CAVAGNA, A.; CISBANI, E.; GIARDINA, I.; LECOMONTE, V.; ORLANDI, A.; PARISI, G.; PROCACCINI, A.; VIALE, M. & V.ZDRAVKOVIC (2004), Interaction Ruling Animal CollectiveBehaviour Depends on Topological ratherthan Metric Distance: Evidence from a FieldStudy.
  • BAYAZIT, O. B.; LIEN, J. M. & AMATO, N. M. (2002), Better groupbehaviors in complex environments with global roadmaps.
  • Breitbart, J. (2008), Case studies on GPU usage and data structure design.
  • Breitbart, J. (2008), A framework for easy CUDA integration in C++ applications. Diplomarbeit.
  • Chenney, S. (2004), Flow tiles, SIGGRAPH 2004.
  • COURTY, N. & MUSSE, S. R. (2005), Simulation of large crowds inemergency situations including gaseous phenomena.
  • ERRA, U.; CHIARA, R. D.; SCARANO, V. & TATAFIORE, M. (2004), Massive Simulation using GPU of a distributed behavioral modelof a flock with obstacle avoidance.
  • FICKETT, M. & ARKO, Z. (2007), GPU Continuum Crowds.
  • FUNGE, J.; TU, X. & TERZOPOULOS, D. (1999), Cognitive modeling: Knowledge,reasoning and planning for intelligent characters, SIGGRAPH 1999.
  • GOLDENSTEIN, S.; KARAVELAS, M.; METAXAS, D.; GUIBAS, L.; AARON, E. & GOSWAMI, A. (2001), Scalable nonlinear dynamicalsystems for agent steering and crowd simulation..
  • Green, S. (2008), CUDA particles, nVidia research.
  • HEIGEAS, L.; LUCIANI, A.; THOLLOT, J. & CASTAGNE, N. (2003), A physicallybased particle model of emergent crowd behaviors., GraphiCon 03.
  • HELBING, D.; FARKAS, I. & VICSEK, T. (2000), Simulatingdynamical features of escape panic, Nature.
  • HELBING, D.; MOLNAR, P.; FARKAS, I. J. & BOLAY, K. (2001), Self organizing pedestrian movement.
  • JEONG, W. & ROSS, T. (2007), A fast eikonal equation solver for parallel system.
  • KAMPHUIS, A. & OVERMARS, M. H. (2004), Finding paths forcoherent groups using clearance, SIGGRAPH 2004.
  • KARLSSON, B. F. (2003), Issues andApproaches in ArtificialIntelligence MiddlewareDevelopment for Digital Gamesand Entertainment Products.
  • KIPFER, P.; MARK, S. & WESTERMANN, W. (2004), UberFlow: A GPUBasedParticle Engine, ATI research.
  • KNAFLA, B. & LEPOLD, C. (2007), Parallelizing a Real Time SteeringSimulation for Computer Games with OpenMP.
  • KWON, T.; LEE, K. H.; LEE, J. & TAKAHASHI, S. (2007), Group Motion Editing.
  • LAKOBA; KAUP & FINK (2005), Modification of the Helbing Molnar Farkas Vicsek Social Force Model for Pedestrian Evolution.
  • LAMARCHE, F. & DONIKIAN, S. (2004), Crowd of virtual humans: anew approach.
  • LATTA, L. (2004), Building a Million Particle System, nVidia research.
  • LOSCOS, C.; MARCHAL, D. & MEYER, A. (2003), Intuitive crowd behaviour in dense urban environments using local laws..
  • MAIM, J.; HAEGLER, S.; YESING, B.; PASCAL, M.; THALMANN, D. & GOOL, L. V. (2007), Populating Ancient Pompeii with Crowds of Virtual Romans, SIGGRAPH2007.
  • MORINI, F.; YERSIN, B.; MAIM, J. & THALMANN, D. (2007), Real-time scalable motion planning for crowds.
  • Musse, S. R. & Thalmann, D.Springer, ed. (2007), Crowd Simulation.
  • Musse, S. R. & Thalmann, D. (2001), Hierarchical model for real time simulation of virtual human crowds.
  • MUSSE, S. R. & THALMANN, D. (1997), A model of human crowd behavior: Group inter-relationship and collision detection analysis.
  • Nguyen, H. (2007), GPU Gems 3, Addison Wesley Professional.
  • Nvdia (2008), NVIDIA CUDA Compute Unified Device Architecture - Programming guide.
  • Nvidia (2008), NVIDIA CUDA Compute Unified Device Architecture - Reference Manual.
  • PELECHANO, N.; ALLBECK, J. & BADLER, N. (2007), Controlling Individual Agents inHigh Density Crowd Simulation, SCA-SIGGRAPH 2007.
  • PELECHANO, N.; OBRIEN, K.; SILVERMAN, B. & BADLER, N. (2005), Crowd simulation incorporating agent psychological models, rolesand communication..
  • PELECHANO, N.; STOCKER, C.; ALLBECK, J. & BADLER, N. (2008), Being a Part of theCrowd: Towards Validating VR Crowd Using Presence.
  • PETTRE, J.; LAUMOND, J. P. & THALMANN, D. (2005), A navigation graph for real-time crowdanimation on multilayered and uneven terrain.
  • M. J.; METOYER, R. A. & HUNTER, ZAWORSKI, K. (2003), Parallel Implementation of the Social Forces Model.
  • Reynolds, C. (2006), Big Fast Crowd.
  • Reynolds, C. (2004), OpenSteer Online Documentation.
  • Reynolds, C. (2000), Interaction with Groups of autonomous Characters, GDC 2000.
  • Reynolds, C. (1999), Steering Behaviors For Autonomous Characters, GDC 2000.
  • Reynolds, C. (1987), Flocks, herds, and schools: A distributed behavioral model., SIGGRAPH 1987.
  • SHAO, W. & TERZOPOULOS, D. (2005), Autonomous pedestrians, SCA-SIGGRAPH 2005.
  • SUNG, M.; GLEICHER, M. & CHENNEY, S. (2004), Scalable behaviors for crowd.
  • SUNG, M.; KOVAR, L. & GLEICHER, M. (2005), Fast and accurategoal directed motion synthesis for crowds, SIGGRAPH 2005.
  • TANTISIRIWAT, W.; SUMLEEON, A. & KONONGCHAIYOS, P. (2007), A Crowd Simulation Using Individual-Knowledge-Merge based PathConstruction and Smoothed Particle Hydrodynamics.
  • TECCHIA, F.; LOSCOS, C.; CONROY, R. & CHRYSANTHOU, Y. (2001), Agent behavior simulator (ABS): A platform for urban behavior development.
  • TREUILLE, A.; COOPER, S. & POPOVIC, Z. (2006), Continuum Crowds, SIGGRAPH 2006.
  • TU, X. & TERZOPOULOS, D. (1994), Artificial fishes: Physics, locomotion,perception, behavior, SIGGRAPH 1994.
  • YERSIN, B.; MAIM, J.; CIECHOMSKI, P. D. H.; SCHERTENLEIB, S. & THALMANN, D. (2007), Steering a virtualcrowd based on a semantically augmented navigation graph..
  • YUE, B. & DEBYL, P. (2005), The State ofthe Art in Game AI Standardisation.
  • ZHOU, B. & ZHOU, S. (2004), ParallelSimulation of Group Behaviors.