A known method for modeling and simulating the dynamics of multi-agent systems is the Petri nets. It provides the best results? It can be used for large systems? Know you a better way?
Traditionally, MAS are modeled and simulated using platforms as JADE, but where the simulation is not based on an analytical or logical model (deterministic
or statistic). In JADE and other platforms, we have an evolution of MAS driven by external events (nondeterministic). This creates difficulty in using MAS in industrial
and technical applications, where the determinism is the rule, but where the traditional methods (according to IEC 61131-3 standard) are exceeded.
I tried a simulation of MAS using FSM language implementation in Erlang, a functional language. I immediately found that FSM modeling and simulation using the MAS is not a good idea for somewhat larger
systems, because of their complexity .
A better solution would be Petri nets, but I have not found good examples of use for large MAS. Perhaps even the idea of applying a tool to MAS for analytical or logical modeling or simulation is not suitable. MAS systems are usually complex non-deterministic systems. Perhaps this topic has been debated somewhere, sometime, and I want to know if this has occurred.
In my view, MAS are generally too complex systems to be amenable to modeling with one universal type of models. It depends on what aspects of MAS are of your primary interest and importance: knowledge, communication, beliefs, intentions, actions, strategic abilities, etc. My preference amongst those models currently in use are concurrent game models with incomplete information (see e.g. http://link.springer.com/chapter/10.1007/1-4020-4094-6_3) or see links here for more recent references: http://www2.imm.dtu.dk/~vfgo/ESSLLI2013/LogicsForMASandStrategicReasoning-ESSLLI2013.html
These models are relatively good to model static knowledge and abilities, but not so much the dynamics of these. I am currently working on developing a more universal modelling framework for MAS, combining useful features from several others. This work is not a completed and published yet, but here is a relatively recent set of slides that gives an idea of that framework: http://www2.imm.dtu.dk/~vfgo/ArchiveSlides/Toulouse%20April%202011%20Logic%20for%20Information%20Security%20Trans.pdf (see the 2nd half).
I try to reconstruct the question, because the argument is very broad.
You want to model
- 1) the structure and the dynamics of a MAS
- 2) via a mathematical method (either logical or analytical).
One of the more investigated problems in MAS is the connection between micro and macro behaviour. If you want define the structure and dynamics of the MAS only at individual level, then, because of the non-determinism of the interaction of aggregations of individuals, the structure and dynamics at macro level cannot easily be predicted in advance. In this respect you may look on the literature on complex systems for formal methods. All mathematical methods cannot avoid to integrate a probabilistic stance.
If you want to model the MAS also at meso and macro level, you may check all the literature or organizational and normative MAS. (Organizational) rules are proposed to govern the individual level, in respect to higher-order behaviour. For instance, check the NorMAS workshops.
Finally, the most important question. What kind of agents are you referring to?
Cognitive agents (e.g. provided with a BDI paradigm) or "simple" behavioural agents?
In the second case, you may also refer to different mathematical models, like actors or also process algebra, which provide formal models to cope with concurrency and to validate systems involving concurrency.
In the first case, you can look at this: Behrens, T. M. and Dix, J. (2008). Model checking multi-agent systems with logic based Petri nets. Annals of Mathematics and Artificial Intelligence, 51(2-4):81–121.
Constructivist, either logical or analytical, should be completed with Ecological forms of rationality. This is a core issue with ABM as a generative bottom-up method.
See Vernon Smith Book Rationality in Economics : Constructivist amd Ecological Forms. 2008 Cambridge Un.Press
Your question is very general. Many mathematical models were proposed since the early 90s until now (temporal and modal logic, set theory, algebra, combinations of those, ...). It mainly depends on what type of MAS you want to model and, more precisely, what part of the part is to be modelled.
Eurgen, You are true, not easy to model logical or semantical agents.
That's I worked. So I encourage you to model the reasoning of your agent with protegé and OWL ontologies. Then you should implement an ACL Agent communication language in JADE or other platform. I personaly used a Knowledge representation language (KRL) for memory, communication and reasoning which is also designed to read/import OWL knowledge. I validate my own inference engine with CPNTools (colored stochastic petri nets). If you want to know more, read my book or contact me. I will answer you with pleasure. cheers.
No single method will satisfy our model in the respect of immersive, real, realiable for all movement, in my view. However, some general rules would be:
1. In MAS the following tendency is almost always happen. The leader and follower actor/agent would be debatable and it could logical or analytical method.
2. The barrier, attractor, 'reppelor' would occur in some kind of agents.
3. No simple grouping of agents in reality but in the model we always assume we are able to group the agents.
My concern, fractal might be the best for modelling MAS but the fractal concept itself cannot be limited with any traditional pattern.
as noted in most of the previous comments, the answer to your question depends a lot on what your are trying to find out as well as on where you start from.
If you already have a model in form of an algorithm, I guess Petri nets and logical model checking are a proper starting point.
If you start from a formal model I would generally suggest to write down the iterative scheme explicitly in formulas. With that you probably get a feeling of the "best" formal method.
We have been doing that with simple Agent-based models writing them down explicitly as a stochastic choice of deterministic update rules. This gives rise to Stochastic Dynamical Systems or Markov Chains. We have been using the latter in Banisch et al. (2012), Social Networks, 34:549-561 (arxiv.org/abs/1108.1716).
In principle, this is generalizable. But, of course, it may become complicated especially if the agents themselves become more complex.
There are many methods available such as Petri Nets ( more than 7 in this category) , UML, Object oriented methods as well. Any one standard method can be used or a combination can be done or customization can also be done. Tools are readily available too for modelling.
First is needed to distinguish between models and its implementation. Models are mainly a representation of the reality you want to analyze and includes the modeling hypotheses needed. In MAS the inherent complexity of those systems and the multidisciplinary teams that participate in the model definition, makes needed the formal definition of the structure and the behavior of the inner elements that compose the system.
Following this approach, recently we publish a book that describes some formal languages can be used to do this:
One you have the model, the implementation can be done using several tools, some of them specifically designed for MAS systems, but, and because you own the model, you are not constrained to any specific tool, and you can also use generic simulation tools, or tools specifically designed to understand the formal language you use (simplifying the verification process), or generic programming languages like C++.
I agree with Shweta, Petri Nets are an interesting choice. The problem is that Agent-Based Systems are models themselves and what you want to do is to model the model behavior. By doing so, you are most certainly have to give up on several of the real-world characteristics. Nevertheless, the reason why Petri Nets may be a good start is that they inherently represent a graph structure that can be represented hierarchical. i.e., at one level the vertices may represent individual agents with edges showing there interaction (frequency etc.). In another level, the graph may represent a state machine, with vertices representing the possible states of an individual agent and the edges represent transitions.
It is also possible to use a graph representation of the "Agent Population" and capture their interactions on each of the edges. Careful though - for even a modes number of agents, this model can get large if interactions among all agents occur. You can then capture various statistical measurements that will represent the dynamics of your system.
As argued by Armin, a graph theoretic representation of the agent population seems to me the most natural way to formalized multi-agent systems, specially the ones in which the social environment plays a major role. Generally I am quite sceptical about the advantages of using formal representation of MAS, such as Petri Net or similar tools, because I believe that whatever dynamic system (including MAS) can be straightforwardly represented in a pseudo-code format, using rigorous mathematical notation. Any MAS is a deterministic or randomized algorithm which has specific recursive functions which allow to update the state variables. I do not see any advantage from having a graphical formal representation of it beyond the one provided by a mathematical pseudo-code.