TY - JOUR
ID - RazaviGaudMozayaniKoukam2011_131
PY - 2011-01-20
T1 - Multi-agent based simulations using fast multipole method: application to large scale simulations of flocking dynamical systems
AU - Razavi,Seyed Naser
AU - GAUD,Nicolas
AU - MOZAYANI,Nasser
AU - KOUKAM,Abderrafiaa
N2 - This article introduces a novel approach to increase the performances of multi-agent based simulations. We focus on a particular kind of multi-agent based simulation where a collection of interacting autonomous situated entities evolve in a situated environment. Our approach combines the fast multipole method coming from computational physics with agent-based microscopic simulations. The aim is to speed up the execution of a multi-agent based simulation while controlling the precision of the associated approximation. This approach may be considered as the first step of a larger effort aiming at designing a generic kernel to support efficient large-scale multi-agent based simulations. This approach is illustrated in this paper by the simulation of large scale flocking dynamical systems.
JA - Artificial Intelligence Review
IS - 1
VL - 35
SP - 53
EP - 72
SN - ISSN 02692821
KW - multi-agent based simulations
KW - fast multipole method
KW - microscopic simulations
KW - large scale flocking dynamical systems
UR - http://dx.doi.org/10.1007/s10462-010-9183-9
UR - http://www.multiagent.fr/Special:FOAF/bib:131
ER -
TY - CHAP
ID - RazaviGaudKoukamMozayani2011_132
PY - 2011-07-20
T1 - Using Motion Levels of Detail in the Fast Multipole Method for Simulation of Large Particle Systems
AU - Razavi,Seyed Naser
AU - GAUD,Nicolas
AU - KOUKAM,Abderrafiaa
AU - MOZAYANI,Nasser
N2 - This article introduces a novel approach to increase the performances of N-body simulations. In an N-body simulation, we wish to evaluate all pairwise interactions between N bodies or particles. The direct computation of all pairwise interactions requires O(N2) time, which is clearly prohibitive for a very large N. Our approach combines the Fast Multipole Method (FMM) coming from computational physics with motion levels of detail from computer graphics. The main goal is to speed up the execution of the N-body simulations while controlling the precision of the associated approximation, a natural trade-off between accuracy and efficiency common in the field of simulation. At each simulation cycle, the motion levels of detail are generated automatically and the appropriate ones are chosen adaptively to reduce computational costs. The new approach follows the overall structure of the FMM. However, clusters are approximated using their Center of Mass (CoM) in force computations. A similarity measure is used to decide which clusters can be approximated without any significant loss in the accuracy of the simulation. The proposed approach is tested for Coulombic system, in which N charges induce potentials to each other. The preliminary results show a significant complexity reduction without any remarkable loss in the visual appearance of the simulation, indicating the potential use of the proposed model in the simulation of a wide range of N-Body systems.
AD - Orlando, Florida, USA
JF - the 15th World Multi-Conference on Systemics, Cybernetics and Informatics (WMSCI)
PB - International Institute of Informatics and Cybernetics
KW - Dynamics Simplification
KW - Fast Multipole Method
KW - Motion levels of Detail
KW - Multi-Agent Based Simulation
L1 - /extensions/ICAPManager/pdf/RazaviGaudKoukamMozayani2011.pdf
UR - http://www.multiagent.fr/Special:FOAF/bib:132
ER -
TY - CHAP
ID - RazaviGaudKoukamMozayani2012_367
PY - 2012-06-17
T1 - An Automatic Learning System to Derive Multipole and Local Expansions for the Fast Multipole Method
AU - Razavi,Seyed Naser
AU - GAUD,Nicolas
AU - KOUKAM,Abderrafiaa
AU - MOZAYANI,Nasser
N2 - This paper introduces an automatic learning method based on genetic programming to derive local and multipole expansions required by the Fast Multipole Method (FMM). FMM is a well-known approximation method widely used in the field of computational physics, which was first developed to approximately evaluate the product of particular N ×N dense matrices with a vector in O(N log N) operations. Later, it was applied successfully in many scientific fields such as simulation of physical systems, Computer Graphics and Molecular dynamics. However, FMM relies on the analytical expansions of the underlying kernel function defining the interactions between particles, which are not always obvious to derive. This is a major factor limiting the application of the FMM to many interesting problems. Thus, the proposed method here can be regarded as a useful tool helping practitioners to apply FMM to their own problems such as agent-based simulation of large complex systems. The preliminary results of the implemented system are very promising, and so we hope that the proposed method can be applied to other problems in different application domains.
AD - Shenzhen, China
JF - Third International Conference on Swarm Intelligence (ICSI), Advances in Swarm Intelligence, Lecture Notes in Computer Science 7332
PB - Springer-Verlag
SP - 1
EP - 10
SN - ISBN 978-3-642-31019-5
KW - Agent-Based Simulation
KW - Complex Systems
KW - Fast Multipole Method
KW - Genetic Programming
L1 - /extensions/ICAPManager/pdf/RazaviGaudKoukamMozayani2012_1.pdf
UR - http://dx.doi.org/10.1007/978-3-642-31020-1_1
UR - http://www.multiagent.fr/Special:FOAF/bib:367
ER -
TY - JOUR
ID - RazaviGaudKoukamMozayani2012_380
PY - 2012-12-16
T1 - Automatic dynamics simplification in Fast Multipole Method: application to large flocking systems
AU - Razavi,Seyed Naser
AU - GAUD,Nicolas
AU - KOUKAM,Abderrafiaa
AU - MOZAYANI,Nasser
N2 - This paper introduces a novel framework with the ability to adjust simulation’s accuracy level dynamically for simplifying the dynamics computation of large particle systems to improve simulation speed. Our new approach follows the overall structure of the well-known Fast Multipole Method (FMM) coming from computational physics. The main difference is that another level of simplification has been introduced by combining the concept of motion levels of detail from computer graphics with the FMM. This enables us to have more control on the FMM execution time and thus to trade accuracy for efficiency whenever possible. At each simulation cycle, the motion levels of detail are updated and the appropriate ones are chosen adaptively to reduce computational costs. The proposed framework has been tested on the simulation of a large dynamical flocking system. The preliminary results show a significant complexity reduction without any remarkable loss in the visual appearance of the simulation, indicating the potential use of the proposed model in more realistic situations such as crowd simulation.
JA - The Journal of Supercomputing
IS - 3
PB - Springer US
VL - 62
SP - 1537
EP - 1559
SN - ISSN 0920-8542
KW - Dynamics simplification
KW - Fast Multipole Method
KW - Multi-agent based simulation
KW - Flocking
UR - http://dx.doi.org/10.1007/s11227-012-0816-4
UR - http://www.multiagent.fr/Special:FOAF/bib:380
ER -
TY - JOUR
ID - RazaviGaudKoukamMozayani2012_450
PY - 2012-10-02
T1 - A genetic programming based learning system to derive multipole and local expansions for the fast multipole method
AU - Razavi,Seyed Naser
AU - GAUD,Nicolas
AU - KOUKAM,Abderrafiaa
AU - MOZAYANI,Nasser
N2 - This paper introduces an automatic learning algorithm based on genetic programming to derive local and multipole expansions required by the Fast Multipole Method (FMM). FMM is a well-known approximation method widely used in the field of computational physics, which was first developed to approximately evaluate the product of particular N×N dense matrices with a vector in O(Nlog N) operations, while direct multiplication requires O(N2) operations. Soon after its invention, the FMM algorithm was applied successfully in many scientific fields such as simulation of physical systems (Electromagnetic, Stellar clusters, Turbulence), Computer Graphics and Vision (Light scattering) and Molecular dynamics. However, FMM relies on the analytical expansions of the underlying kernel function defining the interactions between particles, which are not obvious to derive. This is a major factor that severely limits the application of the FMM to many interesting problems. Thus, the proposed automatic technique in this article can be regarded as a very useful tool helping practitioners to apply FMM to their own problems. Here, we have implemented a prototype system and tested it on various types of kernels. The preliminary results are very promising, and so we hope that the proposed method can be applied successfully to other problems in different application domains.
JA - AI Communications
IS - 4
PB - IOS Press
UR - http://iospress.metapress.com/content/964105681v528t63/fulltext.pdf
VL - 25
SP - 305
EP - 319
SN - ISSN 0921-7126
KW - Fast Multipole Method
KW - genetic programming
KW - local expansion
KW - multipole expansion
UR - http://iospress.metapress.com/content/964105681v528t63/fulltext.pdf
UR - http://dx.doi.org/10.3233/AIC-2012-0538
UR - http://www.multiagent.fr/Special:FOAF/bib:450
ER -