Query on Fundamentals of Agent-Based Simulation

[Jim Duggan]

Hi,

I'm new to the list. I work at NUI, Galway (West Coast of Ireland!), and my research interests include System Dynamics, Simulation and Operations Research. I have
designed and built simulators based on numerical
integration and timed Petri nets, and I am looking to
extend these systems (if possible) so that they can
model societies of interacting agents.

Before I attempt this, I'm looking for any pointers
(books, web sites) on how you might built an
agent-based simulation system from scratch. I have
a reasonable understanding of systems such as Zeus
and Jade, but these seem more suited to building
agent implemations, rather than models of agents. I
am aware of systems such as Swarm and Repast, although
I have not built any models using these environments
yet.

Some initial questions I'm exploring include:

- Are agent-based simulation systems always based on the discrete-event simulation?
- What underlying techniques are used to build agent societies (graph theory?) and maintain connections between agents?
- How are heuristics/behaviours dealt with in agent-based simulation systems?

Any insights on these questions would be appreciated,

many thanks,

Jim Duggan.


_________________________________
Dr. Jim Duggan, Chartered Engineer,
Department of Information Technology,
National University of Ireland, Galway,
IRELAND.
Email:     jim.duggan at nuigalway.ie
Web:     http://corrib.it.nuigalway.ie
Phone:   [phone]
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://redfish.com/pipermail/friam_redfish.com/attachments/20060301/068eb4fe/attachment.htm

[Jochen Fromm-3]

AGENT is a very general and ambiguous expression which has many different
meanings. There is no universally accepted definition of the word "Agent".
Many people (at least here in Germany) associate the name with secret
agents like James Bond, others think of agents in science fiction films as
MiB or Matrix. That's certainly one reason why they are popular.

In our context, one can distinguish between agents which represent
natural agents (actors, animals, etc.) in simulations, for example
in sociology or ecology, and autonomous software entities in computer
science and software engineering that show agent-like behavior in
their environment (extended mobile software objects which can move around
in networks).

In the former case, the specific scientific problem in question
from sociology, ecology, etc. offers detailed guidance how to create
a model. These simulations are in fact discrete-event simulations,
usually built with some object-oriented language (not necessarily
with software agents).

In the latter case (real software agents, for example built with
JADE, ZEUS or a similar framework), the question if mobile agents or
societies of agents are really useful for any application
at all is still unclear and controversial. It is not difficult
to create a framework for mobile agents in Java or .NET (a socket
connection, a bit serialization, and a few other things). The
difficult thing is to figure out what you can do with your system.
These systems and the corresponding international conferences often
revolve around themselves.

_________________________________
Jochen Fromm, PhD Student
Distributed Systems Research Group
EECS Department, Kassel University, Germany
http://www.vs.uni-kassel.de/~fromm/

[Robert Holmes-2]

Welcome Jim,

One of the best sites for peer-reviewed work in this area (rather than the
usual self-published ramblings you get at conferences :-) is
http://jasss.soc.surrey.ac.uk/JASSS.html.

As to software, there's a bunch of Netlogo (
http://ccl.northwestern.edu/netlogo/) users on this list. Owen & Steve have
both done work that demonstrates some of Netlogo's advanced features

What is Zeus like for developing ABMs? I tried to use it about 5 years ago
but couldn't get it to work for me. Are BT Research still actively
supporting and developing it?

Robert


On 3/1/06, Jim Duggan <jim.duggan at nuigalway.ie> wrote:

>
> Hi,
>
> I'm new to the list. I work at NUI, Galway (West Coast of Ireland!), and
> my research interests include System Dynamics, Simulation and Operations
> Research. I have
> designed and built simulators based on numerical
> integration and timed Petri nets, and I am looking to
> extend these systems (if possible) so that they can
> model societies of interacting agents.
>
> Before I attempt this, I'm looking for any pointers
> (books, web sites) on how you might built an
> agent-based simulation system from scratch. I have
> a reasonable understanding of systems such as Zeus
> and Jade, but these seem more suited to building
> agent implemations, rather than models of agents. I
> am aware of systems such as Swarm and Repast, although
> I have not built any models using these environments
> yet.
>
> Some initial questions I'm exploring include:
>
> - Are agent-based simulation systems always based on the discrete-event
> simulation?
> - What underlying techniques are used to build agent societies (graph
> theory?) and maintain connections between agents?
> - How are heuristics/behaviours dealt with in agent-based simulation
> systems?
>
> Any insights on these questions would be appreciated,
>
> many thanks,
>
> Jim Duggan.
>
>
> _________________________________
> Dr. Jim Duggan, Chartered Engineer,
> Department of Information Technology,
> National University of Ireland, Galway,
> IRELAND.
> Email:     jim.duggan at nuigalway.ie
> Web:     http://corrib.it.nuigalway.ie
> Phone:   [phone]
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9a-11:30 at cafe at St. John's College
> lectures, archives, unsubscribe, maps at http://www.friam.org
>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://redfish.com/pipermail/friam_redfish.com/attachments/20060301/8ef696e2/attachment-0001.htm

[Stephen Guerin]

Hello Jim,

Welcome to Friam!

You wrote:

>Some initial questions I'm exploring include:
>  - Are agent-based simulation systems always based on the discrete-event
simulation?

I think of agent-based and discrete-event as distinct.

You mentioned coming from the Operations Research world. There I think discrete
event simulation is closely associate with queueing models where the simulation
is managing servers and individuals in queues. Individuals as the things in the
queues, tend to have minimal behavioral rules with most of the behavioral rules
residing in the servers. Most of the "agency" tends to be in the servers
managaing the queues. Focus of the researchers tend to be on flow rates and
bottlenecks.

With agent-based models, we define agents as anything in the model that makes a
decision. Information for the decisions and the immediate effect of the
decisions tend to be local. We tend to implement ABM's as software objects that
respond to a "step" method. Updating the agents' state may or may not be done
synchronously. The agents in ABM tend not to be fixed to a prescribed network
and are free to associate and disassociate in the simulations. Focus of the
researchers tend to be on phase transitions and emergent dynamics.

After making the above distincition between DES and ABM, I should say that while
most toy/level "0" models tend to be of one flavor or the other, most real world
projects tend to be hybrid models with some portions of the model being portions
discrete event, others agent-based and still others being system dynamics. In
fact, it's relatively easy to implement a DES in an ABM tool and you can bend a
DES tool, with some effort, to do ABM.

> - What underlying techniques are used to build agent societies (graph theory?)
and maintain connections between agents?

Yes, graph theory is used. Research in the last 5-10 years of small worlds and
scale-free networks has created a subdiscipline of "network dynamics" thay may
bring up more relevant google hits.

To build agent interactions, we tend to implement agents as first class software
objects. Connections are represented as a software reference to other agent
objects. These connections are usually stored in lists. Connections are often
indirect and communication is mediated by the environment so no references to
other agents are maintained.

If we're focusing on the network structure in a particular model, we also
implement the connections or "edges" as first class software objects. This way
the edges can have behavior and state. Edges have a reference to the two agents
on the ends and the agents tend to have a list of edges.

In rare cases but of growing interest to me, is where we represent the network
primarily from the connection perspective. Edges are first class objects and
agents exist only as the intersection of relations...

> - How are heuristics/behaviours dealt with in agent-based simulation systems?

Agents are usually implemented as software objects. The methods of the objects
usually implement the interaction rules. I think interaction rules tend to
capture most of the heuristics or behaviors of interest. Agent-based modeling
tends to focus on the the interactions between agents and between agents and
their environment. Given that, the term Interaction Based Modeling might have
been a better descriptor. BTW, other near-synonyms are individual based modeling
(from ecology) and microsimulation.


HTH,

Steve

[Jim Duggan]

Hi all:

Many thanks for the replies, they are really helpful.

If my understanding is correct, essentially the main
difference between ABM and other approaches is
where the agent interactions are the dominant feature
of what is being modelled. I guess this would include
scenarios such as game theory and complex
negotiation problems where many agents are
trying to solve a common problem.

Having said that, I still see more similarities than
differences in, lets say, ABM and System Dynamics.
In SD, one of the "paradigm-case" models is the Beer
Game, which is agent-based (4 agents) and captures
inter-agent interactions. It represents each agent's
goal, expectation and behaviour, and overall the
model gives rise to interesting behaviours. The underlying
technique is integration (stocks and flows), where
stocks can repesent real world entities such as inventory
and orders, as well as "mental stocks" such as expected orders. Flows then
represent decision points in the model.

What would be useful for my own understanding of the key differences between
ABM and other approaches, would be to get an insight into what the
"paradigm-case" model(s) are for ABM.

So my follow-on question is: In the ABM community, what model (or models)
are the classic ABM type models, in that the dimension of inter-agent
interactions is most prominent? Or to put it another way, what would be
regarded as the System Dynamics "Beer Game" equivalent for ABM?

best regards,
Jim.

----- Original Message -----
From: "Stephen Guerin" <[hidden email]>
To: "The Friday Morning Applied Complexity Coffee Group" <Friam at redfish.com>
Sent: Wednesday, March 01, 2006 7:29 PM
Subject: Re: [FRIAM] Query on Fundamentals of Agent-Based Simulation

> Hello Jim,
>
> Welcome to Friam!
>
> You wrote:
>
> >Some initial questions I'm exploring include:
> >  - Are agent-based simulation systems always based on the discrete-event
> simulation?
>
> I think of agent-based and discrete-event as distinct.
>
> You mentioned coming from the Operations Research world. There I think

discrete
> event simulation is closely associate with queueing models where the
simulation
> is managing servers and individuals in queues. Individuals as the things
in the
> queues, tend to have minimal behavioral rules with most of the behavioral
rules
> residing in the servers. Most of the "agency" tends to be in the servers
> managaing the queues. Focus of the researchers tend to be on flow rates
and
> bottlenecks.
>
> With agent-based models, we define agents as anything in the model that
makes a
> decision. Information for the decisions and the immediate effect of the
> decisions tend to be local. We tend to implement ABM's as software objects
that
> respond to a "step" method. Updating the agents' state may or may not be
done
> synchronously. The agents in ABM tend not to be fixed to a prescribed
network
> and are free to associate and disassociate in the simulations. Focus of
the
> researchers tend to be on phase transitions and emergent dynamics.
>
> After making the above distincition between DES and ABM, I should say that
while
> most toy/level "0" models tend to be of one flavor or the other, most real
world
> projects tend to be hybrid models with some portions of the model being
portions
> discrete event, others agent-based and still others being system dynamics.
In
> fact, it's relatively easy to implement a DES in an ABM tool and you can
bend a
> DES tool, with some effort, to do ABM.
>
> > - What underlying techniques are used to build agent societies (graph
theory?)
> and maintain connections between agents?
>
> Yes, graph theory is used. Research in the last 5-10 years of small worlds
and
> scale-free networks has created a subdiscipline of "network dynamics" thay
may
> bring up more relevant google hits.
>
> To build agent interactions, we tend to implement agents as first class
software
> objects. Connections are represented as a software reference to other
agent
> objects. These connections are usually stored in lists. Connections are
often
> indirect and communication is mediated by the environment so no references
to
> other agents are maintained.
>
> If we're focusing on the network structure in a particular model, we also
> implement the connections or "edges" as first class software objects. This
way
> the edges can have behavior and state. Edges have a reference to the two
agents
> on the ends and the agents tend to have a list of edges.
>
> In rare cases but of growing interest to me, is where we represent the
network
> primarily from the connection perspective. Edges are first class objects
and
> agents exist only as the intersection of relations...
>
> > - How are heuristics/behaviours dealt with in agent-based simulation
systems?
>
> Agents are usually implemented as software objects. The methods of the
objects
> usually implement the interaction rules. I think interaction rules tend to
> capture most of the heuristics or behaviors of interest. Agent-based
modeling
> tends to focus on the the interactions between agents and between agents
and
> their environment. Given that, the term Interaction Based Modeling might
have
> been a better descriptor. BTW, other near-synonyms are individual based
modeling

> (from ecology) and microsimulation.
>
>
> HTH,
>
> Steve
>
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9a-11:30 at cafe at St. John's College
> lectures, archives, unsubscribe, maps at http://www.friam.org
>

[Jochen Fromm-3]

 
The NetLogo Models Library has most
of the "classic" ABM models
http://ccl.northwestern.edu/netlogo/models/

-J.

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf
Of Jim Duggan
Sent: Friday, March 03, 2006 11:46 AM
To: The Friday Morning Applied Complexity Coffee Group
Subject: Re: [FRIAM] Query on Fundamentals of Agent-Based Simulation

So my follow-on question is: In the ABM community, what model (or models)
are the classic ABM type models, in that the dimension of inter-agent
interactions is most prominent? Or to put it another way, what would be
regarded as the System Dynamics "Beer Game" equivalent for ABM?

best regards,
Jim.

[Mohammed El-Beltagy]

Hello Jim,

> If my understanding is correct, essentially the main
> difference between ABM and other approaches is
> where the agent interactions are the dominant feature
> of what is being modelled. I guess this would include
> scenarios such as game theory and complex
> negotiation problems where many agents are
> trying to solve a common problem.

I would hesitate to say that ABM deals with problems involving game theory
in the broadest sense. Certainly ABM deals with problems involving strategic
interaction, but the game theoretic notions of rationality and equilibrium
are out the window. Agents may learn and improve their strategies in an
iterated game, but there is no way to guarantee that they will stumble on a
Nash equilibrium.



Often ABM is used in situations where we know a priori that the rationality
assumption is weak and that the information is far from complete, or
perfect. These are the sort of situations that traditional game theory is
not equipped to handle.



With regards to agents working together to solve a common problem, this does
not fall within what most ABM practitioners do. Collective Intelligence
tries to establish a theoretical framework for doing that (c.f.
http://ic.arc.nasa.gov/people/dhw/collectives.php)

> Having said that, I still see more similarities than
> differences in, lets say, ABM and System Dynamics.
> In SD, one of the "paradigm-case" models is the Beer
> Game, which is agent-based (4 agents) and captures
> inter-agent interactions. It represents each agent's
> goal, expectation and behaviour, and overall the
> model gives rise to interesting behaviours. The underlying
> technique is integration (stocks and flows), where
> stocks can repesent real world entities such as inventory
> and orders, as well as "mental stocks" such as expected orders. Flows then
> represent decision points in the model.

A major difference in the flexibility that ABM provides. ABM allows you to
have agents that learn and make decisions in an if-then manner that is very
difficult and sometimes impossible to do in SD. It breaks the modeling
mental straight jacket the stocks and flows forces you to adopt in SD.



In ABM, the agents can adapt and change their decision making strategies
over time. They can use sophisticated optimizers and learning algorithms to
improve their decision strategies (evolutionary algorithms, reinforcement
learning and neural networks).



A nice comparison between ABM and EBM (of which SD is but a subset) in
Bonabeau's PNAS article

http://www.pnas.org/cgi/content/full/99/suppl_3/7280


> So my follow-on question is: In the ABM community, what model (or models)
> are the classic ABM type models, in that the dimension of inter-agent
> interactions is most prominent? Or to put it another way, what would be
> regarded as the System Dynamics "Beer Game" equivalent for ABM?
>



My favorite is Epstien and Axtell's sugar scape model:

http://repast.sourceforge.net/examples/java/SugarModel.jnlp

It is a variant of the iterated prisoner's dilemma game. For someone with a
background in OR and game theory, this could be a good place to start.
There is a nice book written about sugar scape and similar models

http://www.amazon.com/gp/product/0262550253/sr=8-1/qid=1141392581/ref=pd_bbs_1/002-3822002-8215227?%5Fencoding=UTF8



More Repast models can be found at



http://repast.sourceforge.net/examples/index.html




Cheers,



Mohammed



==========================================
mohammed at optomatica.com  http://www.optomatica.com  Tel: [phone]

[Stephen Guerin]

> So my follow-on question is: In the ABM community, what model (or models)
> are the classic ABM type models, in that the dimension of inter-agent
> interactions is most prominent? Or to put it another way, what would be
> regarded as the System Dynamics "Beer Game" equivalent for ABM?

I tend to think of flocking and the ant foraging model as paradigmatic examples.
Both models have simple interaction rules that have the potential for emergent
behavior -- flocks and foraging trails.

We have a flocking model at http://www.redfish.com/projects/SwarmEffects/
(Shockwave) and an ant foraging at
http://www.redfish.com/research/RedfishAnts.htm (Netlogo/Java).

-Steve