Command disabled: revisions

Multi-Agent Systems

Multi-agent System (MAS for short) is a system composed of a population of entities, called agents, localized in some environment, and interacting with each other. The description of such a MAS consists of the specification of the decision procedure used by an agent to choose an action from its own state and the state of the nearby environment (which may include other agents). The decision procedure and the type of possible actions may differ and depend on the nature of the MAS (for example, reactive agents vs. cognitive agents).

In general MAS can be easily translated in MGS using two kinds of transformation rules:

  • a:agent ⇒ … neighborfold(…, …, a) … specifying the procedure decision for an agent
  • a1:agent, a2:agent ⇒ … specifying some interaction between two agents

The main difference between MAS and their MGS implementations comes from the externalization of the decision procedure from the agent in MGS: where classically in a MAS an agent is owner of its decision, in MGS actions and interactions are specified in transformations as laws governing the agents from outside. Theoretically, the two points of view are reconcilable but sometimes the expression of a MAS in MGS may suffer from the shift. Evaluate it with the examples below.

The following examples illustrate how MAS can be implemented in MGS:

  • Diffusion Limited Aggregation
  • Simplified Reynolds' boids

Diffusion Limited Aggregation

MGS Implementation

Let start by setting an option to get randomized pattern matching (remove the line and see what happens)

!set match_random := 100;;

Let define the filename for JBView visualization

ofile := "/tmp/toto" ;;

Particules are of two kinds: fixed or mobile

type particle = `Mobile | `Fixed ;;

The whole system is represented by a grid of particles

type mas = [particle]Moore ;;

Let define an initialization function populating a given grid with fixed particles as walls on the boundary and mobile particles localized at random

fun populate_grid(g:Moore, size_x:int, size_y:int, nb_particle: int) = (
 
  for i = 0 to size_x-1 do (
    g.(i * |E> + 0 * |N>) := `Fixed;
    g.(i * |E> + (size_y-1) * |N>) := `Fixed
  );
 
  for j = 0 to size_y-1 do (
    g.(0 * |E> + j * |N>) := `Fixed;
    g.((size_x-1) * |E> + j * |N>) := `Fixed
  );
 
  for p = 0 to nb_particle-1 do
    g.(<E+N> + random(size_x-1) * |E> + random(size_y-1) * |N>) := `Mobile;
 
  g
 
) ;;

Let define the initial state S0

S0 := populate_grid(Moore:(),100,100, 1000) ;;
 
mas(S0);;

Let define the evolution rules of the cells

trans behaviors = {
 
  // Aggregation
  `Fixed, `Mobile => `Fixed, `Fixed;
 
  // Diffusion (random walk)
  `Mobile, <undef> => [| <undef>, `Mobile |];
 
} ;;

Let define a function to save data for the viewer

fun output(S) = (
 
  ofile << " { " ;
  foreach c @ p in S do
    begin
      let (x,y) = sequify(p) in
        ofile << " { " << x << " " << y;
        ofile << switch c
                 case `Mobile: " 1 0 0 } "
                 case `Fixed:  " 0 1 0 } "
                 endswitch
    end;
  ofile << " }\n" ;
  S
 
) ;;

Let save data during the simulation

behaviors[iter = 300,
          prelude = output,
          interlude = output,
          postlude = output
         ](S0) ;;

The whole code follows

dla.mgs
!set match_random := 100;;
 
ofile := "/tmp/dla.jbv" ;;
 
type particle = `Mobile | `Fixed ;;
 
type mas = [particle]Moore ;;
 
fun populate_grid(g:Moore, size_x:int, size_y:int, nb_particle: int) = (
 
  for i = 0 to size_x-1 do (
    g.(i * |E> + 0 * |N>) := `Fixed;
    g.(i * |E> + (size_y-1) * |N>) := `Fixed
  );
 
  for j = 0 to size_y-1 do (
    g.(0 * |E> + j * |N>) := `Fixed;
    g.((size_x-1) * |E> + j * |N>) := `Fixed
  );
 
  for p = 0 to nb_particle-1 do
    g.(<E+N> + random(size_x-1) * |E> + random(size_y-1) * |N>) := `Mobile;
 
  g
 
) ;;
 
S0 := populate_grid(Moore:(),100,100, 1000) ;;
 
mas(S0);;
 
trans behaviors = {
 
  // Aggregation
  `Fixed, `Mobile => `Fixed, `Fixed;
 
  // Diffusion (random walk)
  `Mobile, <undef> => [| <undef>, `Mobile |];
 
} ;;
 
fun output(S) = (
 
  ofile << " { " ;
  foreach c @ p in S do
    begin
      let (x,y) = sequify(p) in
        ofile << " { " << x << " " << y;
        ofile << switch c
                 case `Mobile: " 1 0 0 } "
                 case `Fixed:  " 0 1 0 } "
                 endswitch
    end;
  ofile << " }\n" ;
  S
 
) ;;
 
behaviors[iter = 300,
          prelude = output,
          interlude = output,
          postlude = output
         ](S0) ;;

Reynolds' Boids

MGS Implementation

Let define the filename for JBView visualization

ofile := "/tmp/toto" ;;

A boid is characterized by

  • its cartesian coordinates in 2D (x, y)
  • its orientation/angle (t)
  • an integer (w) representing a number of boids which has to be 1 for a regular boid
record pre_boid = { x:float, y:float, t:float, w:int } ;;
record boid = pre_boid + { w = 1 } ;;

A population is represented by a geo-proximal of boids

  • two boids are neighbors if the distance between them is less than 5.0
  • the space is 2D and cyclic on each dimension with a period of 20 radius (ie 100.)
  • the last expression is an anonymous function used to extract the coordinates of a boid
geoprox population((20, 20), 5.0) = fun b -> (b.x, b.y) ;;

Let define the initial state S0 which consists of 100 regular (w=1) boids localized and oriented randomly

fun cons_random_boid(id, pop) = { x = random(100.), y = random(100.), t = random(2.0 * PI), w = 1 } :: pop ;;
 
S0 := fold(cons_random_boid, population:(), 100) ;;

Let define some functions to manage boids, respectively

  • the squared distance between two boids
  • the addition of two boids (w counts the number of summed boids)
  • the position update function (Euler integration with time step dt)
  • the predicate checking if two boids are too close
  • the predicate checking if two boids are too far
fun dist2(b1,b2) = (
  let dx = b1.x - b2.x
  and dy = b1.y - b2.y
  in
    dx * dx + dy * dy
) ;;
 
fun add_boids(b1,b2) =
  { x = b1.x + b2.x,
    y = b1.y + b2.y,
    t = b1.t + b2.t,
    w = b1.w + b2.w }
;;
 
fun move_boid[dt=0.1](b) =
  let x = (b.x + dt * cos(b.t) + 100.0) % 100.0
  and y = (b.y + dt * sin(b.t) + 100.0) % 100.0 in
    b + { x = x, y = y }
;;
 
fun too_close(b1, b2) = dist2(b1,b2) <= 1.0 ;;
 
fun too_far(b1, b2) = dist2(b1,b2) >= 16.0 ;;

Let define the three boid behaviors: separation, cohesion and aligment

trans rules = {
 
  // Separation rule
  b / neighbors_exists(too_close(b), b) => (
    let g = neighbors_fold(add_boids, { x = 0., y = 0., t = 0., w = 0 }, b) in
    let dx = b.x - g.x / g.w
    and dy = b.y - g.y / g.w  in
    let t = if dy == 0. && dx <= 0. then PI else 2. * atan(dy / (dx + sqrt(dx*dx + dy*dy))) fi in
    let b' = b + { t = t } in
      !! g.w > 0;
      move_boid(b')
  );
 
  // Cohesion rule
  b / neighbors_forall(too_far(b), b) => (
    let g = neighbors_fold(add_boids, { x = 0., y = 0., t = 0., w = 0 }, b) in
      if g.w == 0 then move_boid(b)
      else
        let dx = g.x / g.w - b.x
        and dy = g.y / g.w - b.y in
        let t = if dy == 0. && dx <= 0. then PI else 2. * atan(dy / (dx + sqrt(dx*dx + dy*dy))) fi in
        let b' = b + { t = t } in
          move_boid(b')
      fi
  );
 
  // Alignment rule (default rule)
  b => (
    let g = neighbors_fold(add_boids, b, b) in
    let b' = b + { t = g.t / g.w } in
      move_boid(b')
  );
 
} ;;

For managing the separation rule as an interaction preventing collision, prefer

  // Separation rule (interaction alternative)
  b1, b2 / too_close(b1,b2) => (
    let dx = b1.x - b2.x
    and dy = b1.y - b2.y in
    let t1 = if dy == 0. && dx <= 0. then PI else 2. * atan(dy / (dx + sqrt(dx*dx + dy*dy))) fi in
    let t2 = t1 + PI in
    let b1' = b1 + { t = t1 }
    and b2' = b2 + { t = t2 } in
      move_boid(b1'), move_boid(b2')
  );

Let define a function to save data for the viewer

fun output(S) = (
  if (iteration % 10 == 0)
  then
    ofile << " { " ;
    foreach b in S do (
      ofile << " { " << b.x << " " << b.y << " 0 0 0 } ";
      ofile << " [ " << b.x << " " << b.y << " " << (b.x + 5*cos(b.t)) << " " <<(b.y + 5*sin(b.t)) << " 1 0 0 ] "
    );
    ofile << " }\n"
  fi;
  S
) ;;

Let save data during the simulation

rules[iter = 10000,
      prelude = output,
      interlude = output,
      postlude = output
     ](S0) ;;
boids.mgs
ofile := "/tmp/toto" ;;
 
record pre_boid = { x:float, y:float, t:float, w:int } ;;
record boid = pre_boid + { w = 1 } ;;
geoprox population((20, 20), 5.0) = fun b -> (b.x, b.y) ;;
 
fun cons_random_boid(id, pop) = { x = random(100.), y = random(100.), t = random(2.0 * PI), w = 1 } :: pop ;;
 
S0 := fold(cons_random_boid, population:(), 100) ;;
 
fun dist2(b1,b2) = (
  let dx = b1.x - b2.x
  and dy = b1.y - b2.y
  in
    dx * dx + dy * dy
) ;;
 
fun add_boids(b1,b2) =
  { x = b1.x + b2.x,
    y = b1.y + b2.y,
    t = b1.t + b2.t,
    w = b1.w + b2.w }
;;
 
fun move_boid[dt=0.1](b) =
  let x = (b.x + dt * cos(b.t) + 100.0) % 100.0
  and y = (b.y + dt * sin(b.t) + 100.0) % 100.0 in
    b + { x = x, y = y }
;;
 
fun too_close(b1, b2) = dist2(b1,b2) <= 1.0 ;;
 
fun too_far(b1, b2) = dist2(b1,b2) >= 16.0 ;;
 
trans rules = {
 
  b / neighbors_exists(too_close(b), b) => (
    let g = neighbors_fold(add_boids, { x = 0., y = 0., t = 0., w = 0 }, b) in
    let dx = b.x - g.x / g.w
    and dy = b.y - g.y / g.w  in
    let t = if dy == 0. && dx <= 0. then PI else 2. * atan(dy / (dx + sqrt(dx*dx + dy*dy))) fi in
    let b' = b + { t = t } in
      !! g.w > 0;
      move_boid(b')
  );
 
  b / neighbors_forall(too_far(b), b) => (
    let g = neighbors_fold(add_boids, { x = 0., y = 0., t = 0., w = 0 }, b) in
      if g.w == 0 then move_boid(b)
      else
        let dx = g.x / g.w - b.x
        and dy = g.y / g.w - b.y in
        let t = if dy == 0. && dx <= 0. then PI else 2. * atan(dy / (dx + sqrt(dx*dx + dy*dy))) fi in
        let b' = b + { t = t } in
          move_boid(b')
      fi
  );
 
  b => (
    let g = neighbors_fold(add_boids, b, b) in
    let b' = b + { t = g.t / g.w } in
      move_boid(b')
  );
 
} ;;
 
fun output(S) = (
  if (iteration % 10 == 0)
  then
    ofile << " { " ;
    foreach b in S do (
      ofile << " { " << b.x << " " << b.y << " 0 0 0 } ";
      ofile << " [ " << b.x << " " << b.y << " " << (b.x + 5*cos(b.t)) << " " <<(b.y + 5*sin(b.t)) << " 1 0 0 ] "
    );
    ofile << " }\n"
  fi;
  S
) ;;
 
rules[iter = 10000,
      prelude = output,
      interlude = output,
      postlude = output
     ](S0) ;;

Personal Tools