Parallel and Distributed Agent-based Simulation of large-scale socio-technical Systems with loosely coupled Virtual Machines

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Introduction

Agent-based systems are inherently distributed and parallel by a distributed memory model!

Agents are loosely coupled - a precondition for parallelisation

But agent-based simulation is often characterised by a shared memory model and tight coupling of agents!

This work investigates architectures and methods for parallel and distributed large-scale agent-based simulations

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Simulation of Socio-Technical Systems

Simulation of large-scale socio-technical systems (like in the Smart City context) is a challenge due to high number of entities and complex dynamic interaction networks

• Simulation can map physical (materialised) entities on state-based agents like:
  • Humans
  • Vehicles
  • Machines
  • Buildings
  • Traffic signals
  • Robots
  • ...
• NetLogo is a widely used agent-based simulator (some of its operational semantics is addressed in this work)

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Agent Model and Agent-based Methods

Agent

Loosely coupled software unit or a hardware device (robot) situated in a specific environment posing perception, interaction, knowledge representation, learning, and self-* capabilities.

Agent-based Computing

Agent architecture representing a software and communication model (mobile software processes).

Agent-based Simulation

Bottom-up approach for simulation and computation of dynamic large-scale systems and world. Agents are elementary cells connecting to an emergent system (holonic design principle).

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Agent Model and Agent-based Methods

The agent behaviour consists of:

1. Computation (only modifying internal agent state);

2. Communication (with other agents and the environment);

3. Actions (modifying the state of other agents or the environment).

• The most important parts addressed in this work are communication and interaction of agents.

• Computation is always decoupled from other processing units and can be parallelised without any limiting constraints.

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Agent Classes

There are two main agent classes:

Computational Agents

A computational agent represents a (mobile) software process with the primary goal of computation, typical situated and processed in real world.

Physical Agents

A physical agent represents a physical entity (machine, human, animal, device, avatar), typically situated and processed only in simulation and virtual worlds. Example: NetLogo agents

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Agent Classes

(Left) Physical agents bound to a body (vehicle, human, building, ..) (Right) Computational agents processed by a virtual machine (Beha) Behaviour (Comp) Computation

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Computational Agents

• In this work mobile reactive state-based agents are considered,

  • programmed in JavaScript;
  • processed by the JavaScript Agent Machine (JAM);
  • used originally for distributed computing.

• The agent behaviour is represented by an Activity-Transition Graph and code consists of:

  • A set of private state variables 𝕍 (body variables);
  • A set of activities 𝔸 (nodes of a graph ATG) performing actions;
  • A set of transitions 𝕋 between activities (edges of ATG);
  • A set of signal handlers 𝕊.

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Computational Agents

The reactive agents can perform the following actions (inside activities):

1. Computation (using body variables, only);

2. Communication (using Tuple spaces and signals);

3. Agent Control (creating, forking, and killing of agents);

4. Agent Modification (code morphing, modifying the ATG);

5. Migration (mobility by process snapshot transfer between JAM platforms).

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Computational Agents

A reactive state-based ATG agent and its memory model: Non-shared registers (body variables), shared platform data base (Tuple space), temporarily shared-by-copy messages (signals)

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Physical Agents

• In simulation physical entities are simulated by physical agents (which can be represented by computational agents in a simulation, too)

• Spatial context and group relationships play a central role:
  • Actions of physical agents can effect other agents within a bounded region;
  • Beside the computational tasks of agents, spatial region search is a major contribution to computational complexity of agent-based simulations!

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Simulation

• Well known simulation model using physical agents: NetLogo

• In this work a simulator based on the JAM platform is used (already existing, just the starting point)

• Physical agents in this simulation world consist of:

  • A state (body variables);
  • Computational activities;
  • A body represented by a visual shape bound to a virtual vJAM plaform processing the agent;
  • A (dynamic) spatial position in the simulation world

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Simulation: SEJAM

SEJAM: Simulation Environment for JAM binding phyiscal agents to virtualised JAM nodes with a spatial position in the simulation world (dynamic); one JAM is processed by node.js and one process

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Parallelisation and Distribution

Problem Classes

1. Static problem size, i.e., a fixed sized problem is partitioned on N processes/regions
2. Dynamic problem size, i.e., the number of processes/regions N increases with the problem size;
   • typical for simulations of real-world and socio-technical environments.

Communication Classes

1. Short-range vs. long-range;
2. Static vs. dynamic ranges and network connectivity;
3. Peer-to-peer versa multi- and broadcasting of messages.

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Communication

Simulation of limitation of parallel speed-up in presence of η% communication fraction → friction (fully connected N:N graph network)

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Parallelisation by Partitioning

1. If there is a two- or three-dimensional world populated with agents, the simulation can be spatially partitioned.
2. Each partition represents a spatial region with a sub-set of agents within a bounded region but with inter-partition connectivity.
3. Each partition can be processed by its own simulation instance.

Spatial partitioning of a simulation world with parallel simulation instances with communication

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Parallelisation by Partitioning

Pitfall: Remote Procedure Call Communication

• Regions and simulation instances communicate via socket-based RPC

• Advantage: Suitable for distributed and parallel computation

• Spatial search, monitoring, and physical agent modification result in high communication overhead and costs

Speed-up < 1!

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Parallel Cellular Automata

Parallel Partitioning of CA regions with communication stripes → Shared Memory Backing Store

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Parallel Cellular Automata

• Cells have clearly limited communciation ranges ⇒ Well suited for parallelisation with low communication overhead ⇒ High speed-up can be expected!

• The shared memory backing store is used for boundary cell region communication and to monitor cell states (globally by the simulation control)

• All cell regions are controlled and stepped by one global clock.

  • Process signalling and SM structures are used for region IPC

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Parallel SEJAM

• Generic agents feature unlimited communication ranges with an arbitrary number of communication partners ⇒ High communication overhead, lowering speed-up of parallelisation...

• Generic agents have commonly complex states (dynamic variables) limiting the deployment of shared memory

• But physical agents will typically interact only with agents within a bounded spatial range.

• Spatial partitioning of the simulation world and parallel processing of independent simulation instances is possible.

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Parallel SEJAM

Concept and Architecture

• The simulation world is partitioned into N regions each with their own physical JAM instance processed by one node.js instance (process)
• Visualisation is decoupled from computation: Visualisation is a monitor
• Structured Shared Memory (SSM) and shared semaphores are used to connect JAM instances and to enable agent and world monitoring;

Data structures are implemented in the SSM by object wrappers (object monitors) performing buffer operations (bobjects)

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Parallel SEJAM

Parallel Region Partitionining architecture with Structured Shared Memory (SSM) and process signal communication

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Parallel SEJAM

Communication

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Use Case: Smart City

Example segmentation of a traffic simulation world (art. city with streets, signals, and vehicle agents) that is partitioned into four regions, each associated to a JAM node (DOM: Distributed Shared Object Manager), connected by SSM

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Agent State Monitoring

• There are vehicle agents performing long-range navigation (by RL) that require sensor input from their neighbourhood:
  • Other vehicles (position, sub-set state)
  • Traffic signals (position, sub-set state, represented by agent)
  • Streets (position, passive agents, ressources)
• So a sub-set of an agent state is monitored and a shadow (read-only) object is mapped in the Structured Shared Memory ⇒ Communication complexity Θ_com(N)=1!

{
  x:1,  // globally readable
  y:2,
  z:3,  // locally accessible
  export : { x:'int', y:'int' }, // mapped in SSM
  act : { .. }, trans : { .. },
}

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Prelimenary Results

Results of the evaluation of the parallel traffic simulation. (a) Measured speed-up with respect to number of regions/pJAM nodes (b) Scaling of computation time with respect to agents/region with 6 pJAM regions (summarising all nodes and 10000 simulation steps)

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Summary

PD Stefan Bosse - Parallel and Distributed Agent-based Simulation

Any Questions?

Parallel and Distributed Agent-based Simulation of large-scale socio-technical Systems with loosely coupled Virtual Machines

Challenges and Pitfalls

PD Dr. Stefan Bosse

sbosse@uni-bremen.de, www.ag-0.de

University of Bremen, Dept. Mathematics and Computer Science, Bremen, Germany