Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Agent-based models by example

Presented at Young Scientist Conferece, Amsterdam. http://uva.computationalscience.nl/events/young-scientists-conference
by

Michael Lees

on 30 October 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Agent-based models by example

Agent-based Modelling What is an agent? Not an easy answer.... It means many things
to many people A.I. An intelligent agent is a computer system capable of flexible autonomous action in some environment [Wooldridge] reactive: deal with change
pro-active: goal directed behaviour
social: interact with other agents An agent-based model, is an abstraction of a real or physical system described in terms of multiple, flexible agents. [Lees] Development & History: AI Economics/Social Science Graphics The birth is hard to pin to one place On to:
- Biologiy (Cellular models ,bacteria models)
- Engineering (evacuation)
- Spread of Infectious disease
- many others.... An agent-based system, is an engineered or designed system consisting of perhaps multiple, flexible agents.
game theory, coallition, negotiation, etc.
e.g., self managing/healing systems, manufacturing Why/When agent-based model? *[Bonabeau] PNAS May 14, 2002 vol. 99 no. Suppl 3 7280-7287 A quick example... Everyone has their own typical agent-based model, often depends on their field (Economist, AI, graphics, etc.)

I choose Boids because I think it's a beautiful way of showing the power of emergence.

The idea of enough very simple local interactions creating hugely complex global phenomena www.red3d.com/cwr/boids/ Agent-based Model timeline... 1971
1978
Scheling Segregation Is it an Agent, or just a Program?: A Taxonomy for Autonomous Agents
http://www.msci.memphis.edu/~franklin/AgentProg.html 1984

Axelrod Prisoners 1987

Reynolds Boids 1970

Conway Game of Life 1996

Sugarscape: Epstein & Axtell http://www2.econ.iastate.edu/tesfatsi/abmread.htm Types of Agent A.I. Describes Heavyweight (deliberative) & Lightweight (reactive) agents:

lightweight agent:
simple reactive if-then rules

Possible to have deliberative agents do more:
plan, evolve, learn, emotional agents,...
Santa-Fe artificial stockmarket - agents that learn trading behavior Simulation Tools Once the model is designed, needs to be translated to a simulation Netlogo
http://ccl.northwestern.edu/netlogo/models/run.cgi?Flocking.783.569 Excellent for experimenting

Non-programmers

Program models using Logo language

- Not so scalable, toy examples Repast
http://repast.sourceforge.net/ [v2.0 March 2012]
Repast HPC version C++ (New: 5/3/2012)! Java libraries (Simphony and 3.1)

Write models in Java, download with Eclipse

Non-programmers, and programmers

- Quite Cumbersome for programmers [v1.0] Mason
http://cs.gmu.edu/~eclab/projects/mason/ [v16] Java libraries

Write models in Java.

For Programmers - code is well written, excellent support community

My choice... Others: SIM_AGENT, Swarm, JADE, SimPy, ... Challenges ABM can solve all the world's problems! There are important challenges/limitations 1. Validation? Often the same question
Why do we model? Prediction? Exploration?


There is a difference between validating: Model of air flow over a car


The spread of a pandemic over a city/country


Are both models useful?? Social Science Vs Natural Science [Why Model?, Epstein 2008: JASSS http://jasss.soc.surrey.ac.uk/11/4/12.html] 2. Computation?
ABM came with computing.

Simulating 100,000's of agents


Exascale ABM: Each is planning, moving, etc. http://www.alcf.anl.gov/projects/exascale-agent-based-modeling-system

Large-Scale Computing Techniques for Complex System Simulations
Werner Dubitzky, Krzysztof Kurowski, Bernard Schott. ABMs consist of a space, framework or environment in which interactions take place and a number of agents whose behavior is defined in this space is defined by a basic set of rules and by characteristic parameters. [Reynolds]

The aim of ABM is to look at global consequences of individual or local interactions in a given space. Agents are seen as the generators of emergent behavior in that space. [Holland] Types of Space [Macal & North 06] Examples Dynamic Egress PlAning Through Symbiotic Simulation An agent-based model of egress (evacuation)

Agents have:
Reasoning ability (fire alarms, smoke, etc.)
Personal knowledge (people unfamiliar/familiar with a building)
Communication ability
Navigation and motion (RVO2, SocialForce, etc.) Symbiotic Simulation Physical
System Simulated
System Sensors/Data Actuators Real time decision support... Simulated
System E-Vehicle Simulation TUM-Create program looking at electro-mobility in Tropical Mega-cities

SEMSim - Scalable Electro-Mobility Simulator
Distributed Discrete-event Simulation engine (for HPC)
Behavior-based
Builds on exisitng models from the last 50+ years
Simulate components, battery, air-conditioning
Will be open source (soon-ish) Data? Validation? Notoriously difficult...

Need to use data, from exisitng fires, from exisitng literature

Conduct controlled experiments? Not ideal...

Use Serious Games! Initial Results Optimization

Consistency Question?

The situation is dynamic.
If the guidance changes too frequently?
Behavioral component is critical (trust in the system) Survival Rate: Ground floor (without guidance) Change in Survival Rate: Ground floor Singapore - a database! Traffic is easier than people! Data Sources:

Land Transport Authority - HITS
A survery of peoples travelling behavior in Singapore
Comfort Delgro Taxi
26000 taxis, all driving 23.5 hours a day, all equiped with 30 second frequency GPS monitoring
Navteq (see right)
Highly detailed map of Singapore, with average speeds, lane information
Singtel (largest mobile phone operator)
High density cell region for mobile phone patters, good esitmator of mobility Active Data Collection:

Traffic Density App
Participatory sharing of mobility patterns Questions? To enable electro-mobility in Singapore there is a huge investment requirement.

Why do we need such a high detailed model?
You don't necessarily Other Resources: Thanks.... "Essentially, all models are wrong but some are useful" mhlees@ntu.edu.sg | mhlees.com Agent-based models by example Michael Lees
Nanyang Technological University | Singapore Objective

1. Background on Agent-Based Modeling
2. Examples of tools used by Agent-based Modelers
3. Overview of ongoing work in Singapore
4. Challenges of ABM - research direction geekiness Algorithmic! A joint project with Optimize charging station placement

Method One : Take real/synthetic traffic data => Spatio-temporal traffic, optimize station placement for traffic.
Standard traffic simulation, optimization techniques


Method Two : Account for behavior/charging preference
Need to model behavior
Do I charge at home and work, or as I'm driving.
What about my battery capacity - how does this impact placement?
Variable energy pricing V2G Q2. How robust is the infrastructure?
Singapore is hot and full
5m people and 1m cars (on an island ~1/60 size of the Netherlands)
Throughput of the road system is very high - but accidents are frequent and have large impact Cascading failure for (fully electric) EV's For a given distribution of charging stations, a given typical form of charging behavior
What is the likelihood of total collapse agents in environments When a fire/emergency starts....
1. We detect the event... somehow. We need to determine the best evacuation given the scenario (which we can infer from the sensors).

2. We have a Genetic Algorithm, with each genome in the population representing one possible evacuation route/scheme (one simulation).

3. Evolve the GA in realtime, finding the best solution.

4. Things may change (congestion) - always monitoring and adapting evacuation plan. Environment When the interactions between the agents are complex, nonlinear, discontinuous, or discrete (for example, when the behavior of an agent can be altered dramatically, even discontinuously, by other agents).

When space is crucial and the agents' positions are not fixed. Example: fire escape, theme park, supermarket, traffic.

When the population is heterogeneous, when each individual is (potentially) different.

When the topology of the interactions is heterogeneous and complex. Example: when interactions are homogeneous and globally mixing, there is no need for agent-based simulation, but social networks are rarely homogeneous, they are characterized by clusters, leading to deviations from the average behavior.

When the agents exhibit complex behavior, including learning and adaptation. Example: NASDAQ.
Q1. Where do we put this infrastructure?
e.g., Where to install charging stations?
Positions.... 4 PhD/RA positions available

Joint TUM-NTU PhD

Spend time in Munich and Singapore
Full transcript