Logo image cannot be loaded

IODA Formal Model

The formal model of IODA defines precisely what informations the model of a simulation has to contains, and how these informations have to be represented.

The presentation of the formal model of IODA uses the following plan:

  1. Preliminary comment
  2. Interactions
    1. Polymorphism
    2. Interaction Typology
    3. Agent function in an interaction
    4. Interaction formal definition
  3. Interaction Matrix
    1. Limit distance
    2. Agent family and Agent instance
    3. Interaction matrix formal definition
  4. Agents
    1. Perception halo
    2. Realizable tuples census
    3. Interaction selection
    4. State update
    5. Agents formal definition
  5. Environment
  6. Simulation

Back to top Preliminary comment

The difference that lies between agents, objects of the scenery, or tools that lie in the environment is merly operational: it depends only on the interactions they can participate in. Thus, IODA considers that the representation of the whole entities contained in a simulation can be unified in a single notion that we call Agent.

Back to top Interactions

IODA relies on an homogeneous representation of actions performed by agents, called Interaction.

An interaction is a semantic block of actions involving simultaneously a fixed number of agents, which describes how and under what kind of conditions agents may interact one with others or with the environment.

Similarly to PRS action representation, the conditions of an interaction are the conjunction of:

  • preconditions that describe the logical or physical conditions required to initiate the interaction. For instance, "The position where the source wants to move is empty" for a Move interaction, or "The target is not rotten" for an Eat interaction;
  • triggers that describe the teleonomic part of the conditions - i.e. explicit or implicit goals this interaction aims at. For instance "The source is hungry" for the Eat interaction, since its implicit goal is to reduce the hunger sensation of the source.
Highslide JS
Fig.2: General structure of an interaction (a) applied to the Eat interaction (b), which describes how an X agent eats an Y agent.

Back to top Polymorphism

Designing generic and agent-independent interactions is not easy. Indeed, every interaction has parts, which description depends on the agents that interact. Yet, even if interaction have agent specific elements, their overall semantic might be similar.

To cope with this issue, IODA upholds that interactions manipulate abstract and agent-independent primitives, instead of directly manipulating agent states. These abstract primitives are declared in interactions as factory methods that the agents have to implement.

For instance, the isHungry() primitive of Fig.1(b) can be implemented in agents as:

Back to top Interaction Typology

Agents involved in an interaction generally do not play the same function. Difference is made between agents that initiate the interaction -- for which the participation in the interaction comes from their own action selection process -- and agents that undergo the interaction -- which are chosen by the action selection process of source agents.

The Source agents of an interaction are the set of agents that initiate the interaction, and the Target agents are the set of agents that undergo the interaction.
Highslide JS
Illustration of how an interaction between agents is considered as possible.

This figure tells that a woodcutter agent can be the source of the Cut and Open interactions, and can be the target of the Fall and the Kill interaction. The tree agent can be the source of the Fall interaction, and can be the target of the Burn, Cut and the Break interactions. Consequently, the Woodcutter might be able to cut trees (this interaction is represented by an arrow).

Fig.2: Illustration of how an interaction between agents is considered as possible.

The cardinality of an interaction defines how many source and target agent participate in the interaction:

The cardinality of an interaction is a pair (n,p), where:
  • n is the number of source agents involved in the interaction.
  • p is the number of target agents involved in the interaction.

Complex problems may require to define particular situations like the interaction of an agent with itself -- for instance to Rest -- or with the environment -- for instance to Move or to Die. Calling them interaction may seem questionable since they involve a single agent -- i.e. their cardinality is (1,0). Yet, their structure is identical to regular interactions, and they do have an implicit target. Thus, to make the definition of agents abilities homogeneous, such elements are called degenerate interactions.

Reflexive interactions -- i.e. interactions that target the source itself -- and interactions involving only the environment are cases where the target of the interaction is implicit. Such interactions, which cardinality is (1,0), are called Degenerate Interactions.

Back to top Agent function in an interaction

In order to participate in an interaction, an agent has to implement a particular set of abstract primitives. Yet, all the agents involved in an interaction do not have to implement the same primitives. To differentiate the primitives that agents have to implement, we introduce the notion of function in an interaction.

Interactions are meant to be re-used in various contexts, potentially by different designers. Since the aim of the different primitives cannot always be deduced thanks to their name, each function has to provide a documentation to each primitive it contains.

An function in an interaction corresponds to the set of abstract primitives that an agent has to implement in order to participate in the interaction. It provides a documentation to each primitive, to make their implementation in agents possible.

Consequently, an interaction has to define as many functions as its cardinality states.

In this page, we focus on interactions, which cardinality is either (1,0) or (1,1). In such cases, at most two functions have to be defined: the Source function (i.e. the primitives that the source agent has to implement), and the Target function (i.e. the primitives that the target agent has to implement).

Back to top Interaction formal definition

Thanks to all the elements defined above, the formal definition of an interaction is as following:

An interaction is a semantic block of actions involving simultaneously a fixed number of agents, which describes how and under what kind of conditions agents may interact one with others or with the environment. It is defined by:
  • a trigger, which is a boolean expression describing the implicit or explicit goal of the interaction;
  • preconditions, which are a boolean expression describing the logical or physical conditions required to initiate the interaction;
  • actions, which correspond to the modification of agents and of the environment made by the interaction;
  • a cardinality, which defines the number of agents that are involved in it;
  • a set of functions, which are played by the different agents involved in it.

Back to top Interaction Matrix

An overview on the interactions occurring in the simulation can be displayed in an Interaction Matrix. Such a matrix defines what interactions an agent instance can initiate as a source together with another agent instance as target (see Fig. 3).

Highslide JS
Fig.3: Interaction Matrix of an ecosystem simulation, where wolves, sheep, goats and grass agents evolve. The element (Eat, d = 0) at the intersection of the line starting with Sheep and the column starting with Grass is read "Sheep agents are able to initiate the Eat interaction with a target Grass agent that lies at a maximal distance of 0 from the source".

Degenerate interactions do not have explicit target. Yet, the interaction matrix aims at providing a summary of all interactions occurring in the simulation. Consequently, a particular column - labeled with a ∅ character - is added in order to display all degenerate interactions a source agent might initiate.

Back to top Limit distance

An agent does not interact with any other agent: it interacts only with agents that are close enough from it. This distance - called limit distance - depends not only on the interaction, but also on the agents that participate in the interaction. For instance, a sheep may Eat grass agents only at a distance of 0 (only at their feet), but a chameleon may Eat insect agents at a greater distance thanks to its tongue. Consequently, a cell of the matrix does not contain interactions, but assignation elements.

An assignation element corresponds to the representation, in the interaction matrix, of an interaction that a source agent is able to initiate. Assignation elements can either:
  • represent a degenerate interaction I that the source agent is able to initiate. Such assignation elements are called degenerate assignation elements, and are written (I) in the matrix. They are put in the column of the matrix labeled by ∅
  • represent a non-degenerate interaction I that the source agent is able to initiate with a particular target agent. The interaction is possible only if the distance between these agents is lower or equal to a limit distance dist. Such an assignation element is written (I, d = dist) - or (I, dist) for short.

Back to top Agent family and Agent instance

In IODA, difference is made between agent instances and agent families.

An agent family is an abstract specification of agents, which share all or part of their primitives, abilities or behavior. An agent instance instantiates at least one agent family, and instances of an agent families can be reduced to a singleton.

During simulation, interactions occur between agent instances. Yet, it is their agent families that define what they are able to initiate or undergo. Thus, the interaction matrix specifies what instances of particular agent families are able to initiate together with instances of particular agent families as target.

Back to top Interaction matrix formal definition

The interaction matrix is the set of all possible assignations of the simulation:
The assignation aS/T represents the set of interactions that an agent from the S family is able to initiate with a target agent from the T family. The elements of aS/T are non-degenerate assignation elements. The set of degenerate interactions an agent from the S family is able to initiate is labeled aS/∅, and contains only degenerate assignation elements.

An assignation represents a cell of the interaction matrix.

Let F be the set of all agent families. A raw interaction matrix M represents all interactions that occur between the different agents during simulation. It is the aggregation of all possible assignations of the simulation: M = (aS/T) S ∈ F, T ∈ F ∪ {∅}.

An interaction matrix illustration on a toy problem is provided on Figure 3. This matrix defines the possible interactions between entities in an ecosystem simulation, where the different species are Grass, Sheep, Goat and Wolf.

Back to top Agents

In IODA, agents are represented homogeneously. It makes possible to design a wide set of interactions independently from the reactive, cognitive or hybrid nature of agents. An agent is an autonomous entity instantiated from an agent family.

When the scheduler of the simulation asks an agent to behave, the agent:

  1. gets the set of agents it perceives;
  2. gets the set of all interactions it can perform in its context. This set contains either degenerate interactions, which condictions are true, or couples (interaction, target agent);
  3. selects among the latter set of elements the interaction it will initiate. The agent can select no elements;

Each of these steps is presented below.

Back to top Perception halo

An agent does not interact with any kind of agents: it interacts only with the agents it perceives. In IODA, the perception process is defined thanks to the notion of halo. An agent perceives only its neighborhood -- i.e. the agents that are present into its halo.

The Halo of an agent A is the process that tells how to get the agents perceived by A. The Neighborhood of an agent A is the set of all agents A retrieved thanks to its halo -- i.e. it is the set of perceived agents.

The description of agents halo depends on what kind of environment is used in the simulation. In most cases, the halo defines in what subset of the environment agent are perceived. This halo depends of the nature of environments topology:

  • a surface in a two dimensional space;
  • a volume in a three dimensional space;
  • acquaintances in a contact network, etc.

The Halo can also include agents within the memory of perceiving agent.

Because the definition of the halo is domain-dependent, IODA does not constrain its specification. Moreover, IODA does not make any assumption on the environment used in the simulation, as long as a distance can be expressed in it (in order to define the limit distances in the interaction matrix).

Back to top Realizable tuples census

The set of interactions an agent can perform in a particular context depends on both its abilities -- i.e. what interactions it is able to initiate with target agent families -- and on the agents that lie in its neighborhood.

This set is called realizable tuples set. A realizable tuple represents either:

  • a degenerate interaction, which conditions hold true for the source agent;
  • or a couple containing an interaction and a target agent, such that the conditions of the interaction hold true for the source agent and target agents;

Realizable tuples census is part of the algorithms available in the IODA project. More details are provided on this page.

Back to top Interaction selection

Interaction selection consists in selecting from the realizable tuples of a source agent the one that represents the interaction it initiates. The modalities of this selection depend on whether the agent is a cognitive, hybrid, or reactive one.

IODA is compatible with any interaction selection processes.

The specification of the behavior of reactive agents is described on this page.

Back to top State update

The state of agents may evolve independently from the interactions in which they participate. For instance, an agent may grow old, a pheromone have its concentration dropping, etc. In IODA, such a process is defined by agents in a primitive called Updating Primitive.

The call to this primitive depends on the time representation used in the simulation -- i.e. depends on the scheduler used in the simulation. An algorithm presenting its call in the case of discrete time is presented on this page.

Like the halo, the specification of agents updating process is domain-dependent.

Back to top Agents formal definition

Thanks to all the elements defined above, in IODA, agents and agent families follow a simple architecture, which makes possible to design homogeneously agents with different specificities in the same simulation.

An agent family is an abstract specification of agents, which share all or part of their primitives, abilities or behavior. Such a family is defined by:

The interaction matrix is a whole only during model specification. In practice, the interaction matrix lines are dispatched between the different source agent families.

The structure of agents is highly customizable: their halo can be changed independently from what they are able to do, or their interaction matrix line can be defined independently from their interaction selection process, etc.

Back to top Environment

In IODA, the environment only contains agents. It provides support to compute the distance between agents, as well as to compute their halo.

Back to top Simulation

Providing a generic simulation algorithm is almost impossible, because of the great differences between discrete, continuous, or discrete event time representations. Yet, the semantic of agent and interactions in a simulation can be defined independently from the time representations. Indeed, the Eat interaction (as described in Fig.1) can be defined independently from answering the question how much simulation time an agent has to Eat before finishing its meal ?. Thus, IODA make no assumption on the time representation used in the simulation.

This does not mean that agent and interactions are completely independent from time issues. When a time representation is chosen, the model built with IODA will be refined to add time related informations. For instance, answers to the questions:

The page presenting JEDI describes an accurate implementation of IODA concepts in an application dedicated to discrete time simulations occurring in a two dimensional environment.

Copyright © 2001-2009 Philippe Mathieu  --   Legal mentions  --   Valid XHTML 1.0 Transitional  --  W3C validation image