SWEN90004
Modelling Complex Software Systems Lecture Cx.07
Agent-Based Models I
Artem Polyvyanyy, Nic Geard
artem.polyvyanyy@unimelb.edu.au;
nicholas.geard@unimelb.edu.au
Semester 1, 2021
1 / 34
Outline
Introduction to agent-based models
Characteristics of agents
Environment and interactions Agent decision making
2 / 34
What is an “agent-based” model?
Like cellular automata (CA), agent-based models (ABMs) are an ap- proach to modelling complex systems that focuses on the components of the system and the interactions between them.
An ABM typically has three elements:
agents
environment (including other agents) interactions
ABMs differ from CA in that allow more flexibility in how they represent agent behaviour and interaction structure.
3 / 34
An example: flocking behaviour
Flocking behaviour, as exhibited by large groups of birds and fish, was earlier introduced as a canonical example of complex system.
FigureA murmuration of starlings
http://www.alaindelorme.com/
Craig Reynolds, a computer graphics and animation expert who has worked for Electronic Arts, DreamWorks Animation and Sony, develped an early (1986) ABM model of flocking behaviour.
4 / 34
‘Boids’ model of flocking behaviour
The agent (Reynolds used the term boid)
Agent behaviours include:
forward motion
turning left or right
(perhaps) acceleration and deceleration
5 / 34
The boids neighbourhood function
http://www.red3d.com/cwr/steer/gdc99/
The environment consists of the other boids in the flock.
The neighbourhood function is the sensory range of the boid
(how far away it can perceive other agents).
Boids ‘interact’ according to the following three rules. . .
6 / 34
Rules for flocking behaviour 1. Separation
Boids will steer to avoid crowding nearby boids—collision avoidance
7 / 34
http://www.red3d.com/cwr/steer/gdc99/
Rules for flocking behaviour 2. Cohesion
Boids will steer towards the average location of nearby boids—safety in numbers
http://www.red3d.com/cwr/steer/gdc99/
8 / 34
Rules for flocking behaviour 3. Alignment
Boids will steer toward the average bearing of nearby boids
http://www.red3d.com/cwr/steer/gdc99/
9 / 34
Outline
Introduction to agent-based models
Characteristics of agents
Environment and interactions Agent decision making
10 / 34
Essential characteristics: self-contained
An agent is a modular component of a system, is has a boundary and can be clearly distinguished from and recognised by other agents.
Flocking model: the boids are clearly distinguishable and ‘recognised’ (though not uniquely) by other boids.
11 / 34
Essential characteristics: autonomous
http://pixabay.com/
An agent can function independently in its environment, and in its interactions with other agents (within the scope of the defined model).
Flocking model: the behaviour of each boid is entirely defined by the information it obtains about its local environment
12 / 34
Essential characteristics: dynamic state
http://www.hudforglass.com/
An agent has attributes, or variables, that can change over time. An agents current state is what determines its future actions and behaviour.
Flocking model: a boid’s state consists of its current heading and
speed. This state determines the motion of the boid, and is modified
on the basis of information it recieves about its local environment.
13 / 34
Essential characteristics: social
http://www.alexanderwild.com/
An agent has dynamic interactions with other agents that influence their behaviour.
Flocking model: boids ‘interact’ by perceiving and reacting to the location and behaviour of other boids.
14 / 34
Other characteristics: adaptive
An agent may have the ability to learn and adapt its behaviour on the basis of its past experiences.
For example, imagine if prey boids in predator-prey model observed that predators more often attacked boids on their right than their left (becuase of the location of their sensors/eyes), they might be
able to ‘learn’ to move to the left of a predator and hence escape
detection.
15 / 34
Other characteristics: goal-directed
An agent may have goals that it is attempting to achieve via its behaviours.
For example, imagine that, in addition to avoiding predators, prey boids also have the goal of collecting materials to build a nest… This would be another factor influencing their behaviour.
16 / 34
Other characteristics: heterogeneous
A system may be comprised of agents of different types: these differences may be by design (eg, predators and prey), or a result of an agents’ past history (eg, the ‘energy level’ of predators, based upon whether it has eaten recently)
More complex ABMs might include a wide array of different types of agents; for example, models of land use may include residents, plan- ners, infrastructure providers, businesses, developers and lobbyists, etc.
17 / 34
Outline
Introduction to agent-based models
Characteristics of agents
Environment and interactions
Agent decision making
18 / 34
Environment
Agents monitor and react to their environment—the physical or virtual space in which the agent ‘functions’.
The one- and two- dimensional grids of CA were very simple environments.
Environments may be static (unchanging over time), or they may change as a result of agent behaviour, or they may be independently dynamic.
Real environments are typically dynamic (and often stochastic). Therefore we may not be able to foresee all possible ‘states’ of the environment and how agents will respond to them.
19 / 34
Interactions
A defining characteristic of complex systems is local interactions between agents, as defined by the agent neighbourhood.
Depending on the structure of the system, the composition of an agent’s neighbourhood may be dynamic (ie, change over time as it moves through its environment)
Neighbourhoods, and hence patterns of interaction, are not always defined in spatial terms—they may also be networks with a particular topology (more on this next week)
20 / 34
Example: Foraging in ant colony
Ant colonies are able to achieve remarkable feats of organisation— constructing elaborates nests and efficiently foraging for food—
“without chief, overseer or ruler”
Work by evolutionary biologist Edmund O. Wilson in the 1960s and 1970s led to new understanding of how ant societies operate.
Individual ants perform a limited range of tasks—picking up and dropping food and building materials—based on relatively simple decision rules.
The inputs to these decision rules are chemical signals (pheromones). These signals can come from both:
direct interactions with nearby ants; and
stigmergic interactions via pheromones deposited by ants in the
environment
21 / 34
Ant colony foraging
Dorigo M, Stutzle (2004) Ant Colony Optimization, MIT Press
22 / 34
NetLogo ‘Ants’ model
Ant rules
1. If an ant is not carrying food:
move randomly around its environment
if it encounters food pherommenes, move in the direction of the
strongest signal
2. If an ant encounters food:
pick it up
3. If an ant is carrying food:
follow the nest pheromone gradient back toward the nest
deposit food pheromones into the environment while moving
Environment
There is a nest pheromone gradient diffusing out from the nest food pheromones evaporate over time
23 / 34
Outline
Introduction to agent-based models
Characteristics of agents
Environment and interactions
Agent decision making
24 / 34
Agent decision making
Agents are often designed to make rational decisions: they will act to maximise the expected value of their behaviour given the information they have received thus far.
Note that:
rational ̸= omniscient: an agent’s percepts may not supply all required information
rational ̸= clairvoyant: an agent’s actions may not produce the expected outcome
therefore, rational ̸= successful (necessarily)
rational → exploration, learning, adaptation, . . .
25 / 34
Agent decision making
Agent decision making may be:
probabilistic: representing decisions using distributions
rule-based: modelling the decision making process
adaptive: agents may learn via reinforcement or evolution
The choice will often depend on the purpose of the model (what question is it being used to answer?)
Agent decision making can range from simple to complex. . .
26 / 34
Reflexive agents
Russell and Norvig (2009) Artificial Intelligence: A Modern Approach, Prentice Hall
27 / 34
Reflexive agents with internal state
Russell and Norvig (2009) Artificial Intelligence: A Modern Approach, Prentice Hall
28 / 34
Goal-driven agents
Russell and Norvig (2009) Artificial Intelligence: A Modern Approach, Prentice Hall
29 / 34
Utilitarian agents
Russell and Norvig (2009) Artificial Intelligence: A Modern Approach, Prentice Hall
30 / 34
Learning agents
Russell and Norvig (2009) Artificial Intelligence: A Modern Approach, Prentice Hall
31 / 34
Summary
Agent-based models consist of agents, an environment, and interactions between agents and (a) other agents and (b) the environment.
ABMs feature decentralised information and decision making, and can reproduce the emergent behaviour and self-organisation found in complex systems.
ABMs are employed in a wide variety of domains: ecology, social science, economics, political science, etc.
ABMs can be much more elaborate than CAs.
32 / 34
Follow up activites!
Explore the Flocking, Ants and Segregation models in NetLogo
Think about:
What are agents? What state variables do they have? What decisions do they make?
What is the environment? Is it static or dynamic?
What interactions take place? Between agents? Between the agents and the environment?
33 / 34
References
Macal CM, North MJ (2010), Tutorial on agent-based modeling and simulation. Journal of Simulation 4:151–162
Reynolds C (1987) Flocks, herds and schools: a distributed behavioral model, SIGGRAPH ’87: Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, Association for Computing Machinery, pp 25–34
Schwarz N, Kahlenberg D, Haase D, Seppelt R (2012) ABMland—a Tool for Agent-Based Model Development on Urban Land Use Change, Journal of Artificial Societies and Social Simulation 15(2):8
Bonabeau E, Theraulz G, Deneuborg J-L, Aron S, Camazine S (1997) Self-organization in social insects, Trends in Ecology and Evolution 12(5):188–193
34 / 34