| Thanks to the fast progresses in hardware
and communication technology, today it is possible to connect inexpensively
a large numbers of powerful processing units that execute asynchronously.
This gives us the possibility of design complex systems in which different
intelligent unites work together to solve problems that are beyond their
individual capabilities. In last 15 years, Distributed Artificial Intelligence
has faced this matter with Multi-Agent Systems(MAS). The focus of MAS research
is on the agent (getting it to interact meaningfully with other agents)
and on collections of agents as a whole (identifying under what conditions
the agents will rationally choose to act, such that the society displays
certain properties). Agents are conceived as autonomous and rational entities
that perform tasks in complex and dynamically changing environments: autonomous
because have the ability to make decisions based on aninternal representation
of the world, without being controlled by a centralized instance; rational
because it is assumed that an agent will act in order to achieve its goals.
Autonomy and rationality are attributes strongly dependent on the consistency
of the agent's knowledge, and in particular, they can not prescind from
it.
By belief revision it is meant the process of rearranging
a cognitive state in order to embody an incoming information while preserving
the global consistency. Since the seminal, philosophical and influential
works of Gärdenfors et al. [83,105], ideas on belief revision have
been progressively refined [85] and ameliorated toward normative, effective
and quasi-computable paradigms [82,130,131]. Some of the main contributes
have been the idea of "revision as transmutation of partial epistemic rankings"
[91], "revision for finite bases" [104], the distinction between revision
and updating [92] and a related approach based on the notion of possible
models [94]. Side by side to this "symbolic" line of research, there has
been also a "numerical" way to belief revision [111] whose main contributes
were the probabilistic [109], possibilistic [114], and the evidence-based
approaches [110].
In this dissertation, we propose two ways to perform
belief revision in multi-agent environments. In the first case the belief
revision problem is approached from a centralized perspective, that is,
it is assigned to a single agent; whereas, in the second case, it is approached
from a distributed perspective, that is, it is assigned to a group of agents.
According to us, in a multi-agent environment, where
information come from a variety of sources with different degrees of reliability,
belief revision has to depart considerably from its original framework.
Particularly, the principle of "priority of the incoming information" should
be abandoned; while it is acceptable when updating the representation of
an evolving world, that principle is not generally justified when revising
the representation of a static situation. In this case, the chronological
sequence of the informative acts has nothing to do with their credibility
or importance. Another point is that changes should not be irrevocable.
To make practical and useful belief revision in a multi-agent environment,
we substitute the priority of the incoming information with the principle
of recoverability: any previously believed information item must belong
to the current cognitive state if it is consistent with it.
Our approach to centralized belief revision combines
symbolic and numerical operations. Particularly, we use operations in Assumption
Truth Maintenance System [122] style to treat the symbolic part of information,
and the Dempster-Shafer theory [116] to treat their numerical part. We
distinguish two knowledge bases: the knowledge background (KB), which is
the set of all the pieces of knowledge available to the reasoning agent
(since it can be inconsistent, it cannot be used as a whole to support
reasoning and decision processes); and, the knowledge base BÍ KB,
which is the maximally consistent, currently preferred piece of knowledge
that should be used for reasoning and decision supporting (since it is
maximally consistent, it can contain incredible pieces of knowledge). The
incoming information, with its weight of evidence, is confronted not just
with B, but with the overall KB.
Belief revision is a process computationally very
expensive. From an engineering point of view, this means that it not always
convenient or possible to build systems in which the belief revision process
is performed only by a central unit. Therefore, an alternative approach
is the distributed one, where the belief revision process is no longer
assigned to a single agent but to a society of agents, in which each single
is able to perform belief revision and communicate with the others. The
main difference is that in this case there is no more a single agent having
a global view of the system, but any agent has a partial view of it. This
allows that the computational load to be divided among the agents of the
group.
Our way to distributed belief revision consists
of a society of agents, which adopt locally a centralized belief revision
model, communicate with each other and adopt global strategies to extract
an emergent global opinion regarding the treated information. In particular,
we assume that the agents locally adopt our model for centralized belief
revision, spontaneous and/or on-demand polities of communication and data
or agent driven election to form global opinions. This approach is conceptually
different from the classical Distributed (Assumption) Truth Maintain Systems
[124,125] since it allows each agent to maintain its own opinions, independently
from those of the others. We determinate two main desiderata: convergence
(i.e., which local decision strategies favour the convergence of the opinions
rather than the chaotic divergence or the static indifference?) and correctness
(i.e., which local decision strategies favour the convergence of the opinions
to the most correct pieces of knowledge globally available to the overall
agency?). Obviously, the choice of the best strategies depends on the structure
of the agency and on the context to which it is applied.
We believe that the evaluation and the comparison
of the performances of the centralized and distributed approach can be
done only on a simulative basis. At the end of this dissertation, we will
present a study on the simulative basis of the behavior of a society of
agents that interact in presence of conflicting knowledge. Particularly,
we will try to evaluate and compare the performances of the two approaches
to belief revision. Furthermore, we will study how the cognitive state
of each single agent evolves during interaction, and how these single evolutions
influence the global knowledge of the group.
This dissertation is structured as follows:
Chapter 1 illustrates and compares the two
main research areas of Distributed Artificial Intelligence: Distributed
Problem Solving and Multi-Agent Systems. Particularly, it evidences the
main characteristics that differentiate an agent from a problem solver.
Chapter 2 gives a general perspective of
belief revision. It starts by describing and comparing the main theoretical
contributes of the symbolic and numerical approaches and finishes by giving
a brief description of the two main practical approaches.
Chapter 3 presents our two models for belief
revision. It introduces the principle of recoverability and the reasons
that make it very suitable in a multi-agent environments.
Chapter 4 presents a study on the simulative
basis of the behavior of a society of agents that interact in presence
of conflicting knowledge. It gives a brief description of our specific
belief revision test-bed for multi-agent systems and reports the description
and the results of five different types of experiments run with it. Moreover,
it outlines general considerations on the performances of the adopted strategies.
|