Information Technology Reference
In-Depth Information
model checked, such as whether there is an emergent behaviour in the system when this
MAS is massively populated with similar agents. This idea is captured in Section 5,
which leads to the development of a supporting framework for modelling and verifica-
tion of bio-MAS. Finally, a discussion and ideas for future work conclude the paper.
2
Background on X-Machines: Theory, Definition and Practice
An X-machine (XM) resembles a Final State Machine (FSM) with the power of being
more expressive [10]. This is achieved due to the addition of a memory, and functions
operating on the inputs and memory values. Considering stream XMs (a representative
class of XMs), the memory is a typed tuple of values which supports the modelling of
complex data structures. The control, on the other hand, can be visualised by utilising
a diagrammatic approach. Thus stream XMs have the ability of modelling both the
data (held in the memory) and the control. The processing of the data is modelled by
transitions between states, represented with functions. A function receives the memory
values together with an input, performs changes on these memory values and produces
an output. Based on the current state and application of a function, the stream XM
evaluates the next state.
Formally, a stream XM can be described as an 8-tuple XM = (
Σ
,
Γ
,Q,M,
Φ
,F,
q
0
,
m
0
), such that [11, 12]:
-
Σ
and
Γ
are the sets of input and output symbols, respectively;
-
Q is a finite set of states;
-
M is an n-tuple called memory;
-
Φ
is a finite set of partial functions that map an input and a memory state to an
output and a new memory state,
φ
:
Σ
M;
-
F is a function that determines the next state, given a state and a function from the
type
Φ
,F:Q
×
M
→
Γ
×
Q, for deterministic XMs; and
-
q
0
and
m
0
are the initial state and memory respectively.
With the focus on the practical development of communicating systems, the output of
an X-machine function can become input to a function of another X-machine. This way
a structure known as Communicating X-machine (CXM) is being formed, providing a
way to deal with agents communication [13, 14].
×
Φ
→
2.1
Case Study: A Foraging Agent
Let us consider the following example of an agent that randomly moves in 2-D space,
picks up an object it encounters and carries it back to the base (Fig. 1). Clearly, although
this is a very simple example, there could be quite a few solutions (from a very abstract
to more detailed one). Likewise, Fig. 2 depicts three alternative XM models that can be
considered as solutions to the foraging agent problem.
Table 1 demonstrates three ways of modelling the foraging agent problem (the num-
bering (a), (b) and (c) corresponds to the numbering in Fig. 2). Solution (a) is a very
abstract representation that does not even take into consideration the position coor-
dinates of the agent. The fact that XMs are generic and do not impose modelling of
