The Azimuth Project
Experiments in bigraphs (part 2) - Bigraphical Reactive Systems (changes)

Showing changes from revision #1 to #2: Added | Removed | Changed

I’ve started reading about bigraphs and Bigraphical Reactive Systems (BRS), and I think I have the basic idea. I still have a lot to learn, but it’s helpful to write as I’m learning. In this experiment, I use an example to work through something that is at least similar to BRS, something that I’m already familiar with.

A Petri net can readily be transformed into an Agent Based Model (ABM), where Place and Transition nodes are agents that constantly move around in a Grid. A grid has two or more Row nodes, and each row has two or more GridCell nodes. An 80 by 120 grid has 80 rows and each row has 120 grid cells.

The grid can be populated with places and transitions from the Petri net. If the types of places in a Petri net are A, B, C, D, and E, and if the current marking for places in the Petri net is:

A:140, B:180, C:200, D:25, E:80

then the grid will contain 140 separate A nodes, 180 B modes, and so on. If the Petri net has six types of transitions (A_BB, BB_A, AC_D, D_AC, D_BE, BE_AC), then we could also add 10 of each of these to the grid, for a total of 60. Each place and transition node is added at a random location in the grid, as a child of a GridCell node.

The result would look similar to the following image which has 80 x 120 = 960 grid cells. The small black squares are empty grid cells. The colored squares are grid cells that contain one or more places or transitions. There should be a total of 140 + 180 + 200 + 25 + 80 = 625 place nodes, and 6 * 10 = 60 transition nodes.

Agent Based Modeling - Feinberg 1.1

Let’s drill down and have a closer look at one grid cell. The following image is composed of four separate windows from a simulation of this Petri net that’s been transformed into an ABM. The grid is only 20 x 20 to make it easier to work with. The window on the left shows part of the model as a tree structure. Node 1 contains the details of the Petri net specification. Node 99 contains the 20 rows of the grid. Each row contains 20 GridCell nodes. Many of the grid cells contain Transition and/or Place nodes. For example, gridCell_212 contains a transition of type A_BB (a_BB_1780) and a place of type A (A_531). Each transition contains two behavior nodes, and each place contains one behavior node. A moving behavior knows how to move the node it belongs to, and a firing node knows how to fire the transition it belongs to. A graphical visualization of the 20 x 20 grid appears as a small window in the upper right portion of the image.

Bigraphical Reactive System - Feinberg 1.1

A bigraph consists of two graphs, a Place Graph and a Link Graph. The lower right window in the image shows a small part of the place graph, and the upper right window shows a small part of the link graph. The place graph shows the structure of one GridCell node. It contains a Transition node and several Place nodes, each of which in turn contain behavior nodes. The link graph shows what other nodes that GridCell node is linked to, and also shows what its child nodes are linked to. As you can see, the grid cell is linked to eight other grid cells, its neighbors in the grid. The transition node (a_BB_1780) is linked to four nodes inside the Petri net.

The transition node (a_BB_1780) links to a single InputArc node that links to a Place node (a_7). The place specifies the type of node that the transition is allowed to act on. In this case, the place is an A node, so the transition must find an A node in the grid that it can act on. The Petri net specifies the rule for the transition, and the FiringTransitionBehavior node executes the rule if there’s a match.

The following Petri net rule specifies that an A_BB transition node will fire if it has access to at least 1 A place node. If it does fire, it will transform one A node into two B place nodes.

<A_BB>
  <InputArcs>
    <InputArc connector="A" weight="1" />
  </InputArcs>
  <OutputArcs>
    <OutputArc connector="B" weight="2" />
  </OutputArcs>
</A_BB>

In the ABM (Grid) implementation of the Petri net, if the following input pattern is present:

<GridCell>
  <A_BB/>
  <A/>
  <!-- other nodes that aren't part of this reaction -->
</GridCell>

then it will be transformed into the following result:

<GridCell>
  <A_BB/>
  <B/>
  <B/>
  <!-- other nodes that aren't part of this reaction -->
</GridCell>

This is essentially what a Bigraphical Reactive System (BRS) does. BRS calls the input pattern a redex, and the result a reactum. To quote from the 2006 Matching of Bigraphs paper by Birkedal, Damgaard, and Glenstrup:

Bigraphical Reactive Systems (BRSs) provide a graphical model of computation in which both locality and connectivity are prominent. In essence, a bigraph consists of a place graph; a forest, whose nodes represent a variety of computational objects, and a link graph, which is a hyper graph connecting ports of the nodes. Bigraphs can be reconfigured by means of reaction rules. Loosely speaking, a bigraphical reactive system consists of a set of bigraphs and a set of reaction rules, which can be used to reconfigure the set of bigraphs. … There is a reaction rule expressed by the redex R and the reactum R’ … (with R and R’ both bigraphs).

In the Petri-net-as-a-Grid example, the model is a bigraph because it consists of both a place graph and a link graph. A small part of that bigraph is illustrated in the above image. We can observe from the place graph (such as in the tree representation on the left of the image) the current location of various nodes, and we can also observe how some of the nodes are connected (such as in the link graph in the upper right of the image). Note that the same nodes belong to both the place graph and the link graph. The nodes have ports, some of which are named in the description line at the lowermost left part of the image. The reaction rules are specified by the Petri net transitions (such as a_BB_13), each of which is itself a bigraph with hierarchical structure (a place graph) and internal connections (a link graph). The input arcs specify (approimately) the BRS redex, and the output arcs specify the BRS reactum.

category: experiments