Part V. Agent-Based Modeling and SimulationChapter 16. Basic Agents with Perfect Information (44/52)16.3. Interleaved Agent Simulation

Chapter 16. Basic Agents with Perfect Information

Basic agents are objects that (1) have an information state, (2) may have perceptions of their environment affecting their information state, and (3) may communicate with each other and, as a consequence, change their information state. We define perfect information agents as basic agents that

  1. have complete and correct information about all objects they know;
  2. are sincere: they do not provide intentionally incorrect information in their communications with other agents (that is, they do not lie).

Condition 1 does not hold for physical agents in the real-world, such as humans, animals or robots. Rather it's a simplifying assumption that we may want to make in a simulation model abstracting away from the limitations of real-world agents. Condition 2 typically holds for robots (and other artifact agents), but not for humans.

In A/OEM&S, agents are, by default, perfect information agents with

  1. two collection-valued properties, objects and agents, which represent their information state (the objects and agents they know);

  2. three generic "event-handling" operations that are invoked by the simulator when processing message events, perception events or action events for a particular agent:

    1. onReceive for handling in-message events (i.e., for receiving messages),
    2. onPerceive for handling perception events (i.e., for perceiving percepts), and
    3. perform for handling action events (i.e., for performing actions).

  3. two generic (shortcut) operations for agents to perform send message actions:

    1. send for sending a message to another agent (by scheduling a generic MessageEvent with a single receiver),
    2. broadcast for sending a message to all agents known by a given agent (by scheduling a generic MessageEvent with many receivers).

This is depicted in the following diagram showing an A/OEM&S meta-model fragment:

A conceptual process model in the form of a DPMN diagram

In A/OEM&S, the behavior of an agent is encapsulated in its event handling operations onPerceive and onReceive for reacting to perceptions and incoming messages, and perform for performing actions.

In a standalone (non-distributed) simulator for A/OEM&S, the most efficient way of implementing inter-agent communication is achieved by having the sender directly invoking a message reception method of the receiver (corresponding to synchronous message passing).

However, such an implementation would bypass the fundamental event scheduling mechanism of OEM&S, which also warrants the occurrence time consistency of events. Each perception and each action (including message send actions) of an agent should be processed by a simulator as an event.

There are two alternative architectures for simulating agents and their interactions with their environment and with each other:

  1. An interleaved architecture that interleaves the processing of events and the execution of agent behavior.
  2. A round-based architecture that first processes all current events and then waits for the execution of all agents' behaviors before it proceeds.

The interleaved architecture allows the immediate processing of perception events and message events by the simulator, while the round-based architecture requires to pass percepts and messages to affected agents and wait for their reactions.

16.1. Perception and Action

Agents may perceive objects and events in their environment and, in response, take certain actions, possibly causing changes in their environment.

One can distinguish between a passive and an active form of perception. Passive perception takes place asynchronously, while an agent is busy or idle, in the form of (instantaneous) perception events, while active perception requires the agent to perform a perceptive action or activity (like scanning the neighborhood). In general, agents are exposed to perception events and may react in response to them.

In the case of physical agents, like robots, passive perception events are created by a sensor containing an event detector, such as a Proximity Infra-Red (PIR) sensor, which has its output pin going high whenever it detects an infra-red emitting object (e.g., a human or a medium to large sized animal) in its reach. Active perceptions are created by querying the measurement value of a sensor containing a quality detector, such as a DHT22 temperature and humidity sensor. The distinction between event detectors and quality detectors has been proposed in (Diaconescu and Wagner 2015).

Perception events typically lead to an update of existing beliefs or to the creation of new beliefs.

16.2. Communication

There are various forms of communication between agents. In particular, we can distinguish between verbal and non-verbal communication. We are only concerned with verbal communication, which is based on messages.

Ontological Considerations

Conceptually, a communication event is composed of two successive atomic events: an out-message event (corresponding to a message send action of the sender) and a correlated in-message event (or message reception by the receiver). This is illustrated by the following diagram:

A conceptual process model in the form of a DPMN diagram

This concept diagram expresses the following ontological stipulations:

  • A message is sent from a sender agent to one or more receiver agents via an out-message event.

  • A message from a sender agent is received by a receiver agent via an in-message event.

  • A communication event consists of a pair of correlated out/in message events out and in, such that the following conditions hold:

    • in.message = out.message
    • in.receiver is included in out.receivers
    • in.sender = out.sender
    • in.occurrenceTime > out.occurrenceTime

Communication events may lead to updates (and deletions) of existing beliefs or to the creation of new beliefs, especially in information exchange processes based on Tell-Ask-Reply messages.

Message Types

Each message is of a certain type defining its properties and implicit semantics. There are two kinds of message types:

  1. User-defined problem/domain-specific message types: the structure of such a message type is defined within a simulation model in the form of a class defining its properties; their semantics is defined in the receive methods of receiver agents in terms of how messages of such a type are processed.
  2. Pre-defined problem/domain-independent message types: Tell and Ask/Reply are examples of problem/domain-independent message types that may be supported by a simulator. As they refer to general speech acts, the semantics of these message types should be based on the philosophical speech act theory of Austin and Searle.
A conceptual process model in the form of a DPMN diagram

There are two prominent agent communication language standards: FIPA and KQML (Finin et al 1997), both defining domain-independent standard message types with a semantics based on speech act theory. We briefly describe the rules for processing Tell, Ask, Reply and Request messages:

Tell

Using this message type, agents may communicate some of their beliefs to other agents, without being asked. In general, a teller may tell the truth or may lie; and in both cases the provided information may or may not be correct.

A Tell message is similar to what is called a Signal in the Unified Modeling Language (UML) where a Signal is sent asynchronously from an object to another object. The event rule for processing a Signal reception event is defined by specifying a Reception operation in the classifier of the receiver object, such that this operation has the same name as the type of the Signal (and a corresponding signature). We do not use these UML concepts (and the UML terminology) since they are too limited.

Ask
Using this message type, an agent may query another agent about some of its beliefs. Queries are expressed in a suitable query language, such as the RDF-based query language SPARQL. An asker expects to receive an answer via a Reply message some time later.
Reply
This message type is used for replying to a previously received Ask message. In general, the answers provided may or may not be correct. Therefore, askers should only update their beliefs according to the received answers when they trust the replier.
Request
This message type is used by an agent for requesting another agent to perform a certain action. Such a request can be either accepted or rejected.

Since a perfect information agent already has complete information about the objects it knows,

  • sending a query via an Ask message only makes sense if the query may retrieve objects the sender does not yet know;
  • sending an answer via a Reply message only makes sense if the answer provides information about objects the receiver does not yet know;
  • receiving a statement via a Tell message only makes sense if the statement provides information about an object the receiver does not yet know.