Transcript Document

Agent-based Systems
in geosimulation
Geog 220, Winter 2005
Arika Ligmann-Zielinska
February 14, 2005
Sources
1) Weiss G. ed. (1999) Multiagent Systems: a modern approach
to distributed artificial intelligence, Cambridge, MA, MIT
Press
• Prologue pp. 1 – 9
• Chapter 1 Intelligent Agents by Michael Wooldridge pp. 27 – 42
• Chapter 2 Multiagent Systems and Societies of Agents by Michael N.
Huhns and Larry M. Stephens pp. 79 – 84
2) Batty M., Jiang B. (1999) Multi-agent Simulation: new
approaches to exploring space-time dynamics within GIS,
CASA paper 10
• pp. 1 – 7
3) Benenson I., Torrens P. (2004) Geosimulation Automatabased Modeling of Urban Phenomena, John Wiley & Sons,
LTD
• Chapter 6 Modeling Urban Dynamics with Multiagent Systems pp.154 –
184
Outline
• Agency
• Distributed Artificial Intelligence & Multi
Agent Systems
• Agents environments
• Agents in geosimulation
• General typology of agents & urban agents
• Location choice behavior
• General Models of Urban Agents
• Examples
Agents
Demystified
agere (Latin) – to do
Agent - a computational entity such as a software program or robot that can be
viewed as perceiving and acting upon its environment and that is autonomous in
that its behavior at least partially depends on its own experience
Agent - system that decides for itself what it needs to do in order to satisfy its
objectives
Characteristics
•
•
•
Autonomous
Goal-oriented
Interacting – agents “sense” or are “aware” of other agents
Key behavioral processes
•
•
•
•
Problem solving
Planning
Decision-making
Learning
When and how to interact with whom?
Agents Demystified
Intelligent agents - agents operating robustly in rapidly changing,
unpredictable, or open environments
“Sense the future”
• Flexible autonomous action in order to meet design objectives
(flexibility – reactivity)
• Pro-activeness (goal directed behavior, taking the initiative)
• Social ability (interact with other agents/humans)
Effective integrating goal-oriented and reactive behavior
Multiagent Systems (MAS)
MAS – a community of agents, situated in an environment.
MAS – systems in which several interacting, intelligent agents pursue some set of
goals or perform some set of tasks.
– Inherent distribution (spatial, temporal, semantic, functional)
– Inherent complexity
• MAS studied by Distributed Artificial Intelligence – DAI
• DAI and AI
– AI – intelligent BUT stand-alone systems
• Intelligence acts in isolation
• Cognitive processes of individuals
• Psychology and behaviorism
– DAI – intelligent connected systems
• Intelligence acts through interaction
• Social processes in groups of individuals
• Sociology and economics
Hence DAI is a generalization of AI, and not its specialization!
Agents’ environment
•
•
•
•
•
Accessible vs. inaccessible
Deterministic vs. non-deterministic
Episodic vs. non-episodic
Static vs. dynamic
Discrete vs. continuous
What typology can be assigned to urban/spatial models?
If an environment is sufficiently complex, the fact that it is actually deterministic is not much
help – Why?
Summary of MAS attributes
Why Agents in Spatial Models?
• Urban systems are a product of human
decisions
• CA cousins lack
–
–
–
–
–
Mobility
Purposefulness
Social ability
Adaptability
Transition Rules heterogeneity
Refer to Figure 5.4 p. 169 in BenTor
Types of Agents
• Geosimulation: mobile, adaptive &…?
• Weak vs. strong agency
Geosimulation deals with weak agents
Urban Agents
10th of
seconds
Characteristic time ”t”
months
years
seconds
month
s
Urban Agent Choice Behavior
•
•
•
•
Location and migration behavior
Changes in state and location
Mobile agents carry their characteristics with them
Ability to make decision concerning the entire urban space
(action-at-a-distance)
• Location choice modeled with rational decision-making and
bounded rationality
• Utility Functions
Set of opportunities {Ci}available for agent A, where each Ci has some level
of Utility U(A, Ci) and/or Disutility D(A, Ci) = 1 – U(A, Ci)
(assumed that U belongs to [0,1])
Variability in the perception of utility – choice probabilities P(A, Ci), where
P(A, Ci) = f(U(A, Ci)) e.g. logit model
Bounded Rationality Heuristics
• Random choice: pick one of the opportunities Ci randomly
• Satisfier choice: pick one of the opportunities Ci randomly
and compare it to a pre-defined threshold ThA of an Agent A
if U(A, Ci) > ThA
pick Ci
• Ordered choice: order Ci for A in descending order, creating
an ordered set of opportunities, pick the first opportunity from
this set
Residential Decision Making
Experimental results based on:
• Revealed preferences of subjects
• Stated preferences of subjects
Taxonomy of residential decision-factors (adapted from
Speare, 1974):
•
•
•
•
•
Individual
Household
Housing
Neighborhood
Above-neighborhood
Stress(dissatisfaction/dissonance)-resistance Residential
Behavior (steps):
• Decision to leave the current location
• Decision to reside in a new location
General Models of Agents’ Collectives
Diffusion-Limited Aggregation (DLA)
• Urban context – simulating new building locations:
DLA of Developers Efforts
• Monocentricity (CBD core)
• Sprawl diffusion
• Urban land use density represented by power law:
Density(d) ~ d D-2
d – distance from the city center
D – fractal dimension
Nicholas Gessler UCLA
http://www.sscnet.ucla.edu/geog/gessler/borland/
General Models of Agents’ Collectives
Percolation
• Percolation of the Developers’
Efforts
• Developers build close to
existing constructions
Real
• Clustered
• Multicenteric
• Density of urban uses decreases
according to exponential law
Density(d) = d0e-Ld
d – distance from the city center
L – constant
Image source: http://lisgi1.engr.ccny.cuny.edu/~makse/urban.html
Simulation
General Models of Agents’ Collectives
Intermittency
Bifurcation of a cell
• Each time a fraction α of population leaves a cell C
• α distributes among von Neumann neighborhood of C –
close migration
• C becomes an attractor or repelling center – distant
migration
• Exponential decrease in density of urbanized land from
the city center
General Models of Agents’ Collectives
Spatiodemographic processes
• Particles are born and die
• Parameters of reproduction β and
mortality γ
– γT
T - threshold
– Partially clustered
Diffusion of Innovation
• probability of acceptance 1 – γ
• γT (T – threshold) defined as
intensity of innovation
dissemination β
ABM in Urban Context - Examples
• XJ Technologies demos
http://www.xjtek.com/models/agent_based_models/
• CommunityViz Policy Simulator Analysis
by Arika Ligmann-Zielinska
http://www.uweb.ucsb.edu/~arika/agents/chelan/anim/basic.html
• Schelling’s segregation
Source: Nicholas Gessler UCLA
http://www.sscnet.ucla.edu/geog/gessler/borland/