Distributed Artificial Intelligence

Introduction to DAI

martedì 29 settembre 2020 18:54

What is Distributed Artificial Intelligence?

What is Intelligence?

Perceiving:

- ○ Perceiving and understanding what happens in the environment in which an entity lives,

which can be a virtual, a physical or a computational environment.

○ The environment includes the perceiving entity, so perceiving is also about self-

perception.

Reasoning:

- ○ Deducing new information/conclusions from what an entity perceives.

○ Known also as "theoretical reasoning".

Acting:

- ○ Capability of acting with a purpose, to achieve desired situations in the environment.

○ Also known as "practical reasoning".

Adaptivity:

- ○ Reasoning and acting depend on the current situation, being able to change conclusions

and course of actions in presence of changing situations.

The real world is not predictable, so no a-priori plan is guaranteed to work:

An entity must consider possibility for the original plan to fail.

- An entity must be capable of dinamically replan actions.

-

What is DAI?

A system of multiple distributed entities in need to interact/coordinate to express intelligence in the

environment at a global level.

Single AI vs Distributed AI - DAI Definition

Distributed Perception:

- ○ Different entities may perceive different portions of the environment.

○ There may be need to interact to build a common perception of the environment.

○ One entity should consider that the others have different viewpoints.

Distributed Reasoning:

- ○ Different perceptions can lead to different conclusions during theoretical reasoning.

○ There may be need to interact to reconcile conclusions.

○ One entity should consider that the others may have reached different conclusions.

Distributed Acting:

- ○ The capabilities of acting entities are different.

To reach its own goal, a single entity should select its actions by taking into account what

Distributed Artificial Intelligence Pagina 1

○ To reach its own goal, a single entity should select its actions by taking into account what

the others will do.

○ To reach a collective goal the different entities should coordinate their actions.

All of which in an adaptive way.

-

If we have an environment in which all entities perceive the same, reach the same conclusions, and all

can do actions, we don't have a DAI system, but a parallelized AI system (it can be reconducted as a

single AI problem).

Motivations for DAI

Some individual AI may live in the same environment, they need to coordinate to reach their

- individual goals.

Some problems are inherenlty distributed and complex, and cannot be approached by individual

- AIs: Perception, Reasoning, Acting.

Reliability:

- ○ Multiple AIs act together to survive crashes.

○ No single point of failure (SPOF).

Emergent DAI:

No individual intelligence, but system property. There is no reasoning, but only perception and acting.

Distributed Systems vs DAI

What is a Distributed System in General?

A DAI system is a distributed system with some levels of intelligence in it.

Distributed Architecture definition:

A distributed architecture is a set of connected computational elements that do not share

- memory and/or clock and/or space.

Each computational element has its own memory and clock (no global time).

- There is a communication system that enables elements to interact.

- These systems are defined as loosely-coupled (tightly-coupled is when memory and clock are

- shared).

DAI systems execute on distributed architectures.

Examples of distributed architectures:

Distributed System definition:

A distributed archtecture becomes a distributed system when the set of independent

- Distributed Artificial Intelligence Pagina 2

A distributed archtecture becomes a distributed system when the set of independent

- computational elements can be operated as a single coherent whole.

Node, site, machine, host and the network structure are abstracted.

- No more explicit distinction between local and remote resources and interactions.

-

DAI systems are typically based on distributed systems.

Motivations for Distributed Systems (similar to DAI ones):

Resource sharing.

- Better performance.

- Reliability (replication and no SPOF).

- Inherent distribution of the system.

-

Distributed Computing definition:

Distributed computing is when we need to solve a problem with a distributed system, where:

Each process has only a partial knowledge of the many parameters involved in the problems to

- solve.

Each process has only a partial capability of acting towards solving the problem.

-

Distributed Computing and DAI:

DAI is about distributed computing.

- There is not clear distinction, it is a matter of:

- ○ Adaptivity to unexpected situations.

○ Autonomy of the internal activities.

○ Flexibility of interactions.

○ Learning of the entities.

Distributed Algorithms definition:

A distributed computing system executes distributed algorithms:

An algorithm is made to be executed by a set of concurrently executing distributed processes.

- ○ To solve an algorithmic problem more efficiently or more robustly.

○ To solve an inherenlty distributed problem.

○ To coordinate actions of processes.

Requires interactions between the distributed entities:

- ○ To exchange information.

○ To synchronize execution of the algorithm steps.

Distributed Algorithms and DAI:

Distributed algorithms are at the basis of DAI.

- Algorithms to compute distributed information by a set of processes (perception and reasoning).

- Algorithms to coordinate actions of distribited processes (for a global goal).

- However, DAI are more than algorithms:

- ○ Algorithms typically leave little or no autonomy in decisions to processes.

○ Algorithms are typically based on fixed interactions schemes between processes.

○ Algorithms typically do not define the concept of "goal".

But we don't have a clear distinction between a non-intellingent and an intelligent algorithm.

-

Middleware

In DAI systems, the hardware network architecture enables communication between distributed

components. But we need some software to define how the components interact.

We have different software levels that contribute to that:

Operating system level.

- Middleware level.

- Application level.

- Distributed Artificial Intelligence Pagina 3

Application level.

-

Operating System Level

It is an higher level wrt the hardware. We use memories, virtual pages, files and addresses.

Network operating systems:

- ○ The user sees the nodes of the system.

○ To use a resource, the user must specify its location and address.

○ There is NO trasparency.

Distributed operating systems:

- ○ The system hides the location of the resources to the user.

○ The user accesses remote resources like local ones.

○ There is full transparency, no perception of the distributed architecture.

Network Operating systems:

Easier to develop.

- Cheaper to maintain.

- Modern OS are network operating systems with platform-independent mechanism to access

- remote resources, like socket programming, remote procedure call, remote terminal and file

transfer, remote command execution.

Distributed Operating systems:

Full transparency.

- Enable managing and programming a distributed architecture as if it was a single computer.

-

Middleware

A true distributed operating system is difficult to implement and very expensive, with low

performances.

A solution can be to rely on an additional middle level or middleware.

Middleware is a distributed software system that exploits the services of the network operating

system in order to provide services to distributed applications.

Middleware acts as a middle layer between the os-ware and the application software.

What problems Middleware solve?

Transparency and Scalability:

- ○ No need to know network and distribution details.

○ Support systems with a large number of components.

Heterogeneity:

- ○ Components may be developed with different technologies or platforms.

Application-level adaptivity:

- New components and services can join or leave the system.

Distributed Artificial Intelligence Pagina 4

○ New components and services can join or leave the system.

○ The middleware takes care of re-configuring the system and the interactions between

components upon changes.

Environment-level adaptivity:

- ○ The middleware can understand what is happening in the env and can re-configure at

run-time the components to dynamically adapt the dynamics.

Architectural Paradigms or Styles

A middleware supports a specific architectural style and a model of distributed programming.

We have:

Middleware for object oriented (client-server) distributed computing:

- ○ RMI, CORBA.

○ JEE, CORBAservices.

Generic message-passing middleware:

- ○ Support generic communication between processes on different nodes.

○ No distinction of server and client, all processes are equal (peers).

Domani-specific middleware:

- ○ Multiagent middleware.

In a DS, the architectural paradigm dictate according to which style the interaction between

distributed components will be organized. We have:

Client-Server based:

- ○ Layered architectures.

○ Object-based architectures.

○ RESTful.

Peer-to-Peer based:

- ○ Event-based architectures.

○ Data-centered architectures.

○ P2P Overlays.

○ Multiagent.

Client-Server Models

The only mean of interacton is request-response.

- This model specifies the interaction between two components, which have two different roles in

- the interaction.

Asymmetric roles:

- ○ Only the client starts the interaction and must know the server.

○ The server does not know the clients and passively waits, receives the request, performs

the computation and responds.

Client-Server Architectural Styles:

Layered (spaghetti) Style:

- Distributed Artificial Intelligence Pagina 5

Layered (spaghetti) Style:

- The pattern of object interactions is constrained: at Layer 1 we have pure servers, while at Layer

N we have pure clients; in between, the layers can request only from top to down and can

respond only from bottom to up.

Distributed Objects:

- ○ A server object can be a client on its turn.

○ No specific structure of the interaction network.

3-Layer or 3-Tier Architectures:

- A server can request a service to other servers, so it becomes a client.

N-Tier Architectures.

-

Stateful vs Stateless:

Stateful:

- ○ The server keeps track of the clients.

○ Pros: faster operations, sessions.

○ Cons: complex, resource needs, problems in case of failure.

Stateless:

- ○ The server does NOT keep track of the clients.

○ Pros: simpler, less resources needed.

○ Cons: no session, no history, self-contained operations.

Peer-to-Peer (P2P) Models

The mean of interaction is a message.

- We need to engineer the mean of interaction and the strategy, interactions are no pre-defined.

- There is no distinction between clients and servers.

- Symmetric model.

-

P2P Architectural Styles:

Pub/Sub:

- Event-based mean of interaction: components interact by generating events and listening to

events.

Dataspace:

- The mean of interaction is writing and reading information in a shared data-space.

Distributed Artificial Intelligence Pagina 6

Multiagent Model:

- ○ Each component is an autonomous independent software module (peer) capable of

autonomous actions and decisions.

○ They interact with the environment and with each other to reach the goal.

○ The mean of interaction are interaction protocols:

 Highly flexible and suited to dynamic unpredictable scenarios.

 Fully enabling distributed artificial intelligence and collective intelligence models.

Distributed Artificial Intelligence Pagina 7

Complex Adaptive Systems for DAI

mercoledì 30 settembre 2020 19:43

What is a System?

A system is an ensemble of individual entities that interact with each other in an environment.

Modeling Individuals in a System:

In general, an entity in a system is characterized by:

State: is the dimensions fully characterizing the current situation of the individual.

- Transition rules: are the events in the system that make an individual change its state.

- Behavior: is what the individual do in the system and how it affects the system.

- Context: is the position in the environment.

-

Modeling Interactions in a System:

An interaction is any event in a system that:

Is caused by an individual in the system.

- Affects the state of one or several individuals in the system.

-

Types of interactions:

Direct: when we have a direct effect of one individual on another.

- Indirect: when the environment affects an individual.

-

Local vs Global System State:

The global state of the system is the collection of all the states of all individuals of the system (local

states), plus the state of the environment.

In many cases, the global state is represented by more "synthetic" indicators, which give us a clue of

what is happening in the system, because for open and large systems it is impossible to determine the

global state in terms of local states.

System Dynamics:

A system evolves in time through the local state transition of the individuals, that affects the global

system state.

The study of system dynamics implies determining the evolution of the system given an initial state

(ex. will the system reach the equilibrium?)

The Phase Space of a System

The phase space is a virtual space whose dimensions are the synthetic indicators of the global system

state.

Studying the evolution of a system means to know the initial state of the system, which is a point in

the phase space, and know how it evolves in time studying the trajectory of the system in the phase

space.

Typically, the trajectory tends to be attracted in specific regions of the diagram:

Attractors are where the trajectory tends to go.

- Attractors express stability: once the system reaches an attractor, it will stay there undefinetely,

- until perturbed.

Movements and Attractors in the Phase Space:

Single point attractor: from whatever starting point, the dynamic trajectory always ends up in a

- single point (ex. pendulum).

Cycle: periodic behavior.

- Chaotic: move without apparent rationality in the whole phase space (non stable).

- Strange attractors: between periodic and chaos.

- Distributed Artificial Intelligence Pagina 8

Strange attractors: between periodic and chaos.

-

Phase Space and DAI:

We want to have a system that converges towards a single point and reaches stability.

- We want a system that exhibit a periodic behavior, that periodically repeats the same actions.

- We want to have a system that tolerates perturbations.

-

What is an Adaptive System?

What is Adaptivity?

Adaptivity is the capability of a system and/or of its individuals of tuning its behavior to

- unexpected possible situations.

Adaptivity implies that the system is both flexible and robust:

- ○ Flexible response: the system adapts its overall dynamics in response to stimuli and

perturbations.

○ Robust behavior: the system absorbs the perturbations without changing its overall

behavior and dynamics, or at least some of its relevant characteristics.

Adaptivity in the Phase Space:

If something moves the system away from its desired trajectory, the system absorbs that without

changing its basic properties, and the behavior is still as desired.

Adaptive Individuals and Adaptive Systems:

Sometimes, individuals may be adaptive making the whole system consequently adaptive;

- sometimes, individuals are adaptive, but the system is not.

In other cases, ensembles of very simple stupid reactive components could lead to very adaptive

- systems; system adaptivity in this case is a consequence of individuals interactions.

Why Adaptivity in Distributed Systems?

Because systems are decentralized: distributed in different environments and belonging to

- different stakeholders, with no central control and no one can foresee the behavior of each

Distributed Artificial Intelligence Pagina 9

different stakeholders, with no central control and no one can foresee the behavior of each

component.

Because of the structural dynamics of the systems: where users/components can be mobile and

- some components can be ephemeral (very short life) or become unreachable.

Because the system interacts with dynamic environments and needs to adapt to unforeseen

- environmental dynamics of the physical world.

Because of social dynamics: components interacts with each other and need to adapt to interact

- with unknown/external entities.

Openness and Dynamics

To face perturbations, it may be necessary to model explicitly what is inside and outside of the system:

The inside is what we can decide and control.

- The outside or context is not under engineering control, so we have to understand what are the

- possible sources of dynamics that cross the border and affect the internal.

Context-aware and Context-adaptive:

When talking about context, adaptivity implies being context-aware and context-adaptive, that is:

The system or its components need to recongnize the context, recognize the changes in context

- and adapt their behavior accordingly.

This can be achieved either at individual or system level.

-

This is achieved by inspection of the context (perception) and tuning the behavior depending on the

context (action).

What is a Complex System?

A complex system is a system in which it is hard to infer its global dynamics from the behavior and

state of its individual components:

It is difficult or impossible to detect its evolution in the phase space.

- It has very chaotic trajectories in the phase space.

-

Reasons for complex systems:

Local interactions: when we have many components in the system and a component interacts

- Distributed Artificial Intelligence Pagina 10

Local interactions: when we have many components in the system and a component interacts

- only with few components (neighbors), their global